Quantum computing, postselection, and probabilistic polynomial-time
From MaRDI portal
Abstract: I study the class of problems efficiently solvable by a quantum computer, given the ability to "postselect" on the outcomes of measurements. I prove that this class coincides with a classical complexity class called PP, or Probabilistic Polynomial-Time. Using this result, I show that several simple changes to the axioms of quantum mechanics would let us solve PP-complete problems efficiently. The result also implies, as an easy corollary, a celebrated theorem of Beigel, Reingold, and Spielman that PP is closed under intersection, as well as a generalization of that theorem due to Fortnow and Reingold. This illustrates that quantum computing can yield new and simpler proofs of major results about classical computation.
Recommendations
Cites work
- Adaptive quantum computation, constant depth quantum circuits and Arthur-Merlin games
- Complexity limitations on quantum computation
- Computational Complexity of Probabilistic Turing Machines
- Determining acceptance possibility for a quantum computation is hard for the polynomial hierarchy
- Exponential lower bound for 2-query locally decodable codes via a quantum argument
- scientific article; zbMATH DE number 3128586 (Why is no real title available?)
- Limitations of Quantum Advice and One-Way Communication
- Lower bounds for local search by quantum arguments
- Perceptrons, PP, and the polynomial hierarchy
- PP is closed under intersection
- PP is closed under truth-table reductions
- Quantum Complexity Theory
- Quantum computations: algorithms and error correction
- Quantum theory of probability and decisions
- Some optimal inapproximability results
- Threshold Computation and Cryptographic Security
- Undirected ST-connectivity in log-space
- Unknown quantum states: The quantum de Finetti representation
- Weinberg’s nonlinear quantum mechanics and the Einstein-Podolsky-Rosen paradox
Cited in
(66)- Quantum computing and quadratically signed weight enumerators
- The landscape of communication complexity classes
- Quantum algorithm for linear differential equations with exponentially improved dependence on precision
- The complexity of approximating complex-valued Ising and Tutte partition functions
- Simulations of closed timelike curves
- The weirdness theorem and the origin of quantum paradoxes
- A structured view on weighted counting with relations to counting, quantum computation and applications
- The Python's lunch: geometric obstructions to decoding Hawking radiation
- Quantum Fourier transforms and the complexity of link invariants for quantum doubles of finite groups
- Quantum information in the Posner model of quantum cognition
- Quantum alternation
- Computation with multiple CTCs of fixed length and width
- A common algebraic description for probabilistic and quantum computations
- A linear-optical proof that the permanent is \(\#\mathrm{P}\)-hard
- Duality quantum computer and the efficient quantum simulations
- Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy.
- Quantum computing and hidden variables
- Computational Complexity of Projected Entangled Pair States
- The learnability of quantum states
- scientific article; zbMATH DE number 5360947 (Why is no real title available?)
- Temporally unstructured quantum computation
- Quantum multiparty communication complexity and circuit lower bounds
- Perfect state distinguishability and computational speedups with postselected closed timelike curves
- scientific article; zbMATH DE number 2013801 (Why is no real title available?)
- Computational tameness of classical non-causal models
- Quantum hedging in two-round prover-verifier interactions
- Proving the power of postselection
- A complete characterization of unitary quantum space
- Quantum lower bounds for approximate counting via Laurent polynomials
- scientific article; zbMATH DE number 7250159 (Why is no real title available?)
- scientific article; zbMATH DE number 7250161 (Why is no real title available?)
- Shadow tomography of quantum states
- The BQP-hardness of approximating the Jones polynomial
- Robust entangled qutrit states in atmospheric turbulence
- Computation in generalised probabilisitic theories
- Mathematical Foundations of Computer Science 2004
- Affine computation and affine automaton
- Operational quantum theory without predefined time
- Area laws and efficient descriptions of quantum many-body states
- A SCHEMATIC DEFINITION OF QUANTUM POLYNOMIAL TIME COMPUTABILITY
- Quantum double aspects of surface code models
- Rectangles are nonnegative juntas
- Complementarity and the unitarity of the black hole \(S\)-matrix
- Non-isometric codes for the black hole Interior from fundamental and effective dynamics
- Cryptography from pseudorandom quantum states
- Commuting quantum circuits and complexity of Ising partition functions
- On the impossibility of key agreements from quantum random oracles
- Post-quantum simulatable extraction with minimal assumptions: black-box and constant-round
- Quantum logarithmic space and post-selection
- Constructive post-quantum reductions
- Picturing Counting Reductions with the ZH-Calculus
- Bulk reconstruction and non-isometry in the backwards-forwards holographic black hole map
- Well-tempered ZX and ZH calculi
- Tensor networks for black hole interiors: non-isometries, quantum extremal surfaces, and wormholes
- Revisiting integer factorization using closed timelike curves
- On the maximum-likelihood decoding problem
- Classical and quantum Merlin-Arthur automata
- Even quantum advice is unlikely to solve \(\mathsf{PP}\)
- On the physical basis for the incomparability of NP and BQP
- A qubit, a coin, and an advice string walk into a relational problem
- Symbolic synthesis of Clifford circuits and beyond
- Quantum differential equation solvers: limitations and fast-forwarding
- Quantum state tomography on closed timelike curves using weak measurements
- Rewindable quantum computation and its equivalence to cloning and adaptive postselection
- Quantum interpretations, causality and quantum computation
- A broader view on the limitations of information processing and communication by nature
This page was built for publication: Quantum computing, postselection, and probabilistic polynomial-time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5428317)
