Source-linked AI summary
Adaptive Quantum Computation, Constant Depth Quantum Circuits and Arthur-Merlin Games
Barbara M. Terhal, David P. DiVincenzo
TL;DR
The paper asks whether constant-depth quantum computations using two-qubit gates can resist efficient classical simulation. It constructs nonadaptive versions of adaptive computations and shows that efficient high-accuracy simulation would imply BQP ⊆AM, while stronger simulation assumptions yield broader complexity collapses.
Problem
It is unclear whether constant-depth quantum circuits with two-qubit gates can be simulated classically with high accuracy.
Source: §1 · pp. 1–2Method
The paper replaces adaptive measurement outcomes with guessed outcomes, creating nonadaptive circuits whose intermediate measurements can be deferred and whose successful cases are identifiable.
Source: §1 · p. 1, §4.1 · p. 10Results
Efficient simulation with accuracy ǫ < 1/3 for the relevant nonadaptive circuits would imply BQP ⊆AM.
Source: §4.1 · p. 10Takeaways & Limitations
The results provide evidence that constant-depth nonadaptive quantum circuits may perform non-classical computation that is difficult to simulate classically.
Source: §1 · p. 2, §5 · p. 11Whether BQP ⊆AM is unlikely is not known, and whether BPPGCnad exceeds BPP remains open.
Source: §4.1 · p. 11, §5 · p. 11
Abstract
from arXiv · showhide
We present evidence that there exist quantum computations that can be carried out in constant depth, using 2-qubit gates, that cannot be simulated classically with high accuracy. We prove that if one can simulate these circuits classically efficiently then the complexity class BQP is contained in AM.
1 Introduction
The paper develops nonadaptive quantum computation by replacing measurement-dependent gates with guessed outcomes, enabling constant-depth circuits whose classical simulation would have major complexity-theoretic consequences.
1 Introduction
- Nonadaptive computation replaces adaptive measurement outcomes with a guessed bit string, allowing intermediate measurements to be deferred and revealing when the guess is correct.The successful case is the rare event that every guessed outcome matches the actual measurement outcomes.Source: §1 · p. 1
1.1 Previous work
- Earlier work established that adaptive measurements do not increase computational power, while adaptive computation may use a smaller and physically simpler gate set.The paper distinguishes computational power from implementation convenience.Source: §1 · p. 1
1 Introduction
- Constant-depth, fan-in-two quantum circuits arise from the nonadaptive form of the Gottesman–Chuang adaptive construction, despite the model’s apparently limited depth.The resulting circuit uses a constant number of time steps and at most two-qubit gates.Source: §1 · p. 2, §1.1 · p. 2
- If density computation can efficiently follow any computational pathway, then BPP = BQP and the polynomial hierarchy collapses.This stronger simulation notion is defined as density computation.Source: §1 · p. 2
- If classical simulation can follow the rare successful pathways, it would simulate polynomial-time quantum computation and imply BQP ⊆AM.Merlin can steer Arthur’s simulation toward successful cases, yielding the Arthur–Merlin containment.Source: §1 · p. 2
2 Definitions
The paper defines quantum registers, gates, measurements, circuits, and BQP/AM, then formalizes adaptive computation and its nonadaptive guessed-outcome variant.
2.1 Basic Concepts
- Standard measurements output bits and reduce the register, while Bell measurement is a particularly important two-qubit measurement.Measurements on different qubits commute and can be treated as a composite measurement.Source: §2.1 · p. 3
- A quantum circuit acts on a w-qubit register through one- or two-qubit gates and ends with standard-basis measurement producing up to w′ classical output bits.The circuit has depth d, initialized state |init⟩, and a remaining unmeasured quantum state after output.Source: §2.1 · p. 3
- BQP consists of uniformly generated polynomial-size quantum circuits deciding membership with acceptance probability at least 2/3 and nonmembership with probability at most 1/3.AM similarly uses Arthur’s randomness and Merlin’s response in a polynomial-time verification procedure.Source: §2.1 · p. 4
2.2 Adaptive and nonadaptive quantum computation
- Adaptive computation chooses each subsequent circuit as a function of prior measurement outcomes and the input, with polynomially bounded rounds, depths, widths, and efficiently computable control functions.This dependence is the defining distinction from ordinary composed circuits.Source: §2.2 · p. 4
- Nonadaptive computation associates each adaptive computation with a circuit for every guess string g, replacing measured outcomes by guessed values.Because no gate depends on actual intermediate outcomes, measurements can be moved to the end and the circuit becomes ordinary.Source: §2.2 · pp. 4–5
3 Classical Simulations
The paper formalizes approximate and density-based classical simulations, then relates nonadaptive simulations to adaptive quantum computations. Efficient simulation of suitable nonadaptive circuits would imply strong classical complexity consequences, including PH = BPP = BQP.
Classical simulation definitions
- The approximate simulation S_ε(QC) requires a classical circuit whose output frequencies approximate every quantum output probability within multiplicative error ε.The simulator is uniformly generated and may have polynomial input width and depth.Source: §3 · p. 5
- Efficient density computation evaluates conditional outcome probabilities for constant-size measurement blocks, enabling exact sampling of quantum-circuit outputs.The procedure samples measurements sequentially, conditioning each outcome on previously fixed outcomes.Source: §3 · pp. 5–6
- An efficient density computation immediately provides an efficient simulation with accuracy parameter ε = 0.Sequentially sampling all measurement blocks uses at most w max_i c_i conditional probabilities for circuit width w.Source: §3 · pp. 5–6
Adaptive and nonadaptive simulations
- If every nonadaptive circuit QC_nad(g) has an efficient density computation, then adaptive circuits QCad can be simulated with ε = 0.The proof progressively fixes measurement outcomes as guess bits and treats each resulting stage sequence as a nonadaptive circuit.Source: §3 · p. 6
- For fixed-logical-circuit families, efficient density computation of QC_nad,fix(g) transfers to QCad,fix because intermediate-outcome distributions are identical.This applies when the logical circuit does not depend on intermediate measurement outcomes.Source: §3 · pp. 6–7
Complexity consequences
- If the relevant fixed adaptive family is universal, efficient density computation of its nonadaptive counterpart implies PH = BPP = BQP.The argument uses adaptive simulation to calculate quantum acceptance probabilities and derives coC=P ⊆ BPP, yielding the collapse.Source: §3 · p. 7
4 Constant-Depth Quantum Circuits
The paper converts Gottesman–Chuang adaptive teleportation circuits into nonadaptive circuits of depth at most four, while preserving quantum computational power only on rare flagged outcomes. It then shows that efficient classical simulation of these circuits would imply unlikely complexity-class containments.
4 Constant-Depth Quantum Circuits
- Gottesman–Chuang replaces each CNOT with teleportation using an offline-prepared entangled four-qubit state and Bell measurements.The Bell-measurement outcomes determine subsequent one-qubit corrections in the adaptive construction.Source: §4 · pp. 7–8, Figure 1 · p. 8
- GCad circuits restrict component computations to one-qubit gates, use |ΨC⟩ and |0⟩ inputs, and perform two Bell measurements for each intermediate operation.This defines the circuit family whose nonadaptive versions are analyzed.Source: §4 · p. 7
- Any corresponding nonadaptive GCnad circuit has depth at most four and uses only one- and two-qubit gates from the all-zero initial state.Bell measurements are deferred, entangled resource states are prepared in parallel, and basis changes and final measurements occupy later layers.Source: §4 · pp. 8–9
- If efficient density computation exists for all depth-four circuits, then PH = BPP = BQP.The result follows by applying the preceding simulation consequences to the constant-depth construction.Source: §4 · p. 9
- Depth three remains efficiently density-simulatable because each measurement can be processed using states involving at most four qubits.A fourth layer breaks this proof strategy because Bell-basis measurements can leave larger entangled states without efficient classical representations.Source: §4 · p. 9
4.1 General Simulations
- Although GCnad computation succeeds with exponentially small probability, a flag identifies successful outcomes corresponding to the guessed Bell-measurement results.This rare-success structure allows the model to encode ordinary polynomial-time quantum computations.Source: §4.1 · pp. 9–10
- An efficient simulation of G(g = 0) with accuracy ǫ < 1/3 would imply BQP ⊆AM.The proof maps accepting versus rejecting quantum computations to distinguishing whether efficiently testable simulator coin settings form a large or small set.Source: §4.1 · p. 10
- The proposed BQP ⊆AM consequence is regarded as rather unlikely, although the paper states that this is not definitively known.The argument uses approximate set-size estimation, a problem solvable as a two-round AM game.Source: §4.1 · pp. 10–11
5 Conclusion
The paper presents evidence that nonadaptive constant-depth quantum circuits may be hard to simulate classically, while identifying open questions about their computational power. The result applies beyond the Gottesman–Chuang model to corresponding nonadaptive versions of adaptive schemes including KLM.
5 Conclusion
- Whether BPPGCnad has more computational power than BPP remains an open question, despite evidence that its multiple-bit output is hard to generate classically.Source: §5 · p. 11
- A problem in BPPGCnad that is not known to be in BPP would be experimentally interesting because constant-depth circuits should be easier to build than universal quantum computers.Source: §5 · p. 11
- Theorem 1 applies to any adaptive quantum computation model and its corresponding nonadaptive version, including the KLM scheme.This suggests that nonadaptive KLM computation using linear optics on Fock states followed by photon counting may exhibit non-classical computational behavior.Source: §5 · p. 11
A Appendix: Bell outcomes
The appendix analyzes Bell measurements in the Gottesman–Chuang circuit by using the uncorrelated structure of the measured qubits. It concludes that every Bell-state outcome, and therefore every output bit pair, occurs uniformly.
A Appendix: Bell outcomes
- Each Bell measurement acts on uncorrelated qubits, including one qubit from the state ΨC, so the measured two-qubit density matrix has the stated product form.Source: A Appendix: Bell outcomes · p. 12
- The probability of any Bell measurement outcome is computed from ⟨Φ+|ρAB|Φ+⟩ and the analogous expressions for the other Bell states.Source: A Appendix: Bell outcomes · p. 13
- p = 1/4: the probability of outputting any bit pair is uniform across the four Bell outcomes.Source: A Appendix: Bell outcomes · p. 13
B Appendix: Approximate Set Size
The appendix amplifies a BIG/SMALL set-size gap by taking repeated simulations and then uses a hash-based Arthur–Merlin game to distinguish the resulting cases. With suitable amplification, the game succeeds with exponentially small error.
B Appendix: Approximate Set Size
- The initial BIG/SMALL ratio is amplified to d/8 by taking u = log(d/8)/log((2−2ǫ)/(1+ǫ)) runs and forming S′ as their Cartesian product.Source: B Appendix: Approximate Set Size · p. 13
- The repetition parameter is chosen as p = ⌊8 log BIG⌋, with p approximately u(n − k), before the hash-based protocol begins.Source: B Appendix: Approximate Set Size · p. 13
- Arthur sends p + 1 random hash functions and l^2 random target strings to Merlin, who must return t ∈ S′ whose hash matches one target.The hash functions may use Carter–Wegman hashing, represented by random Boolean matrices.Source: B Appendix: Approximate Set Size · p. 13
- The amplified game accepts with probability at least 1 − 2^−l/8 when |S′| ≥ BIG, but with probability at most l^3/d when |S′| ≤ SMALL.The amplification can make both failure probabilities exponentially small in |x|, while requiring only polynomially many repetitions for exponentially large d.Source: B Appendix: Approximate Set Size · p. 13