Stationary Phase Method in Discrete Wigner Functions and Classical Simulation of Quantum Circuits

Lucas Kocia; Peter Love

doi:10.22331/q-2021-07-05-494

Stationary Phase Method in Discrete Wigner Functions and Classical Simulation of Quantum Circuits

Lucas Kocia¹ and Peter Love²

¹National Institute of Standards and Technology, Gaithersburg, Maryland, 20899, U.S.A.
²Department of Physics, Tufts University, Medford, Massachusetts 02155, U.S.A.

Published:	2021-07-05, volume 5, page 494
Eprint:	arXiv:1810.03622v4
Doi:	https://doi.org/10.22331/q-2021-07-05-494
Citation:	Quantum 5, 494 (2021).

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

Abstract

One of the lowest-order corrections to Gaussian quantum mechanics in infinite-dimensional Hilbert spaces are Airy functions: a uniformization of the stationary phase method applied in the path integral perspective. We introduce a "periodized stationary phase method" to discrete Wigner functions of systems with odd prime dimension and show that the $\frac{\pi}{8}$ gate is the discrete analog of the Airy function. We then establish a relationship between the stabilizer rank of states and the number of quadratic Gauss sums necessary in the periodized stationary phase method. This allows us to develop a classical strong simulation of a single qutrit marginal on $t$ qutrit $\frac{\pi}{8}$ gates that are followed by Clifford evolution, and show that this only requires $3^{\frac{t}{2}+1}$ quadratic Gauss sums. This outperforms the best alternative qutrit algorithm (based on Wigner negativity and scaling as $\sim\hspace{-3pt} 3^{0.8 t}$ for $10^{-2}$ precision) for any number of $\frac{\pi}{8}$ gates to full precision.

► BibTeX data

@article{Kocia2021stationaryphase,
  doi = {10.22331/q-2021-07-05-494},
  url = {https://doi.org/10.22331/q-2021-07-05-494},
  title = {Stationary {P}hase {M}ethod in {D}iscrete {W}igner {F}unctions and {C}lassical {S}imulation of {Q}uantum {C}ircuits},
  author = {Kocia, Lucas and Love, Peter},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {5},
  pages = {494},
  month = jul,
  year = {2021}
}

► References

[1] Greg Kuperberg. How hard is it to approximate the jones polynomial? Theory of Computing, 11 (6): 183–219, 2015. 10.4086/toc.2015.v011a006. URL http://www.theoryofcomputing.org/articles/v011a006.
https://doi.org/10.4086/toc.2015.v011a006
http://www.theoryofcomputing.org/articles/v011a006

[2] Keisuke Fujii and Tomoyuki Morimae. Commuting quantum circuits and complexity of ising partition functions. New Journal of Physics, 19 (3): 033003, Mar 2017. 10.1088/1367-2630/aa5fdb. URL https://doi.org/10.1088.
https://doi.org/10.1088/1367-2630/aa5fdb

[3] Dominik Hangleiter, Juan Bermejo-Vega, Martin Schwarz, and Jens Eisert. Anticoncentration theorems for schemes showing a quantum speedup. Quantum, 2: 65, May 2018. ISSN 2521-327X. 10.22331/q-2018-05-22-65. URL https://doi.org/10.22331/q-2018-05-22-65.
https://doi.org/10.22331/q-2018-05-22-65

[4] Lucas Kocia, Yifei Huang, and Peter Love. Discrete Wigner function derivation of the Aaronson-Gottesman tableau algorithm. Entropy, 19 (7), 2017a. ISSN 1099-4300. 10.3390/e19070353. URL http://www.mdpi.com/1099-4300/19/7/353.
https://doi.org/10.3390/e19070353
http://www.mdpi.com/1099-4300/19/7/353

[5] Lucas Kocia and Peter Love. Discrete wigner formalism for qubits and noncontextuality of clifford gates on qubit stabilizer states. Phys. Rev. A, 96: 062134, Dec 2017. 10.1103/PhysRevA.96.062134. URL https://link.aps.org/doi/10.1103/PhysRevA.96.062134.
https://doi.org/10.1103/PhysRevA.96.062134

[6] Lucas Kocia and Peter Love. Measurement contextuality and planck's constant. New Journal of Physics, 20 (7): 073020, Jul 2018. 10.1088/1367-2630/aacef2. URL https://doi.org/10.1088/1367-2630/aacef2.
https://doi.org/10.1088/1367-2630/aacef2

[7] E.J. Heller. The Semiclassical Way to Dynamics and Spectroscopy. Princeton University Press, 2018. ISBN 9781400890293. URL https://books.google.com/books?id=c59HDwAAQBAJ.
https://books.google.com/books?id=c59HDwAAQBAJ

[8] Robert W. Spekkens. Negativity and contextuality are equivalent notions of nonclassicality. Phys. Rev. Lett., 101: 020401, Jul 2008. 10.1103/PhysRevLett.101.020401. URL https://link.aps.org/doi/10.1103/PhysRevLett.101.020401.
https://doi.org/10.1103/PhysRevLett.101.020401

[9] Nicolas Delfosse, Philippe Allard Guerin, Jacob Bian, and Robert Raussendorf. Wigner function negativity and contextuality in quantum computation on rebits. Phys. Rev. X, 5: 021003, Apr 2015. 10.1103/PhysRevX.5.021003. URL https://link.aps.org/doi/10.1103/PhysRevX.5.021003.
https://doi.org/10.1103/PhysRevX.5.021003

[10] S. Abramsky, R. S. Barbosa, and S. Mansfield. Contextual Fraction as a Measure of Contextuality. Physical Review Letters, 119 (5): 050504, August 2017. 10.1103/PhysRevLett.119.050504.
https://doi.org/10.1103/PhysRevLett.119.050504

[11] Cristhiano Duarte and Barbara Amaral. Resource theory of contextuality for arbitrary prepare-and-measure experiments. Journal of Mathematical Physics, 59 (6): 062202, 2018. 10.1063/1.5018582.
https://doi.org/10.1063/1.5018582

[12] E. Wigner. On the quantum correction for thermodynamic equilibrium. Phys. Rev., 40: 749–759, Jun 1932. 10.1103/PhysRev.40.749. URL https://link.aps.org/doi/10.1103/PhysRev.40.749.
https://doi.org/10.1103/PhysRev.40.749

[13] William K Wootters. A wigner-function formulation of finite-state quantum mechanics. Annals of Physics, 176 (1): 1–21, 1987. ISSN 0003-4916. https://doi.org/10.1016/0003-4916(87)90176-X. URL https://www.sciencedirect.com/science/article/pii/000349168790176X.
https://doi.org/10.1016/0003-4916(87)90176-X
https://www.sciencedirect.com/science/article/pii/000349168790176X

[14] Christopher Ferrie and Joseph Emerson. Framed hilbert space: hanging the quasi-probability pictures of quantum theory. New Journal of Physics, 11 (6): 063040, jun 2009. 10.1088/1367-2630/11/6/063040. URL https://doi.org/10.1088/1367-2630/11/6/063040.
https://doi.org/10.1088/1367-2630/11/6/063040

[15] A. Mari and J. Eisert. Positive wigner functions render classical simulation of quantum computation efficient. Phys. Rev. Lett., 109: 230503, Dec 2012. 10.1103/PhysRevLett.109.230503. URL http://link.aps.org/doi/10.1103/PhysRevLett.109.230503.
https://doi.org/10.1103/PhysRevLett.109.230503

[16] 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, nov 2012. 10.1088/1367-2630/14/11/113011. URL https://doi.org/10.1088/1367-2630/14/11/113011.
https://doi.org/10.1088/1367-2630/14/11/113011

[17] Victor Veitch, Nathan Wiebe, Christopher Ferrie, and Joseph Emerson. Efficient simulation scheme for a class of quantum optics experiments with non-negative wigner representation. New Journal of Physics, 15 (1): 013037, jan 2013. 10.1088/1367-2630/15/1/013037. URL https://doi.org/10.1088/1367-2630/15/1/013037.
https://doi.org/10.1088/1367-2630/15/1/013037

[18] Eric Chitambar and Gilad Gour. Quantum resource theories. Rev. Mod. Phys., 91: 025001, Apr 2019. 10.1103/RevModPhys.91.025001. URL https://link.aps.org/doi/10.1103/RevModPhys.91.025001.
https://doi.org/10.1103/RevModPhys.91.025001

[19] Hakop Pashayan, Joel J. Wallman, and Stephen D. Bartlett. Estimating outcome probabilities of quantum circuits using quasiprobabilities. Phys. Rev. Lett., 115: 070501, Aug 2015. 10.1103/PhysRevLett.115.070501. URL https://link.aps.org/doi/10.1103/PhysRevLett.115.070501.
https://doi.org/10.1103/PhysRevLett.115.070501

[20] Alfredo M.Ozorio de Almeida. The weyl representation in classical and quantum mechanics. Physics Reports, 295 (6): 265–342, 1998. ISSN 0370-1573. https://doi.org/10.1016/S0370-1573(97)00070-7. URL https://www.sciencedirect.com/science/article/pii/S0370157397000707.
https://doi.org/10.1016/S0370-1573(97)00070-7
https://www.sciencedirect.com/science/article/pii/S0370157397000707

[21] A.M.F. Rivas and A.M. Ozorio de Almeida. The weyl representation on the torus. Annals of Physics, 276 (2): 223–256, 1999. ISSN 0003-4916. https://doi.org/10.1006/aphy.1999.5942. URL https://www.sciencedirect.com/science/article/pii/S0003491699959420.
https://doi.org/10.1006/aphy.1999.5942
https://www.sciencedirect.com/science/article/pii/S0003491699959420

[22] Lucas Kocia, Yifei Huang, and Peter Love. Semiclassical formulation of the gottesman-knill theorem and universal quantum computation. Phys. Rev. A, 96: 032331, Sep 2017b. 10.1103/PhysRevA.96.032331. URL https://link.aps.org/doi/10.1103/PhysRevA.96.032331.
https://doi.org/10.1103/PhysRevA.96.032331

[23] Quntao Zhuang, Peter W. Shor, and Jeffrey H. Shapiro. Resource theory of non-gaussian operations. Phys. Rev. A, 97: 052317, May 2018. 10.1103/PhysRevA.97.052317. URL https://link.aps.org/doi/10.1103/PhysRevA.97.052317.
https://doi.org/10.1103/PhysRevA.97.052317

[24] Ryuji Takagi and Quntao Zhuang. Convex resource theory of non-gaussianity. Phys. Rev. A, 97: 062337, Jun 2018. 10.1103/PhysRevA.97.062337. URL https://link.aps.org/doi/10.1103/PhysRevA.97.062337.
https://doi.org/10.1103/PhysRevA.97.062337

[25] Francesco Albarelli, Marco G. Genoni, Matteo G. A. Paris, and Alessandro Ferraro. Resource theory of quantum non-gaussianity and wigner negativity. Phys. Rev. A, 98: 052350, Nov 2018. 10.1103/PhysRevA.98.052350. URL https://link.aps.org/doi/10.1103/PhysRevA.98.052350.
https://doi.org/10.1103/PhysRevA.98.052350

[26] D.J. Tannor. Introduction to Quantum Mechanics: A Time-dependent Perspective. University Science Books, 2007. ISBN 9781891389238. URL https://books.google.com/books?id=t7m08j3Wi9YC.
https://books.google.com/books?id=t7m08j3Wi9YC

[27] M. Brack. Semiclassical Physics. CRC Press, 2018. ISBN 9780429982453. URL https://books.google.com/books?id=jVNPDwAAQBAJ.
https://books.google.com/books?id=jVNPDwAAQBAJ

[28] John H Van Vleck. The correspondence principle in the statistical interpretation of quantum mechanics. Proceedings of the National Academy of Sciences of the United States of America, 14 (2): 178, 1928. 10.1073/pnas.14.2.178.
https://doi.org/10.1073/pnas.14.2.178

[29] Cécile Morette. On the definition and approximation of feynman's path integrals. Phys. Rev., 81: 848–852, Mar 1951. 10.1103/PhysRev.81.848. URL https://link.aps.org/doi/10.1103/PhysRev.81.848.
https://doi.org/10.1103/PhysRev.81.848

[30] Martin C Gutzwiller. Phase-integral approximation in momentum space and the bound states of an atom. Journal of Mathematical Physics, 8 (10): 1979–2000, 1967. 10.1063/1.1705112.
https://doi.org/10.1063/1.1705112

[31] F.A. Berezin and M.S. Marinov. Particle spin dynamics as the grassmann variant of classical mechanics. Annals of Physics, 104 (2): 336–362, 1977. ISSN 0003-4916. https://doi.org/10.1016/0003-4916(77)90335-9. URL https://www.sciencedirect.com/science/article/pii/0003491677903359.
https://doi.org/10.1016/0003-4916(77)90335-9
https://www.sciencedirect.com/science/article/pii/0003491677903359

[32] Romuald Dąbrowski and Benji Fisher. A stationary phase formula for exponential sums over $ \mathbb z/p^m \mathbb z $ and applications to gl (3)-kloosterman sums. Acta Arithmetica, 80 (1): 1–48, 1997.

[33] Benji Fisher. The stationary-phase method for exponential sums with multiplicative characters. Journal of Number Theory, 96 (1): 201–224, 2002. ISSN 0022-314X. https://doi.org/10.1006/jnth.2002.2790. URL https://www.sciencedirect.com/science/article/pii/S0022314X02927903.
https://doi.org/10.1006/jnth.2002.2790
https://www.sciencedirect.com/science/article/pii/S0022314X02927903

[34] Nicolas Bourbaki. Elements of mathematics: Algebra ii, chapters 4–7. translated from the french by pl cohn and j. howie, 1990. IV, Sect. 1, No. 4. 10.1007/978-3-642-61698-3.
https://doi.org/10.1007/978-3-642-61698-3

[35] Earl T. Campbell, Hussain Anwar, and Dan E. Browne. Magic-state distillation in all prime dimensions using quantum reed-muller codes. Phys. Rev. X, 2: 041021, Dec 2012. 10.1103/PhysRevX.2.041021. URL https://link.aps.org/doi/10.1103/PhysRevX.2.041021.
https://doi.org/10.1103/PhysRevX.2.041021

[36] Mark Howard and Jiri Vala. Qudit versions of the qubit ${\pi}/8$ gate. Phys. Rev. A, 86: 022316, Aug 2012. 10.1103/PhysRevA.86.022316. URL https://link.aps.org/doi/10.1103/PhysRevA.86.022316.
https://doi.org/10.1103/PhysRevA.86.022316

[37] FWJ Olver. Chapter 9 airy and related functions. NIST Handbook of Mathematical Functions, pages 193–214, 2010.

[38] T. Pearcey. Xxxi. the structure of an electromagnetic field in the neighbourhood of a cusp of a caustic. The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science, 37 (268): 311–317, 1946. 10.1080/14786444608561335.
https://doi.org/10.1080/14786444608561335

[39] R. Gilmore. Catastrophe Theory for Scientists and Engineers. Dover books on advanced mathematics. Dover Publications, 1993. ISBN 9780486675398. URL https://books.google.com/books?id=HbuecPcWxJUC.
https://books.google.com/books?id=HbuecPcWxJUC

[40] C. Chester, B. Friedman, and F. Ursell. An extension of the method of steepest descents. Mathematical Proceedings of the Cambridge Philosophical Society, 53 (3): 599–611, 1957. 10.1017/S0305004100032655.
https://doi.org/10.1017/S0305004100032655

[41] David Gross. Hudson's theorem for finite-dimensional quantum systems. Journal of mathematical physics, 47 (12): 122107, 2006. 10.1063/1.2393152.
https://doi.org/10.1063/1.2393152

[42] P.O. Boykin, T. Mor, M. Pulver, V. Roychowdhury, and F. Vatan. On universal and fault-tolerant quantum computing: a novel basis and a new constructive proof of universality for shor's basis. In 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039), pages 486–494, 1999. 10.1109/SFFCS.1999.814621.
https://doi.org/10.1109/SFFCS.1999.814621

[43] Sergey Bravyi and David Gosset. Improved classical simulation of quantum circuits dominated by clifford gates. Phys. Rev. Lett., 116: 250501, Jun 2016. 10.1103/PhysRevLett.116.250501. URL https://link.aps.org/doi/10.1103/PhysRevLett.116.250501.
https://doi.org/10.1103/PhysRevLett.116.250501

[44] Mark Howard and Earl Campbell. Application of a resource theory for magic states to fault-tolerant quantum computing. Phys. Rev. Lett., 118: 090501, Mar 2017. 10.1103/PhysRevLett.118.090501. URL https://link.aps.org/doi/10.1103/PhysRevLett.118.090501.
https://doi.org/10.1103/PhysRevLett.118.090501

[45] 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, September 2019. ISSN 2521-327X. 10.22331/q-2019-09-02-181. URL https://doi.org/10.22331/q-2019-09-02-181.
https://doi.org/10.22331/q-2019-09-02-181

[46] Sergey Bravyi, Graeme Smith, and John A. Smolin. Trading classical and quantum computational resources. Phys. Rev. X, 6: 021043, Jun 2016. 10.1103/PhysRevX.6.021043. URL https://link.aps.org/doi/10.1103/PhysRevX.6.021043.
https://doi.org/10.1103/PhysRevX.6.021043

[47] Yifei Huang and Peter Love. Approximate stabilizer rank and improved weak simulation of clifford-dominated circuits for qudits. Phys. Rev. A, 99: 052307, May 2019. 10.1103/PhysRevA.99.052307. URL https://link.aps.org/doi/10.1103/PhysRevA.99.052307.
https://doi.org/10.1103/PhysRevA.99.052307

[48] Lucas Kocia and Peter Love. The non-disjoint ontic states of the grassmann ontological model, transformation contextuality, and the single qubit stabilizer subtheory. Journal of Physics A: Mathematical and Theoretical, 52 (9): 095303, Feb 2019. 10.1088/1751-8121/aafca7. URL https://doi.org/10.1088/1751-8121/aafca7.
https://doi.org/10.1088/1751-8121/aafca7

[49] Dennis S Bernstein. Matrix mathematics: Theory, facts, and formulas with application to linear systems theory, volume 41. Princeton university press Princeton, 2005.

Cited by

[1] Kaifeng Bu and Dax Enshan Koh, "Classical Simulation of Quantum Circuits by Half Gauss Sums", Communications in Mathematical Physics 390 2, 471 (2022).

[2] Lieuwe Vinkhuijzen, Tim Coopmans, David Elkouss, Vedran Dunjko, and Alfons Laarman, "LIMDD: A Decision Diagram for Simulation of Quantum Computing Including Stabilizer States", Quantum 7, 1108 (2023).

[3] Niklas Mueller, Andrey Tarasov, and Raju Venugopalan, "Deeply inelastic scattering structure functions on a hybrid quantum computer", Physical Review D 102 1, 016007 (2020).

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

[5] James R. Seddon, Bartosz Regula, Hakop Pashayan, Yingkai Ouyang, and Earl T. Campbell, "Quantifying quantum speedups: improved classical simulation from tighter magic monotones", arXiv:2002.06181, (2020).

[6] Lucas Kocia, "Improved Strong Simulation of Universal Quantum Circuits", arXiv:2012.11739, (2020).

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

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

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.