Quantum Proofs for Classical Theorems
arXiv:0910.3376
Abstract
Alongside the development of quantum algorithms and quantum complexity theory in recent years, quantum techniques have also proved instrumental in obtaining results in classical (non-quantum) areas. In this paper we survey these results and the quantum toolbox they use.
arXiv comment50 pages LaTeX. Updated based on journal version; the journal version is open-access and has nicer typesetting (http://theoryofcomputing.org/articles/gs002/)
References in corpus (12)
- Strengths and Weaknesses of Quantum Computing
- Quantum Amplitude Amplification and Estimation
- Negative weights make adversaries stronger
- Quantum communication complexity of symmetric predicates
- Complexity limitations on quantum computation
- Quantum Search on Bounded-Error Inputs
- A Hypercontractive Inequality for Matrix-Valued Functions with Applications to Quantum Computing and LDCs
- Complexity Classes of Equivalence Problems Revisited
- Quantum lower bounds by quantum arguments
- Three lines proof of the lower bound for the matrix rigidity
- On Quantum Versions of the Yao Principle
- A Lattice Problem in Quantum NP
Cited by in corpus (7)
- Quantum algorithms: an overview
- Graph States, Pivot Minor, and Universality of (X,Z)-measurements
- Complexity of Supersymmetric Systems and the Cohomology Problem
- From Ansätze to Z-gates: a NASA View of Quantum Computing
- Non-Markovian quantum interference in multilevel quantum systems: Exact master equation approach
- Spatial Search on Graphs with Multiple Targets using Flip-flop Quantum Walk
- Adaptivity vs Postselection