Re:A Model of a Mind
by oersted on Tuesday July 02, 2024 @04:52AM
(#40854753)
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.
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.