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.

Abstract

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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
arXiv:1704.04487

[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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
arXiv:1712.05384

[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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
arXiv:1805.01450

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

[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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
arXiv:1412.6062

[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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
arXiv:1210.6646

[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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
arXiv:1712.08628

[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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
arXiv:1804.10368

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

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

[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.
arXiv:1802.07744

[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.
https:/​/​doi.org/​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.
arXiv:1510.02767

[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.
arXiv:1804.04797

[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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​10.1109/​TIT.2018.2825602
arXiv:1705.09176

[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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
arXiv:1710.05867

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

[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.
https:/​/​doi.org/​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.
arXiv:1601.07195

[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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
arXiv:1609.08172

[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.
https:/​/​doi.org/​10.1088/​0305-4470/​33/​10/​307

Cited by

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

[2] 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).

[3] 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.

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

[5] Sergey Bravyi, David Gosset, Robert Koenig, and Marco Tomamichel, "Quantum advantage with noisy shallow circuits in 3D", arXiv:1904.01502.

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

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

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

[9] 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.

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

[11] Michael Beverland, Earl Campbell, Mark Howard, and Vadym Kliuchnikov, "Lower bounds on the non-Clifford resources for quantum computations", arXiv:1904.01124.

[12] Xin Wang, Mark M. Wilde, and Yuan Su, "Efficiently computable bounds for magic state distillation", arXiv:1812.10145.

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

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

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

[16] Markus Heinrich and David Gross, "Robustness of Magic and Symmetries of the Stabiliser Polytope", arXiv:1807.10296.

[17] Daochen Wang, "Simulating quantum circuits by classical circuits", arXiv:1904.05282.

[18] Hammam Qassim, Joel J. Wallman, and Joseph Emerson, "Clifford recompilation for faster classical simulation of quantum circuits", arXiv:1902.02359.

[19] Kun Fang and Zi-Wen Liu, "No-Go Theorems for Quantum Resource Distillation", arXiv:1909.02540.

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

[21] 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).

[22] 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.

The above citations are from Crossref's cited-by service (last updated 2019-11-13 07:16:26) and SAO/NASA ADS (last updated 2019-11-13 07:16:28). The list may be incomplete as not all publishers provide suitable and complete citation data.