Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy.
From MaRDI portal
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.
Recommendations
- Commuting quantum circuits with few outputs are unlikely to be classically simulatable
- Classical simulation and complexity of quantum computations (invited talk)
- Commuting quantum circuits and complexity of Ising partition functions
- Complexity classification of two-qubit commuting Hamiltonians
- The computational complexity of linear optics
Cites work
Cited in
(49)- The complexity of approximating complex-valued Ising and Tutte partition functions
- Learning nonlinear input-output maps with dissipative quantum systems
- Classically simulating quantum circuits with local depolarizing noise
- Verification of quantum computation: an overview of existing approaches
- From the quantum approximate optimization algorithm to a quantum alternating operator ansatz
- Quantum extensive-form games
- Complexity classification of local Hamiltonian problems
- A linear-optical proof that the permanent is \(\#\mathrm{P}\)-hard
- Quantum circuits and low-degree polynomials over \(\mathbb{F}_2\)
- Optimised resource construction for verifiable quantum computation
- Quantum Circuits That Can Be Simulated Classically in Polynomial Time
- The computational complexity of linear optics
- Commuting quantum circuits with few outputs are unlikely to be classically simulatable
- Information theoretically secure hypothesis test for temporally unstructured quantum computation (extended abstract)
- Classical simulation and complexity of quantum computations (invited talk)
- Fault-tolerant conversion between adjacent Reed–Muller quantum codes based on gauge fixing
- scientific article; zbMATH DE number 7559454 (Why is no real title available?)
- Average-case quantum advantage with shallow circuits
- scientific article; zbMATH DE number 7250159 (Why is no real title available?)
- On the classical hardness of spoofing linear cross-entropy benchmarking
- Compact Gaussian quantum computation by multi-pixel homodyne detection
- A framework for phase and interference in generalized probabilistic theories
- Generating a state t-design by diagonal quantum circuits
- Exact and efficient simulation of concordant computation
- On the power of quantum Fourier sampling
- Diagonal-unitary 2-design and their implementations by quantum circuits
- The computational complexity of linear optics
- Quantum computing, postselection, and probabilistic polynomial-time
- Computation in a general physical setting
- Trading inverses for an irrep in the Solovay-Kitaev theorem
- Commuting quantum circuits and complexity of Ising partition functions
- Approximate unitary t-designs by short random quantum circuits using nearest-neighbor and long-range gates
- Random quantum circuits transform local noise into global white noise
- Certified randomness from quantum supremacy
- Quantum advantage from any non-local game
- On the need for large quantum depth
- Generative invertible quantum neural networks
- Generators and relations for the group \(\mathrm{O}_n(\mathbb{Z}[\frac{1}{2}])\)
- Quantum advantage from one-way functions
- Guidable local Hamiltonian problems with implications to heuristic ansatz state preparation and the quantum PCP conjecture
- Quantum cryptography and meta-complexity
- A direct product theorem for quantum communication complexity with applications to device-independent cryptography
- Gaussianity and simulability of Cliffords and matchgates
- Rewindable quantum computation and its equivalence to cloning and adaptive postselection
- Verifiable quantum advantage without structure
- Quantum polynomial hierarchies: Karp-Lipton, error reduction, and lower bounds
- Efficient quantum pseudorandomness from Hamiltonian phase states
- Zero-knowledge proofs of quantumness
- Discrete quantum gaussians and central limit theorem
This page was built for publication: Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3088963)
