{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T05:50:29Z","timestamp":1778219429220,"version":"3.51.4"},"reference-count":26,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2018,1,8]],"date-time":"2018-01-08T00:00:00Z","timestamp":1515369600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.22331\/q-2018-01-08-44","type":"journal-article","created":{"date-parts":[[2018,1,8]],"date-time":"2018-01-08T13:27:32Z","timestamp":1515418052000},"page":"44","source":"Crossref","is-referenced-by-count":87,"title":["BQP-completeness of scattering in scalar quantum field theory"],"prefix":"10.22331","volume":"2","author":[{"given":"Stephen P.","family":"Jordan","sequence":"first","affiliation":[{"name":"National Institute of Standards and Technology, Gaithersburg, MD, USA"},{"name":"Joint Center for Quantum Information and Computer Science, University of Maryland, College Park, MD, USA"}]},{"given":"Hari","family":"Krovi","sequence":"additional","affiliation":[{"name":"Quantum Information Processing Group, Raytheon BBN Technologies, Cambridge, MA, USA"}]},{"given":"Keith S. M.","family":"Lee","sequence":"additional","affiliation":[{"name":"Centre for Quantum Information & Quantum Control and Department of Physics, University of Toronto, Toronto, ON, Canada"}]},{"given":"John","family":"Preskill","sequence":"additional","affiliation":[{"name":"Institute for Quantum Information and Matter, California Institute of Technology, Pasadena, CA, USA"}]}],"member":"9598","published-online":{"date-parts":[[2018,1,8]]},"reference":[{"key":"1","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1145\/258533.258579"},{"key":"2","doi-asserted-by":"crossref","unstructured":"Sanjeev Arora and Boaz Barak. Computational Complexity A Modern Approach. Cambridge University Press, 2009.","DOI":"10.1017\/CBO9780511804090"},{"key":"3","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1007\/bf01209015"},{"key":"4","doi-asserted-by":"crossref","unstructured":"R. Baltin. Exact Green's function for the finite rectangular potential well in one dimension. Zeitschrift f\u00fcr Naturforschung, 40a: 379-382, 1984.","DOI":"10.1515\/zna-1985-0411"},{"key":"5","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1088\/1367-2630\/17\/9\/093028"},{"key":"6","doi-asserted-by":"crossref","unstructured":"Jean-Luc Brylinski and Ranee Brylinsky. Universal quantum gates. In Mathematics of Quantum Computation, chapter 4. Chapman and Hall, 2002. arXiv:quant-ph\/0108062.","DOI":"10.1201\/9781420035377.pt2"},{"key":"7","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1088\/1751-8113\/46\/3\/035301"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Andrew M. Childs. Universal computation by quantum walk. Physical Review Letters, 102: 180501, 2009. 10.1103\/physrevlett.102.180501. arXiv:0806.1972.","DOI":"10.1103\/physrevlett.102.180501"},{"key":"9","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1126\/science.1229957"},{"key":"10","unstructured":"Jonathan Dimock. The $P(\\phi)_2$ green's functions: Asymptotic perturbation expansion. Helvetica Physica Acta, 49: 199-216, 1976."},{"key":"11","unstructured":"J.-P. Eckmann, H. Epstein, and J. Fr\u00f6hlich. 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\u00e9 (A) Physique th\u00e9orique, 25: 1-34, 1976."},{"key":"12","doi-asserted-by":"publisher","unstructured":"Alexander Elgart and George A. Hagedorn. A note on the switching adiabatic theorem. Journal of Mathematical Physics, 53: 102202, 2012. 10.1063\/1.4748968.","DOI":"10.1063\/1.4748968"},{"key":"13","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1063\/1.2798382"},{"key":"14","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1126\/science.1217069"},{"key":"15","doi-asserted-by":"crossref","unstructured":"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.","DOI":"10.26421\/QIC14.11-12-8"},{"key":"16","unstructured":"Stephen P. Jordan, Keith S. M. Lee, and John Preskill. Quantum algorithms for fermionic quantum field theories. arXiv:1404.7115, 2014b."},{"key":"17","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1038\/35051009"},{"key":"18","unstructured":"Albert Messiah. Quantum Mechanics. Dover, 1999. (Reprint of the two-volume edition published by Wiley, 1961-1962)."},{"key":"19","doi-asserted-by":"publisher","unstructured":"G. Nenciu. Linear adiabatic theory. Exponential estimates. Communications in Mathematical Physics, 152: 479-496, 1993. 10.1007\/978-94-017-0693-3_6.","DOI":"10.1007\/978-94-017-0693-3_6"},{"key":"20","unstructured":"Michael Nielsen and Isaac Chuang. Quantum Computation and Quantum Information. Cambridge, 2000."},{"key":"21","unstructured":"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."},{"key":"22","unstructured":"Konrad Osterwalder and Roland S\u00e9n\u00e9or. The scattering matrix is nontrivial for weakly coupled $P(\\phi)_2$ models. Helvetica Physica Acta, 49: 525-536, 1976."},{"key":"23","doi-asserted-by":"publisher","unstructured":"G. P\u00f6schl and E. Teller. Bemerkungen zur quantenmechanik des anharmonischen oszillators. Z. Physik, 83: 143-151, 1933. 10.1007\/bf01331132.","DOI":"10.1007\/bf01331132"},{"key":"24","doi-asserted-by":"publisher","unstructured":"N. Rosen and Philip M. Morse. On the vibrations of polyatomic molecules. Physical Review, 42: 210-217, 1932. 10.1103\/physrev.42.210.","DOI":"10.1103\/physrev.42.210"},{"key":"25","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.2183\/pjab.69.161"},{"key":"26","doi-asserted-by":"publisher","unstructured":"Nathan Wiebe, Dominic W. Berry, Peter H\u00f8yer, 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.","DOI":"10.1088\/1751-8113\/43\/6\/065203"}],"container-title":["Quantum"],"original-title":[],"language":"en","deposited":{"date-parts":[[2022,8,11]],"date-time":"2022-08-11T23:57:00Z","timestamp":1660262220000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2018-01-08-44\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1,8]]},"references-count":26,"URL":"https:\/\/doi.org\/10.22331\/q-2018-01-08-44","relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1,8]]},"article-number":"44"}}