Quantum Proofs for Classical Theorems

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.

50 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 (3)

• Complexity Classes of Equivalence Problems Revisited
• Three lines proof of the lower bound for the matrix rigidity
• 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