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

Abstract

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.

13 pages

References in corpus (7)

• Quantum Teleportation is a Universal Computational Primitive
• Cluster-state quantum computation
• Instantaneous Quantum Computation
• Fault-Tolerant Computing With Biased-Noise Superconducting Qubits
• Matchgate and space-bounded quantum computations are equivalent
• Binary Matroids and Quantum Probability Distributions
• Quantum Complexity: restrictions on algorithms and architectures

Cited by in corpus (194)

• Characterizing Quantum Supremacy in Near-Term Devices
• Circuit-centric quantum classifiers
• Quantum Computational Supremacy
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Photonic Boson Sampling in a Tunable Circuit
• Strawberry Fields: A Software Platform for Photonic Quantum Computing
• The Expressive Power of Parameterized Quantum Circuits
• Average-case complexity versus approximate simulation of commuting quantum computations
• Quantum Supremacy and the Complexity of Random Circuit Sampling
• Achieving quantum supremacy with sparse and noisy commuting quantum computations
• Hyper-optimized tensor network contraction
• Quantum Sampling Problems, BosonSampling and Quantum Supremacy
• Verification of quantum computation: An overview of existing approaches
• Efficient classical simulation of random shallow 2D quantum circuits
• Computational advantage of quantum random sampling
• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• Approximate unitary $t$-designs by short random quantum circuits using nearest-neighbor and long-range gates
• Power of Pausing: Advancing Understanding of Thermalization in Experimental Quantum Annealers
• Contextuality and Wigner function negativity in qubit quantum computation
• Quantum Computation Based on Quantum Adiabatic Bifurcations of Kerr-Nonlinear Parametric Oscillators
• Efficient Quantum Walk on a Quantum Processor
• Efficient classical simulation of noisy random quantum circuits in one dimension
• Robust Extraction of Tomographic Information via Randomized Benchmarking
• On the hardness of classically simulating the one clean qubit model
• Architectures for quantum simulation showing a quantum speedup
• Quantum Supremacy for Simulating A Translation-Invariant Ising Spin Model
• Quantum Chaos is Quantum
• A Linear-Optical Proof that the Permanent is #P-Hard
• Regimes of classical simulability for noisy Gaussian boson sampling
• Verification of Many-Qubit States
• General-purpose quantum circuit simulator with Projected Entangled-Pair States and the quantum supremacy frontier
• Classical simulation of photonic linear optics with lost particles
• How many qubits are needed for quantum computational supremacy?
• Subtleties in the trainability of quantum machine learning models
• Computational power of one- and two-dimensional dual-unitary quantum circuits
• Verified measurement-based quantum computing with hypergraph states
• Resources for bosonic quantum computational advantage
• Continuous-Variable Instantaneous Quantum Computing is hard to sample
• Impossibility of Classically Simulating One-Clean-Qubit Computation
• Efficient classical simulation of matchgate circuits with generalized inputs and measurements
• Anticoncentration theorems for schemes showing a quantum speedup
• Compact Gaussian quantum computation by multi-pixel homodyne detection
• Boson sampling with Gaussian measurements
• Probing post-measurement entanglement without post-selection
• Boundaries of quantum supremacy via random circuit sampling
• Classical simulation of lossy boson sampling using matrix product operators
• From estimation of quantum probabilities to simulation of quantum circuits
• Quantum Commuting Circuits and Complexity of Ising Partition Functions
• Dynamical phase transitions in sampling complexity
• A hidden variable model for universal quantum computation with magic states on qubits
• Hardness of classically sampling one clean qubit model with constant total variation distance error
• Efficient classical simulation of Clifford circuits with nonstabilizer input states
• Simulating Noisy Quantum Circuits with Matrix Product Density Operators
• Generative Quantum Learning of Joint Probability Distribution Functions
• The Complexity of Bipartite Gaussian Boson Sampling
• Classical simulation of boson sampling based on graph structure
• Fermion Sampling: a robust quantum computational advantage scheme using fermionic linear optics and magic input states
• Application-Motivated, Holistic Benchmarking of a Full Quantum Computing Stack
• Limitations of Linear Cross-Entropy as a Measure for Quantum Advantage
• Quantum advantage of unitary Clifford circuits with magic state inputs
• Generation of Universal Linear Optics by Any Beamsplitter
• A Grover-search Based Quantum Learning Scheme for Classification
• Quantum Entropy and Central Limit Theorem
• Entanglement in a dephasing model and many-body localization
• Learning Nonlinear Input-Output Maps with Dissipative Quantum Systems
• Noise and the frontier of quantum supremacy
• Optimised resource construction for verifiable quantum computation
• Generating a state $t$-design by diagonal quantum circuits
• Optimising Matrix Product State Simulations of Shor's Algorithm
• Quantum computed moments correction to variational estimates
• The computational landscape of general physical theories
• Measurement-based classical computation
• Diagonal quantum circuits: their computational power and applications
• Structural risk minimization for quantum linear classifiers
• Efficient verification of Boson Sampling
• State preparation by shallow circuits using feed forward
• Extending matchgates into universal quantum computation
• Noise in BosonSampling and the threshold of efficient classical simulatability
• Diagonal unitary entangling gates and contradiagonal quantum states
• A single $T$-gate makes distribution learning hard
• Simulating Noisy Variational Quantum Algorithms: A Polynomial Approach
• Quantum machine learning with adaptive linear optics
• Quantum circuits and low-degree polynomials over F_2
• Phase-random states: ensembles of states with fixed amplitudes and uniformly distributed phases in a fixed basis
• Verifying commuting quantum computations via fidelity estimation of weighted graph states
• Sampling generalized cat states with linear optics is probably hard
• Energy-Consumption Advantage of Quantum Computation
• Quantum supremacy in constant-time measurement-based computation: A unified architecture for sampling and verification
• A general framework for phase and interference
• The complexity of simulating constant-depth BosonSampling
• Verifiable Quantum Advantage without Structure
• Complexity phase diagram for interacting and long-range bosonic Hamiltonians
• Quantum AI simulator using a hybrid CPU-FPGA approach
• Entanglement-free certification of entangling gates
• Implementing quantum algorithms on temporal photonic cluster states
• From Many-Particle Interference to Correlation Spectroscopy
• Efficient Algorithms for Approximating Quantum Partition Functions
• A quantum algorithm for additive approximation of Ising partition functions
• Magic Resource Can Enhance the Quantum Capacity of Channels
• Computational power of matchgates with supplementary resources
• Effects of quantum resources on the statistical complexity of quantum circuits
• Non-Unitary Quantum Computation in the Ground Space of Local Hamiltonians
• Efficient simulation of Gottesman-Kitaev-Preskill states with Gaussian circuits
• Quantum Schur Sampling Circuits can be Strongly Simulated
• Simulating noisy variational quantum eigensolver with local noise models
• Exact calculation of phonon effects on spin squeezing
• Error mitigation on a near-term quantum photonic device
• Power of one non-clean qubit
• Stabilizer Tensor Networks with Magic State Injection
• Mitigating errors by quantum verification and post-selection
• Geometries for universal quantum computation with matchgates
• Diagonal-unitary 2-designs and their implementations by quantum circuits
• A robust W-state encoding for linear quantum optics
• Preparation and verification of tensor network states
• Nonadaptive fault-tolerant verification of quantum supremacy with noise
• On the sampling complexity of open quantum systems
• The principle of majorization: application to random quantum circuits
• Correcting finite squeezing errors in continuous-variable cluster states
• Quantum Extensive Form Games
• Low Depth Quantum Circuits for Ising Models
• On the Need for Large Quantum Depth
• Classical verification of quantum circuits containing few basis changes
• Exact sampling hardness of Ising spin models
• Information Theoretically Secure Hypothesis Test for Temporally Unstructured Quantum Computation (Extended Abstract)
• Information Theoretically Secure Hypothesis Test for Temporally Unstructured Quantum Computation
• Optimal Hadamard gate count for Clifford$+T$ synthesis of Pauli rotations sequences
• Merlin-Arthur with efficient quantum Merlin and quantum supremacy for the second level of the Fourier hierarchy
• Exact and Efficient Simulation of Concordant Computation
• Quantum supremacy and quantum phase transitions
• Robust sparse IQP sampling in constant depth
• Fault-tolerant conversion between adjacent Reed-Muller quantum codes based on gauge fixing
• Ancilla-driven instantaneous quantum polynomial time circuit for quantum supremacy
• A Classical Algorithm for Quantum $\text{SU}(2)$ Schur Sampling
• Approximation Algorithms for Complex-Valued Ising Models on Bounded Degree Graphs
• Fault-tolerant quantum speedup from constant depth quantum circuits
• A game of quantum advantage: linking verification and simulation
• Forbidden subspaces for level-1 QAOA and IQP circuits
• Faster Born probability estimation via gate merging and frame optimisation
• Quantum self-learning Monte Carlo with quantum Fourier transform sampler
• Entanglement Scaling in Quantum Advantage Benchmarks
• Quantum advantage from energy measurements of many-body quantum systems
• Disentangling magic states with classically simulable quantum circuits
• Quantum supremacy in driven quantum many-body systems
• Fault-tolerant compiling of classically hard IQP circuits on hypercubes
• Simulating Quantum Computations with Tutte Polynomials
• Efficient classical computation of expectation values in a class of quantum circuits with an epistemically restricted phase space representation
• Quantifying multiparticle entanglement with randomized measurements
• Quantum tomography with random diagonal unitary maps and statistical bounds on information generation using random matrix theory
• Dual-isometric Projected Entangled Pair States
• Fast simulation of planar Clifford circuits
• Feynman-path type simulation using stabilizer projector decomposition of unitaries
• Forging quantum data: classically defeating an IQP-based quantum test
• Quantum complexity phase transitions in monitored random circuits
• Connection between single-layer Quantum Approximate Optimization Algorithm interferometry and thermal distributions sampling
• Generative Invertible Quantum Neural Networks
• The Hadamard gate cannot be replaced by a resource state in universal quantum computation
• Emergent Quantum Mechanics at the Boundary of a Local Classical Lattice Model
• Quantum Computing for Data Centric Engineering and Science
• On Certified Randomness from Fourier Sampling or Random Circuit Sampling
• Lower T-count with faster algorithms
• On the average-case complexity of learning output distributions of quantum circuits
• Methods for Classically Simulating Noisy Networked Quantum Architectures
• Generators and Relations for the Group On(Z[1/2])
• Efficiently verifiable quantum advantage on near-term analog quantum simulators
• Contagious error sources would need time travel to prevent quantum computation
• Extending Classically Simulatable Bounds of Clifford Circuits with Nonstabilizer States via Framed Wigner Functions
• Additive-error fine-grained quantum supremacy
• Phase context decomposition of diagonal unitaries for higher-dimensional systems
• Computation in a general physical setting
• Single-qubit gate teleportation provides a quantum advantage
• Representation matching for delegated quantum computing
• Secret extraction attacks against obfuscated IQP circuits
• Tomography-assisted noisy quantum circuit simulator using matrix product density operators
• Discord in relation to resource states for measurement-based quantum computation
• Classically Simulating Quantum Supremacy IQP Circuits through a Random Graph Approach
• On the Hardness of Measuring Magic
• Classical simulation of circuits with realistic odd-dimensional Gottesman-Kitaev-Preskill states
• Rewindable Quantum Computation and Its Equivalence to Cloning and Adaptive Postselection
• Symmetric channel verification for purifying noisy quantum channels
• Generalized Cross-Entropy Benchmarking for Random Circuits with Ergodicity
• Performance analysis of a filtering variational quantum algorithm
• Expressiveness of Commutative Quantum Circuits: A Probabilistic Approach
• Low overhead universality and quantum supremacy using only $Z$-control
• Estimation of mutual information via quantum kernel method
• Instantaneous Quantum Polynomial-Time Sampling and Verifiable Quantum Advantage: Stabilizer Scheme and Classical Security
• Quantum Cryptography and Meta-Complexity
• Resourcefulness of non-classical continuous-variable quantum gates
• Computational Complexity and Simulability of Non-Hermitian Quantum Dynamics
• Sampling (noisy) quantum circuits through randomized rounding
• Zero-Knowledge Proofs of Quantumness
• Validating multi-photon quantum interference with finite data
• Hardness of efficiently generating ground states in postselected quantum computation
• Efficient classical simulation of cluster state quantum circuits with alternative inputs
• Cryptographic Characterization of Quantum Advantage