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

Conference on Innovations in Theoretical Computer Science

The Space "Just Above" BQP

Scott Aaronson, Adam Bouland, Joseph F. Fitzsimons, Mitchell Lee

Published Jan 5, 2016• 15 citations
Publisher

Abstract

We explore the space "just above" BQP by defining a complexity class naCQP (non-adaptive Collapse-free Quantum Polynomial time) which is larger than BQP but does not contain NP relative to an oracle. The class is defined by imagining that quantum computers can perform (non-adaptive) measurements that do not collapse the wavefunction. This non-physical model of computation can efficiently solve problems such as Graph Isomorphism and Approximate Shortest Vector which are believed to be intractable for quantum computers. Furthermore, it can search an unstructured N-element list in Õ(N1/3) time, but no faster than Ω(N1/4), and hence cannot solve NP-hard problems in a black box manner. In short, this model of computation is more powerful than standard quantum computation, but only slightly so. This is surprising as most modifications of BQP increase the power of quantum computation to NP or beyond.

DOI
10.1145/2840728.2840739

Related papers

The space "just above" BQP

Scott Aaronson, Adam Bouland, Joseph F. Fitzsimons +1 more

We explore the space "just above" BQP by defining a complexity class PDQP (Product Dynamical Quantum Polynomial time) which is larger than BQP but does not contain NP relative to an oracle. The class is defined by imagining that quantum computers can perform measurements that do not collapse the wavefunction. This (non-physical) model of computation can efficiently solve problems such as Graph Isomorphism and Approximate Shortest Vector which are believed to be intractable for quantum computers. Furthermore, it can search an unstructured N-element list in $\tilde O$(N^{1/3}) time, but no faster than Ω(N^{1/4}), and hence cannot solve NP-hard problems in a black box manner. In short, this model of computation is more powerful than standard quantum computation, but only slightly so. Our work is inspired by previous work of Aaronson on the power of sampling the histories of hidden variables. However Aaronson's work contains an error in its proof of the lower bound for search, and hence it is unclear whether or not his model allows for search in logarithmic time. Our work can be viewed as a conceptual simplification of Aaronson's approach, with a provable polynomial lower bound for search.

arXiv:1412.6507•Electronic colloquium on computational complexity•Dec 19, 2014•0 citations

The complexity class PDQP SPUR Final Paper: Summer 2013

Mitchell Lee, Adam Bouland, Scott Aaronson

Quantum computers are believed to be strictly more computationally powerful than classical computers, but not so much more powerful that they can solve NP-complete problems eciently. This is because of the result that a quantum computer takes ( N 1=2 ) time to search an unstructured N-element list for a particular marked item, as opposed to poly(logN) time for a nondeterministic computer. On the other hand, many seemingly innocuous modications of quantum mechanics increase the power of quantum computers drastically enough that they can solve NP-complete problems eciently [3]. This paper denes a model of computation slightly more powerful than quantum computation, but only slightly so. In particular, we show that by allowing \non-collapsing measurements, we can solve eciently problems such as Graph Isomorphism and Approximate Shortest Vector which are believed to be intractable for quantum computers. We can also search an unstructured N-element list for a particular marked item in ~ O(N 1=3 ) time, but no faster than ( N 1=4 ).

•Jan 1, 2013•0 citations

BQP is not in NP

J.T. Librande

Quantum computers are widely believed have an advantage over classical computers, and some have even published some empirical evidence that this is the case. However, these publications do not include a rigorous proof of this advantage, which would have to minimally state that the class of problems decidable by a quantum computer in polynomial time, BQP, contains problems that are not in the class of problems decidable by a classical computer with similar time bounds, P. Here, I provide the proof of a stronger result that implies this result: BQP contains problems that lie beyond the much larger classical computing class NP. This proves that quantum computation is able to efficiently solve problems which are far beyond the capabilities of classical computers.

arXiv:2209.10398•Sep 19, 2022•0 citations

New Lower-Bounds for Quantum Computation with Non-Collapsing Measurements

David Miloschewsky, Supartha Podder

Aaronson, Bouland, Fitzsimons and Lee introduced the complexity class PDQP (which was original labeled naCQP), an alteration of BQP enhanced with the ability to obtain non-collapsing measurements, samples of quantum states without collapsing them. Although PDQP contains SZK, it still requires $Ω(N^{1/4})$ queries to solve unstructured search. We formulate an alternative equivalent definition of PDQP, which we use to prove the positive weighted adversary lower-bounding method, establishing multiple tighter bounds and a trade-off between queries and non-collapsing measurements. We utilize the technique in order to analyze the query complexity of the well-studied majority and element distinctness problems. Additionally, we prove a tight $Θ(N^{1/3})$ bound on search. Furthermore, we use the lower-bound to explore PDQP under query restrictions, finding that when combined with non-adaptive queries, we limit the speed-up in several cases.

arXiv:2411.04085•Leibniz international proceedings in informatics•Nov 6, 2024•0 citations

A Collapse-free Quantum Algorithm for a Problem in QSZK

Henrique Hepp, Murilo V. G. da Silva, Leandro M. Zatesko

The complexity class of the problems that can be solved by a quantum algorithm in a non-adaptive collapse-free model is called naCQP. This class was introduced in 2016 by Aaronson et al. intended to be a slightly larger class than BQP: larger enough to include important NP-intermediate candidate problems, but likely not to include NP-complete problems. Aaronson et al. (2016) showed that there is an oracle A for which NPA ⊈ naCQPA; and Hepp et al. (2025) showed that relative to an oracle A chosen uniformly at random, (UP ∩ coUP)A ⊈ naCQPA with probability 1, being UP ∩ coUP a subclass of NP. Amongst the NP-intermediate candidate problems in naCQP is the entire class SZK, of the problems that admit a statistical zero-knowledge interactive proof system. The relation between QSZK, which is the class of the problems that admit a quantum zero-knowledge interactive proof system, and naCQP is unknown, with some believing that there is an oracle A for which QSZKA ⊈ naCQPA. A promise problem complete for QSZK is the trace distance distinguishability of mixed quantum states. We show that this problem, when restricted to pure quantum states, is in naCQP.

Anais do Encontro de Teoria da Computação (ETC)•Jul 17, 2025•0 citations

Quantum Algorithms in a Superposition of Spacetimes

Omri Shmueli

Quantum computers are expected to revolutionize our ability to process information. The advancement from classical to quantum computing is a product of our advancement from classical to quantum physics -- the more our understanding of the universe grows, so does our ability to use it for computation. A natural question that arises is, what will physics allow in the future? Can more advanced theories of physics increase our computational power, beyond quantum computing? An active field of research in physics studies theoretical phenomena outside the scope of explainable quantum mechanics, that form when attempting to combine Quantum Mechanics (QM) with General Relativity (GR) into a unified theory of Quantum Gravity (QG). QG is known to present the possibility of a quantum superposition of causal structure and event orderings. In the literature of quantum information theory, this translates to a superposition of unitary evolution orders. In this work we show a first example of a natural computational model based on QG, that provides an exponential speedup over standard quantum computation (under standard hardness assumptions). We define a model and complexity measure for a quantum computer that has the ability to generate a superposition of unitary evolution orders, and show that such computer is able to solve in polynomial time two of the fundamental problems in computer science: The Graph Isomorphism Problem ($\mathsf{GI}$) and the Gap Closest Vector Problem ($\mathsf{GapCVP}$), with gap $O\left( n \sqrt{n} \right)$. These problems are believed by experts to be hard to solve for a regular quantum computer. Interestingly, our model does not seem overpowered, and we found no obvious way to solve entire complexity classes that are considered hard in computer science, like the classes $\mathbf{NP}$ and $\mathbf{SZK}$.

arXiv:2403.02937•Mar 5, 2024•0 citations
We explore the space "just above" BQP by defining a complexity class naCQP (non-adaptive Collapse-free Quantum Polynomial time) which is larger than BQP but does not contain NP relative to an oracle. The class is defined by imagining that quantum computers can perform (non-adaptive) measurements that do not collapse the wavefunction. This non-physical model of computation can efficiently solve problems such as Graph Isomorphism and Approximate Shortest Vector which are believed to be intractable for quantum computers. Furthermore, it can search an unstructured N-element list in Õ(N1/3) time, but no faster than Ω(N1/4), and hence cannot solve NP-hard problems in a black box manner. In short, this model of computation is more powerful than standard quantum computation, but only slightly so. This is surprising as most modifications of BQP increase the power of quantum computation to NP or beyond.
We explore the space "just above" BQP by defining a complexity class PDQP (Product Dynamical Quantum Polynomial time) which is larger than BQP but does not contain NP relative to an oracle. The class is defined by imagining that quantum computers can perform measurements that do not collapse the wavefunction. This (non-physical) model of computation can efficiently solve problems such as Graph Isomorphism and Approximate Shortest Vector which are believed to be intractable for quantum computers. Furthermore, it can search an unstructured N-element list in O~\tilde OO~(N^{1/3}) time, but no faster than Ω(N^{1/4}), and hence cannot solve NP-hard problems in a black box manner. In short, this model of computation is more powerful than standard quantum computation, but only slightly so. Our work is inspired by previous work of Aaronson on the power of sampling the histories of hidden variables. However Aaronson's work contains an error in its proof of the lower bound for search, and hence it is unclear whether or not his model allows for search in logarithmic time. Our work can be viewed as a conceptual simplification of Aaronson's approach, with a provable polynomial lower bound for search.
Quantum computers are believed to be strictly more computationally powerful than classical computers, but not so much more powerful that they can solve NP-complete problems eciently. This is because of the result that a quantum computer takes ( N 1=2 ) time to search an unstructured N-element list for a particular marked item, as opposed to poly(logN) time for a nondeterministic computer. On the other hand, many seemingly innocuous modications of quantum mechanics increase the power of quantum computers drastically enough that they can solve NP-complete problems eciently [3]. This paper denes a model of computation slightly more powerful than quantum computation, but only slightly so. In particular, we show that by allowing \non-collapsing measurements, we can solve eciently problems such as Graph Isomorphism and Approximate Shortest Vector which are believed to be intractable for quantum computers. We can also search an unstructured N-element list for a particular marked item in ~ O(N 1=3 ) time, but no faster than ( N 1=4 ).
Quantum computers are widely believed have an advantage over classical computers, and some have even published some empirical evidence that this is the case. However, these publications do not include a rigorous proof of this advantage, which would have to minimally state that the class of problems decidable by a quantum computer in polynomial time, BQP, contains problems that are not in the class of problems decidable by a classical computer with similar time bounds, P. Here, I provide the proof of a stronger result that implies this result: BQP contains problems that lie beyond the much larger classical computing class NP. This proves that quantum computation is able to efficiently solve problems which are far beyond the capabilities of classical computers.
Aaronson, Bouland, Fitzsimons and Lee introduced the complexity class PDQP (which was original labeled naCQP), an alteration of BQP enhanced with the ability to obtain non-collapsing measurements, samples of quantum states without collapsing them. Although PDQP contains SZK, it still requires Ω(N1/4)Ω(N^{1/4})Ω(N1/4) queries to solve unstructured search. We formulate an alternative equivalent definition of PDQP, which we use to prove the positive weighted adversary lower-bounding method, establishing multiple tighter bounds and a trade-off between queries and non-collapsing measurements. We utilize the technique in order to analyze the query complexity of the well-studied majority and element distinctness problems. Additionally, we prove a tight Θ(N1/3)Θ(N^{1/3})Θ(N1/3) bound on search. Furthermore, we use the lower-bound to explore PDQP under query restrictions, finding that when combined with non-adaptive queries, we limit the speed-up in several cases.
The complexity class of the problems that can be solved by a quantum algorithm in a non-adaptive collapse-free model is called naCQP. This class was introduced in 2016 by Aaronson et al. intended to be a slightly larger class than BQP: larger enough to include important NP-intermediate candidate problems, but likely not to include NP-complete problems. Aaronson et al. (2016) showed that there is an oracle A for which NPA ⊈ naCQPA; and Hepp et al. (2025) showed that relative to an oracle A chosen uniformly at random, (UP ∩ coUP)A ⊈ naCQPA with probability 1, being UP ∩ coUP a subclass of NP. Amongst the NP-intermediate candidate problems in naCQP is the entire class SZK, of the problems that admit a statistical zero-knowledge interactive proof system. The relation between QSZK, which is the class of the problems that admit a quantum zero-knowledge interactive proof system, and naCQP is unknown, with some believing that there is an oracle A for which QSZKA ⊈ naCQPA. A promise problem complete for QSZK is the trace distance distinguishability of mixed quantum states. We show that this problem, when restricted to pure quantum states, is in naCQP.
Quantum computers are expected to revolutionize our ability to process information. The advancement from classical to quantum computing is a product of our advancement from classical to quantum physics -- the more our understanding of the universe grows, so does our ability to use it for computation. A natural question that arises is, what will physics allow in the future? Can more advanced theories of physics increase our computational power, beyond quantum computing? An active field of research in physics studies theoretical phenomena outside the scope of explainable quantum mechanics, that form when attempting to combine Quantum Mechanics (QM) with General Relativity (GR) into a unified theory of Quantum Gravity (QG). QG is known to present the possibility of a quantum superposition of causal structure and event orderings. In the literature of quantum information theory, this translates to a superposition of unitary evolution orders. In this work we show a first example of a natural computational model based on QG, that provides an exponential speedup over standard quantum computation (under standard hardness assumptions). We define a model and complexity measure for a quantum computer that has the ability to generate a superposition of unitary evolution orders, and show that such computer is able to solve in polynomial time two of the fundamental problems in computer science: The Graph Isomorphism Problem (GI\mathsf{GI}GI) and the Gap Closest Vector Problem (GapCVP\mathsf{GapCVP}GapCVP), with gap O(nn)O\left( n \sqrt{n} \right)O(nn​). These problems are believed by experts to be hard to solve for a regular quantum computer. Interestingly, our model does not seem overpowered, and we found no obvious way to solve entire complexity classes that are considered hard in computer science, like the classes NP\mathbf{NP}NP and SZK\mathbf{SZK}SZK.