BQP-completeness of scattering in scalar quantum field theory

Stephen P. Jordan1,2, Hari Krovi3, Keith S. M. Lee4, and John Preskill5

1National Institute of Standards and Technology, Gaithersburg, MD, USA
2Joint Center for Quantum Information and Computer Science, University of Maryland, College Park, MD, USA
3Quantum Information Processing Group, Raytheon BBN Technologies, Cambridge, MA, USA
4Centre for Quantum Information & Quantum Control and Department of Physics, University of Toronto, Toronto, ON, Canada
5Institute for Quantum Information and Matter, California Institute of Technology, Pasadena, CA, USA

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


Recent work has shown that quantum computers can compute scattering probabilities in massive quantum field theories, with a run time that is polynomial in the number of particles, their energy, and the desired precision. Here we study a closely related quantum field-theoretical problem: estimating the vacuum-to-vacuum transition amplitude, in the presence of spacetime-dependent classical sources, for a massive scalar field theory in (1+1) dimensions. We show that this problem is BQP-hard; in other words, its solution enables one to solve any problem that is solvable in polynomial time by a quantum computer. Hence, the vacuum-to-vacuum amplitude cannot be accurately estimated by any efficient classical algorithm, even if the field theory is very weakly coupled, unless BQP=BPP. Furthermore, the corresponding decision problem can be solved by a quantum computer in a time scaling polynomially with the number of bits needed to specify the classical source fields, and this problem is therefore BQP-complete. Our construction can be regarded as an idealized architecture for a universal quantum computer in a laboratory system described by massive phi^4 theory coupled to classical spacetime-dependent sources.

► BibTeX data

► References

[1] Dorit Aharonov and Michael Ben-Or. Fault-tolerant quantum computation with constant error rate. SIAM Journal on Computing, 38 (4): 1207–1282, 2008. 10.1145/​258533.258579. arXiv:quant-ph/​9611025.

[2] Sanjeev Arora and Boaz Barak. Computational Complexity A Modern Approach. Cambridge University Press, 2009.

[3] J. E. Avron, R. Seiler, and L. G. Yaffe. Adiabatic theorems and applications to the quantum Hall effect. Communications in Mathematical Physics, 110: 33–49, 1987. 10.1007/​bf01209015.

[4] R. Baltin. Exact Green's function for the finite rectangular potential well in one dimension. Zeitschrift für Naturforschung, 40a: 379–382, 1984.

[5] Ning Bao, Patrick Hayden, Grant Salton, and Nathaniel Thomas. Universal quantum computation by scattering in the Fermi-Hubbard model. arXiv:1409.3585, 2014. 10.1088/​1367-2630/​17/​9/​093028.

[6] Jean-Luc Brylinski and Ranee Brylinsky. Universal quantum gates. In Mathematics of Quantum Computation, chapter 4. Chapman and Hall, 2002. arXiv:quant-ph/​0108062.

[7] Bei-Hua Chen, Yan Wu, and Qiong-Tau Xie. Heun functions and quasi-exactly solvable double-well potentials. Journal of Physics A, 46: 035301, 2012. 10.1088/​1751-8113/​46/​3/​035301.

[8] Andrew M. Childs. Universal computation by quantum walk. Physical Review Letters, 102: 180501, 2009. 10.1103/​physrevlett.102.180501. arXiv:0806.1972.

[9] Andrew M. Childs, David Gosset, and Zak Webb. Universal computation by multiparticle quantum walk. Science, 339: 791–794, 2013. 10.1126/​science.1229957. arXiv:1205.3782.

[10] Jonathan Dimock. The $P(\phi)_2$ green's functions: Asymptotic perturbation expansion. Helvetica Physica Acta, 49: 199–216, 1976.

[11] J.-P. Eckmann, H. Epstein, and J. Fröhlich. Asymptotic perturbation expansion for the $S$ matrix and the definition of time ordered functions in relativistic quantum field models. Annales de l'institut Henri Poincaré (A) Physique théorique, 25: 1–34, 1976.

[12] Alexander Elgart and George A. Hagedorn. A note on the switching adiabatic theorem. Journal of Mathematical Physics, 53: 102202, 2012. 10.1063/​1.4748968.

[13] Sabine Jansen, Ruedi Seiler, and Mary-Beth Ruskai. Bounds for the adiabatic approximation with applications to quantum computation. Journal of Mathematical Physics, 48: 102111, 2007. 10.1063/​1.2798382. arXiv:quant-ph/​0603175.

[14] Stephen P. Jordan, Keith S. M. Lee, and John Preskill. Quantum algorithms for quantum field theories. Science, 336 (6085): 1130–1133, 2012. 10.1126/​science.1217069. arXiv:1111.3633.

[15] Stephen P. Jordan, Keith S. M. Lee, and John Preskill. Quantum computation of scattering in scalar quantum field theories. Quantum Information and Computation, 14 (11/​12): 1014–1080, 2014a. arXiv:1112.4833.

[16] Stephen P. Jordan, Keith S. M. Lee, and John Preskill. Quantum algorithms for fermionic quantum field theories. arXiv:1404.7115, 2014b.

[17] E. Knill, R. Laflamme, and G. J. Milburn. A scheme for efficient quantum computation with linear optics. Nature, 409: 46–52, 2001. 10.1038/​35051009. arXiv:quant-ph/​0006088.

[18] Albert Messiah. Quantum Mechanics. Dover, 1999. (Reprint of the two-volume edition published by Wiley, 1961-1962).

[19] G. Nenciu. Linear adiabatic theory. Exponential estimates. Communications in Mathematical Physics, 152: 479–496, 1993. 10.1007/​978-94-017-0693-3_6.

[20] Michael Nielsen and Isaac Chuang. Quantum Computation and Quantum Information. Cambridge, 2000.

[21] F. W. J. Olver, D. W. Lozier, R. F. Boisvert, and C. W. Clark, editors. NIST Handbook of Mathematical Functions. Cambridge University Press, New York, NY, 2010.

[22] Konrad Osterwalder and Roland Sénéor. The scattering matrix is nontrivial for weakly coupled $P(\phi)_2$ models. Helvetica Physica Acta, 49: 525–536, 1976.

[23] G. Pöschl and E. Teller. Bemerkungen zur quantenmechanik des anharmonischen oszillators. Z. Physik, 83: 143–151, 1933. 10.1007/​bf01331132.

[24] N. Rosen and Philip M. Morse. On the vibrations of polyatomic molecules. Physical Review, 42: 210–217, 1932. 10.1103/​physrev.42.210.

[25] Masuo Suzuki. General decomposition theory of ordered exponentials. Proceedings of the Japan Academy, Series B, 69 (7): 161–166, 1993. 10.2183/​pjab.69.161.

[26] Nathan Wiebe, Dominic W. Berry, Peter Høyer, and Barry C. Sanders. Higher order decompositions of ordered operator exponentials. Journal of Physics A: Mathematical and Theoretical, 43 (6): 065203, 2010. 10.1088/​1751-8113/​43/​6/​065203. arXiv:0812.0562.

Cited by

[1] Mari Carmen Bañuls and Krzysztof Cichy, "Review on novel methods for lattice gauge theories", Reports on Progress in Physics 83 2, 024401 (2020).

[2] Longhan Wang, Yifan Sun, and Xiangdong Zhang, "Quantum deep transfer learning", New Journal of Physics 23 10, 103010 (2021).

[3] Erik J. Gustafson and Henry Lamm, "Toward quantum simulations ofZ2gauge theory without state preparation", Physical Review D 103 5, 054507 (2021).

[4] Andrew Blance and Michael Spannowsky, "Unsupervised event classification with graphs on classical and photonic quantum computers", Journal of High Energy Physics 2021 8, 170 (2021).

[5] N. Klco, E. F. Dumitrescu, A. J. McCaskey, T. D. Morris, R. C. Pooser, M. Sanz, E. Solano, P. Lougovski, and M. J. Savage, "Quantum-classical computation of Schwinger model dynamics using quantum computers", Physical Review A 98 3, 032331 (2018).

[6] Alex May, "Complexity and entanglement in non-local computation and holography", Quantum 6, 864 (2022).

[7] Mohsen Bagherimehrab, Yuval R. Sanders, Dominic W. Berry, Gavin K. Brennen, and Barry C. Sanders, "Nearly Optimal Quantum Algorithm for Generating the Ground State of a Free Quantum Field Theory", PRX Quantum 3 2, 020364 (2022).

[8] Benjamin Nachman, Miroslav Urbanek, Wibe A. de Jong, and Christian W. Bauer, "Unfolding quantum computer readout noise", npj Quantum Information 6 1, 84 (2020).

[9] Lior Cohen, Anthony J. Brady, Zichang Huang, Hongguang Liu, Dongxue Qu, Jonathan P. Dowling, and Muxin Han, "Efficient Simulation of Loop Quantum Gravity: A Scalable Linear-Optical Approach", Physical Review Letters 126 2, 020501 (2021).

[10] Michael Kreshchuk, Shaoyang Jia, William M. Kirby, Gary Goldstein, James P. Vary, and Peter J. Love, "Simulating hadronic physics on noisy intermediate-scale quantum devices using basis light-front quantization", Physical Review A 103 6, 062601 (2021).

[11] Marco Rigobello, Simone Notarnicola, Giuseppe Magnifico, and Simone Montangero, "Entanglement generation in(1+1)DQED scattering processes", Physical Review D 104 11, 114501 (2021).

[12] Marcela Carena, Erik J. Gustafson, Henry Lamm, Ying-Ying Li, and Wanqiang Liu, "Gauge theory couplings on anisotropic lattices", Physical Review D 106 11, 114504 (2022).

[13] Erik J. Gustafson, Henry Lamm, and Felicity Lovelace, "Primitive quantum gates for an SU(2) discrete subgroup: Binary octahedral", Physical Review D 109 5, 054503 (2024).

[14] Marcela Carena, Henry Lamm, Ying-Ying Li, and Wanqiang Liu, "Improved Hamiltonians for Quantum Simulations of Gauge Theories", Physical Review Letters 129 5, 051601 (2022).

[15] Pablo Arnault and Christopher Cedzich, "A single-particle framework for unitary lattice gauge theory in discrete time", New Journal of Physics 24 12, 123031 (2022).

[16] L. Cohen, A. J. Brady, Z. Huang, H. Liu, D. Qu, J. P. Dowling, and M. Han, Frontiers in Optics / Laser Science FTu6D.4 (2020) ISBN:978-1-943580-80-4.

[17] Natalie Klco and Martin J. Savage, "Fixed-point quantum circuits for quantum field theories", Physical Review A 102 5, 052422 (2020).

[18] Michael Kreshchuk, William M. Kirby, Gary Goldstein, Hugo Beauchemin, and Peter J. Love, "Quantum simulation of quantum field theory in the light-front formulation", Physical Review A 105 3, 032418 (2022).

[19] Caroline E. P. Robin and Martin J. Savage, "Quantum simulations in effective model spaces: Hamiltonian-learning variational quantum eigensolver using digital quantum computers and application to the Lipkin-Meshkov-Glick model", Physical Review C 108 2, 024313 (2023).

[20] Scott Lawrence and Yukari Yamauchi, "Normalizing flows and the real-time sign problem", Physical Review D 103 11, 114509 (2021).

[21] Rebecca Hicks, Christian W. Bauer, and Benjamin Nachman, "Readout rebalancing for near-term quantum computers", Physical Review A 103 2, 022407 (2021).

[22] Khadeejah Bepari, Sarah Malik, Michael Spannowsky, and Simon Williams, "Towards a quantum computing algorithm for helicity amplitudes and parton showers", Physical Review D 103 7, 076020 (2021).

[23] Andrei Alexandru, Paulo F. Bedaque, Ruairí Brett, and Henry Lamm, "Spectrum of digitized QCD: Glueballs in a S(1080) gauge theory", Physical Review D 105 11, 114508 (2022).

[24] Marc Illa and Martin J. Savage, "Basic elements for simulations of standard-model physics with quantum annealers: Multigrid and clock states", Physical Review A 106 5, 052605 (2022).

[25] Hanqing Liu and Shailesh Chandrasekharan, "Qubit Regularization and Qubit Embedding Algebras", Symmetry 14 2, 305 (2022).

[26] Yao Ji, Henry Lamm, and Shuchen Zhu, "Gluon digitization via character expansion for quantum computers", Physical Review D 107 11, 114503 (2023).

[27] Junyu Liu and Yue-Zhou Li, "Quantum simulation of cosmic inflation", Physical Review D 104 8, 086013 (2021).

[28] Aleksandr Raikov, SpringerBriefs in Applied Sciences and Technology 43 (2024) ISBN:978-981-97-1290-8.

[29] Erik J. Gustafson, Henry Lamm, and Judah Unmuth-Yockey, "Quantum mean estimation for lattice field theory", Physical Review D 107 11, 114511 (2023).

[30] Andrew Blance and Michael Spannowsky, "Quantum machine learning for particle physics using a variational quantum classifier", Journal of High Energy Physics 2021 2, 212 (2021).

[31] Henry Lamm, Scott Lawrence, and Yukari Yamauchi, "General methods for digital quantum simulation of gauge theories", Physical Review D 100 3, 034518 (2019).

[32] Natalie Klco, Alessandro Roggero, and Martin J Savage, "Standard model physics and the digital quantum revolution: thoughts about the interface", Reports on Progress in Physics 85 6, 064301 (2022).

[33] Wibe A. de Jong, Kyle Lee, James Mulligan, Mateusz Płoskoń, Felix Ringer, and Xiaojun Yao, "Quantum simulation of nonequilibrium dynamics and thermalization in the Schwinger model", Physical Review D 106 5, 054508 (2022).

[34] Natalie Klco and Martin J. Savage, "Systematically localizable operators for quantum simulations of quantum field theories", Physical Review A 102 1, 012619 (2020).

[35] M. Sohaib Alam, Stuart Hadfield, Henry Lamm, and Andy C. Y. Li, "Primitive quantum gates for dihedral gauge theories", Physical Review D 105 11, 114501 (2022).

[36] João Barata, Xiaojian Du, Meijian Li, Wenyang Qian, and Carlos A. Salgado, "Medium induced jet broadening in a quantum computer", Physical Review D 106 7, 074013 (2022).

[37] Natalie Klco and Martin J. Savage, "Minimally entangled state preparation of localized wave functions on quantum computers", Physical Review A 102 1, 012612 (2020).

[38] Kyle Lee, James Mulligan, Felix Ringer, and Xiaojun Yao, "Liouvillian dynamics of the open Schwinger model: String breaking and kinetic dissipation in a thermal medium", Physical Review D 108 9, 094518 (2023).

[39] Ron Belyansky, Seth Whitsitt, Niklas Mueller, Ali Fahimniya, Elizabeth R. Bennewitz, Zohreh Davoudi, and Alexey V. Gorshkov, "High-Energy Collision of Quarks and Mesons in the Schwinger Model: From Tensor Networks to Circuit QED", Physical Review Letters 132 9, 091903 (2024).

[40] Erik J. Gustafson, Henry Lamm, Felicity Lovelace, and Damian Musk, "Primitive quantum gates for an SU(2) discrete subgroup: Binary tetrahedral", Physical Review D 106 11, 114501 (2022).

[41] Bin Xu and Wei Xue, "( 3+1 )-dimensional Schwinger pair production with quantum computers", Physical Review D 106 11, 116007 (2022).

[42] Henry Lamm, Scott Lawrence, and Yukari Yamauchi, "Parton physics on a quantum computer", Physical Review Research 2 1, 013272 (2020).

[43] Clement Charles, Erik J. Gustafson, Elizabeth Hardt, Florian Herren, Norman Hogan, Henry Lamm, Sara Starecheski, Ruth S. Van de Water, and Michael L. Wagman, "Simulating Z2 lattice gauge theory on a quantum computer", Physical Review E 109 1, 015307 (2024).

[44] S. Hasibul Hassan Chowdhury, Talal Ahmed Chowdhury, Salah Nasri, Omar Ibna Nazim, and Shaikh Saad, "Quantum simulation of quantum mechanical system with spatial noncommutativity", International Journal of Quantum Information 21 06, 2350028 (2023).

[45] Junyu Liu and Yuan Xin, "Quantum simulation of quantum field theories as quantum chemistry", Journal of High Energy Physics 2020 12, 11 (2020).

[46] Thomas D. Cohen, Henry Lamm, Scott Lawrence, and Yukari Yamauchi, "Quantum algorithms for transport coefficients in gauge theories", Physical Review D 104 9, 094514 (2021).

[47] Marcela Carena, Henry Lamm, Ying-Ying Li, and Wanqiang Liu, "Lattice renormalization of quantum simulations", Physical Review D 104 9, 094519 (2021).

[48] Kazuki Ikeda, "Universal computation with quantum fields", Quantum Information Processing 19 9, 331 (2020).

[49] Andre He, Benjamin Nachman, Wibe A. de Jong, and Christian W. Bauer, "Zero-noise extrapolation for quantum-gate error mitigation with identity insertions", Physical Review A 102 1, 012426 (2020).

[50] Hrant Gharibyan, Masanori Hanada, Masazumi Honda, and Junyu Liu, "Toward simulating superstring/M-theory on a quantum computer", Journal of High Energy Physics 2021 7, 140 (2021).

[51] G. Magnifico, D. Vodola, E. Ercolessi, S. P. Kumar, M. Müller, and A. Bermudez, "ZN gauge theories coupled to topological fermions: QED2 with a quantum mechanical θ angle", Physical Review B 100 11, 115152 (2019).

[52] Jaeho Choi, Seunghyeok Oh, and Joongheon Kim, "Energy-Efficient Cluster Head Selection via Quantum Approximate Optimization", Electronics 9 10, 1669 (2020).

[53] Steven Abel, Nicholas Chancellor, and Michael Spannowsky, "Quantum computing for quantum tunneling", Physical Review D 103 1, 016008 (2021).

[54] Natalie Klco and Martin J. Savage, "Digitization of scalar fields for quantum computing", Physical Review A 99 5, 052335 (2019).

[55] Natalie Klco and Martin J. Savage, "Geometric quantum information structure in quantum fields and their lattice simulation", Physical Review D 103 6, 065007 (2021).

[56] Robert A. Jefferson and Robert C. Myers, "Circuit complexity in quantum field theory", Journal of High Energy Physics 2017 10, 107 (2017).

[57] Alexander M. Dalzell, Sam McArdle, Mario Berta, Przemyslaw Bienias, Chi-Fang Chen, András Gilyén, Connor T. Hann, Michael J. Kastoryano, Emil T. Khabiboulline, Aleksander Kubica, Grant Salton, Samson Wang, and Fernando G. S. L. Brandão, "Quantum algorithms: A survey of applications and end-to-end complexities", arXiv:2310.03011, (2023).

[58] Lucas Hackl and Robert C. Myers, "Circuit complexity for free fermions", Journal of High Energy Physics 2018 7, 139 (2018).

[59] Arpan Bhattacharyya, Arvind Shekar, and Aninda Sinha, "Circuit complexity in interacting QFTs and RG flows", Journal of High Energy Physics 2018 10, 140 (2018).

[60] Tibra Ali, Arpan Bhattacharyya, S. Shajidul Haque, Eugene H. Kim, and Nathan Moynihan, "Time evolution of complexity: a critique of three methods", Journal of High Energy Physics 2019 4, 87 (2019).

[61] J. Preskill, "Simulating quantum field theory with a quantum computer", The 36th Annual International Symposium on Lattice Field Theory. 22-28 July 24 (2018).

[62] Roland C. Farrell, Marc Illa, Anthony N. Ciavarella, and Martin J. Savage, "Quantum Simulations of Hadron Dynamics in the Schwinger Model using 112 Qubits", arXiv:2401.08044, (2024).

[63] Siddhartha Harmalkar, Henry Lamm, and Scott Lawrence, "Quantum Simulation of Field Theories Without State Preparation", arXiv:2001.11490, (2020).

[64] Steven Abel, Michael Spannowsky, and Simon Williams, "With a Little Help from Photons: Quantum Field Theory on Continuous-Variable Quantum Computers", arXiv:2403.10619, (2024).

[65] Simon Catterall, Roni Harnik, Veronika E. Hubeny, Christian W. Bauer, Asher Berlin, Zohreh Davoudi, Thomas Faulkner, Thomas Hartman, Matthew Headrick, Yonatan F. Kahn, Henry Lamm, Yannick Meurice, Surjeet Rajendran, Mukund Rangamani, and Brian Swingle, "Report of the Snowmass 2021 Theory Frontier Topical Group on Quantum Information Science", arXiv:2209.14839, (2022).

[66] A. Bermudez, G. Aarts, and M. Müller, "Quantum Sensors for the Generating Functional of Interacting Quantum Field Theories", Physical Review X 7 4, 041012 (2017).

[67] Ali Hamed Moosavian, James R. Garrison, and Stephen P. Jordan, "Site-by-site quantum state preparation algorithm for preparing vacua of fermionic lattice field theories", arXiv:1911.03505, (2019).

[68] Xiaojun Yao, "Quantum Simulation of Light-Front QCD for Jet Quenching in Nuclear Environments", arXiv:2205.07902, (2022).

[69] Marcela Carena, Henry Lamm, Ying-Ying Li, and Wanqiang Liu, "Quantum error thresholds for gauge-redundant digitizations of lattice field theories", arXiv:2402.16780, (2024).

[70] Raghav G. Jha, "Notes on Quantum Computation and Information", arXiv:2301.09679, (2023).

[71] Christopher F. Kane, Niladri Gomes, and Michael Kreshchuk, "Nearly-optimal state preparation for quantum simulations of lattice gauge theories", arXiv:2310.13757, (2023).

[72] Andre He, Benjamin Nachman, Wibe A. de Jong, and Christian W. Bauer, "Resource Efficient Zero Noise Extrapolation with Identity Insertions", arXiv:2003.04941, (2020).

[73] Ning Bao and Junyu Liu, "Quantum algorithms for conformal bootstrap", Nuclear Physics B 946, 114702 (2019).

[74] Reyhaneh Aghaei Saem and Ali Hamed Moosavian, "Classical Algorithm for the Mean Value problem over Short-Time Hamiltonian Evolutions", arXiv:2301.11420, (2023).

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