PaperlayerView exact revision on arXiv

Source-linked AI summary

BQP-completeness of Scattering in Scalar Quantum Field Theory

Stephen P. Jordan, Hari Krovi, Keith S. M. Lee, John Preskill

arXiv:1703.00454v4quant-ph

TL;DR

The paper asks whether estimating vacuum-to-vacuum transitions in sourced massive scalar field theory is computationally hard. It encodes quantum computation in the source-driven field dynamics and proves the decision problem BQP-complete, subject to the construction's stated scope and assumptions.

  • Problem

    The paper asks whether estimating vacuum-to-vacuum transitions in massive scalar field theory with spacetime-dependent classical sources is computationally hard.

    Source: §1 · p. 2

  • Method

    The construction encodes a quantum circuit in sourced field dynamics, with source functions supplied as the problem input.

    Source: §1 · p. 2, §2.1 · p. 4

  • Results

    The vacuum-to-vacuum decision problem is BQP-hard and, via a Hadamard-test algorithm, belongs to BQP, making it BQP-complete.

    Source: §1 · pp. 2–3

  • Takeaways & Limitations

    The construction provides an idealized architecture for universal quantum computation in a laboratory system described by massive φ⁴ theory coupled to classical sources.

    Source: §2.1 · pp. 4–5

    The gate construction is geometrically local in one dimension, so distant two-qubit gates require swaps that increase circuit depth by O(n).

    Source: §4.2 · p. 27

Abstract

from arXiv · show

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.

1 Introduction

The paper studies whether a vacuum-to-vacuum transition probability in (1+1)-dimensional φ⁴ theory with spacetime-dependent sources is computationally hard. It proves BQP-hardness and shows that the decision problem is also in BQP, making it BQP-complete.

1 Introduction

  • Earlier work [14] [15] [16] showed efficient quantum computation of transition probabilities in interacting theories including φ⁴; this paper establishes hardness for a related source-driven vacuum transition.The source terms at worst cause modest efficiency penalties for the Suzuki-Trotter formulae used in [14] [15].Source: §1 · pp. 2–3
  • For φ4 theory with spacetime-dependent sources, the promised decision of whether the vacuum-to-vacuum probability at time T is greater than 2/3 or smaller than 1/3 is BQP-hard and in BQP.Source: §1 · pp. 2–3
  • The problem starts in the vacuum with both sources off, varies the sources according to their input bit strings, then asks whether the final state remains the vacuum.The source functions J1(t, x) and J2(t, x) are the classical inputs.Source: §1 · pp. 2–3
  • A polynomial-time classical estimate of the vacuum probability to error less than 1/6 would decide the BQP-hard problem, implying BPP = BQP.The paper therefore rules out such an efficient classical solution unless BPP = BQP.Source: §1 · pp. 2–3

2 Overview and Discussion

The overview motivates a physically natural hardness problem and sketches a field-theory architecture that encodes a universal quantum circuit. Its feasibility relies on controlled source design and perturbative assumptions, while the resulting gate layout is one-dimensional and local.

2.1 Choice of problem

  • The construction makes a vacuum initial state part of the hardness result, requiring particle creation during the dynamics and strengthening the result beyond bound-particle initial states.The paper notes that this choice makes the construction more complicated because it requires a state-preparation scheme and fidelity analysis.Source: §2.1 · p. 5

2.2 Proof sketch

  • The architecture encodes each qubit in a double well, uses well motion for single- and two-qubit gates, and uses oscillatory J1 to create and later annihilate particles.The source J2 sets the potential wells; the source-driven dynamics implement the circuit between preparation and annihilation.Source: §2.2 · pp. 6–7
  • For coupling λ = O(1/G), the construction uses perturbative gate analysis and gives a classical source description of size eO(nG²D), preserving polynomial reduction size.Here G is the number of gates, D the circuit depth, and n the number of qubits.Source: §2.2 · p. 7

2.3 Conditions for successful simulation

  • Successful simulation requires conditions on particle preparation, source and interaction scales, adiabatic evolution, gate duration, and lattice accuracy for BQP membership.The BQP-completeness argument also requires polynomially many runs to control statistical error.Source: §2.3 · p. 8

2.4 Validity of perturbation theory

  • The analysis assumes perturbative approximations remain reliable with time-varying sources, because analogous asymptotic results for perturbation theory with sources are unavailable.The paper notes that perturbation theory without sources is asymptotic, which does not guarantee that adding higher-order terms always reduces error.Source: §2.4 · pp. 8–9

3 State Preparation

The section builds qubits in double wells and uses adiabatic passage to create one particle per well. It analyzes how to suppress unwanted transitions while keeping preparation errors small.

3 State Preparation

  • The protocol turns on a static double-well potential, then uses an oscillatory source to create one particle per well in a logical state.The ground and first excited states can encode the logical states.Source: §3 · p. 9

3.1 Adiabatic Passage

  • Adiabatic passage sweeps the drive frequency across resonance, allowing high-fidelity excited-state preparation with only approximate knowledge of the transition frequency and matrix element.This avoids the precise frequency and Rabi-rate knowledge required by the Rabi-oscillation approach.Source: §3 · p. 10, §3.1 · p. 11

3.1.1 Effective Hamiltonian in the Rotating Frame

  • As detuning sweeps through zero slowly enough, the lower eigenstate evolves from the uncoupled ground state to the excited state.The minimal gap is Ω, and successful passage requires suppressing transitions across it.Source: §3.1.1 · p. 12, Figure 1 · p. 12

3.1.2 Rotating-Wave Approximation

  • The rotating-wave approximation drops counter-rotating terms that oscillate rapidly in the rotating frame and nearly average away.The analysis bounds the error introduced by neglecting these terms.Source: §3.1.2 · pp. 12–13

3.1.3 Conditions for Successful Adiabatic Passage

  • Successful passage requires the initial and target states to align with the endpoint eigenstates, an adiabatic sweep, and a duration compatible with both adiabaticity and the rotating-wave approximation.The analysis also requires controlling transitions from the two-level system to other states.Source: §3.1.3 · p. 14

3.2 Free Theory with Sources

  • In the non-interacting theory, particle production follows a Poisson distribution, so creation of more than one particle cannot be adequately suppressed.Source: §3.2 · p. 15

3.3 Interacting Theory with Sources

  • Interactions shift two-particle energies by O(λ), moving unwanted transitions outside the driven frequency band; a spatial profile can also null a resonant bound-to-continuum matrix element.The most dangerous unwanted diagram combines three source insertions at frequency ω into one particle at 3ω.Source: §3.3 · pp. 16–17, Figure 2 · p. 17
  • Parallel preparation takes time of order n^8; for deeper circuits, λ ∼ 1/G is more stringent and makes T correspondingly larger.The λ scaling also ensures the entangling gate can be computed classically and efficiently.Source: §3.3 · p. 18

4 Quantum Gates

Directly bringing wells together makes tunneling more likely than interaction, so the encoded qubit states can leak out of the computational subspace. The paper instead builds universal gates using adiabatic operations in a larger six-state space, with a gate duration that scales with circuit size.

4 Quantum Gates

  • Direct well approach fails because tunneling can move particles out of the computational subspace, and no regime makes interaction parametrically stronger than tunneling.The construction instead uses operations in a larger space to implement gates on the encoded subspace.Source: §4 · p. 18

4.2 Gate Universality

  • The gate construction uses the six configurations of two particles in four wells and varies the wells slowly to suppress leakage from that space.Smooth well variations can limit leakage to ϵ at a time cost τ = poly(log 1/ϵ).Source: §4 · p. 18, §4.2 · pp. 22–23

4.1 Gate Times

  • In φ⁴ theory, the interaction includes an O(λ) repulsive contact term and an O(λ²) attractive exchange term that falls off faster with well separation.The exchange contribution is further suppressed by exp(−m_effℓ).Source: §4.1 · pp. 20–21
  • For weak coupling, the interaction energy is parametrically smaller than tunneling, so tunneling cannot be ignored during an entangling gate.The interaction energy scales as (λ/m²) × W², while the tunneling matrix element scales as W.Source: §4.1 · p. 20

4.2 Gate Universality

  • Varying well depths implements logical Z rotations, while lowering the barrier implements logical X rotations; together they generate arbitrary single-qubit gates.The operation durations and strengths can be adjusted to meet the adiabaticity constraint while achieving the desired rotation angles.Source: §4.2 · pp. 23–24, Figure 4 · p. 24
  • The two-qubit operation preserves the encoded four-dimensional subspace and is entangling for generic well shapes and trajectories.The construction tunes the tunneling rotation angle to an integer multiple of 2π; the resulting gate is entangling unless ei(α+β) = 1.Source: §4.2 · pp. 26–27
  • With λ = O(1/G), the simulation time is O(G²) per gate and O(G²D) for a circuit of depth D.The stated circuit runtime excludes state preparation.Source: §4.2 · p. 27
  • The gates are local in one dimension, so implementing a gate between distant qubits requires swaps that increase circuit depth by O(n).The swaps can be approximated with polylogarithmic overhead.Source: §4.2 · p. 27

5 Measurements and BQP-completeness

The paper establishes BQP-completeness for vacuum-to-vacuum transition probabilities by reducing quantum-circuit amplitudes to the field-theory problem and giving an efficient quantum estimation procedure. The Hadamard-test approach uses controlled time evolution, while an alternative readout uses a particle detector.

5 Measurements and BQP-completeness

  • The BQP-hardness reduction constructs sources J1(t, x) and J2(t, x) so the vacuum-to-vacuum amplitude approximates a quantum circuit’s all-zero-to-all-zero amplitude.Consequently, estimating the corresponding transition probability to sufficiently small constant error is BQP-hard.Source: §5 · p. 27
  • The Hadamard test estimates the real and imaginary parts of ⟨ψ|U|ψ⟩ by preparing a control qubit, applying controlled-U, and measuring the control.For the real part, O(1/ϵ^2) measurements suffice to estimate within ϵ.Source: §5 · p. 28, Figure 7 · p. 29
  • The decision problem is BQP-complete: a quantum circuit can be encoded so its all-zero transition amplitude is approximated by the vacuum-to-vacuum amplitude, and the Hadamard-test algorithm estimates it efficiently.The circuit-amplitude threshold problem is BQP-complete, and the paper’s reduction makes estimating the corresponding field-theory probability BQP-hard.Source: §5 · pp. 27–28
  • An alternative omits final particle annihilation and uses phase estimation to simulate a localized particle detector, avoiding controlled versions of each gate but requiring more complicated final measurement.The Hadamard-test scheme instead requires only a single-qubit readout, at the cost of replacing each gate with its controlled version.Source: §5 · p. 28

A Dynamics within an Adiabatic Subspace

The appendix derives an approximate dynamics within an isolated adiabatic subspace. A spectral gap bounds leakage, while a technical discrete, nondegenerate-spectrum assumption limits the derivation’s generality.

A Dynamics within an Adiabatic Subspace

  • Changing to the instantaneous eigenbasis yields Schrödinger-like dynamics for the eigenstate coefficients, with a Hermitian matrix governing their evolution.The analysis adopts a phase convention for the eigenvectors before deriving the coefficient dynamics.Source: A Dynamics within an Adiabatic Subspace · pp. 31–33
  • For an isolated group of eigenstates separated by a sufficiently large energy gap, adiabatic evolution keeps an initially contained state in that subspace up to corrections of order ϵ.The appendix adapts standard adiabatic arguments to bound escape from the isolated subspace and describe its internal dynamics.Source: A Dynamics within an Adiabatic Subspace · pp. 30, 33
  • Neglecting amplitudes outside the isolated subspace gives a self-contained approximate evolution there, with the state approximation accurate to corrections of order ϵ.The omitted component has magnitude at most ϵ under the stated adiabatic assumption.Source: A Dynamics within an Adiabatic Subspace · pp. 33–34
  • The derivation assumes a fully discrete, nondegenerate spectrum, which the authors say suffices because the relevant low-lying spectrum in Sec. 4.2 is discrete and nondegenerate.This assumption is not generally true of quantum field theories.Source: A Dynamics within an Adiabatic Subspace · p. 33

B Fourier Transform of the Source

This appendix analyzes the Fourier transform of the source, using expansions to characterize its low-frequency, transition, and tail behavior. It also gives conditions under which truncating the expansions has a bounded error.

B Fourier Transform of the Source

  • The time-envelope function is normalized so that its squared integral is O(1), independent of T, before its Fourier transform is considered.The transform’s behavior is then analyzed for large but finite T with B fixed.Source: B Fourier Transform of the Source · pp. 34–35
  • For real arguments satisfying the stated bounds, truncating the series after m terms incurs an error with the same sign as, and no larger magnitude than, the mth term.The bounds apply to the series expansions introduced for the Fresnel integrals.Source: B Fourier Transform of the Source · p. 35
  • The source Fourier transform has separately characterized low-frequency, transition-region, and tail behavior, with the tail magnitude zero up to specified corrections.The appendix points to explicit expansions for the corrections in each region.Source: B Fourier Transform of the Source · p. 37

C Example X Gate

The example implements an X rotation by varying a double-well barrier. A chosen ramp produces a phase of π, which acts as an X gate when left- and right-well occupation encode the logical states.

C Example X Gate

  • The appendix gives a concrete example of implementing a π X rotation by varying the height of a double-well barrier.The example uses a specified potential and a time-dependent barrier profile.Source: C Example X Gate · p. 37
  • A Gevrey-class barrier variation invokes an adiabatic theorem with exponential convergence to perfect adiabaticity as the variation becomes slower.The ground and first excited states have opposite parity, making the adiabatic-frame Hamiltonian’s off-diagonal elements zero in this example.Source: C Example X Gate · p. 38
  • For g = 0.01, β = 50, and τ = 96.1602, the barrier variation yields φ = π and an X gate when left- and right-well occupation represent logical zero and one.In the double-well eigenbasis, the operation is a Z gate.Source: C Example X Gate · p. 38

D Example Z Gate

The section analyzes a Z gate using an exactly solvable double-well potential. It relates well-depth changes and slower evolution to the gate phase and errors, then bounds the effect of finite well separation.

D Example Z Gate

  • The gate analysis uses an exactly solvable two-well example built from special cases of hyperbolic Pöschl–Teller and Rosen–Morse potentials; for λ > 1, each well is attractive.Source: D Example Z Gate · pp. 38–39
  • Increasing the logical-one well depth induces a Pauli Z rotation, with θ = π giving a standard Z gate.Source: D Example Z Gate · p. 39
  • Slowing the process by increasing τ makes diabatic error amplitudes vanish; maintaining a fixed target phase as τ increases requires decreasing β.Source: D Example Z Gate · p. 39
  • Finite-separation corrections are of the order of the wells’ ground-state overlap, and the approximation improves exponentially as their separation increases.The stated exponential behavior follows from the localized well and the decay of its ground-state wavefunction in the outer region.Source: D Example Z Gate · p. 39
Loading 1703.00454v4…