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:1412.6507 · Electronic colloquium on computational complexity

The space "just above" BQP

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

Published Dec 19, 2014• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.1412.6507

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 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.

Conference on Innovations in Theoretical Computer Science•Jan 5, 2016•15 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

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

Quantum Computing and Hidden Variables II: The Complexity of Sampling Histories

Scott Aaronson

This paper shows that, if we could examine the entire history of a hidden variable, then we could efficiently solve problems that are believed to be intractable even for quantum computers. In particular, under any hidden-variable theory satisfying a reasonable axiom called "indifference to the identity," we could solve the Graph Isomorphism and Approximate Shortest Vector problems in polynomial time, as well as an oracle problem that is known to require quantum exponential time. We could also search an N-item database using O(N^{1/3}) queries, as opposed to O(N^{1/2}) queries with Grover's search algorithm. On the other hand, the N^{1/3} bound is optimal, meaning that we could probably not solve NP-complete problems in polynomial time. We thus obtain the first good example of a model of computation that appears slightly more powerful than the quantum computing model.

arXiv:quant-ph/0408119•Aug 19, 2004•8 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

BQP, Meet NP: Search-To-Decision Reductions and Approximate Counting

Sevag Gharibian, Jonas Kamminga

What is the power of polynomial-time quantum computation with access to an NP oracle? In this work, we focus on two fundamental tasks from the study of Boolean satisfiability (SAT) problems: search-to-decision reductions, and approximate counting. We first show that, in strong contrast to the classical setting where a poly-time Turing machine requires $Θ(n)$ queries to an NP oracle to compute a witness to a given SAT formula, quantumly $Θ(\log n)$ queries suffice. We then show this is tight in the black-box model - any quantum algorithm with "NP-like" query access to a formula requires $Ω(\log n)$ queries to extract a solution with constant probability. Moving to approximate counting of SAT solutions, by exploiting a quantum link between search-to-decision reductions and approximate counting, we show that existing classical approximate counting algorithms are likely optimal. First, we give a lower bound in the "NP-like" black-box query setting: Approximate counting requires $Ω(\log n)$ queries, even on a quantum computer. We then give a "white-box" lower bound (i.e. where the input formula is not hidden in the oracle) - if there exists a randomized poly-time classical or quantum algorithm for approximate counting making $o(log n)$ NP queries, then $\text{BPP}^{\text{NP}[o(n)]}$ contains a $\text{P}^{\text{NP}}$-complete problem if the algorithm is classical and $\text{FBQP}^{\text{NP}[o(n)]}$ contains an $\text{FP}^{\text{NP}}$-complete problem if the algorithm is quantum.

arXiv:2401.03943•Leibniz international proceedings in informatics•Jan 1, 2024•0 citations
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.
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.
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 ).
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.
This paper shows that, if we could examine the entire history of a hidden variable, then we could efficiently solve problems that are believed to be intractable even for quantum computers. In particular, under any hidden-variable theory satisfying a reasonable axiom called "indifference to the identity," we could solve the Graph Isomorphism and Approximate Shortest Vector problems in polynomial time, as well as an oracle problem that is known to require quantum exponential time. We could also search an N-item database using O(N^{1/3}) queries, as opposed to O(N^{1/2}) queries with Grover's search algorithm. On the other hand, the N^{1/3} bound is optimal, meaning that we could probably not solve NP-complete problems in polynomial time. We thus obtain the first good example of a model of computation that appears slightly more powerful than the quantum computing model.
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.
What is the power of polynomial-time quantum computation with access to an NP oracle? In this work, we focus on two fundamental tasks from the study of Boolean satisfiability (SAT) problems: search-to-decision reductions, and approximate counting. We first show that, in strong contrast to the classical setting where a poly-time Turing machine requires Θ(n)Θ(n)Θ(n) queries to an NP oracle to compute a witness to a given SAT formula, quantumly Θ(log⁡n)Θ(\log n)Θ(logn) queries suffice. We then show this is tight in the black-box model - any quantum algorithm with "NP-like" query access to a formula requires Ω(log⁡n)Ω(\log n)Ω(logn) queries to extract a solution with constant probability. Moving to approximate counting of SAT solutions, by exploiting a quantum link between search-to-decision reductions and approximate counting, we show that existing classical approximate counting algorithms are likely optimal. First, we give a lower bound in the "NP-like" black-box query setting: Approximate counting requires Ω(log⁡n)Ω(\log n)Ω(logn) queries, even on a quantum computer. We then give a "white-box" lower bound (i.e. where the input formula is not hidden in the oracle) - if there exists a randomized poly-time classical or quantum algorithm for approximate counting making o(logn)o(log n)o(logn) NP queries, then BPPNP[o(n)]\text{BPP}^{\text{NP}[o(n)]}BPPNP[o(n)] contains a PNP\text{P}^{\text{NP}}PNP-complete problem if the algorithm is classical and FBQPNP[o(n)]\text{FBQP}^{\text{NP}[o(n)]}FBQPNP[o(n)] contains an FPNP\text{FP}^{\text{NP}}FPNP-complete problem if the algorithm is quantum.