Quantum Proofs for Classical Theorems

Alongside the development of quantum algorithms and quantum complexity theory in recent years, quantum techniques have also proved instrumental in obtaining results in diverse classical (non-quantum) areas, such as coding theory, communication complexity, and polynomial approximations. In this paper we survey these results and the quantum toolbox they use.

• Publication year

  2009

• Venue

  Theory of Computing

• Publication date

  2009-10-18

• Fields of study

  Mathematics, Physics, Computer Science

• Identifiers
  DOI 10.4086/toc.gs.2011.002arXiv 0910.3376
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Perceptrons

  2021cited by this paper
• Communication Complexity

  2016cited by this paper
• The Probabilistic Method

  2015influential reference
• Über die analytische Darstellbarkeit sogenannter willkürlicher Functionen reeller Argumente

  2013cited by this paper
• Pattern Matrix Method

  2012cited by this paper
• Information theory methods in communication complexity

  2012cited by this paper
• A Quadratic Lower Bound for Three-Query Linear Locally Decodable Codes over Any Field

  2012cited by this paper
• Quantum Computation and Quantum Information

  2012influential reference
• Can Quantum-Mechanical Description of Physical Reality Be Considered Complete ' ?

  2011cited by this paper
• Erdős and the Quantum Method

  2010cited by this paper
• Uniform approximation by (quantum) polynomials

  2010influential reference
• Span programs and quantum query algorithms

  2010cited by this paper
• A Quadratic Lower Bound for Three-Query Linear Locally Decodable Codes over Any Field

  2010cited by this paper
• Lower Bounds on the Randomized Communication Complexity of Read-Once Functions

  2009cited by this paper
• 3-query locally decodable codes of subexponential length

  2009cited by this paper
• Lower Bounds on Quantum Multiparty Communication Complexity

  2009cited by this paper
• On the Communication Complexity of Read-Once AC^0 Formulae

  2009cited by this paper
• A note on the sign degree of formulas

  2009cited by this paper
• Complexity Lower Bounds using Linear Algebra

  2009cited by this paper
• BQP and the polynomial hierarchy

  2009cited by this paper
• Public-key cryptosystems from the worst-case shortest vector problem: extended abstract

  2009cited by this paper
• Complexity classes of equivalence problems revisited

  2009cited by this paper
• Span Programs and Quantum Query Complexity: The General Adversary Bound Is Nearly Tight for Every Boolean Function

  2009influential reference
• 1 . 2 Lattice-based cryptography

  2008cited by this paper
• Approximate Inclusion-Exclusion for Arbitrary Symmetric Functions

  2008influential reference
• Learning Complexity vs. Communication Complexity

  2008cited by this paper
• Towards 3-query locally decodable codes of subexponential length

  2008cited by this paper
• A Quantum Information-Theoretic Proof of the Relation between Horn's Problem and the Littlewood-Richardson Coefficients

  2008cited by this paper
• A note on quantum algorithms and the minimal degree of ε-error polynomials for symmetric functions

  2008influential reference
• The First and Fourth Public-Key Cryptosystems with Worst-Case/Average-Case Equivalence

  2007cited by this paper
• Tensor-based hardness of the shortest vector problem to within almost polynomial factors

  2007cited by this paper
• Halfspace Matrices

  2007cited by this paper
• Under consideration for publication in Math. Struct. in Comp. Science Quantum Multiparty Communication Complexity and Circuit Lower Bounds

  2007cited by this paper
• Lower bounds in communication complexity based on factorization norms

  2007cited by this paper
• On Computation and Communication with Small Bias

  2007cited by this paper
• A Quantum Algorithm for the Hamiltonian NAND Tree

  2007cited by this paper
• A Hypercontractive Inequality for Matrix-Valued Functions with Applications to Quantum Computing and LDCs

  2007cited by this paper
• Any AND-OR Formula of Size N can be Evaluated in time N^{1/2 + o(1)} on a Quantum Computer

  2007cited by this paper
• Unbounded-Error Classical and Quantum Communication Complexity

  2007cited by this paper
• Limits on the ability of quantum states to convey classical messages

  2006cited by this paper
• Quadratic Lower Bounds on Matrix Rigidity

  2006cited by this paper
• Negative weights make adversaries stronger

  2006cited by this paper
• THE QUANTUM ADVERSARY METHOD AND CLASSICAL FORMULA SIZE LOWER BOUNDS

  2005cited by this paper
• Matrix Exponentiated Gradient Updates for On-line Learning and Bregman Projection

  2005cited by this paper
• Elements of Information Theory

  2005cited by this paper
• Lattice problems in NP ∩ coNP

  2005influential reference
• On lattices, learning with errors, random linear codes, and cryptography

  2005cited by this paper
• Three lines proof of the lower bound for the matrix rigidity

  2005cited by this paper
• Lower Bounds on Matrix Rigidity Via a Quantum Argument

  2005influential reference
• Hardness of approximating the shortest vector problem in lattices

  2004cited by this paper
• Almost Perfect Lattices, the Covering Radius Problem, and Applications to Ajtai's Connection Factor

  2004cited by this paper
• Quantum and classical strong direct product theorems and optimal time-space tradeoffs

  2004cited by this paper
• Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs

  2004cited by this paper
• Improved Lower Bounds for Locally Decodable Codes and Private Information Retrieval

  2004cited by this paper
• 20世紀の名著名論：Peter Shor : Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer

  2004cited by this paper
• Limitations of quantum advice and one-way communication

  2004cited by this paper
• An optimal randomised cell probe lower bound for approximate nearest neighbour searching

  2004influential reference
• Quantum computing, postselection, and probabilistic polynomial-time

  2004cited by this paper
• Some Applications of Coding Theory in Computational Complexity

  2004cited by this paper
• Lower bounds for predecessor searching in the cell probe model

  2003cited by this paper
• A lattice problem in quantum NP

  2003influential reference
• Lower bounds for local search by quantum arguments

  2003cited by this paper
• New Bounds in Secret-Key Agreement: The Gap between Formation and Secrecy Extraction

  2003cited by this paper
• Robust Polynomials and Quantum Algorithms

  2003cited by this paper
• New lattice based cryptographic constructions

  2003cited by this paper
• An Introduction to the Approximation of Functions

  2003cited by this paper
• Polynomial degree vs. quantum query complexity

  2003cited by this paper
• New degree bounds for polynomial threshold functions

  2003cited by this paper
• Quantum Search on Bounded-Error Inputs

  2003cited by this paper
• Lower bounds for randomized and quantum query complexity using Kolmogorov arguments

  2003cited by this paper
• Two applications of information complexity

  2003cited by this paper
• Complexity measures and decision tree complexity: a survey

  2002cited by this paper
• On communication over an entanglement-assisted quantum channel

  2002cited by this paper
• Complexity of lattice problems - a cryptographic perspective

  2002cited by this paper
• Linking Classical and Quantum Key Agreement: Is There a Classical Analog to Bound Entanglement?

  2002cited by this paper
• Dense quantum coding and quantum finite automata

  2002cited by this paper
• Quantum communication and complexity

  2002cited by this paper
• An information statistics approach to data stream and communication complexity

  2002cited by this paper
• Exponential lower bound for 2-query locally decodable codes via a quantum argument

  2002influential reference
• Lower bounds for linear locally decodable codes and private information retrieval

  2002cited by this paper
• Quantum communication complexity of symmetric predicates

  2002cited by this paper
• Quantum computation and lattice problems

  2002influential reference
• A tracial quantum central limit theorem

  2002cited by this paper
• Extremal Combinatorics

  2001cited by this paper
• Lower bounds for quantum communication complexity

  2001cited by this paper
• Quantum lower bounds for the collision and the element distinctness problems

  2001cited by this paper
• A sieve algorithm for the shortest lattice vector problem

  2001cited by this paper
• Informational complexity and the direct sum problem for simultaneous message complexity

  2001cited by this paper
• Extremal Combinatorics: With Applications in Computer Science

  2001cited by this paper
• On Quantum Versions of the Yao Principle

  2001cited by this paper
• On the efficiency of local decoding procedures for error-correcting codes

  2000cited by this paper
• Quantum Amplitude Amplification and Estimation

  2000cited by this paper
• The Quantum Complexity of Set Membership

  2000cited by this paper
• Quantum lower bounds by quantum arguments

  2000cited by this paper
• Are bitvectors optimal?

  2000cited by this paper
• On the Limits of Nonapproximability of Lattice Problems

  2000cited by this paper
• Random words, quantum statistics, central limits, Random matrices

  1999cited by this paper
• Bounds for small-error and zero-error quantum algorithms

  1999cited by this paper
• Optimal lower bounds for quantum automata and random access codes

  1999cited by this paper
• Approximating Shortest Lattice Vectors is Not Harder Than Approximating Closest Lattice Vectors

  1999cited by this paper

• Classical and Quantum Polynomial Freiman-Ruzsa Algorithms

  2026cites this paper
• Algorithmic Polynomial Freiman-Ruzsa Theorems

  2025cites this paper
• Werner states from diagrams

  2023cites this paper
• Quantum-inspired classical algorithms for molecular vibronic spectra

  2022cites this paper
• Complexity of Supersymmetric Systems and the Cohomology Problem

  2021cites this paper
• Mathematics and Computation

  2019cites this paper
• From Ans\"atze to Z-gates: a NASA View of Quantum Computing

  2019cites this paper
• Algorithmic polynomials

  2018cites this paper
• A Quantum Polynomial Hierarchy and a Simple Proof of Vyalyi's Theorem

  2018cites this paper
• C C ] 1 4 O ct 2 01 6 Adaptivity vs Postselection

  2018cites this paper
• Formula lower bounds via the quantum method

  2017cites this paper
• The potential impact of quantum computers on society

  2017cites this paper
• Bounds on computation from physical principles

  2017cites this paper
• Controlled Quantum Amplification

  2017cites this paper
• Non-Markovian quantum interference in multilevel quantum systems: exact master equation approach

  2017cites this paper
• Adaptivity vs. Postselection, and Hardness Amplification for Polynomial Approximation

  2016cites this paper
• Quantum circuits and low-degree polynomials over F2

  2016cites this paper
• New Hardness Results for the Permanent Using Linear Optics

  2016cites this paper
• Unconventional Finite Automata and Algorithms

  2016cites this paper
• Adaptivity vs Postselection

  2016cites this paper
• Bounds on the power of proofs and advice in general physical theories

  2015cites this paper
• Quantum algorithms: an overview

  2015cites this paper
• Quantum Computing: Lecture Notes

  2015cites this paper
• Span Programs are Equivalent to Quantum Query Algorithms

  2014cites this paper
• Quantum Complexity of Boolean Matrix Multiplication and Related Problems

  2014cites this paper
• Query Complexity in Expectation

  2014cites this paper
• Rational approximations and quantum algorithms with postselection

  2014cites this paper
• Turing in Quantumland

  2014cites this paper
• Data Structures in Classical and Quantum Computing

  2013cites this paper
• A ug 2 01 3 Data Structures in Classical and Quantum Computing

  2013cites this paper
• Generalized probabilistic theories and conic extensions of polytopes

  2013cites this paper
• Commuting quantum circuits and complexity of Ising partition functions

  2013cites this paper
• Graph States, Pivot Minor, and Universality of (X, Z)-Measurements

  2012cites this paper
• Position-Based Quantum Cryptography and the Garden-Hose Game

  2012cites this paper
• Locally Decodable Codes

  2012cites this paper
• The Quantum Frontier

  2012cites this paper
• Lower Bounds on the Probability of Error for Classical and Classical-Quantum Channels

  2012cites this paper
• How Low can Approximate Degree and Quantum Query Complexity be for Total Boolean Functions?

  2012cites this paper
• Quantum Information and Variants of Interactive Proof Systems

  2011cites this paper
• Exponential Lower Bounds for Polytopes in Combinatorial Optimization

  2011cites this paper
• Two-player interaction in quantum computing : cryptographic primitives & query complexity. (Interaction à deux joueurs en informatique quantique : primitives cryptographiques et complexité en requêtes)

  2011cites this paper
• A linear-optical proof that the permanent is #P-hard

  2011cites this paper
• Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds

  2011cites this paper
• Quantum Encodings, with a Non-Quantum Application

  2011cites this paper
• Quantum coin flipping and bit commitment : optimal bounds, pratical constructions and computational security. (Pile-ou-face et mise-en-gage de bit quantique : bornes optimales, constructions pratiques et sécurité calculatoire)

  2011cites this paper
• Explorer Uniform approximation by ( quantum ) polynomials

  2011cites this paper
• Review of N . David Mermin ’ s Quantum Computer Science : An Introduction

  2010cites this paper
• Least span program witness size equals the general adversary lower bound on quantum query complexity

  2010cites this paper
• Uniform approximation by (quantum) polynomials

  2010cites this paper
• Quantum computer science: an introduction author of book: N. David Mermin's publisher: cambridge press, 2007, 236 pages

  2010cites this paper
• Rapport scientifique présenté pour l ’ obtention d ’ une Habilitation á Diriger des Recherches Interaction in the Quantum World

  2010cites this paper
• Lower bounds for quantum oblivious transfer

  2010cites this paper
• On the Computational Power of Locally Random Reductions ∗

  2010cites this paper
• The Book Review Column 1 the Mathematics of Voting and Elections: a Hands-on Approach Cryptography and Coding Theory Review 2 of Random Curves: Journeys of a Mathematician 4 a List of Questions for Neal Koblitz

  year unknowncites this paper