Simulation of quantum circuits by low-rank stabilizer decompositions

Sergey Bravyi1, Dan Browne2, Padraic Calpin2, Earl Campbell3, David Gosset1,4, and Mark Howard3

1IBM T.J. Watson Research Center, Yorktown Heights NY 10598
2Department of Physics and Astronomy, University College London, London, UK
3Department of Physics and Astronomy, University of Sheffield, Sheffield, UK
4Department of Combinatorics & Optimization and Institute for Quantum Computing, University of Waterloo, Waterloo, Canada

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.


Recent work has explored using the stabilizer formalism to classically simulate quantum circuits containing a few non-Clifford gates. The computational cost of such methods is directly related to the notion of $\it{stabilizer}$ $\textit{rank}$, which for a pure state $\psi$ is defined to be the smallest integer $\chi$ such that $\psi$ is a superposition of $\chi$ stabilizer states. Here we develop a comprehensive mathematical theory of the stabilizer rank and the related approximate stabilizer rank. We also present a suite of classical simulation algorithms with broader applicability and significantly improved performance over the previous state-of-the-art. A new feature is the capability to simulate circuits composed of Clifford gates and arbitrary diagonal gates, extending the reach of a previous algorithm specialized to the Clifford+T gate set. We implemented the new simulation methods and used them to simulate quantum algorithms with 40-50 qubits and over 60 non-Clifford gates, without resorting to high-performance computers. We report a simulation of the Quantum Approximate Optimization Algorithm in which we process superpositions of $\chi\sim10^6$ stabilizer states and sample from the full $n$-bit output distribution, improving on previous simulations which used $\sim 10^3$ stabilizer states and sampled only from single-qubit marginals. We also simulated instances of the Hidden Shift algorithm with circuits including up to 64 $T$ gates or 16 CCZ gates; these simulations showcase the performance gains available by optimizing the decomposition of a circuit's non-Clifford components.

► BibTeX data

► References

[1] Scott Aaronson and Lijie Chen. Complexity-theoretic foundations of quantum supremacy experiments. In 32nd Computational Complexity Conference (CCC 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. 10.4230/​LIPIcs.CCC.2017.22.

[2] Scott Aaronson and Daniel Gottesman. Improved simulation of stabilizer circuits. Physical Review A, 70 (5): 052328, 2004. 10.1103/​PhysRevA.70.052328.

[3] Dorit Aharonov, Michael Ben-Or, Elad Eban, and Urmila Mahadev. Interactive proofs for quantum computations. arXiv preprint arXiv:1704.04487, 2017.

[4] Gadi Aleksandrowicz, Thomas Alexander, Panagiotis Barkoutsos, Luciano Bello, Yael Ben-Haim, David Bucher, Francisco Jose Cabrera-Hernández, Jorge Carballo-Franquis, Adrian Chen, Chun-Fu Chen, Jerry M. Chow, Antonio D. Córcoles-Gonzales, Abigail J. Cross, Andrew Cross, Juan Cruz-Benito, Chris Culver, Salvador De La Puente González, Enrique De La Torre, Delton Ding, Eugene Dumitrescu, Ivan Duran, Pieter Eendebak, Mark Everitt, Ismael Faro Sertage, Albert Frisch, Andreas Fuhrer, Jay Gambetta, Borja Godoy Gago, Juan Gomez-Mosquera, Donny Greenberg, Ikko Hamamura, Vojtech Havlicek, Joe Hellmers, Łukasz Herok, Hiroshi Horii, Shaohan Hu, Takashi Imamichi, Toshinari Itoko, Ali Javadi-Abhari, Naoki Kanazawa, Anton Karazeev, Kevin Krsulich, Peng Liu, Yang Luh, Yunho Maeng, Manoel Marques, Francisco Jose Martín-Fernández, Douglas T. McClure, David McKay, Srujan Meesala, Antonio Mezzacapo, Nikolaj Moll, Diego Moreda Rodríguez, Giacomo Nannicini, Paul Nation, Pauline Ollitrault, Lee James O'Riordan, Hanhee Paik, Jesús Pérez, Anna Phan, Marco Pistoia, Viktor Prutyanov, Max Reuter, Julia Rice, Abdón Rodríguez Davila, Raymond Harry Putra Rudy, Mingi Ryu, Ninad Sathaye, Chris Schnabel, Eddie Schoute, Kanav Setia, Yunong Shi, Adenilton Silva, Yukio Siraichi, Seyon Sivarajah, John A. Smolin, Mathias Soeken, Hitomi Takahashi, Ivano Tavernelli, Charles Taylor, Pete Taylour, Kenso Trabing, Matthew Treinish, Wes Turner, Desiree Vogt-Lee, Christophe Vuillot, Jonathan A. Wildstrom, Jessica Wilson, Erick Winston, Christopher Wood, Stephen Wood, Stefan Wörner, Ismail Yunus Akhalwaya, and Christa Zoufal. Qiskit: An open-source framework for quantum computing, 2019.

[5] Noga Alon. Transversal numbers of uniform hypergraphs. Graphs and Combinatorics, 6 (1): 1–4, 1990. 10.1007/​BF01787474.

[6] Simon Anders and Hans J Briegel. Fast simulation of stabilizer circuits using a graph-state representation. Physical Review A, 73 (2): 022334, 2006. 10.1103/​PhysRevA.73.022334.

[7] Ryan S. Bennink, Erik M. Ferragut, Travis S. Humble, Jason A. Laska, James J. Nutaro, Mark G. Pleszkoch, and Raphael C. Pooser. Unbiased simulation of near-Clifford quantum circuits. Physical Review A, 95: 062337, Jun 2017. 10.1103/​PhysRevA.95.062337.

[8] Sergio Boixo, Sergei V Isakov, Vadim N Smelyanskiy, and Hartmut Neven. Simulation of low-depth quantum circuits as complex undirected graphical models. arXiv preprint arXiv:1712.05384, 2017.

[9] Sergio Boixo, Sergei V Isakov, Vadim N Smelyanskiy, Ryan Babbush, Nan Ding, Zhang Jiang, Michael J Bremner, John M Martinis, and Hartmut Neven. Characterizing quantum supremacy in near-term devices. Nature Physics, 14 (6): 595, 2018. 10.1038/​s41567-018-0124-x.

[10] Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.

[11] Sergey Bravyi and David Gosset. Improved classical simulation of quantum circuits dominated by Clifford gates. Physical Review Letters, 116 (25): 250501, 2016. 10.1103/​PhysRevLett.116.250501.

[12] Sergey Bravyi and Alexei Kitaev. Universal quantum computation with ideal Clifford gates and noisy ancillas. Physical Review A, 71 (2): 022316, 2005. 0.1103/​PhysRevA.71.022316.

[13] Sergey Bravyi, David Fattal, and Daniel Gottesman. Ghz extraction yield for multipartite stabilizer states. Journal of Mathematical Physics, 47 (6): 062106, 2006. 10.1063/​1.2203431.

[14] Sergey Bravyi, Graeme Smith, and John A. Smolin. Trading classical and quantum computational resources. Physical Review X, 6: 021043, Jun 2016. 10.1103/​PhysRevX.6.021043.

[15] Michael J Bremner, Ashley Montanaro, and Dan J Shepherd. Average-case complexity versus approximate simulation of commuting quantum computations. Physical Review Letters, 117 (8): 080501, 2016. 0.1103/​PhysRevLett.117.080501.

[16] Earl T. Campbell. Catalysis and activation of magic states in fault-tolerant architectures. Physical Review A, 83: 032317, Mar 2011. 10.1103/​PhysRevA.83.032317.

[17] Jianxin Chen, Fang Zhang, Mingcheng Chen, Cupjin Huang, Michael Newman, and Yaoyun Shi. Classical simulation of intermediate-size quantum circuits. arXiv preprint arXiv:1805.01450, 2018.

[18] Elizabeth Crosson and John Bowen. Quantum ground state isoperimetric inequalities for the energy spectrum of local hamiltonians. arXiv preprint arXiv:1703.10133, 2017.

[19] Koen De Raedt, Kristel Michielsen, Hans De Raedt, Binh Trieu, Guido Arnold, Marcus Richter, Th Lippert, H Watanabe, and N Ito. Massively parallel quantum computer simulator. Computer Physics Communications, 176 (2): 121–136, 2007. 10.1016/​j.cpc.2006.08.007.

[20] Nicolas Delfosse, Philippe Allard Guerin, Jacob Bian, and Robert Raussendorf. Wigner function negativity and contextuality in quantum computation on rebits. Physical Review X, 5: 021003, Apr 2015. 10.1103/​PhysRevX.5.021003.

[21] Lior Eldar and Aram W Harrow. Local Hamiltonians whose ground states are hard to approximate. In Foundations of Computer Science (FOCS), 2017 IEEE 58th Annual Symposium on, pages 427–438. IEEE, 2017. 10.1109/​FOCS.2017.46.

[22] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm applied to a bounded occurrence constraint problem. arXiv preprint arXiv:1412.6062, 2014.

[23] Austin G Fowler, Simon J Devitt, and Cody Jones. Surface code implementation of block code state distillation. Scientific reports, 3: 1939, 2013. 10.1038/​srep01939.

[24] E Schuyler Fried, Nicolas PD Sawaya, Yudong Cao, Ian D Kivlichan, Jhonathan Romero, and Alán Aspuru-Guzik. qtorch: The quantum tensor contraction handler. PloS one, 13 (12): e0208510, 2018. 10.1371/​journal.pone.0208510.

[25] Hector J Garcia, Igor L Markov, and Andrew W Cross. Efficient inner-product algorithm for stabilizer states. arXiv preprint arXiv:1210.6646, 2012.

[26] Héctor J. García, Igor L. Markov, and Andrew W. Cross. On the geometry of stabilizer states. Quantum Information & Computation, 14: 683, 2014.

[27] Daniel Gottesman. Theory of fault-tolerant quantum computation. Physical Review A, 57 (1): 127, 1998. 10.1103/​PhysRevA.57.127.

[28] Daniel Gottesman and Isaac L. Chuang. Demonstrating the viability of universal quantum computation using teleportation and single-qubit operations. Nature, 402: 390, 1999. 10.1038/​46503.

[29] David Gross, Sepehr Nezami, and Michael Walter. Schur-Weyl duality for the Clifford group with applications: Property testing, a robust Hudson theorem, and de Finetti representations. arXiv preprint arXiv:1712.08628, 2017.

[30] Thomas Häner and Damian S Steiger. 0.5 petabyte simulation of a 45-qubit quantum circuit. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, page 33. ACM, 2017. 10.1145/​3126908.3126947.

[31] Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58 (301): 13–30, 1963.

[32] Mark Howard and Earl Campbell. Application of a resource theory for magic states to fault-tolerant quantum computing. Physical Review Letters, 118: 090501, Mar 2017. 10.1103/​PhysRevLett.118.090501.

[33] Cupjin Huang, Michael Newman, and Mario Szegedy. Explicit lower bounds on strong quantum simulation. arXiv preprint arXiv:1804.10368, 2018.

[34] Cody Jones. Low-overhead constructions for the fault-tolerant Toffoli gate. Physical Review A, 87 (2): 022328, 2013. 10.1103/​PhysRevA.87.022328.

[35] Richard Jozsa and Sergii Strelchuk. Efficient classical verification of quantum computations. arXiv preprint arXiv:1705.02817, 2017.

[36] Angela Karanjai, Joel J Wallman, and Stephen D Bartlett. Contextuality bounds the efficiency of classical simulation of quantum processes. arXiv preprint arXiv:1802.07744, 2018.

[37] Lucas Kocia and Peter Love. Discrete Wigner formalism for qubits and noncontextuality of Clifford gates on qubit stabilizer states. Physical Review A, 96 (6): 062134, 2017. 10.1103/​PhysRevA.96.062134.

[38] Richard Kueng and David Gross. Qubit stabilizer states are complex projective 3-designs. arXiv preprint arXiv:1510.02767, 2015.

[39] Riling Li, Bujiao Wu, Mingsheng Ying, Xiaoming Sun, and Guangwen Yang. Quantum supremacy circuit simulation on Sunway TaihuLight. arXiv preprint arXiv:1804.04797, 2018.

[40] Igor L Markov and Yaoyun Shi. Simulating quantum computation by contracting tensor networks. SIAM Journal on Computing, 38 (3): 963–981, 2008. 10.1137/​050644756.

[41] Servet Martínez, Gérard Michon, and Jaime San Martín. Inverse of strictly ultrametric matrices are of Stieltjes type. SIAM Journal on Matrix Analysis and Applications, 15 (1): 98–106, 1994. 10.1137/​S0895479891217011.

[42] Dmitri Maslov and Martin Roetteler. Shorter stabilizer circuits via Bruhat decomposition and quantum circuit transformations. arXiv preprint arXiv:1705.09176, 2017. 10.1109/​TIT.2018.2825602.

[43] David C McKay, Christopher J Wood, Sarah Sheldon, Jerry M Chow, and Jay M Gambetta. Efficient Z gates for quantum computing. Physical Review A, 96 (2): 022330, 2017. 10.1103/​PhysRevA.96.022330.

[44] Tomoyuki Morimae and Joseph F Fitzsimons. Post hoc verification with a single prover. Physical Review Letters, 120: 040501, 2018. 10.1103/​PhysRevLett.120.040501.

[45] Reinhard Nabben and Richard S Varga. A linear algebra proof that the inverse of a strictly ultrametric matrix is a strictly diagonally dominant Stieltjes matrix. SIAM Journal on Matrix Analysis and Applications, 15 (1): 107–113, 1994. 10.1137/​S0895479892228237.

[46] Michael A Nielsen and Isaac Chuang. Quantum computation and quantum information, 2002.

[47] Hakop Pashayan, Joel J Wallman, and Stephen D Bartlett. Estimating outcome probabilities of quantum circuits using quasiprobabilities. Physical Review Letters, 115 (7): 070501, 2015. 10.1103/​PhysRevLett.115.070501.

[48] Edwin Pednault, John A Gunnels, Giacomo Nannicini, Lior Horesh, Thomas Magerlein, Edgar Solomonik, and Robert Wisnieff. Breaking the 49-qubit barrier in the simulation of quantum circuits. arXiv preprint arXiv:1710.05867, 2017.

[49] John Preskill. Quantum computing in the NISQ era and beyond. arXiv preprint arXiv:1801.00862, 2018. 10.22331/​q-2018-08-06-79.

[50] Bartosz Regula. Convex geometry of quantum resource quantification. Journal of Physics A: Mathematical and Theoretical, 51 (4): 045303, 2017. 10.1088/​1751-8121/​aa9100.

[51] M. Rötteler. Quantum algorithms for highly non-linear Boolean functions. In Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms, pages 448–457, 2010.

[52] Mikhail Smelyanskiy, Nicolas PD Sawaya, and Alán Aspuru-Guzik. qHiPSTER: the quantum high performance software testing environment. arXiv preprint arXiv:1601.07195, 2016.

[53] W. van Dam, S. Hallgren, and L. Ip. Quantum Algorithms for Some Hidden Shift Problems. SIAM Journal on Computing, 36 (3): 763–778, January 2006. ISSN 0097-5397.

[54] Maarten Van Den Nest. Classical simulation of quantum computation, the Gottesman-Knill theorem, and slightly beyond. Quantum Information & Computation, 10 (3): 258–271, 2010.

[55] Maarten Van den Nest. Simulating quantum computers with probabilistic methods. Quantum Information & Computation, 11 (9-10): 784–812, 2011.

[56] Victor Veitch, Christopher Ferrie, David Gross, and Joseph Emerson. Negative quasi-probability as a resource for quantum computation. New Journal of Physics, 14 (11): 113011, 2012. 10.1088/​1367-2630/​14/​11/​113011.

[57] Zak Webb. The clifford group forms a unitary 3-design. Quantum Information & Computaion, 16: 1379, 2016.

[58] Ulli Wolff, Alpha Collaboration, et al. Monte Carlo errors with less errors. Computer Physics Communications, 156 (2): 143–153, 2004. 10.1016/​S0010-4655(03)00467-3.

[59] Huangjun Zhu, Richard Kueng, Markus Grassl, and David Gross. The Clifford group fails gracefully to be a unitary 4-design. arXiv preprint arXiv:1609.08172, 2016.

[60] Karol Zyczkowski and Hans-Jürgen Sommers. Truncations of random unitary matrices. Journal of Physics A: Mathematical and General, 33 (10): 2045, 2000. 10.1088/​0305-4470/​33/​10/​307.

Cited by

[1] Bartosz Regula, Kaifeng Bu, Ryuji Takagi, and Zi-Wen Liu, "Benchmarking one-shot distillation in general quantum resource theories", Physical Review A 101 6, 062315 (2020).

[2] Bartosz Regula, "Tight constraints on probabilistic convertibility of quantum states", Quantum 6, 817 (2022).

[3] Sergey Bravyi, David Gosset, and Yinchen Liu, "How to Simulate Quantum Measurement without Computing Marginals", Physical Review Letters 128 22, 220503 (2022).

[4] Christopher Chamberland, Kyungjoo Noh, Patricio Arrangoiz-Arriola, Earl T. Campbell, Connor T. Hann, Joseph Iverson, Harald Putterman, Thomas C. Bohdanowicz, Steven T. Flammia, Andrew Keller, Gil Refael, John Preskill, Liang Jiang, Amir H. Safavi-Naeini, Oskar Painter, and Fernando G.S.L. Brandão, "Building a Fault-Tolerant Quantum Computer Using Concatenated Cat Codes", PRX Quantum 3 1, 010329 (2022).

[5] Yifei Huang and Peter Love, "Feynman-path-type simulation using stabilizer projector decomposition of unitaries", Physical Review A 103 2, 022428 (2021).

[6] James R. Seddon and Earl T. Campbell, "Quantifying magic for multi-qubit operations", Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 475 2227, 20190251 (2019).

[7] Elías F. Combarro, Alejandro Piñera‐Nicolás, José Ranilla, and Ignacio F. Rúa, "An explanation of the Bernstein‐Vazirani and Deustch‐Josza algorithms with the quantum stabilizer formalism", Computational and Mathematical Methods 3 6(2021).

[8] Hammam Qassim, Joel J. Wallman, and Joseph Emerson, "Clifford recompilation for faster classical simulation of quantum circuits", arXiv:1902.02359, Quantum 3, 170 (2019).

[9] Laura García-Álvarez, Cameron Calcluth, Alessandro Ferraro, and Giulia Ferrini, "Efficient simulatability of continuous-variable circuits with large Wigner negativity", Physical Review Research 2 4, 043322 (2020).

[10] Yasunari Suzuki, Yoshiaki Kawase, Yuya Masumura, Yuria Hiraga, Masahiro Nakadai, Jiabao Chen, Ken M. Nakanishi, Kosuke Mitarai, Ryosuke Imai, Shiro Tamiya, Takahiro Yamamoto, Tennin Yan, Toru Kawakubo, Yuya O. Nakagawa, Yohei Ibe, Youyuan Zhang, Hirotsugu Yamashita, Hikaru Yoshimura, Akihiro Hayashi, and Keisuke Fujii, "Qulacs: a fast and versatile quantum circuit simulator for research purpose", Quantum 5, 559 (2021).

[11] Lorenzo Leone, Salvatore F. E. Oliviero, and Alioscia Hamma, "Stabilizer Rényi Entropy", Physical Review Letters 128 5, 050402 (2022).

[12] Hammam Qassim, Hakop Pashayan, and David Gosset, "Improved upper bounds on the stabilizer rank of magic states", Quantum 5, 606 (2021).

[13] Akihiro Mizutani, Yuki Takeuchi, Ryo Hiromasa, Yusuke Aikawa, and Seiichiro Tani, "Computational self-testing for entangled magic states", Physical Review A 106 1, L010601 (2022).

[14] Salvatore Mandra, Jeffrey Marshall, Eleanor G. Rieffel, and Rupak Biswas, 2021 IEEE/ACM Second International Workshop on Quantum Computing Software (QCS) 99 (2021) ISBN:978-1-7281-8674-0.

[15] Runzhou Tao, Yunong Shi, Jianan Yao, John Hui, Frederic T. Chong, and Ronghui Gu, Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation 48 (2021) ISBN:9781450383912.

[16] Ryuji Takagi and Bartosz Regula, "General Resource Theories in Quantum Mechanics and Beyond: Operational Characterization via Discrimination Tasks", Physical Review X 9 3, 031053 (2019).

[17] Hasan YETİŞ and Mehmet KARAKÖSE, "Kuantum Uyarlamalı Genetik Algoritmalar için Çözüm Kalitesini Artıracak Yeni Bir Yaklaşım", Fırat Üniversitesi Mühendislik Bilimleri Dergisi 33 1, 71 (2021).

[18] Christopher David White, ChunJun Cao, and Brian Swingle, "Conformal field theories are magical", Physical Review B 103 7, 075145 (2021).

[19] Nicholas H. Stair and Francesco A. Evangelista, "QForte: An Efficient State-Vector Emulator and Quantum Algorithms Library for Molecular Electronic Structure", Journal of Chemical Theory and Computation 18 3, 1555 (2022).

[20] Thien Nguyen, Lindsay Bassman Oftelie, Dmitry Lyakh, Phillip C. Lotshaw, Alexander McCaskey, Ryan S. Bennink, Vicente Leyton-Ortega, Raphael C. Pooser, Travis S. Humble, and Wibe A. de Jong, 2021 IEEE/ACM Second International Workshop on Quantum Computing Software (QCS) 80 (2021) ISBN:978-1-7281-8674-0.

[21] Kaifeng Bu and Dax Enshan Koh, "Efficient Classical Simulation of Clifford Circuits with Nonstabilizer Input States", Physical Review Letters 123 17, 170502 (2019).

[22] Guoming Chen, Qiang Chen, Shun Long, Weiheng Zhu, Zeduo Yuan, and Yilin Wu, "Quantum convolutional neural network for image classification", Pattern Analysis and Applications (2022).

[23] Jacob Biamonte, "Universal variational quantum computation", Physical Review A 103 3, L030401 (2021).

[24] Hao Dai, Shuangshuang Fu, and Shunlong Luo, "Detecting Magic States via Characteristic Functions", International Journal of Theoretical Physics 61 2, 35 (2022).

[25] Zi-Wen Liu and Andreas Winter, "Many-Body Quantum Magic", PRX Quantum 3 2, 020333 (2022).

[26] Arne Heimendahl, Markus Heinrich, and David Gross, "The axiomatic and the operational approaches to resource theories of magic do not coincide", Journal of Mathematical Physics 63 11, 112201 (2022).

[27] Adrian Chapman and Steven T. Flammia, "Characterization of solvable spin models via graph invariants", Quantum 4, 278 (2020).

[28] Gaurav Saxena and Gilad Gour, "Quantifying multiqubit magic channels with completely stabilizer-preserving operations", Physical Review A 106 4, 042422 (2022).

[29] Nicholas C. Rubin, Klaas Gunst, Alec White, Leon Freitag, Kyle Throssell, Garnet Kin-Lic Chan, Ryan Babbush, and Toru Shiozaki, "The Fermionic Quantum Emulator", Quantum 5, 568 (2021).

[30] Troy J. Sewell and Christopher David White, "Mana and thermalization: Probing the feasibility of near-Clifford Hamiltonian simulation", Physical Review B 106 12, 125130 (2022).

[31] Arne Heimendahl, Felipe Montealegre-Mora, Frank Vallentin, and David Gross, "Stabilizer extent is not multiplicative", Quantum 5, 400 (2021).

[32] Oliver Hahn, Alessandro Ferraro, Lina Hultquist, Giulia Ferrini, and Laura García-Álvarez, "Quantifying Qubit Magic Resource with Gottesman-Kitaev-Preskill Encoding", Physical Review Letters 128 21, 210502 (2022).

[33] Shuangshuang Fu, Xiaohui Li, and Shunlong Luo, "Detecting quantum phase transition via magic resource in the XY spin model", Physical Review A 106 6, 062405 (2022).

[34] M. Lostaglio and A. Ciani, "Error Mitigation and Quantum-Assisted Simulation in the Error Corrected Regime", Physical Review Letters 127 20, 200506 (2021).

[35] Giovanni De Micheli, Jie-Hong R. Jiang, Robert Rand, Kaitlin Smith, and Mathias Soeken, "Advances in Quantum Computation and Quantum Technologies: A Design Automation Perspective", IEEE Journal on Emerging and Selected Topics in Circuits and Systems 12 3, 584 (2022).

[36] Nikolaos Koukoulekidis, Hyukjoon Kwon, Hyejung H. Jee, David Jennings, and M. S. Kim, "Faster Born probability estimation via gate merging and frame optimisation", Quantum 6, 838 (2022).

[37] Ryan L. Mann, "Simulating quantum computations with Tutte polynomials", npj Quantum Information 7 1, 141 (2021).

[38] Lucas Kocia and Mohan Sarovar, "Classical simulation of quantum circuits using fewer Gaussian eliminations", Physical Review A 103 2, 022603 (2021).

[39] Craig Gidney, "Stim: a fast stabilizer circuit simulator", Quantum 5, 497 (2021).

[40] Lucas Kocia and Peter Love, "Stationary Phase Method in Discrete Wigner Functions and Classical Simulation of Quantum Circuits", Quantum 5, 494 (2021).

[41] Matija Medvidović and Giuseppe Carleo, "Classical variational simulation of the Quantum Approximate Optimization Algorithm", npj Quantum Information 7 1, 101 (2021).

[42] Ryuji Takagi, Bartosz Regula, and Mark M. Wilde, "One-Shot Yield-Cost Relations in General Quantum Resource Theories", PRX Quantum 3 1, 010348 (2022).

[43] Tyler D. Ellison, Kohtaro Kato, Zi-Wen Liu, and Timothy H. Hsieh, "Symmetry-protected sign problem and magic in quantum phases of matter", Quantum 5, 612 (2021).

[44] Xiao Mi, Pedram Roushan, Chris Quintana, Salvatore Mandrà, Jeffrey Marshall, Charles Neill, Frank Arute, Kunal Arya, Juan Atalaya, Ryan Babbush, Joseph C. Bardin, Rami Barends, Joao Basso, Andreas Bengtsson, Sergio Boixo, Alexandre Bourassa, Michael Broughton, Bob B. Buckley, David A. Buell, Brian Burkett, Nicholas Bushnell, Zijun Chen, Benjamin Chiaro, Roberto Collins, William Courtney, Sean Demura, Alan R. Derk, Andrew Dunsworth, Daniel Eppens, Catherine Erickson, Edward Farhi, Austin G. Fowler, Brooks Foxen, Craig Gidney, Marissa Giustina, Jonathan A. Gross, Matthew P. Harrigan, Sean D. Harrington, Jeremy Hilton, Alan Ho, Sabrina Hong, Trent Huang, William J. Huggins, L. B. Ioffe, Sergei V. Isakov, Evan Jeffrey, Zhang Jiang, Cody Jones, Dvir Kafri, Julian Kelly, Seon Kim, Alexei Kitaev, Paul V. Klimov, Alexander N. Korotkov, Fedor Kostritsa, David Landhuis, Pavel Laptev, Erik Lucero, Orion Martin, Jarrod R. McClean, Trevor McCourt, Matt McEwen, Anthony Megrant, Kevin C. Miao, Masoud Mohseni, Shirin Montazeri, Wojciech Mruczkiewicz, Josh Mutus, Ofer Naaman, Matthew Neeley, Michael Newman, Murphy Yuezhen Niu, Thomas E. O’Brien, Alex Opremcak, Eric Ostby, Balint Pato, Andre Petukhov, Nicholas Redd, Nicholas C. Rubin, Daniel Sank, Kevin J. Satzinger, Vladimir Shvarts, Doug Strain, Marco Szalay, Matthew D. Trevithick, Benjamin Villalonga, Theodore White, Z. Jamie Yao, Ping Yeh, Adam Zalcman, Hartmut Neven, Igor Aleiner, Kostyantyn Kechedzhi, Vadim Smelyanskiy, and Yu Chen, "Information scrambling in quantum circuits", Science 374 6574, 1479 (2021).

[45] Sergey Bravyi, David Gosset, Robert Koenig, and Marco Tomamichel, 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) 995 (2019) ISBN:978-1-7281-4952-3.

[46] Kun Fang and Zi-Wen Liu, "No-Go Theorems for Quantum Resource Purification: New Approach and Channel Theory", PRX Quantum 3 1, 010337 (2022).

[47] Poulami Das, Swamit Tannu, Siddharth Dangwal, and Moinuddin Qureshi, MICRO-54: 54th Annual IEEE/ACM International Symposium on Microarchitecture 950 (2021) ISBN:9781450385572.

[48] Sergey Bravyi, Oliver Dial, Jay M. Gambetta, Darío Gil, and Zaira Nazario, "The future of quantum computing with superconducting qubits", Journal of Applied Physics 132 16, 160902 (2022).

[49] Shir Peleg, Amir Shpilka, and Ben Lee Volk, "Lower Bounds on Stabilizer Rank", Quantum 6, 652 (2022).

[50] Timothée Goubault de Brugière, Marc Baboulin, Benoît Valiron, and Cyril Allouche, Lecture Notes in Computer Science 11537, 3 (2019) ISBN:978-3-030-22740-1.

[51] James R. Seddon, Bartosz Regula, Hakop Pashayan, Yingkai Ouyang, and Earl T. Campbell, "Quantifying Quantum Speedups: Improved Classical Simulation From Tighter Magic Monotones", PRX Quantum 2 1, 010345 (2021).

[52] Alessandro Rudi, Leonard Wossnig, Carlo Ciliberto, Andrea Rocchetto, Massimiliano Pontil, and Simone Severini, "Approximating Hamiltonian dynamics with the Nyström method", Quantum 4, 234 (2020).

[53] Benjamin Lovitz and Vincent Steffan, "New techniques for bounding stabilizer rank", Quantum 6, 692 (2022).

[54] Antonio Chella, Salvatore Gaglio, Giovanni Pilato, Filippo Vella, and Salvatore Zammuto, "A Quantum Planner for Robot Motion", Mathematics 10 14, 2475 (2022).

[55] Niel de Beaudrap and Steven Herbert, "Fast Stabiliser Simulation with Quadratic Form Expansions", Quantum 6, 803 (2022).

[56] Kaifeng Bu, Dax Enshan Koh, Lu Li, Qingxian Luo, and Yaobo Zhang, "Statistical complexity of quantum circuits", Physical Review A 105 6, 062431 (2022).

[57] Fu Shuangshuang, Li Xiaohui, and Luo Shunlong, "Dynamics of atomic magic in the Jaynes–Cummings model", Quantum Information Processing 22 1, 7 (2022).

[58] Markus Heinrich and David Gross, "Robustness of Magic and Symmetries of the Stabiliser Polytope", arXiv:1807.10296, Quantum 3, 132 (2019).

[59] Xin Wang, Mark M. Wilde, and Yuan Su, "Efficiently Computable Bounds for Magic State Distillation", arXiv:1812.10145, Physical Review Letters 124 9, 090505 (2020).

[60] Christopher Chamberland and Kyungjoo Noh, "Very low overhead fault-tolerant magic state preparation using redundant ancilla encoding and flag qubits", npj Quantum Information 6 1, 91 (2020).

[61] Alexander Tianlin Hu and Andrey Boris Khesin, "Improved graph formalism for quantum circuit simulation", Physical Review A 105 2, 022432 (2022).

[62] Farrokh Labib, "Stabilizer rank and higher-order Fourier analysis", Quantum 6, 645 (2022).

[63] Kun Fang and Zi-Wen Liu, "No-Go Theorems for Quantum Resource Purification", Physical Review Letters 125 6, 060405 (2020).

[64] Ludovico Lami, Bartosz Regula, Ryuji Takagi, and Giovanni Ferrari, "Framework for resource quantification in infinite-dimensional general probabilistic theories", Physical Review A 103 3, 032424 (2021).

[65] J. Haferkamp, F. Montealegre-Mora, M. Heinrich, J. Eisert, D. Gross, and I. Roth, "Efficient Unitary Designs with a System-Size Independent Number of Non-Clifford Gates", Communications in Mathematical Physics (2022).

[66] Ryuji Takagi and Hiroyasu Tajima, "Universal limitations on implementing resourceful unitary evolutions", Physical Review A 101 2, 022315 (2020).

[67] Hakop Pashayan, Oliver Reardon-Smith, Kamil Korzekwa, and Stephen D. Bartlett, "Fast Estimation of Outcome Probabilities for Quantum Circuits", PRX Quantum 3 2, 020361 (2022).

[68] Sergey Bravyi, David Gosset, Robert König, and Marco Tomamichel, "Quantum advantage with noisy shallow circuits", Nature Physics 16 10, 1040 (2020).

[69] Laszlo Gyongyosi and Sandor Imre, "Quantum circuit design for objective function maximization in gate-model quantum computers", Quantum Information Processing 18 7, 225 (2019).

[70] Лин-Сюань Фэн, Lingxuan Feng, Шунь Лун Ло, and Shunlong Luo, "От стабилизирующих состояний к фидуциальным состояниям, задающим симметричную информационно-полную положительную операторнозначную меру", Теоретическая и математическая физика 213 3, 505 (2022).

[71] Bartosz Regula and Ryuji Takagi, "Fundamental limitations on distillation of quantum channel resources", Nature Communications 12 1, 4411 (2021).

[72] Thien Nguyen, Dmitry Lyakh, Eugene Dumitrescu, David Clark, Jeff Larkin, and Alexander McCaskey, "Tensor Network Quantum Virtual Machine for Simulating Quantum Circuits at Exascale", ACM Transactions on Quantum Computing 4 1, 1 (2023).

[73] Alejandro Sopena, Max Hunter Gordon, Germán Sierra, and Esperanza López, "Simulating quench dynamics on a digital quantum computer with data-driven error mitigation", Quantum Science and Technology 6 4, 045003 (2021).

[74] Yasuhiro Kondo, Ryuhei Mori, and Ramis Movassagh, 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) 1296 (2022) ISBN:978-1-6654-2055-6.

[75] Aleks Kissinger and John van de Wetering, "Simulating quantum circuits with ZX-calculus reduced stabiliser decompositions", Quantum Science and Technology 7 4, 044001 (2022).

[76] Edwin Pednault, John A. Gunnels, Giacomo Nannicini, Lior Horesh, Thomas Magerlein, Edgar Solomonik, Erik W. Draeger, Eric T. Holland, and Robert Wisnieff, "Pareto-Efficient Quantum Circuit Simulation Using Tensor Contraction Deferral", arXiv:1710.05867.

[77] Fernando G. S. L. Brandao, Michael Broughton, Edward Farhi, Sam Gutmann, and Hartmut Neven, "For Fixed Control Parameters the Quantum Approximate Optimization Algorithm's Objective Function Value Concentrates for Typical Instances", arXiv:1812.04170.

[78] Igor L. Markov, Aneeqa Fatima, Sergei V. Isakov, and Sergio Boixo, "Quantum Supremacy Is Both Closer and Farther than It Appears", arXiv:1807.10749.

[79] Narayanan Rengaswamy, Robert Calderbank, and Henry D. Pfister, "Unifying the Clifford hierarchy via symmetric matrices over rings", Physical Review A 100 2, 022304 (2019).

[80] Zi-Wen Liu, Kaifeng Bu, and Ryuji Takagi, "One-Shot Operational Quantum Resource Theory", Physical Review Letters 123 2, 020401 (2019).

[81] Christopher David White and Justin H. Wilson, "Mana in Haar-random states", arXiv:2011.13937.

[82] A. D. Corcoles, A. Kandala, A. Javadi-Abhari, D. T. McClure, A. W. Cross, K. Temme, P. D. Nation, M. Steffen, and J. M. Gambetta, "Challenges and Opportunities of Near-Term Quantum Computing Systems", arXiv:1910.02894.

[83] Adam Kelly, "Simulating Quantum Computers Using OpenCL", arXiv:1805.00988.

[84] Yifei Huang and Peter Love, "Approximate stabilizer rank and improved weak simulation of Clifford-dominated circuits for qudits", Physical Review A 99 5, 052307 (2019).

[85] Patrick Rall, Daniel Liang, Jeremy Cook, and William Kretschmer, "Simulation of qubit quantum circuits via Pauli propagation", Physical Review A 99 6, 062337 (2019).

[86] Niel de Beaudrap, Xiaoning Bian, and Quanlong Wang, "Fast and effective techniques for T-count reduction via spider nest identities", arXiv:2004.05164.

[87] Michael J. Bremner, Zhengfeng Ji, Ryan L. Mann, Luke Mathieson, Mauro E. S. Morales, and Alexis T. E. Shaw, "Quantum Parameterized Complexity", arXiv:2203.08002.

[88] Iskren Vankov, Daniel Mills, Petros Wallden, and Elham Kashefi, "Methods for classically simulating noisy networked quantum architectures", Quantum Science and Technology 5 1, 014001 (2020).

[89] Kaifeng Bu and Dax Enshan Koh, "Efficient classical simulation of Clifford circuits with nonstabilizer input states", arXiv:1902.11257.

[90] Cupjin Huang, Michael Newman, and Mario Szegedy, "Explicit lower bounds on strong simulation of quantum circuits in terms of $T$-gate count", arXiv:1902.04764.

[91] Narayanan Rengaswamy, "Classical Coding Approaches to Quantum Applications", arXiv:2004.06834.

[92] Chaowen Guan and Kenneth W. Regan, "Stabilizer Circuits, Quadratic Forms, and Computing Matrix Rank", arXiv:1904.00101.

The above citations are from Crossref's cited-by service (last updated successfully 2022-12-08 12:46:40) and SAO/NASA ADS (last updated successfully 2022-12-08 12:46:42). The list may be incomplete as not all publishers provide suitable and complete citation data.

1 thought on “Simulation of quantum circuits by low-rank stabilizer decompositions

  1. Pingback: Riverlane appoints leading scientist Dr. Earl Campbell to accelerate efforts to solve quantum error correction - Riverlane