Quantum computing, postselection, and probabilistic polynomial-time
From MaRDI portal
Publication:5428317
DOI10.1098/rspa.2005.1546zbMath1337.81032arXivquant-ph/0412187OpenAlexW2158764863WikidataQ29042439 ScholiaQ29042439MaRDI QIDQ5428317
Publication date: 21 November 2007
Published in: Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/quant-ph/0412187
Quantum computation (81P68) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Quantum algorithms and complexity in the theory of computing (68Q12)
Related Items
Quantum alternation, Quantum double aspects of surface code models, Duality quantum computer and the efficient quantum simulations, A linear-optical proof that the permanent is # P -hard, Quantum hedging in two-round prover-verifier interactions, Computational tameness of classical non-causal models, The landscape of communication complexity classes, A broader view on the limitations of information processing and communication by nature, Complementarity and the unitarity of the black hole \(S\)-matrix, Quantum algorithm for linear differential equations with exponentially improved dependence on precision, The complexity of approximating complex-valued Ising and Tutte partition functions, 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, The learnability of quantum states, Picturing Counting Reductions with the ZH-Calculus, Perfect state distinguishability and computational speedups with postselected closed timelike curves, Simulations of closed timelike curves, Shadow Tomography of Quantum States, A structured view on weighted counting with relations to counting, quantum computation and applications, The BQP-hardness of approximating the Jones polynomial, A Complete Characterization of Unitary Quantum Space, The Python's lunch: geometric obstructions to decoding Hawking radiation, Robust entangled qutrit states in atmospheric turbulence, Revisiting integer factorization using closed timelike curves, Computation in generalised probabilisitic theories, Temporally unstructured quantum computation, Quantum Fourier transforms and the complexity of link invariants for quantum doubles of finite groups, Affine Computation and Affine Automaton, Unnamed Item, Rectangles Are Nonnegative Juntas, Quantum multiparty communication complexity and circuit lower bounds, Unnamed Item, Unnamed Item, Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy, The weirdness theorem and the origin of quantum paradoxes, Quantum information in the Posner model of quantum cognition, Computational Complexity of Projected Entangled Pair States, Operational quantum theory without predefined time, Area laws and efficient descriptions of quantum many-body states, Computation with multiple CTCs of fixed length and width
Cites Work
- Unnamed Item
- Unnamed Item
- Perceptrons, PP, and the polynomial hierarchy
- PP is closed under intersection
- PP is closed under truth-table reductions
- Complexity limitations on quantum computation
- Limitations of Quantum Advice and One-Way Communication
- Lower bounds for local search by quantum arguments
- Undirected ST-connectivity in log-space
- Computational Complexity of Probabilistic Turing Machines
- Quantum computations: algorithms and error correction
- Threshold Computation and Cryptographic Security
- Quantum Complexity Theory
- Weinberg’s nonlinear quantum mechanics and the Einstein-Podolsky-Rosen paradox
- Quantum theory of probability and decisions
- Unknown quantum states: The quantum de Finetti representation
- Determining acceptance possibility for a quantum computation is hard for the polynomial hierarchy
- Some optimal inapproximability results
- Exponential lower bound for 2-query locally decodable codes via a quantum argument
