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

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

[2] Ning Bao and Junyu Liu, "Quantum algorithms for conformal bootstrap", arXiv:1811.05675 (2018).

[3] Tibra Ali, Arpan Bhattacharyya, S. Shajidul Haque, Eugene H. Kim, and Nathan Moynihan, "Time Evolution of Complexity: A Critique of Three Methods", arXiv:1810.02734 (2018).

[4] John Preskill, "Simulating quantum field theory with a quantum computer", arXiv:1811.10085 (2018).

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

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

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

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

The above citations are from Crossref's cited-by service (last updated 2019-02-20 19:33:18) and SAO/NASA ADS (last updated 2019-02-20 19:33:19). The list may be incomplete as not all publishers provide suitable and complete citation data.