Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy

By Michael J. Bremner, Richard Jozsa, D. Shepherd. Proceedings of the Royal Society A, 2010

489 citations recorded by the source corpus.

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, either exactly in total variation distance or even approximately up to 41 per cent 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 lines then it may, in fact, be classically efficiently sampled.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/60cffbdecfc9e6d41ae498b69c93d0c0878fca8b

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Quantum circuits and low-degree polynomials over F2 (2016, background): “So, for all x ∈ { 0 , 1 } (cid:96) , (cid:104) x | C (cid:48) | x (cid:105) = ( − 1) f C ( x ) , and hence We can remove any Hadamard gates in C (cid:48) using a trick from [10].”
On the complexity and verification of quantum random circuit sampling (2018, background): “For example, the ability to sample one particular output x of a quantum circuit with the correct probability D ( x ) is known to be hard for classical computers, under standard complexity assumptions (for example, refs 10,20–23 ).”
Circuit-centric quantum classifiers (2018, background): “[3] Michael J Bremner, Richard Jozsa, and Dan J Shepherd.”
Quantum computing and the entanglement frontier (2012, background): “25 Here all the gates executed by our quantum computer are mutually commuting, simultaneously diagonal in the standard Z basis.”
Average-case complexity versus approximate simulation of commuting quantum computations (2015, methodology): “However, if we allow the unphysical resource of postselection, these Hadamard gates can effectively be implemented [3], allowing IQP circuit amplitudes 〈y|C|x〉 to express any quantum circuit amplitude (up to a known constant).”
From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz (2017, methodology): “and the feasibility of classically simulating the measurement of log(n)-qubits in a QAOA circuit by adapting results for IQP circuits [45].”
Complexity-Theoretic Foundations of Quantum Supremacy Experiments (2016, background): “s once again to underscore the advantage of sampling problems over decision problems for quantum supremacy experiments. Given the extremely close connection between Fourier Sampling and the IQP model [BJS10], our result also provides some evidence that classically simulating an n-qubit IQP circuit, ”
Quantum computational supremacy (2017, background): “Such circuits are both potentially easier to implement than general quantum circuits, and have appealing theoretical properties which make them simpler to analyse.(11,19) However, this very simplicity may make them easier to simulate classically too.”
Strawberry Fields: A Software Platform for Photonic Quantum Computing (2018, background): “Efficient classical sampling of the resulting probability distribution H⊗N UH⊗N |0〉 — even approximately [13] or in the presence of noise [84]— has been shown to be #P-hard, and would result in the collapse of the polynomial hierarchy to the third level [12, 85].”
Quantum Supremacy through the Quantum Approximate Optimization Algorithm (2016, methodology): “What was shown in [11] is that if there exists an efficient classical algorithm that can produce strings z with a distribution close to qIQP(z) then the PH collapses at the third level.”
Random Quantum Circuits (2022, methodology): “A model with “instantaneous quantum polynomial time” gates (262) shows another transition, described by mean-field percolation on a time-slice (72).”
The computational complexity of linear optics (2010, methodology): “especially thank Leonid Gurvits for explaining his polynomial formalism and algorithmic results, and Mick Bremner and Richard Jozsa for discussions of their work [8].”
Logical quantum processor based on reconfigurable atom arrays (2023, methodology): “IQP circuits are defined as initializing |+⟩ ⊗ n on n qubits, applying a diagonal entangling unitary such as those composed by {CCZ, CZ, Z} and then measuring in the X basis 20,98 .”