3 ms·
> Its suspected P lies entirely within BQP. It's actually known that BQP contains P[1]. It also contains BPP. What's not known is the relationship between BQP
by moefh 8y ago
> Its suspected P lies entirely within BQP.
It's actually known that BQP contains P[1]. It also contains BPP. What's not known is the relationship between BQP and NP (most experts suspect there's no containment in either direction).
[1] See this for an easy proof: https://people.eecs.berkeley.edu/~vazirani/f04quantum/notes/lec5/lec5.pdf https://people.eecs.berkeley.edu/~vazirani/f04quantum/notes/...
- foxes 8y agoYes sorry you are right. I found this nice example of Grover's algorithm [0]. [0] http://davidbkemp.github.io/animated-qubits/grover.html http://davidbkemp.github.io/animated-qubits/grover.html
- hrygolis 8y agohttps://www.quantamagazine.org/finally-a-problem-that-only-quantum-computers-will-ever-be-able-to-solve-20180621/ https://www.quantamagazine.org/finally-a-problem-that-only-q...
- moefh 8y agoThat's still only relative to an oracle, though (i.e., BQP^O vs NP^O). We also have oracle separations of P and NP, and that proves nothing about P vs NP without an oracle.