Average-case complexity versus approximate simulation of commuting quantum computations

Abstract

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.

This version is arguably easier to read than v1. Trust us, we argued about it. 4+1+5 pages, RevTex 4.1

References in corpus (6)

• Coupling Superconducting Qubits via a Cavity Bus
• Digital quantum simulation of fermionic models with a superconducting circuit
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Power of Quantum Computation with Few Clean Qubits
• Binary Matroids and Quantum Probability Distributions
• Commuting quantum circuits: efficient classical simulations versus hardness results

Cited by in corpus (199)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Supervised learning with quantum enhanced feature spaces
• Quantum computational advantage using photons
• Quantum machine learning in feature Hilbert spaces
• Characterizing Quantum Supremacy in Near-Term Devices
• Logical quantum processor based on reconfigurable atom arrays
• Quantum Computational Supremacy
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• A blueprint for demonstrating quantum supremacy with superconducting qubits
• Quantum advantage with shallow circuits
• Strawberry Fields: A Software Platform for Photonic Quantum Computing
• Quantum Supremacy and the Complexity of Random Circuit Sampling
• Simulation of quantum circuits by low-rank stabilizer decompositions
• Quantum Approximate Optimization of the Long-Range Ising Model with a Trapped-Ion Quantum Simulator
• Stochastic gradient descent for hybrid quantum-classical optimization
• Achieving quantum supremacy with sparse and noisy commuting quantum computations
• Quantum Supremacy through the Quantum Approximate Optimization Algorithm
• Quantum Sampling Problems, BosonSampling and Quantum Supremacy
• Challenges and Opportunities of Near-Term Quantum Computing Systems
• A flexible high-performance simulator for verifying and benchmarking quantum circuits implemented on real hardware
• The Born Supremacy: Quantum Advantage and Training of an Ising Born Machine
• Efficient classical simulation of random shallow 2D quantum circuits
• Computational advantage of quantum random sampling
• Quantum advantage with noisy shallow circuits in 3D
• Theory of quantum system certification: a tutorial
• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• Approximate unitary $t$-designs by short random quantum circuits using nearest-neighbor and long-range gates
• Establishing the Quantum Supremacy Frontier with a 281 Pflop/s Simulation
• Grover Mixers for QAOA: Shifting Complexity from Mixer Design to State Preparation
• Efficient Quantum Walk on a Quantum Processor
• Efficient classical simulation of noisy random quantum circuits in one dimension
• Architectures for quantum simulation showing a quantum speedup
• Quantum Supremacy for Simulating A Translation-Invariant Ising Spin Model
• Quantum Algorithms for Fixed Qubit Architectures
• Regimes of classical simulability for noisy Gaussian boson sampling
• Natural quantum reservoir computing for temporal information processing
• On the Quantum versus Classical Learnability of Discrete Distributions
• Random quantum circuits anti-concentrate in log depth
• Verification of Many-Qubit States
• Classical simulation of photonic linear optics with lost particles
• How many qubits are needed for quantum computational supremacy?
• NISQ Computers: A Path to Quantum Supremacy
• Efficient Verification of Hypergraph States
• Direct certification of a class of quantum simulations
• Temperature scaling law for quantum annealing optimizers
• Computational power of one- and two-dimensional dual-unitary quantum circuits
• Continuous-Variable Instantaneous Quantum Computing is hard to sample
• Anomaly detection with variational quantum generative adversarial networks
• Verified measurement-based quantum computing with hypergraph states
• Quantum approximate optimization with Gaussian boson sampling
• Anticoncentration theorems for schemes showing a quantum speedup
• Review on Quantum Walk Computing: Theory, Implementation, and Application
• Quantum Supremacy Is Both Closer and Farther than It Appears
• Classically-Verifiable Quantum Advantage from a Computational Bell Test
• Boundaries of quantum supremacy via random circuit sampling
• Tight bounds on the convergence of noisy random circuits to the uniform distribution
• Variational inference with a quantum computer
• Dynamical phase transitions in sampling complexity
• From estimation of quantum probabilities to simulation of quantum circuits
• Pattern recognition techniques for Boson Sampling validation
• Efficient classical simulation of Clifford circuits with nonstabilizer input states
• Hardness of classically sampling one clean qubit model with constant total variation distance error
• Simulating Noisy Quantum Circuits with Matrix Product Density Operators
• Sample complexity of device-independently certified "quantum supremacy"
• Continuous-Variable Sampling from Photon-Added or Photon-Subtracted Squeezed States
• Fermion Sampling: a robust quantum computational advantage scheme using fermionic linear optics and magic input states
• Limitations of Linear Cross-Entropy as a Measure for Quantum Advantage
• Application-Motivated, Holistic Benchmarking of a Full Quantum Computing Stack
• Quantum advantage of unitary Clifford circuits with magic state inputs
• Changing the circuit-depth complexity of measurement-based quantum computation with hypergraph states
• Analog Errors in Ising Machines
• Noise and the frontier of quantum supremacy
• Closing gaps of a quantum advantage with short-time Hamiltonian dynamics
• Simulating complex networks in phase space: Gaussian boson sampling
• Accrediting outputs of noisy intermediate-scale quantum computing devices
• The computational landscape of general physical theories
• Quantum semi-supervised generative adversarial network for enhanced data classification
• Random circuit block-encoded matrix and a proposal of quantum LINPACK benchmark
• Benchmarking quantum machine learning kernel training for classification tasks
• Quantum Approximate Optimization Algorithm pseudo-Boltzmann states
• Verifying Random Quantum Circuits with Arbitrary Geometry Using Tensor Network States Algorithm
• Quantum Kitchen Sinks: An algorithm for machine learning on near-term quantum computers
• Quantum circuits and low-degree polynomials over F_2
• Verifying commuting quantum computations via fidelity estimation of weighted graph states
• Energy-Consumption Advantage of Quantum Computation
• Quantum-assisted associative adversarial network: Applying quantum annealing in deep learning
• Efficient verification of quantum gates with local operations
• Bell sampling from quantum circuits
• Further extensions of Clifford circuits and their classical simulation complexities
• Quantum supremacy in constant-time measurement-based computation: A unified architecture for sampling and verification
• Efficient classical simulation of noisy quantum computation
• All-optical quantum computing using cubic phase gates
• A quantum hamiltonian simulation benchmark
• One-particle Green's functions from the quantum equation of motion algorithm
• Magic of quantum hypergraph states
• Power of Quantum Computation with Few Clean Qubits
• Hilbert space delocalization under random unitary circuits
• Numerical evidence against advantage with quantum fidelity kernels on classical data
• Complexity phase diagram for interacting and long-range bosonic Hamiltonians
• Protocol for implementing quantum nonparametric learning with trapped ions
• Efficient verification of continuous-variable quantum states and devices without assuming identical and independent operations
• Neural Quantum Embedding: Pushing the Limits of Quantum Supervised Learning
• Quantum Schur Sampling Circuits can be Strongly Simulated
• Effects of quantum resources on the statistical complexity of quantum circuits
• Simulating noisy variational quantum eigensolver with local noise models
• Quantum-enhanced least-square support vector machine: simplified quantum algorithm and sparse solutions
• Average-Case Quantum Advantage with Shallow Circuits
• Certified variational quantum algorithms for eigenstate preparation
• Entanglement of random hypergraph states
• Power of one non-clean qubit
• Error mitigation on a near-term quantum photonic device
• Mitigating errors by quantum verification and post-selection
• Analogue Quantum Simulation: A New Instrument for Scientific Understanding
• Validating quantum-supremacy experiments with exact and fast tensor network contraction
• Preparation and verification of tensor network states
• Quantum Algorithms for Inverse Participation Ratio Estimation in multi-qubit and multi-qudit systems
• Nonadaptive fault-tolerant verification of quantum supremacy with noise
• Complexity of Fermionic Dissipative Interactions and Applications to Quantum Computing
• A Continuous Variable Born Machine
• Information Theoretically Secure Hypothesis Test for Temporally Unstructured Quantum Computation (Extended Abstract)
• Protocols for classically training quantum generative models on probability distributions
• Information Theoretically Secure Hypothesis Test for Temporally Unstructured Quantum Computation
• Quantum computational advantage with constant-temperature Gibbs sampling
• Merlin-Arthur with efficient quantum Merlin and quantum supremacy for the second level of the Fourier hierarchy
• F-Divergences and Cost Function Locality in Generative Modelling with Quantum Circuits
• Emulating Quantum Interference with Generalized Ising Machines
• Benchmarking 50-Photon Gaussian Boson Sampling on the Sunway TaihuLight
• Phase-space negativity as a computational resource for quantum kernel methods
• Robust sparse IQP sampling in constant depth
• Complexity Classification of Conjugated Clifford Circuits
• Application of quantum computing to a linear non-Gaussian acyclic model for novel medical knowledge discovery
• Fault-tolerant quantum speedup from constant depth quantum circuits
• Forbidden subspaces for level-1 QAOA and IQP circuits
• Exploring the neighborhood of 1-layer QAOA with Instantaneous Quantum Polynomial circuits
• Exploring Shallow-Depth Boson Sampling: Towards Scalable Quantum Supremacy
• Entanglement and complexity of interacting qubits subject to asymmetric noise
• Approximation Algorithms for Complex-Valued Ising Models on Bounded Degree Graphs
• Reuse-Aware Compilation for Zoned Quantum Architectures Based on Neutral Atoms
• Faster Born probability estimation via gate merging and frame optimisation
• A Classical Algorithm for Quantum $\text{SU}(2)$ Schur Sampling
• Ancilla-driven instantaneous quantum polynomial time circuit for quantum supremacy
• Quantum advantage from energy measurements of many-body quantum systems
• Disentangling magic states with classically simulable quantum circuits
• Fault-tolerant compiling of classically hard IQP circuits on hypercubes
• Verifiable measurement-based quantum random sampling with trapped ions
• Quantum supremacy in driven quantum many-body systems
• Sample caching Markov chain Monte Carlo approach to boson sampling simulation
• In situ characterization of linear-optical networks in randomized boson sampling
• Forging quantum data: classically defeating an IQP-based quantum test
• Simulating Quantum Computations with Tutte Polynomials
• On Certified Randomness from Fourier Sampling or Random Circuit Sampling
• Gibbs Sampling gives Quantum Advantage at Constant Temperatures with O(1)-Local Hamiltonians
• Boson Sampling for Generalized Bosons
• Connection between single-layer Quantum Approximate Optimization Algorithm interferometry and thermal distributions sampling
• Backpropagation scaling in parameterised quantum circuits
• Computational self-testing for entangled magic states
• Quantum computation using arrays of N polar molecules in pendular states
• Methods for Classically Simulating Noisy Networked Quantum Architectures
• Test of Quantumness with Small-Depth Quantum Circuits
• Time-optimal multi-qubit gates: Complexity, efficient heuristic and gate-time bounds
• Additive-error fine-grained quantum supremacy
• Analogue Quantum Simulation: A Philosophical Prospectus
• Extending Classically Simulatable Bounds of Clifford Circuits with Nonstabilizer States via Framed Wigner Functions
• Efficient approximation of experimental Gaussian boson sampling
• Efficiently verifiable quantum advantage on near-term analog quantum simulators
• High performance Boson Sampling simulation via data-flow engines
• Input Redundancy for Parameterized Quantum Circuits
• Tomography-assisted noisy quantum circuit simulator using matrix product density operators
• Passive verification protocol for thermal graph states
• Boson sampling with ultracold atoms in a programmable optical lattice
• Quantum advantage in temporally flat measurement-based quantum computation
• Secret extraction attacks against obfuscated IQP circuits
• Pseudochaotic Many-Body Dynamics as a Pseudorandom State Generator
• The one clean qubit model without entanglement is classically simulable
• On computational complexity and average-case hardness of shallow-depth boson sampling
• Multi-channel convolutional neural quantum embedding
• Empirical Power of Quantum Encoding Methods for Binary Classification
• Impossibility of blind quantum sampling for classical client
• Generalized Cross-Entropy Benchmarking for Random Circuits with Ergodicity
• Low overhead universality and quantum supremacy using only $Z$-control
• Sampling of globally depolarized random quantum circuit
• Classically Simulating Quantum Supremacy IQP Circuits through a Random Graph Approach
• Instantaneous Quantum Polynomial-Time Sampling and Verifiable Quantum Advantage: Stabilizer Scheme and Classical Security
• Rewindable Quantum Computation and Its Equivalence to Cloning and Adaptive Postselection
• Estimation of mutual information via quantum kernel method
• Expressiveness of Commutative Quantum Circuits: A Probabilistic Approach
• Performance analysis of a filtering variational quantum algorithm
• Symmetric channel verification for purifying noisy quantum channels
• Simulating Quantum Circuits with Tree Tensor Networks using Density-Matrix Renormalization Group Algorithm
• Quantum Cryptography and Meta-Complexity
• Efficient classical simulation of cluster state quantum circuits with alternative inputs
• Fine-grained quantum computational supremacy
• Polynomial speedup in Torontonian calculation by a scalable recursive algorithm
• Hardness of efficiently generating ground states in postselected quantum computation
• Cryptographic Characterization of Quantum Advantage
• Complexity of Gaussian quantum optics with a limited number of non-linearities
• Classical simulation of noisy quantum circuits via locally entanglement-optimal unravelings
• Symmetry-Accelerated Classical Simulation of Clifford-Dominated Circuits
• High-performance parallel classical scheme for simulating shallow quantum circuits