1Centre for Engineered Quantum Systems, School of Physics, The University of Sydney, Sydney, NSW 2006, Australia
2Institute for Theoretical Physics, University of Cologne, Germany
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
Investigating the classical simulability of quantum circuits provides a promising avenue towards understanding the computational power of quantum systems. Whether a class of quantum circuits can be efficiently simulated with a probabilistic classical computer, or is provably hard to simulate, depends quite critically on the precise notion of “classical simulation” and in particular on the required accuracy. We argue that a notion of classical simulation, which we call EPSILON-simulation (or $epsilon$-simulation for short), captures the essence of possessing “equivalent computational power” as the quantum system it simulates: It is statistically impossible to distinguish an agent with access to an $epsilon$-simulator from one possessing the simulated quantum system. We relate $epsilon$-simulation to various alternative notions of simulation predominantly focusing on a simulator we call a $textit{poly-box}$. A poly-box outputs $1/poly$ precision additive estimates of Born probabilities and marginals. This notion of simulation has gained prominence through a number of recent simulability results. Accepting some plausible computational theoretic assumptions, we show that $epsilon$-simulation is strictly stronger than a poly-box by showing that IQP circuits and unconditioned magic-state injected Clifford circuits are both hard to $epsilon$-simulate and yet admit a poly-box. In contrast, we also show that these two notions are equivalent under an additional assumption on the sparsity of the output distribution ($textit{poly-sparsity}$).
► BibTeX data
► References
[1] R. P. Feynman, “Simulating Physics with Computers,” Int. J. Theor. Phys., 21, 467-488 (1982).
https://doi.org/10.1007/BF02650179
[2] S. Aaronson and D. Gottesman, “Improved simulation of stabilizer circuits,” Phys. Rev. A, 70, 052328 (2004).
https://doi.org/10.1103/PhysRevA.70.052328
[3] L. G. Valiant, “Quantum circuits that can be simulated classically in polynomial time,” SIAM Journal on Computing, 31, 1229-1254 (2002).
https://doi.org/10.1137/S0097539700377025
[4] B. M. Terhal and D. P. DiVincenzo, “Classical simulation of noninteracting-fermion quantum circuits,” Phys. Rev. A 65, 032325 (2002).
https://doi.org/10.1103/PhysRevA.65.032325
[5] S. D. Bartlett, B. C. Sanders, S. L. Braunstein, and K. Nemoto, “Efficient classical simulation of continuous variable quantum information processes,” Phys. Rev. Lett. 88, 097904 (2002).
https://doi.org/10.1103/PhysRevLett.88.097904
[6] L. Gurvits, “On the complexity of mixed discriminants and related problems,” in: Jedrzejowicz J., Szepietowski A. (eds) Mathematical Foundations of Computer Science 2005. MFCS 2005. Lecture Notes in Computer Science, vol 3618. Springer, Berlin, Heidelberg (2005).
https://doi.org/10.1007/11549345_39
[7] S. Aaronson and A. Arkhipov, “The computational complexity of linear optics,” in Proceedings of the forty-third annual ACM symposium on Theory of computing, 333-342, ACM (2011).
https://doi.org/10.1145/1993636.1993682
[8] M. J. Bremner, R. Jozsa, and D. J. Shepherd, “Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy,” Proc. R. Soc. A 467, (2010).
https://doi.org/10.1098/rspa.2010.0301
[9] M. J. Bremner, A. Montanaro, and D. J. Shepherd, “Average-case complexity versus approximate simulation of commuting quantum computations,” Phys. Rev. Lett. 117, 080501 (2016).
https://doi.org/10.1103/PhysRevLett.117.080501
[10] X. Gao, S.-T. Wang, and L.-M. Duan, “Quantum supremacy for simulating a translation-invariant Ising spin model,” Phys. Rev. Lett. 118, 040502 (2017).
https://doi.org/10.1103/PhysRevLett.118.040502
[11] J. Bermejo-Vega, D. Hangleiter, M. Schwarz, R. Raussendorf, and J. Eisert, “Architectures for quantum simulation showing a quantum speedup,” Phys. Rev. X 8, 021010 (2018).
https://doi.org/10.1103/PhysRevX.8.021010
[12] B. Fefferman and C. Umans, “The power of quantum fourier sampling,” arXiv preprint arXiv:1507.05592, (2015).
arXiv:1507.05592
[13] T. Morimae, K. Fujii, and J. F. Fitzsimons, “Hardness of classically simulating the one-clean-qubit model,” Phys. Rev. Lett. 112, 130502 (2014).
https://doi.org/10.1103/PhysRevLett.112.130502
[14] T. Morimae, K. Fujii, and H. Nishimura, “Power of one nonclean qubit,” Phys. Rev. A 95, 042336 (2017).
https://doi.org/10.1103/PhysRevA.95.042336
[15] S. Boixo, S. V. Isakov, V. N. Smelyanskiy, R. Babbush, N. Ding, Z. Jiang, M. J. Bremner, J. M. Martinis, and H. Neven, “Characterizing quantum supremacy in near-term devices,” Nature Phys. 14, 595-600 (2018).
https://doi.org/10.1038/s41567-018-0124-x
[16] A. Bouland, J. F. Fitzsimons, and D. E. Koh, “Complexity Classification of Conjugated Clifford Circuits,” in 33rd Computational Complexity Conference (CCC 2018) (R. A. Servedio, ed.), vol. 102 of Leibniz International Proceedings in Informatics (LIPIcs), (Dagstuhl, Germany), pp. 21:1-21:25, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018.
https://doi.org/10.4230/LIPIcs.CCC.2018.21
[17] D. J. Brod, “Efficient classical simulation of matchgate circuits with generalized inputs and measurements,” Phys. Rev. A 93, 062332 (2016).
https://doi.org/10.1103/PhysRevA.93.062332
[18] R. Jozsa and A. Miyake, “Matchgates and classical simulation of quantum circuits,” Proc. R. Soc. A 464, 3089-3106 (2008).
https://doi.org/10.1098/rspa.2008.0189
[19] V. Veitch, C. Ferrie, D. Gross, and J. Emerson, “Negative quasi-probability as a resource for quantum computation,” New J. Phys. 14, 113011 (2012).
https://doi.org/10.1088/1367-2630/14/11/113011
[20] V. Veitch, N. Wiebe, C. Ferrie, and J. Emerson, “Efficient simulation scheme for a class of quantum optics experiments with non-negative Wigner representation,” New J. Phys. 15, 013037 (2013).
https://doi.org/10.1088/1367-2630/15/1/013037
[21] A. Mari and J. Eisert, “Positive Wigner functions render classical simulation of quantum computation efficient,” Phys. Rev. Lett. 109, 230503 (2012).
https://doi.org/10.1103/PhysRevLett.109.230503
[22] S. Bravyi and D. Gosset, “Improved classical simulation of quantum circuits dominated by Clifford gates,” Phys. Rev. Lett. 116, 250501 (2016).
https://doi.org/10.1103/PhysRevLett.116.250501
[23] R. S. Bennink, E. M. Ferragut, T. S. Humble, J. A. Laska, J. J. Nutaro, M. G. Pleszkoch, and R. C. Pooser, “Unbiased simulation of near-Clifford quantum circuits,” Phys. Rev. A 95, 062337 (2017).
https://doi.org/10.1103/PhysRevA.95.062337
[24] M. J. Bremner, A. Montanaro, and D. J. Shepherd, “Achieving quantum supremacy with sparse and noisy commuting quantum computatio
ns,” Quantum 1, 8 (2017).
https://doi.org/10.22331/q-2017-04-25-8
[25] M. Oszmaniec and D. J. Brod, “Classical simulation of photonic linear optics with lost particles,” New J. Phys. 20, 092002 (2018).
https://doi.org/10.1088/1367-2630/aadfa8
[26] M. Howard and E. Campbell, “Application of a resource theory for magic states to fault-tolerant quantum computing,” Phys. Rev. Lett. 118, 090501 (2017).
https://doi.org/10.1103/PhysRevLett.118.090501
[27] H. Pashayan, J. J. Wallman, and S. D. Bartlett, “Estimating outcome probabilities of quantum circuits using quasiprobabilities,” Phys. Rev. Lett. 115, 070501 (2015).
https://doi.org/10.1103/PhysRevLett.115.070501
[28] M. Van Den Nest, “Efficient classical simulations of quantum Fourier transforms and normalizer circuits over Abelian groups,” arXiv preprint arXiv:1201.4867, 2012.
arXiv:1201.4867
[29] J. Bermejo-Vega and M. Van Den Nest, “Classical simulations of Abelian-group normalizer circuits with intermediate measurements,” Quantum Info. Comput. 14, 181-216 (2014).
[30] M. Schwarz and M. Van Den Nest, “Simulating quantum circuits with sparse output distributions,” arXiv preprint arXiv:1310.6749, 2013.
arXiv:1310.6749
[31] S. Bravyi, G. Smith, and J. A. Smolin, “Trading classical and quantum computational resources,” Phys. Rev. X, 6, 021043 (2016).
https://doi.org/10.1103/PhysRevX.6.021043
[32] K. Temme, S. Bravyi, and J. M. Gambetta, “Error mitigation for short-depth quantum circuits,” Phys. Rev. Lett. 119, 180509 (2017).
https://doi.org/10.1103/PhysRevLett.119.180509
[33] M. Van Den Nest, “Classical simulation of quantum computation, the Gottesman-Knill theorem, and slightly beyond,” Quantum Info. Comput. 10, 258-271 (2010).
[34] R. Jozsa and N. Linden, “On the role of entanglement in quantum-computational speed-up,” Proc. R. Soc. A 459, 2011-2032 (2003).
https://doi.org/10.1098/rspa.2002.1097
[35] B. M. Terhal and D. P. DiVincenzo, “Adaptive quantum computation, constant depth quantum circuits and arthur-merlin games,” Quantum Info. Comput. 4, 134-145 (2004).
[36] T. Morimae, “Hardness of classically sampling the one-clean-qubit model with constant total variation distance error,” Phys. Rev. A 96, 040302 (2017).
https://doi.org/10.1103/PhysRevA.96.040302
[37] S. Aaronson, “The equivalence of sampling and searching,” Theory of Computing Systems, 55, 281-298 (2014).
https://doi.org/10.1007/s00224-013-9527-3
[38] M. Van Den Nest, “Simulating quantum computers with probabilistic methods,” Quantum Info. Comput. 11, 784-812 (2011).
[39] D. Shepherd, “Binary matroids and quantum probability distributions,” arXiv preprint arXiv:1005.1744, (2010).
arXiv:1005.1744
[40] S. Bravyi and A. Kitaev, “Universal quantum computation with ideal clifford gates and noisy ancillas,” Phys. Rev. A 71, 022316 (2005).
https://doi.org/10.1103/PhysRevA.71.022316
[41] R. Jozsa and M. Van Den Nest, “Classical simulation complexity of extended Clifford circuits,” Quantum Info. Comput. 14, 633-648 (2014).
[42] L. A. Goldberg and H. Guo, “The complexity of approximating complex-valued Ising and Tutte partition functions,” comput. complex. 26, 765-833 (2017).
https://doi.org/10.1007/s00037-017-0162-2
[43] G. Kuperberg, “How hard is it to approximate the Jones polynomial?,” Theory of Computing, 11, 183-219 (2015).
https://doi.org/10.4086/toc.2015.v011a006
[44] K. Fujii and T. Morimae, “Commuting quantum circuits and complexity of Ising partition functions,” New J. Phys. 19, 033003 (2017).
https://doi.org/10.1088/1367-2630/aa5fdb
[45] D. Stahlke, “Quantum interference as a resource for quantum speedup,” Phys. Rev. A 90, 022302 (2014).
https://doi.org/10.1103/PhysRevA.90.022302
[46] D. Shepherd and M. J. Bremner, “Temporally unstructured quantum computation,” Proc. R. Soc. A 465, 1413-1439 (2009).
https://doi.org/10.1098/rspa.2008.0443
[47] D. J. Shepherd, “Quantum complexity: restrictions on algorithms and architectures,” arXiv preprint arXiv:1005.1425 (2010).
arXiv:1005.1425
[48] D. Vertigan, “Bicycle dimension and special points of the Tutte polynomial,” J. Combin. Theory Ser. B 74, 378-396 (1998).
https://doi.org/10.1006/jctb.1998.1860
[49] R. Renner and S. Wolf, “Smooth Rényi entropy and applications,” in International Symposium on Information Theory, 2004. ISIT 2004. Proceedings., pp. 233 (2004).
https://doi.org/10.1109/ISIT.2004.1365269
[50] L. Stockmeyer, “The complexity of approximate counting,” in Proceedings of the fifteenth annual ACM symposium on Theory of computing, pp. 118-126, ACM, (1983).
https://doi.org/10.1145/800061.808740
[51] S. Toda, “PP is as hard as the polynomial-time hierarchy,” SIAM Journal on Computing 20, 865-877 (1991).
https://doi.org/10.1137/0220053
[52] S. Aaronson and T. Hance, “Generalizing and derandomizing Gurvits’s approximation algorithm for the permanent,” Quantum Info. Comput. 14, 541-559 (2014).
Cited by
[1] James R. Seddon and Earl T. Campbell, “Quantifying magic for multi-qubit operations”, Proceedings of the Royal Society o
f London Series A 475 2227, 20190251 (2019).
[2] Patrick Rall, Daniel Liang, Jeremy Cook, and William Kretschmer, “Simulation of qubit quantum circuits via Pauli propagation”, Physical Review A 99 6, 062337 (2019).
[3] Wojciech Roga and Masahiro Takeoka, “Classical simulation of boson sampling with sparse output”, arXiv:1904.05494.
[4] Tianyi Peng, Aram Harrow, Maris Ozols, and Xiaodi Wu, “Simulating large quantum circuits on a small quantum computer”, arXiv:1904.00102.
[5] Angela Karanjai, Joel J. Wallman, and Stephen D. Bartlett, “Contextuality bounds the efficiency of classical simulation of quantum processes”, arXiv:1802.07744.
[6] Michał Oszmaniec and Daniel J. Brod, “Classical simulation of photonic linear optics with lost particles”, New Journal of Physics 20 9, 092002 (2018).
[7] Mithuna Yoganathan, Richard Jozsa, and Sergii Strelchuk, “Quantum advantage of unitary Clifford circuits with magic state inputs”, Proceedings of the Royal Society of London Series A 475 2225, 20180427 (2019).
[8] Piers Lillystone and Joseph Emerson, “A Contextual $psi$-Epistemic Model of the $n$-Qubit Stabilizer Formalism”, arXiv:1904.04268.
[9] Daochen Wang, “Simulating quantum circuits by classical circuits”, arXiv:1904.05282.
[10] Patrick Rall, “Simulating Quantum Circuits by Shuffling Paulis”, arXiv:1804.05404.
[11] Leonardo Novo, Juani Bermejo-Vega, and Raúl García-Patrón, “Quantum advantage from energy measurements of many-body quantum systems”, arXiv:1912.06608.
[12] Filip B. Maciejewski, Zoltán Zimborás, and Michał Oszmaniec, “Mitigation of readout noise in near-term quantum devices by classical post-processing based on detector tomography”, arXiv:1907.08518.
The above citations are from SAO/NASA ADS (last updated successfully 2020-01-22 17:25:20). 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 2020-01-22 17:25:18).
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.
Source: https://quantum-journal.org/papers/q-2020-01-13-223/
