1Institute for Quantum Computing, University of Waterloo, Canada
2Department of Combinatorics and Optimization, University of Waterloo, Canada
3Perimeter Institute for Theoretical Physics, Waterloo, Canada
4Cheriton School of Computer Science, University of Waterloo, Canada
5Department of Computer Science and Engineering and Department of Mathematics, University of California, San Diego, US
6Joint Center for Quantum Information and Computer Science, College Park, Maryland, US
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
A general quantum circuit can be simulated classically in exponential time. If it has a planar layout, then a tensor-network contraction algorithm due to Markov and Shi has a runtime exponential in the square root of its size, or more generally exponential in the treewidth of the underlying graph. Separately, Gottesman and Knill showed that if all gates are restricted to be Clifford, then there is a polynomial time simulation. We combine these two ideas and show that treewidth and planarity can be exploited to improve Clifford circuit simulation. Our main result is a classical algorithm with runtime scaling asymptotically as $ n^{omega/2}$ $lt$ $n^{1.19}$ which samples from the output distribution obtained by measuring all $n$ qubits of a planar graph state in given Pauli bases. Here $omega$ is the matrix multiplication exponent. We also provide a classical algorithm with the same asymptotic runtime which samples from the output distribution of any constant-depth Clifford circuit in a planar geometry. Our work improves known classical algorithms with cubic runtime.
A key ingredient is a mapping which, given a tree decomposition of some graph $G$, produces a Clifford circuit with a structure that mirrors the tree decomposition and which emulates measurement of the corresponding graph state. We provide a classical simulation of this circuit with the runtime stated above for planar graphs and otherwise $nt^{omega-1}$ where $t$ is the width of the tree decomposition. Our algorithm incorporates two subroutines which may be of independent interest. The first is a matrix-multiplication-time version of the Gottesman-Knill simulation of multi-qubit measurement on stabilizer states. The second is a new classical algorithm for solving symmetric linear systems over $mathbb{F}_2$ in a planar geometry, extending previous works which only applied to non-singular linear systems in the analogous setting.
Featured image: Clockwise from left: A graph, a nice tree decomposition, and a circuit preparing the corresponding graph state.
[embedded content]
► BibTeX data
► References
[1] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando GSL Brandao, David A Buell, et al. “Quantum supremacy using a programmable superconducting processor”. Nature 574, 505–510 (2019).
https://doi.org/10.1038/s41586-019-1666-5
[2] “Ibm quantum documentation”. https://docs.quantum.ibm.com/run.
https://docs.quantum.ibm.com/run
[3] Matthew D Reed, Leonardo DiCarlo, Simon E Nigg, Luyan Sun, Luigi Frunzio, Steven M Girvin, and Robert J Schoelkopf. “Realization of three-qubit quantum error correction with superconducting circuits”. Nature 482, 382–385 (2012).
https://doi.org/10.1038/nature10786
[4] Antonio D Córcoles, Easwar Magesan, Srikanth J Srinivasan, Andrew W Cross, Matthias Steffen, Jay M Gambetta, and Jerry M Chow. “Demonstration of a quantum error detection code using a square lattice of four superconducting qubits”. Nature communications 6, 1–10 (2015).
https://doi.org/10.1038/ncomms7979
[5] Nissim Ofek, Andrei Petrenko, Reinier Heeres, Philip Reinhold, Zaki Leghtas, Brian Vlastakis, Yehan Liu, Luigi Frunzio, SM Girvin, Liang Jiang, et al. “Extending the lifetime of a quantum bit with error correction in superconducting circuits”. Nature 536, 441–445 (2016).
https://doi.org/10.1038/nature18949
[6] Igor L Markov and Yaoyun Shi. “Simulating quantum computation by contracting tensor networks”. SIAM Journal on Computing 38, 963–981 (2008).
https://doi.org/10.1137/050644756
[7] Sergio Boixo, Sergei V Isakov, Vadim N Smelyanskiy, and Hartmut Neven. “Simulation of low-depth quantum circuits as complex undirected graphical models” (2017).
[8] Sergey Bravyi, Dan Browne, Padraic Calpin, Earl Campbell, David Gosset, and Mark Howard. “Simulation of quantum circuits by low-rank stabilizer decompositions”. Quantum 3, 181 (2019).
https://doi.org/10.22331/q-2019-09-02-181
[9] Edwin Pednault, John A Gunnels, Giacomo Nannicini, Lior Horesh, Thomas Magerlein, Edgar Solomonik, Erik W Draeger, Eric T Holland, and Robert Wisnieff. “Breaking the 49-qubit barrier in the simulation of quantum circuits” (2017).
[10] Edwin Pednault, John A Gunnels, Giacomo Nannicini, Lior Horesh, and Robert Wisnieff. “Leveraging secondary storage to simulate deep 54-qubit Sycamore circuits” (2019).
[11] Boaz Barak, Chi-Ning Chou, and Xun Gao. “Spoofing linear cross-entropy benchmarking in shallow quantum circuits” (2020).
[12] Barbara M Terhal and David P DiVincenzo. “Adaptive quantum computation, constant depth quantum circuits and Arthur-Merlin games” (2002).
[13] Michael J Bremner, Richard Jozsa, and Dan J Shepherd. “Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy”. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 467, 459–472 (2011).
https://doi.org/10.1098/rspa.2010.0301
[14] Scott Aaronson and Alex Arkhipov. “The computational complexity of linear optics”. In Proceedings of the forty-third annual ACM symposium on Theory of computing. Pages 333–342. (2011).
https://doi.org/10.1145/1993636.1993682
[15] Daniel Gottesman. “The Heisenberg representation of quantum computers” (1998).
[16] Sergey Bravyi and David Gosset. “Improved classical simulation of quantum circuits dominated by Clifford gates”. Physical review letters 116, 250501 (2016).
https://doi.org/10.1103/physrevlett.116.250501
[17] Scott Aaronson and Daniel Gottesman. “Improved simulation of stabilizer circuits”. Physical Review A 70, 052328 (2004).
https://doi.org/10.1103/PhysRevA.70.052328
[18] Sergey Bravyi, David Gosset, and Robert König. “Quantum advantage with shallow circuits”. Science 362, 308–311 (2018).
https://doi.org/10.1126/science.aar3106
[19] Adam Bene Watts, Robin Kothari, Luke Schaeffer, and Avishay Tal. “Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits”. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. Pages 515–526. (2019).
https://doi.org/10.1145/3313276.3316404
[20] Daniel Grier and Luke Schaeffer. “Interactive shallow Clifford circuits: quantum advantage against $mathsf{NC}^1$ and beyond”. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. Pages 875–888. (2020).
https://doi.org/10.1145/3357713.3384332
[21] Sergey Bravyi, David Gosset, Robert Koenig, and Marco Tomamichel. “Quantum advantage with noisy shallow circuits”. Nature PhysicsPages 1–6 (2020).
https://doi.org/10.1038/s41567-020-0948-z
[22] Robert Raussendorf and Hans J Briegel. “A one-way quantum computer”. Physical Review Letters 86, 5188 (2001).
https://doi.org/10.1103/PhysRevLett.86.5188
[23] Josh Alman and Virginia Vassilevska Williams. “A refined laser method and faster matrix multiplication” (2020).
[24] Chaowen Guan and Kenneth W Regan. “Stabilizer circuits, quadratic forms, and computing matrix rank” (2019).
[25] Daniel Grier and Luke Schaeffer. “gridCHP++, Apache license version 2.0”. https://github.com/danielgrier/gridCHPpp/tree/v1.0.0.
https://github.com/danielgrier/gridCHPpp/tree/v1.0.0
[26] Alan George. “Nested dissection of a regular finite element mesh”. SIAM Journal on Numerical Analysis 10, 345–363 (1973).
https://doi.org/10.1137/0710032
[27] Richard J Lipton, Donald J Rose, and Robert Endre Tarjan. “Generalized nested dissection”. SIAM journal on numerical analysis 16, 346–358 (1979).
https://doi.org/10.1137/0716027
[28] Noga Alon and Raphael Yuster. “Solving linear systems through nested dissection”. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science. Pages 225–234. IEEE (2010).
https://doi.org/10.1109/FOCS.2010.28
[29] Richard J. Lipton and Robert Endre Tarjan. “A separator theorem for planar graphs”. SIAM Journal on Applied Mathematics 36, 177–189 (1979).
https://doi.org/10.1137/0136016
[30] Scott Aaronson and Lijie Chen. “Complexity-theoretic foundations of quantum supremacy experiments”. In 32nd Computational Complexity Conference (CCC 2017). Schloss Dagstuhl-Leibniz-Zentrum für Informatik (2017).
[31] Jianxin Chen, Fang Zhang, Cupjin Huang, Michael Newman, and Yaoyun Shi. “Classical simulation of intermediate-size quantum circuits” (2018).
[32] Benjamin Villalonga, Dmitry Lyakh, Sergio Boixo, Hartmut Neven, Travis S Humble, Rupak Biswas, Eleanor G Rieffel, Alan Ho, and Salvatore Mandrà. “Establishing the quantum supremacy frontier with a 281 pflop/s simulation”. Quantum Science and Technology 5, 034003 (2020).
https://doi.org/10.1088/2058-9565/ab7eeb
[33] Stefan Arnborg, Derek G Corneil, and Andrzej Proskurowski. “Complexity of finding embeddings in a $k$-tree”. SIAM Journal on Algebraic Discrete Methods 8, 277–284 (1987).
https://doi.org/10.1137/0608024
[34] HL Bodlaender. “A tourist guide through treewidth”. Acta Cybernetica 11, 1–21 (1993).
[35] Hans L. Bodlaender, Pål Grøonås Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov, and Michał Pilipczuk. “A $c^k n$ 5-approximation algorithm for treewidth”. SIAM Journal on Computing 45, 317–378 (2016).
https://doi.org/10.1137/130947374
[36] Sergey Bravyi, Graeme Smith, and John A Smolin. “Trading classical and quantum computational resources”. Physical Review X 6, 021043 (2016).
https://doi.org/10.1103/PhysRevX.6.021043
[37] M Van den Nest. “Classical simulation of quantum computation, the Gottesman-Knill theorem, and slightly beyond” (2008).
[38] Alex Kerzner. “Clifford simulation: Techniques and applications”. Master’s thesis. University of Waterloo. (2021).
[39] Carsten Damm. “Problems complete for $oplus{L}$”. In Jürgen Dassow and Jozef Kelemen, editors, Aspects and Prospects of Theoretical Computer Science. Pages 130–137. Berlin, Heidelberg (1990). Springer Berlin Heidelberg.
https://doi.org/10.1016/0020-0190(90)90150-V
[40] David Eppstein (2007). commons.wikimedia.org/wiki/File:Tree_decomposition.svg, accessed 08/31/2020.
[41] Hans L Bodlaender and Ton Kloks. “Better algorithms for the pathwidth and treewidth of graphs”. In Automata, Languages and Programming: 18th International Colloquium Madrid, Spain, July 8–12, 1991 Proceedings 18. Pages 544–555. Springer (1991).
https://doi.org/10.1007/3-540-54233-7_162
[42] Oscar H Ibarra, Shlomo Moran, and Roger Hui. “A generalization of the fast LUP matrix decomposition algorithm and applications”. Journal of Algorithms 3, 45–56 (1982).
https://doi.org/10.1016/0196-6774(82)90007-4
[43] Adi Ben-Israel and Thomas NE Greville. “Generalized inverses: theory and applications”. Volume 15. Springer Science & Business Media. (2003).
https://doi.org/10.1007/b97366
[44] Michael T Goodrich. “Planar separators and parallel polygon triangulation”. Journal of Computer and System Sciences 51, 374–389 (1995).
https://doi.org/10.1006/jcss.1995.1076
[45] Jeroen Dehaene and Bart De Moor. “Clifford group, stabilizer states, and linear and quadratic operations over $mathrm{GF}$(2)”. Physical Review A 68, 042318 (2003).
https://doi.org/10.1103/PhysRevA.68.042318
[46] Simon Anders and Hans J Briegel. “Fast simulation of stabilizer circuits using a graph-state representation”. Physical Review A 73, 022334 (2006).
https://doi.org/10.1103/PhysRevA.73.022334
[47] Sergey Bravyi. Personal communication, 2017 (2017).
[48] Maarten Van den Nest, Jeroen Dehaene, and Bart De Moor. “Graphical description of the action of local Clifford transformations on graph states”. Physical Review A 69, 022316 (2004).
https://doi.org/10.1103/PhysRevA.69.022316
Cited by
[1] Travis L. Scholten, Carl J. Williams, Dustin Moody, Michele Mosca, William Hurley, William J. Zeng, Matthias Troyer, and Jay M. Gambetta, “Assessing the Benefits and Risks of Quantum Computers”, arXiv:2401.16317, (2024).
[2] Lorenzo Leone, Salvatore F. E. Oliviero, Seth Lloyd, and Alioscia Hamma, “Learning efficient decoders for quasi-chaotic quantum scramblers”, arXiv:2212.11338, (2022).
[3] Ryan L. Mann, “Simulating quantum computations with Tutte polynomials”, npj Quantum Information 7, 141 (2021).
[4] Sahar Atallah, Michael Garn, Sania Jevtic, Yukuan Tao, and Shashank Virmani, “Efficient classical simulation of cluster state quantum circuits with alternative inputs”, arXiv:2201.07655, (2022).
[5] Shihao Zhang, Jiacheng Bao, Yifan Sun, Lvzhou Li, Houjun Sun, and Xiangdong Zhang, “High-performance parallel classical scheme for simulating shallow quantum circuits”, arXiv:2103.00693, (2021).
The above citations are from SAO/NASA ADS (last updated successfully 2024-02-13 03:31:05). The list may be incomplete as not all publishers provide suitable and complete citation data.
On Crossref’s cited-by service no data on citing works was found (last attempt 2024-02-13 03:31:02).
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.
- SEO Powered Content & PR Distribution. Get Amplified Today.
- PlatoData.Network Vertical Generative Ai. Empower Yourself. Access Here.
- PlatoAiStream. Web3 Intelligence. Knowledge Amplified. Access Here.
- PlatoESG. Carbon, CleanTech, Energy, Environment, Solar, Waste Management. Access Here.
- PlatoHealth. Biotech and Clinical Trials Intelligence. Access Here.
- Source: https://quantum-journal.org/papers/q-2024-02-12-1251/
