Average-case complexity versus approximate simulation of commuting quantum computations
arXiv:1504.07999 · doi:10.1103/PhysRevLett.117.080501
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.
arXiv commentThis version is arguably easier to read than v1. Trust us, we argued about it. 4+1+5 pages, RevTex 4.1
References in corpus (18)
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Quantum Simulation
- Coupling Superconducting Qubits via a Cavity Bus
- Engineered 2D Ising interactions on a trapped-ion quantum simulator with hundreds of spins
- Universal digital quantum simulation with trapped ions
- Digital quantum simulation of fermionic models with a superconducting circuit
- Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
- On the experimental verification of quantum complexity in linear optics
- Instantaneous Quantum Computation
- A Linear-Optical Proof that the Permanent is #P-Hard
- Quantum Commuting Circuits and Complexity of Ising Partition Functions
- Measurement-based classical computation
- Power of Quantum Computation with Few Clean Qubits
- A simple encoding of a quantum circuit amplitude as a matrix permanent
- Commuting quantum circuits: efficient classical simulations versus hardness results
- Binary Matroids and Quantum Probability Distributions
- The complexity of approximating complex-valued Ising and Tutte partition functions
- Inapproximability for Antiferromagnetic Spin Systems in the Tree Non-Uniqueness Region
Cited by in corpus (203)
- 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 -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
- On the Quantum versus Classical Learnability of Discrete Distributions
- Natural quantum reservoir computing for temporal information processing
- Verification of Many-Qubit States
- Random quantum circuits anti-concentrate in log depth
- 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
- Impossibility of Classically Simulating One-Clean-Qubit Computation
- Quantum approximate optimization with Gaussian boson sampling
- Anticoncentration theorems for schemes showing a quantum speedup
- Review on Quantum Walk Computing: Theory, Implementation, and Application
- Tight bounds on the convergence of noisy random circuits to the uniform distribution
- Classically-Verifiable Quantum Advantage from a Computational Bell Test
- Variational inference with a quantum computer
- Boundaries of quantum supremacy via random circuit sampling
- Quantum Supremacy Is Both Closer and Farther than It Appears
- 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
- Hardness of classically sampling one clean qubit model with constant total variation distance error
- Pattern recognition techniques for Boson Sampling validation
- Efficient classical simulation of Clifford circuits with nonstabilizer input states
- Continuous-Variable Sampling from Photon-Added or Photon-Subtracted Squeezed States
- Simulating Noisy Quantum Circuits with Matrix Product Density Operators
- Sample complexity of device-independently certified "quantum supremacy"
- 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
- Quantum advantage of unitary Clifford circuits with magic state inputs
- Limitations of Linear Cross-Entropy as a Measure for Quantum Advantage
- 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
- The computational landscape of general physical theories
- Accrediting outputs of noisy intermediate-scale quantum computing devices
- Simulating complex networks in phase space: Gaussian boson sampling
- Quantum semi-supervised generative adversarial network for enhanced data classification
- Random circuit block-encoded matrix and a proposal of quantum LINPACK benchmark
- Verifying Random Quantum Circuits with Arbitrary Geometry Using Tensor Network States Algorithm
- Benchmarking quantum machine learning kernel training for classification tasks
- Quantum Approximate Optimization Algorithm pseudo-Boltzmann states
- Quantum circuits and low-degree polynomials over F_2
- Verifying commuting quantum computations via fidelity estimation of weighted graph states
- Quantum Kitchen Sinks: An algorithm for machine learning on near-term quantum computers
- Efficient verification of quantum gates with local operations
- Bell sampling from quantum circuits
- Energy-Consumption Advantage of Quantum Computation
- Quantum-assisted associative adversarial network: Applying quantum annealing in deep learning
- Further extensions of Clifford circuits and their classical simulation complexities
- Efficient classical simulation of noisy quantum computation
- Quantum supremacy in constant-time measurement-based computation: A unified architecture for sampling and verification
- A quantum hamiltonian simulation benchmark
- All-optical quantum computing using cubic phase gates
- 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
- Efficient verification of continuous-variable quantum states and devices without assuming identical and independent operations
- Protocol for implementing quantum nonparametric learning with trapped ions
- 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
- Power of one non-clean qubit
- Error mitigation on a near-term quantum photonic device
- Entanglement of random hypergraph states
- 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
- Nonadaptive fault-tolerant verification of quantum supremacy with noise
- Quantum Algorithms for Inverse Participation Ratio Estimation in multi-qubit and multi-qudit systems
- Complexity of Fermionic Dissipative Interactions and Applications to Quantum Computing
- Protocols for classically training quantum generative models on probability distributions
- Information Theoretically Secure Hypothesis Test for Temporally Unstructured Quantum Computation
- A Continuous Variable Born Machine
- Information Theoretically Secure Hypothesis Test for Temporally Unstructured Quantum Computation (Extended Abstract)
- 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
- Quantum computational advantage with constant-temperature Gibbs sampling
- Complexity Classification of Conjugated Clifford Circuits
- Phase-space negativity as a computational resource for quantum kernel methods
- Application of quantum computing to a linear non-Gaussian acyclic model for novel medical knowledge discovery
- Emulating Quantum Interference with Generalized Ising Machines
- Robust sparse IQP sampling in constant depth
- Benchmarking 50-Photon Gaussian Boson Sampling on the Sunway TaihuLight
- A Classical Algorithm for Quantum Schur Sampling
- Faster Born probability estimation via gate merging and frame optimisation
- Exploring the neighborhood of 1-layer QAOA with Instantaneous Quantum Polynomial circuits
- Exploring Shallow-Depth Boson Sampling: Towards Scalable Quantum Supremacy
- Forbidden subspaces for level-1 QAOA and IQP circuits
- Ancilla-driven instantaneous quantum polynomial time circuit for quantum supremacy
- Fault-tolerant quantum speedup from constant depth quantum circuits
- Reuse-Aware Compilation for Zoned Quantum Architectures Based on Neutral Atoms
- Approximation Algorithms for Complex-Valued Ising Models on Bounded Degree Graphs
- Entanglement and complexity of interacting qubits subject to asymmetric noise
- 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
- Verifiable measurement-based quantum random sampling with trapped ions
- Simulating Quantum Computations with Tutte Polynomials
- 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
- On Certified Randomness from Fourier Sampling or Random Circuit Sampling
- Connection between single-layer Quantum Approximate Optimization Algorithm interferometry and thermal distributions sampling
- Boson Sampling for Generalized Bosons
- Gibbs Sampling gives Quantum Advantage at Constant Temperatures with O(1)-Local Hamiltonians
- Computational self-testing for entangled magic states
- Backpropagation scaling in parameterised quantum circuits
- Methods for Classically Simulating Noisy Networked Quantum Architectures
- Quantum computation using arrays of N polar molecules in pendular states
- Input Redundancy for Parameterized Quantum Circuits
- Efficiently verifiable quantum advantage on near-term analog quantum simulators
- Additive-error fine-grained quantum supremacy
- Test of Quantumness with Small-Depth Quantum Circuits
- High performance Boson Sampling simulation via data-flow engines
- Extending Classically Simulatable Bounds of Clifford Circuits with Nonstabilizer States via Framed Wigner Functions
- Analogue Quantum Simulation: A Philosophical Prospectus
- Efficient approximation of experimental Gaussian boson sampling
- Computational quantum-classical boundary of complex and noisy quantum systems
- Time-optimal multi-qubit gates: Complexity, efficient heuristic and gate-time bounds
- Secret extraction attacks against obfuscated IQP circuits
- Quantum advantage in temporally flat measurement-based quantum computation
- The one clean qubit model without entanglement is classically simulable
- Passive verification protocol for thermal graph states
- Boson sampling with ultracold atoms in a programmable optical lattice
- Pseudochaotic Many-Body Dynamics as a Pseudorandom State Generator
- Tomography-assisted noisy quantum circuit simulator using matrix product density operators
- Expressiveness of Commutative Quantum Circuits: A Probabilistic Approach
- Multi-channel convolutional neural quantum embedding
- Impossibility of blind quantum sampling for classical client
- Simulating Quantum Circuits with Tree Tensor Networks using Density-Matrix Renormalization Group Algorithm
- Symmetric channel verification for purifying noisy quantum channels
- Empirical Power of Quantum Encoding Methods for Binary Classification
- On computational complexity and average-case hardness of shallow-depth boson sampling
- Low overhead universality and quantum supremacy using only -control
- Sampling of globally depolarized random quantum circuit
- Performance analysis of a filtering variational quantum algorithm
- Rewindable Quantum Computation and Its Equivalence to Cloning and Adaptive Postselection
- 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
- Estimation of mutual information via quantum kernel method
- Generalized Cross-Entropy Benchmarking for Random Circuits with Ergodicity
- Hardness of efficiently generating ground states in postselected quantum computation
- Cryptographic Characterization of Quantum Advantage
- Quantum Cryptography and Meta-Complexity
- Fine-grained quantum computational supremacy
- High-performance parallel classical scheme for simulating shallow quantum circuits
- Complexity of Gaussian quantum optics with a limited number of non-linearities
- Symmetry-Accelerated Classical Simulation of Clifford-Dominated Circuits
- Efficient classical simulation of cluster state quantum circuits with alternative inputs
- Polynomial speedup in Torontonian calculation by a scalable recursive algorithm
- Classical simulation of noisy quantum circuits via locally entanglement-optimal unravelings
- Classical Clifford+T Sampling without Computing Marginals