Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:0910.3376 · Theory of Computing

Quantum Proofs for Classical Theorems

Andrew Drucker, Ronald de Wolf

Published Jan 1, 2011• 49 citations
arXivHTMLPDF

Abstract

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.

DOI
10.4086/toc.gs.2011.002

Related papers

Coding theorems for quantum communication channels

Alexander Semenovich Holevo

The more than thirty years old issue of the information capacity of quantum communication channels was dramatically clarified during when a number of direct quantum coding theorems were discovered. To a considerable extent this progress is due to an interplay between the quantum communication theory and quantum information ideas related to more recent development in quantum computing. It is remarkable, however, that many probabilistic tools underlying the treatment of the quantum case have their roots, and in some cases direct prototypes, in the classical Shannon theory.

arXiv:quant-ph/9708046•IEEE International Symposium on Information Theory (ISIT)•Nov 27, 2002•23 citations

The Quantum PCP Conjecture

Dorit Aharonov, Itai Arad, Thomas Vidick

The classical PCP theorem is arguably the most important achievement of classical complexity theory in the past quarter century. In recent years, researchers in quantum computational complexity have tried to identify approaches and develop tools that address the question: does a quantum version of the PCP theorem hold? The story of this study starts with classical complexity and takes unexpected turns providing fascinating vistas on the foundations of quantum mechanics, the global nature of entanglement and its topological properties, quantum error correction, information theory, and much more; it raises questions that touch upon some of the most fundamental issues at the heart of our understanding of quantum mechanics. At this point, the jury is still out as to whether or not such a theorem holds. This survey aims to provide a snapshot of the status in this ongoing story, tailored to a general theory-of-CS audience.

arXiv:1309.7495•Sep 28, 2013•66 citations

Quantum complexity theory tools, goals and challenges

Jozef Gruska

Analysis of methods and results of quantum complexity theory and their contribution for better understanding of main theoretical and practical problems in quantum information processing.

•Jan 1, 2005•0 citations

Approximate Degree in Classical and Quantum Computing

Mark Bun, Justin Thaler

The ability (or inability) to represent or approximate Boolean functions by polynomials is a central concept in complexity theory, underlying interactive and probabilistically checkable proof systems, circuit lower bounds, quantum complexity theory, and more. In this book, the authors survey what is known about a particularly natural notion of approximation by polynomials, capturing pointwise approximation over This book covers recent progress on proving approximate degree lower and upper bounds and describes some applications of the new bounds to oracle separations, quantum query and communication complexity, and circuit complexity. The authors explain how several of these advances have been unlocked by a particularly simple and elegant technique, called dual block composition, for constructing solutions to this dual linear program. They also provide concise coverage of even more recent lower bound techniques based on a new complexity measure called spectral sensitivity. Finally, they show how explicit constructions of approximating polynomials have been inspired by quantum query algorithms. This book provides a comprehensive review of the foundational and recent developments of an important topic in both classical and quantum computing. The reader has a considerable body of knowledge condensed in an accessible form to quickly understand the principles and further their own research.

•Jan 1, 2022•0 citations

Polynomial Approximations for Quantum Hamiltonian Complexity

Kan, Benjamin Ruoyu

Quantum Hamiltonian Complexity (QHC) sits at the intersection of quantum complexity theory and quantum many-body physics. However, many results in QHC still remain disconnected across domains. The technique of polynomial approximations, derived from classical approximation theory methods, has recently seen remarkable success at proving results in QHC, and may change this detached paradigm. This thesis aims to better unify results in QHC by applying polynomial approximations to provide an alternative proof of the Lieb-Schultz-Mattis (LSM) theorem, a seminal result in condensed matter physics. The LSM theorem provides an upper bound on the spectral gap of quantum many-body systems under certain symmetry conditions, and is deeply related to topological quantum computing. We hope to provide a more elementary proof of LSM based in classical techniques, such as concentration bounds, and demonstrate new applications of the polynomial approximation technique. In this work, we outline the general approach for using polynomial approximations to prove the LSM theorem for a 1D periodic spin-1/2 chain, and characterize the valid ground states for this system. We also provide progress towards this end in the form of examples of unconcentrated LSM ground states, as well as discussing the uniform superposition ground state and alternate perspectives on a full proof or counterexample.

•Jan 1, 2023•0 citations

Quantum Communication Complexity

Hartmut Klauck

This paper surveys the field of quantum communication complexity. Some interesting recent results are collected concerning relations to classical communication, lower bound methods, one-way communication, and applications of quantum communication complexity.

arXiv:quant-ph/0005032•May 8, 2000•48 citations
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.
The more than thirty years old issue of the information capacity of quantum communication channels was dramatically clarified during when a number of direct quantum coding theorems were discovered. To a considerable extent this progress is due to an interplay between the quantum communication theory and quantum information ideas related to more recent development in quantum computing. It is remarkable, however, that many probabilistic tools underlying the treatment of the quantum case have their roots, and in some cases direct prototypes, in the classical Shannon theory.
The classical PCP theorem is arguably the most important achievement of classical complexity theory in the past quarter century. In recent years, researchers in quantum computational complexity have tried to identify approaches and develop tools that address the question: does a quantum version of the PCP theorem hold? The story of this study starts with classical complexity and takes unexpected turns providing fascinating vistas on the foundations of quantum mechanics, the global nature of entanglement and its topological properties, quantum error correction, information theory, and much more; it raises questions that touch upon some of the most fundamental issues at the heart of our understanding of quantum mechanics. At this point, the jury is still out as to whether or not such a theorem holds. This survey aims to provide a snapshot of the status in this ongoing story, tailored to a general theory-of-CS audience.
The ability (or inability) to represent or approximate Boolean functions by polynomials is a central concept in complexity theory, underlying interactive and probabilistically checkable proof systems, circuit lower bounds, quantum complexity theory, and more. In this book, the authors survey what is known about a particularly natural notion of approximation by polynomials, capturing pointwise approximation over This book covers recent progress on proving approximate degree lower and upper bounds and describes some applications of the new bounds to oracle separations, quantum query and communication complexity, and circuit complexity. The authors explain how several of these advances have been unlocked by a particularly simple and elegant technique, called dual block composition, for constructing solutions to this dual linear program. They also provide concise coverage of even more recent lower bound techniques based on a new complexity measure called spectral sensitivity. Finally, they show how explicit constructions of approximating polynomials have been inspired by quantum query algorithms. This book provides a comprehensive review of the foundational and recent developments of an important topic in both classical and quantum computing. The reader has a considerable body of knowledge condensed in an accessible form to quickly understand the principles and further their own research.
Quantum Hamiltonian Complexity (QHC) sits at the intersection of quantum complexity theory and quantum many-body physics. However, many results in QHC still remain disconnected across domains. The technique of polynomial approximations, derived from classical approximation theory methods, has recently seen remarkable success at proving results in QHC, and may change this detached paradigm. This thesis aims to better unify results in QHC by applying polynomial approximations to provide an alternative proof of the Lieb-Schultz-Mattis (LSM) theorem, a seminal result in condensed matter physics. The LSM theorem provides an upper bound on the spectral gap of quantum many-body systems under certain symmetry conditions, and is deeply related to topological quantum computing. We hope to provide a more elementary proof of LSM based in classical techniques, such as concentration bounds, and demonstrate new applications of the polynomial approximation technique. In this work, we outline the general approach for using polynomial approximations to prove the LSM theorem for a 1D periodic spin-1/2 chain, and characterize the valid ground states for this system. We also provide progress towards this end in the form of examples of unconcentrated LSM ground states, as well as discussing the uniform superposition ground state and alternate perspectives on a full proof or counterexample.