Hacker News new | ask | show | jobs
by oersted 718 days ago
BQP (Bounded-error Quantum Polynomial-time) is in PSPACE sure, but that doesn't mean much.

P ⊆ BPP ⊆ BQP ⊆ PSPACE

BQP problems can be solved on quantum computers in polynomial time, some of these problems may be outside of P and BPP (Bounded-error Probabilistic Polynomial-time), so they may not be possible to solve in polynomial time in classical computers, even with probabilistic algorithms.

It is true that there's still room for BPP = BQP, that has not been disproven, but it is somewhat controversial to expect so, at this point many smart people have spent their lifetimes prodding at it.