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:2301.10557

BQP === PSPACE

Shibdas Roy

Published Jan 24, 2023• 0 citations
arXivHTMLPDF

Abstract

The complexity class $PSPACE$ includes all computational problems that can be solved by a classical computer with polynomial memory. All $PSPACE$ problems are known to be solvable by a quantum computer too with polynomial memory and are, thus, known to be in $BQPSPACE$. Here, we present a polynomial time quantum algorithm for a $PSPACE$-complete problem, implying that $PSPACE$ is equal to the class $BQP$ of all problems solvable by a quantum computer in polynomial time. In particular, we outline a $BQP$ algorithm for the $PSPACE$-complete problem of evaluating a full binary $NAND$ tree. An existing best of quadratic speedup is achieved using quantum walks for this problem, so that the complexity is still exponential in the problem size. By contrast, we achieve an exponential speedup for the problem, allowing for solving it in polynomial time. There are many real-world applications of our result, such as strategy games like chess or Go. As an example, in quantum sensing, the problem of quantum illumination, that is treated as that of channel discrimination, is $PSPACE$-complete. Our work implies that quantum channel discrimination, and so, quantum illumination, can be performed efficiently by a quantum computer.

DOI
10.48550/arxiv.2301.10557

Related papers

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

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

Computational Distinguishability of Quantum Channels

Bill Rosgen

The computational problem of distinguishing two quantum channels is central to quantum computing. It is a generalization of the well-known satisfiability problem from classical to quantum computation. This problem is shown to be surprisingly hard: it is complete for the class QIP of problems that have quantum interactive proof systems, which implies that it is hard for the class PSPACE of problems solvable by a classical computation in polynomial space. Several restrictions of distinguishability are also shown to be hard. It is no easier when restricted to quantum computations of logarithmic depth, to mixed-unitary channels, to degradable channels, or to antidegradable channels. These hardness results are demonstrated by finding reductions between these classes of quantum channels. These techniques have applications outside the distinguishability problem, as the construction for mixed-unitary channels is used to prove that the additivity problem for the classical capacity of quantum channels can be equivalently restricted to the mixed unitary channels.

arXiv:0909.3930•Sep 22, 2009•9 citations

Polynomial T-depth quantum solvability of noisy binary linear problem: from quantum-sample preparation to main computation

Wooyeong Song, Youngrong Lim, Kabgyun Jeong +4 more

Abstract The noisy binary linear problem (NBLP) is known as a computationally hard problem, and therefore, it offers primitives for post-quantum cryptography. An efficient quantum NBLP algorithm that exhibits a polynomial quantum sample and time complexities has recently been proposed. However, the algorithm requires a large number of samples to be loaded in a highly entangled state and it is unclear whether such a precondition on the quantum speedup can be obtained efficiently. Here, we present a complete analysis of the quantum solvability of the NBLP by considering the entire algorithm process, namely from the preparation of the quantum sample to the main computation. By assuming that the algorithm runs on ‘fault-tolerant’ quantum circuitry, we introduce a reasonable measure of the computational time cost. The measure is defined in terms of the overall number of T gate layers, referred to as T-depth complexity. We show that the cost of solving the NBLP can be polynomial in the problem size, at the expense of an exponentially increasing logical qubits.

arXiv:2109.11186•New Journal of Physics•Sep 26, 2022•3 citations

NP in BQP by Partial Measurement

Phil Gossett

Abstract: By allowing measurement (read-out) of some, but not all, qubits, this paper shows that NP-complete problems are efficiently solvable by quantum computers in polynomial time with bounded probability (NP in BQP). This is demonstrated by describing a polynomially large network of quantum gates that solves the 3SAT problem with bounded probability in polynomial time. The “weak Church-Turing thesis ” is thus shown to be false. 1.

•Jan 1, 1998•0 citations

Quantum computing, postselection, and probabilistic polynomial-time

Scott Aaronson

I study the class of problems efficiently solvable by a quantum computer, given the ability to ‘postselect’ on the outcomes of measurements. I prove that this class coincides with a classical complexity class called PP, or probabilistic polynomial-time. Using this result, I show that several simple changes to the axioms of quantum mechanics would let us solve PP-complete problems efficiently. The result also implies, as an easy corollary, a celebrated theorem of Beigel, Reingold and Spielman that PP is closed under intersection, as well as a generalization of that theorem due to Fortnow and Reingold. This illustrates that quantum computing can yield new and simpler proofs of major results about classical computation.

Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences•Sep 5, 2005•315 citations
The complexity class PSPACEPSPACEPSPACE includes all computational problems that can be solved by a classical computer with polynomial memory. All PSPACEPSPACEPSPACE problems are known to be solvable by a quantum computer too with polynomial memory and are, thus, known to be in BQPSPACEBQPSPACEBQPSPACE. Here, we present a polynomial time quantum algorithm for a PSPACEPSPACEPSPACE-complete problem, implying that PSPACEPSPACEPSPACE is equal to the class BQPBQPBQP of all problems solvable by a quantum computer in polynomial time. In particular, we outline a BQPBQPBQP algorithm for the PSPACEPSPACEPSPACE-complete problem of evaluating a full binary NANDNANDNAND tree. An existing best of quadratic speedup is achieved using quantum walks for this problem, so that the complexity is still exponential in the problem size. By contrast, we achieve an exponential speedup for the problem, allowing for solving it in polynomial time. There are many real-world applications of our result, such as strategy games like chess or Go. As an example, in quantum sensing, the problem of quantum illumination, that is treated as that of channel discrimination, is PSPACEPSPACEPSPACE-complete. Our work implies that quantum channel discrimination, and so, quantum illumination, can be performed efficiently by a quantum computer.
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.
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.
The computational problem of distinguishing two quantum channels is central to quantum computing. It is a generalization of the well-known satisfiability problem from classical to quantum computation. This problem is shown to be surprisingly hard: it is complete for the class QIP of problems that have quantum interactive proof systems, which implies that it is hard for the class PSPACE of problems solvable by a classical computation in polynomial space. Several restrictions of distinguishability are also shown to be hard. It is no easier when restricted to quantum computations of logarithmic depth, to mixed-unitary channels, to degradable channels, or to antidegradable channels. These hardness results are demonstrated by finding reductions between these classes of quantum channels. These techniques have applications outside the distinguishability problem, as the construction for mixed-unitary channels is used to prove that the additivity problem for the classical capacity of quantum channels can be equivalently restricted to the mixed unitary channels.
Abstract The noisy binary linear problem (NBLP) is known as a computationally hard problem, and therefore, it offers primitives for post-quantum cryptography. An efficient quantum NBLP algorithm that exhibits a polynomial quantum sample and time complexities has recently been proposed. However, the algorithm requires a large number of samples to be loaded in a highly entangled state and it is unclear whether such a precondition on the quantum speedup can be obtained efficiently. Here, we present a complete analysis of the quantum solvability of the NBLP by considering the entire algorithm process, namely from the preparation of the quantum sample to the main computation. By assuming that the algorithm runs on ‘fault-tolerant’ quantum circuitry, we introduce a reasonable measure of the computational time cost. The measure is defined in terms of the overall number of T gate layers, referred to as T-depth complexity. We show that the cost of solving the NBLP can be polynomial in the problem size, at the expense of an exponentially increasing logical qubits.
I study the class of problems efficiently solvable by a quantum computer, given the ability to ‘postselect’ on the outcomes of measurements. I prove that this class coincides with a classical complexity class called PP, or probabilistic polynomial-time. Using this result, I show that several simple changes to the axioms of quantum mechanics would let us solve PP-complete problems efficiently. The result also implies, as an easy corollary, a celebrated theorem of Beigel, Reingold and Spielman that PP is closed under intersection, as well as a generalization of that theorem due to Fortnow and Reingold. This illustrates that quantum computing can yield new and simpler proofs of major results about classical computation.