A new paper appeared on arxiv: PSPACE ⊆ BQP by Shibdas Roy: https://arxiv.org/abs/2301.10557

From the 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, therefore, known to be in BQPSPACE. Here, we present a polynomial time quantum algorithm for a PSPACE-complete problem, implying that PSPACE is a subset of the class BQP of all problems solvable by a quantum computer in polynomial time. The paper is only 4 pages long.

Edit: I am now convinced this paper is in the very unlikely to be correct category. I am still interested in the following.

What would be the impact of proving this inclusion? Would it be a significant result?

  • 15
    $\begingroup$ 1. Very surprising. 2. Most probably, same as the dozens of other papers on the arXiv that prove P = NP, NP = PSPACE, negations thereof, and other things of that sort. $\endgroup$ Jan 27, 2023 at 17:52


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.