Source-linked AI summary
Average-case complexity versus approximate simulation of commuting quantum computations
Michael J. Bremner, Ashley Montanaro, Dan J. Shepherd
TL;DR
The paper connects IQP circuits to shifted gap-counting instances and develops hardness arguments for approximating polynomial gaps. It establishes GapP-completeness for multiplicative approximation and relates additive approximation of circuit probabilities to multiplicative approximation on a fraction of circuits.
Problem
The paper studies the complexity of approximating the squared gap of degree-3 polynomials over F2, including whether multiplicative approximation remains GapP-complete.
Method
The approach constructs shifted polynomial instances linked to IQP circuits and uses post-selection gadgets and approximation-recovery arguments.
Results
GapP-completeness holds for estimating |ngap(f)| within any multiplicative error ϵ < 1/2, while additive approximation of IQP probabilities yields multiplicative error 1/4 + o(1) on at least a p/2 fraction of circuits.
Takeaways & Limitations
The results provide hardness evidence for multiplicative gap estimation and connect additive-error simulation of IQP probabilities with average-case multiplicative approximation.
Abstract
from arXiv · showhide
We use the class of commuting quantum computations known as IQP (Instantaneous Quantum Polynomial time) to strengthen the conjecture that quantum computers are hard to simulate classically. We show that, if either of two plausible average-case hardness conjectures holds, then IQP computations are hard to simulate classically up to constant additive error. One conjecture relates to the hardness of estimating the complex-temperature partition function for random instances of the Ising model; the other concerns approximating the number of zeroes of random low-degree polynomials. We observe that both conjectures can be shown to be valid in the setting of worst-case complexity. We arrive at these conjectures by deriving spin-based generalisations of the Boson Sampling problem that avoid the so-called permanent anticoncentration conjecture.
Appendix A: The Ising model and IQP circuits
The appendix connects Ising-model partition functions to amplitudes of IQP circuits by encoding weighted interactions as commuting gates. This correspondence also specifies finite gate sets and weight choices for random instances.
- Ising model: The model assigns real weights wij to edges and vi to vertices of the complete graph.The spin variables range over z ∈ {−1, +1}n.
- Ising-to-IQP correspondence: The general Ising partition function Z = Tr[eiθHI] is proportional to an n-qubit IQP circuit amplitude.The construction uses edge and vertex weights on a complete graph and chooses ω = eiθ.
- Ising-to-IQP correspondence: IQP circuits built from eiθX⊗X and eiθX gates produce partition functions of the form Z(ω) = Tr[ωHI].Here ω is determined by the gate angle, while the edge and vertex weights record gate multiplicities.
Appendix B: Gaps of degree-3 polynomials
Degree-3 polynomials over F2 are encoded into IQP phases using Z, CZ, and CCZ gates. The resulting IQP amplitude is proportional to the polynomial’s gap.
- Polynomial-to-IQP encoding: An IQP circuit can express the gap of any degree-3 polynomial f : {0, 1}n → {0, 1} over F2.The polynomial coefficients αijk, βij, and γi specify the corresponding phase gates.
- Polynomial-to-IQP encoding: Z, CZ, and CCZ gates generate the phase (−1)f(x) by encoding cubic, quadratic, and linear terms of f.Applying these gates to each nonzero coefficient produces the diagonal circuit eCf, whose Hadamard transform Cf is IQP.
- Amplitude relation: The amplitude ⟨0|⊗nCf|0⟩⊗n equals gap(f)/2n.The gap is the number of zeros of f minus the number of ones.
Appendix C: The Hadamard gadget
The Hadamard gadget implements an intermediate Hadamard operation within an IQP circuit by adding an ancilla, commuting gates, measurement, and post-selection. It preserves multiplicative amplitude approximations but incurs a substantial post-selection cost.
- Gadget construction: An intermediate Hadamard is implemented by adding an ancilla, applying CZ and Hadamard operations, and post-selecting a zero measurement outcome.The protocol teleports the state to the ancilla while applying the Hadamard.
- Resource cost: Each intermediate Hadamard costs 1 qubit, 1 CZ gate, and 1 post-selection.Without post-selection, the procedure succeeds with probability 1/2 per gadget.
- Resource cost: For m intermediate Hadamards, the gadget succeeds without post-selection with probability 1/2m.This makes the procedure impractical as a physical implementation when m is large.
- Approximation preservation: The gadget preserves multiplicative approximations of circuit amplitudes when converting a circuit with intermediate Hadamards into IQP form.The transformed amplitude differs by a known factor depending on m.
Appendix D: Hardness of multiplicative approximations
The appendix establishes GapP-hardness for multiplicative approximation of degree-3 polynomial gaps and reduces general gap computation to this restricted form. A multiplicative amplitude estimator can then recover the gap through iterative shifting and refinement.
- Hardness result: Approximating |ngap(f)| within any multiplicative error ϵ < 1/2 is GapP-complete for degree-3 polynomials over F2.This hardness result underpins the later hardness of approximating the squared gap.
- Reduction: A general GapP computation is reduced to a shifted degree-3 gap using an auxiliary function with ngap(g) = −c.A control bit combines the original function and the auxiliary function to produce fc with a gap proportional to ngap(f) − c.
- Reduction: The resulting classical circuit is converted into an IQP amplitude through reversible computation and Hadamard-gadget constructions.The construction introduces ancillas and produces an amplitude proportional to the shifted gap.
- Iterative recovery: A multiplicative estimator for the shifted amplitude distinguishes whether a guessed c equals ngap(f).The estimator returns an approximation to |ngap(f) − c|, allowing the algorithm to certify correct guesses.
- Iterative recovery: Choosing between c + ed and c − ed reduces the distance to ngap(f) by a factor smaller than ϵ at each iteration.Because ngap(f) is an integer multiple of 2−n, O(n) steps suffice when the correct choice is made.
- Precision condition: The reduction truncates intermediate guesses to integer multiples of 2^(1−m), with m = O(n), introducing only negligible additional error.This discretization addresses guesses that are not directly representable at the chosen precision.
Appendix E: From additive to multiplicative error
This appendix uses Stockmeyer’s theorem to convert an additive-error classical sampler into multiplicative approximations of IQP output probabilities on many random circuits. Under anticoncentration and the stated sampling assumption, this yields an FBPP^NP approximation and supports classical-simulation hardness under the conjectures.
- Stockmeyer counting: Stockmeyer’s Counting Theorem gives an FBPP^NP multiplicative approximation for every #P function with oracle access to its underlying Boolean function.The approximation achieves multiplicative factor 1 + ϵ for ϵ = Ω(1/poly(n)).
- Sampler-to-counting reduction: If a random IQP circuit has output probability at least α·2^-n with probability p, an additive-error sampler can be applied under the corresponding ℓ1-error condition.The assumed additive error is ϵ = αp/8.
- Sampler-to-counting reduction: The resulting FBPP^NP algorithm approximates |⟨0|C|0⟩|^2 to multiplicative error 1/4 + o(1) on at least a p/2 fraction of circuits.The success probability and multiplicative guarantee follow by setting δ = p/2 in Lemma 4.
Appendix F: Proofs of anticoncentration bounds
The appendix proves anticoncentration bounds by averaging random phase coefficients and showing that most terms vanish unless their bit strings satisfy restrictive equality and congruence conditions. It applies this framework to random degree-3 polynomials and random-weight Ising partition functions, obtaining the bounds used for IQP circuits.
- General phase-sum lemma: Lemma 11 analyzes moments of phase sums with independently uniform coefficients modulo r and s.The coefficients are drawn uniformly from modular phase sets determined by ω and η.
- General phase-sum lemma: Averaging over random coefficients makes terms vanish unless z ≡ w + x − y mod s and at least two of w, x, y are equal.The vanishing follows from roots-of-unity identities, and the surviving assignments number at most 3·2^2n.
- Random degree-3 polynomials: For random degree-3 polynomials, the degree-≤2 coefficients are randomized while the higher-degree coefficients are fixed during the moment bound.The linear coefficients correspond to applying X gates to a uniformly random subset of qubits.
- Random degree-3 polynomials: The fourth moment of ngap(f) satisfies E_f[ngap(f)^4] ≤ 3·2^-2n when the degree-≤2 part is uniformly random.This is the stated anticoncentration lemma for the polynomial family.
- Random Ising instances: For the Ising model at ω = e^iπ/8, the partition function can be rewritten as an amplitude of an IQP circuit with random phase and X-gate choices.The circuit uses gates from {diag(1, 1, 1, i), diag(1, e^iπ/4)}.
- Random Ising instances: The Ising analysis preserves the relevant moment bound even when the interaction weights w_ij are sampled uniformly from {0, . . . , 3}.The passage states that this smaller weight set does not affect the analysis.