Quantum computing, postselection, and probabilistic polynomial-time
From MaRDI portal
Publication:5428317
DOI10.1098/rspa.2005.1546zbMath1337.81032arXivquant-ph/0412187WikidataQ29042439 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
81P68: Quantum computation
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q12: Quantum algorithms and complexity in the theory of computing
Related Items
Perfect state distinguishability and computational speedups with postselected closed timelike curves, A broader view on the limitations of information processing and communication by nature, A linear-optical proof that the permanent is # P -hard, Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy, Computational Complexity of Projected Entangled Pair States, The learnability of quantum states, Temporally unstructured quantum computation, Quantum multiparty communication complexity and circuit lower bounds
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
