



01856nas a2200169   4500008004100000245006600041210006500107260001500172300000700187490000600194520134900200100002401549700001601573700002201589700001901611856005601630       2018                        eng d00aBQP-completeness of Scattering in Scalar Quantum Field Theory0 aBQPcompleteness of Scattering in Scalar Quantum Field Theory  c2018/01/08  a440 v23 a<p><span style="font-family: &quot;Lucida Grande&quot;, helvetica, arial, verdana, sans-serif; font-size: 14.4px;">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.</span></p>1 aJordan, Stephen, P.1 aKrovi, Hari1 aLee, Keith, S. M.1 aPreskill, John  uhttps://quantum-journal.org/papers/q-2018-01-08-44/