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

XRDS Crossroads The ACM Magazine for Students

Black holes, quantum mechanics, and the limits of polynomial-time computability

Stephen P. Jordan

Published Sep 20, 2016• 2 citations
Publisher

Abstract

Which computational problems can be solved in polynomial-time and which cannot? Though seemingly technical, this question has wide-ranging implications and brings us to the heart of both theoretical computer science and modern physics.
DOI
10.1145/2983539

Related papers

Holographic Duality in Condensed Matter Physics

Jan Zaanen, Yan Liu, Ya-Wen Sun +1 more

A pioneering treatise presenting how the new mathematical techniques of holographic duality unify seemingly unrelated fields of physics. This innovative development morphs quantum field theory, general relativity and the renormalisation group into a single computational framework and this book is the first to bring together a wide range of research in this rapidly developing field. Set within the context of condensed matter physics and using boxes highlighting the specific techniques required, it examines the holographic description of thermal properties of matter, Fermi liquids and superconductors, and hitherto unknown forms of macroscopically entangled quantum matter in terms of general relativity, stars and black holes. Showing that holographic duality can succeed where classic mathematical approaches fail, this text provides a thorough overview of this major breakthrough at the heart of modern physics. The inclusion of extensive introductory material using non-technical language and online Mathematica notebooks ensures the appeal to students and researchers alike.

Cambridge University Press eBooks•Oct 31, 2015•577 citations

Quantum algorithms, quantum field theory, and computational complexity

Keith S. M. Lee

Bulletin of the American Physical Society•Mar 3, 2015•0 citations

On the Physical Basis for the Incomparability of NP and BQP

Vivek Kumar, Maheshwari Prasad Singh, R. Srikanth

What does it mean for the physically motivated computational complexity class $\mathcal{BQP}$ and the logically motivated class $\mathcal{NP}$ to be incomparable, from a physical perspective? Although it is unlikely that quantum computers can solve $\mathcal{NP}$-complete problems in polynomial time, yet it may be instructive to see how a physical theory (denoted $\Theta^{(\mathcal{NP})}$ or $\Theta^{(\mathcal{PSPACE})}$) for which $\mathcal{NP}$ or even $\mathcal{PSPACE}$, respectively, constitutes an efficient model of computation, would compare with quantum theory. The present work explores this question, after briefly reviewing some complexity results indicative of the incomparability of $\mathcal{BQP}$ and $\mathcal{NP}$. We argue that theories $\Theta^{(\mathcal{NP})}$ or $\Theta^{(\mathcal{PSPACE})}$ effectively feature degrees of nonlinearity. Thus, the linearity of quantum theory prevents complete problems in these complexity classes to be efficiently solvable on a quantum computer. On the other hand, the exponentiality of quantum theory endows quantum computers with a certain strength going beyond $\mathcal{NP}$ or even $\mathcal{PH}$. Thus the contrasting roles of the empowerment provided by quantum mechanical exponentiality and the limitation imposed by quantum mechanical linearity seem to be at the heart of the incomparability of the classes $\mathcal{BQP}$ and $\mathcal{NP}$. Quanta 2025; 14: 38–47.

Quanta•Jun 22, 2025•1 citation

Quantum Principles and Mathematical Computability

Tien D. Kieu

arXiv:quant-ph/0205093•International Journal of Theoretical Physics•Jul 1, 2005•9 citations

Quantum Universality, Computability, & Complexity

Colin P. Williams

Texts in computer science•Dec 6, 2010•0 citations

Computation in quantum space-time could lead to a super-polynomial speedup

Michael Zakharevich, Владик Крейнович

In theoretical computer science, researchers usually distinguish between feasible problems (that can be solved in polynomial time) and problems that require more computation time. A natural question is: can we use new physical processes, processes that have not been used in modern computers, to make computations drastically faster – e.g., to make intractable problems feasible? Such a possibility would occur if a physical process provides a super-polynomial ( = faster than polynomial) speed-up. In this direction, the most active research is undertaken in quantum computing. It is well known that quantum processes can drastically speed up computations; however, there are proven super-polynomial quantum speedups of the overall computation time. Parallelization is another potential source of speedup. In Euclidean space, parallelization only leads to a polynomial speedup. We show that in quantum space-time, parallelization could potentially lead to (provably) super-polynomial speedup of computations. c⃝2012 World Academic Press, UK. All rights reserved.

Journal of Uncertain Systems•Jan 1, 2011•0 citations
A pioneering treatise presenting how the new mathematical techniques of holographic duality unify seemingly unrelated fields of physics. This innovative development morphs quantum field theory, general relativity and the renormalisation group into a single computational framework and this book is the first to bring together a wide range of research in this rapidly developing field. Set within the context of condensed matter physics and using boxes highlighting the specific techniques required, it examines the holographic description of thermal properties of matter, Fermi liquids and superconductors, and hitherto unknown forms of macroscopically entangled quantum matter in terms of general relativity, stars and black holes. Showing that holographic duality can succeed where classic mathematical approaches fail, this text provides a thorough overview of this major breakthrough at the heart of modern physics. The inclusion of extensive introductory material using non-technical language and online Mathematica notebooks ensures the appeal to students and researchers alike.
What does it mean for the physically motivated computational complexity class BQP\mathcal{BQP}BQP and the logically motivated class NP\mathcal{NP}NP to be incomparable, from a physical perspective? Although it is unlikely that quantum computers can solve NP\mathcal{NP}NP-complete problems in polynomial time, yet it may be instructive to see how a physical theory (denoted Θ(NP)\Theta^{(\mathcal{NP})}Θ(NP) or Θ(PSPACE)\Theta^{(\mathcal{PSPACE})}Θ(PSPACE)) for which NP\mathcal{NP}NP or even PSPACE\mathcal{PSPACE}PSPACE, respectively, constitutes an efficient model of computation, would compare with quantum theory. The present work explores this question, after briefly reviewing some complexity results indicative of the incomparability of BQP\mathcal{BQP}BQP and NP\mathcal{NP}NP. We argue that theories Θ(NP)\Theta^{(\mathcal{NP})}Θ(NP) or Θ(PSPACE)\Theta^{(\mathcal{PSPACE})}Θ(PSPACE) effectively feature degrees of nonlinearity. Thus, the linearity of quantum theory prevents complete problems in these complexity classes to be efficiently solvable on a quantum computer. On the other hand, the exponentiality of quantum theory endows quantum computers with a certain strength going beyond NP\mathcal{NP}NP or even PH\mathcal{PH}PH. Thus the contrasting roles of the empowerment provided by quantum mechanical exponentiality and the limitation imposed by quantum mechanical linearity seem to be at the heart of the incomparability of the classes BQP\mathcal{BQP}BQP and NP\mathcal{NP}NP. Quanta 2025; 14: 38–47.
In theoretical computer science, researchers usually distinguish between feasible problems (that can be solved in polynomial time) and problems that require more computation time. A natural question is: can we use new physical processes, processes that have not been used in modern computers, to make computations drastically faster – e.g., to make intractable problems feasible? Such a possibility would occur if a physical process provides a super-polynomial ( = faster than polynomial) speed-up. In this direction, the most active research is undertaken in quantum computing. It is well known that quantum processes can drastically speed up computations; however, there are proven super-polynomial quantum speedups of the overall computation time. Parallelization is another potential source of speedup. In Euclidean space, parallelization only leads to a polynomial speedup. We show that in quantum space-time, parallelization could potentially lead to (provably) super-polynomial speedup of computations. c⃝2012 World Academic Press, UK. All rights reserved.