BQP-completeness of Scattering in Scalar Quantum Field Theory
Stephen P. Jordan, Keith S. Lee, John Preskill
Recent work has shown that quantum computers can in polynomial time compute scattering probabilities in massive quantum field theories. One can translate this task into a corresponding formal problem in computational complexity theory. Here, we establish that this is a BQP-hard problem. In other words, by solving it, one can solve any problem that can be solved in polynomial time by a quantum computer. Hence, these scattering probabilities cannot be obtained by any classical polynomial-time algorithm unless BQP=BPP. Our construction works by encoding a quantum circuit into a spacetime-varying source term in the quantum field theorys Lagrangian.