Source-linked AI summary
Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
Michael J. Bremner, Richard Jozsa, Dan J. Shepherd
TL;DR
The paper asks whether sampling outputs of commuting-gate quantum computations can be efficiently reproduced classically, despite the absence of unconditional proofs of quantum advantage. It defines IQP and post-IQP, proves that post-IQP equals PP, and uses this to show that sufficiently accurate classical sampling would collapse the polynomial hierarchy to its third level. It also identifies restricted output regimes that can be classically simulated efficiently.
Problem
The paper addresses the lack of unconditional evidence that quantum computations outperform classical computation and seeks evidence based on sampling tasks implementable with simple quantum circuits.
Method
The paper studies uniform IQP circuit families, defines post-IQP, and relates post-selected IQP computations to classical complexity classes.
Results
Post-IQP equals PP, and efficient classical sampling of uniform IQP output distributions within the stated multiplicative-error regime would collapse the polynomial hierarchy to its third level.
Takeaways & Limitations
IQP output sampling provides evidence of classical hardness using commuting-gate circuits, while measurements on only O(log n) output lines can be classically efficiently sampled.
Takeaways & Limitations
The independence of bounded-error tolerance is established for post-IQP, but remains unknown for IQP without post-selection because majority vote may not be realizable with commuting gates.
Abstract
from arXiv · showhide
We consider quantum computations comprising only commuting gates, known as IQP computations, and provide compelling evidence that the task of sampling their output probability distributions is unlikely to be achievable by any efficient classical means. More specifically we introduce the class post-IQP of languages decided with bounded error by uniform families of IQP circuits with post-selection, and prove first that post-IQP equals the classical class PP. Using this result we show that if the output distributions of uniform IQP circuit families could be classically efficiently sampled, even up to 41% multiplicative error in the probabilities, then the infinite tower of classical complexity classes known as the polynomial hierarchy, would collapse to its third level. We mention some further results on the classical simulation properties of IQP circuit families, in particular showing that if the output distribution results from measurements on only O(log n) lines then it may in fact be classically efficiently sampled.
1 Introduction
The paper addresses the lack of unconditional evidence for quantum computational advantage by studying simple commuting-gate computations whose efficient classical simulation would have implausible complexity consequences.
- The paper develops sampling tasks based on restricted quantum computational elements that are expected to be classically hard yet especially simple to implement.This approach targets both theoretical evidence of hardness and experimental implementability.
- IQP circuits use only commuting gates and offer theoretical simplicity alongside relevance to fault-tolerant superconductor and semiconductor qubit implementations.The paper notes that commuting-gate circuits are simpler to implement fault-tolerantly than fully universal gate sets.
- Efficient classical simulation of these IQP circuits, even with generous multiplicative error, would collapse the polynomial hierarchy to its third level.Such a collapse is regarded as highly implausible, although it would not imply P = NP.
- The paper introduces post-IQP and shows that post-selection boosts polynomial-time IQP computations to the classical complexity class PP.This parallels the known effect of post-selection on universal polynomial-time quantum computation, which boosts BQP to PP.
- The main simulation result concerns weak classical sampling of output distributions to suitable multiplicative accuracy, rather than computing output probabilities directly.This is substantially weaker than strong simulation, which requires efficient computation of marginal or total probabilities to exponential precision.
2 Preliminary notions
This section defines computational tasks, uniform circuit families, IQP circuits, post-selection, and classical simulation notions used later. It also identifies key scope boundaries, including circuit-size conventions, output-line growth, and the theoretical status of post-selection and error tolerance.
- 2.1 Computational tasks: A computational task maps bit-string inputs to outputs, while sampling tasks ask classical algorithms to sample from circuit-defined probability distributions.For an n-bit input w, a circuit C_w may define an output distribution P_w on m-bit strings.
- 2.2 Uniform families of circuits: A uniform circuit family is a poly(n)-time computable mapping w → C_w that specifies the gates, inputs, outputs, and any auxiliary registers.This condition implies each C_w has poly(n) size and acts on at most poly(n) lines.
- 2.3 IQP circuits: IQP circuits use gates diagonal in the X basis, start in |0⟩ states, and end with computational-basis measurements on specified output lines.An equivalent representation uses Hadamards at the beginning and end of each line, with diagonal Z-basis gates between them.
- 2.3 IQP circuits: The paper’s IQP gate convention gives each gate’s diagonal entries and acted-on lines, so a poly(n)-size description limits each gate to O(log n) lines.Other conventions can permit gates acting on O(n) lines, so the representation convention matters.
- 2.4 Post-selected circuits: Post-selection conditions the output distribution on obtaining 00...0 from a designated, disjoint register whose event has nonzero probability.Because the event may be exponentially unlikely, post-selection is principally a theoretical resource rather than a feasible implementation.
- 2.4 Post-selected circuits: Post-IQP consists of languages decided with bounded error by uniform post-selected IQP circuits, and its definition is independent of the chosen error tolerance.The corresponding independence is stated for post-BPP and post-BQP, while it remains unknown for IQP circuits without post-selection.
3 Main results
The paper shows that post-selection raises IQP's power to PP and that sufficiently accurate classical sampling would collapse PH to its third level, while O(log n)-output IQP circuits remain exactly simulable.
- The power of IQP with post-selection: PP equals post-IQP, so post-selection boosts the computational power of IQP to the classical class PP.The proof reduces post-selected quantum computations to IQP circuits using Hadamard gadgets that replace intermediate H gates with CZ gates, post-selection, and endpoint H gates.
- Classical simulation and collapse of PH: Multiplicative approximation is essential because conditional probabilities are quotients whose positive denominators could diverge catastrophically under additive or total-variation error.The simulation bounds transfer through the numerator and denominator probabilities used for post-selection.
- Classical simulation and collapse of PH: 1 ≤ c < 2 multiplicative-error weak simulation of uniform IQP output distributions would imply PH = ∆3.The argument combines the simulation assumption with the post-IQP result and Toda's theorem.
- Restricted output registers: O(log n) output lines suffice for exact polynomial-time classical weak simulation of any uniform IQP family.The complementary register is sampled uniformly, leaving an O(log n)-qubit state that can be strongly simulated by direct calculation.
- Restricted output registers: The computational power of post-selected IQP circuits depends crucially on the size of the post-selection register.The paper contrasts the restricted-output exact simulation result with the hardness consequence for general output distributions.
4 Some further remarks
The paper’s proof strategy extends beyond IQP circuits: any circuit class whose post-selected version reaches PP inherits the same classical-simulation hardness consequence.
- The methods behind the principal results apply to any circuit class for which post-selection boosts computational power to PP.
- Constant-depth quantum circuits provide an example: post-BQNC0 = PP, so the polynomial-hierarchy collapse conclusion extends from IQP to QNC0.