2 ms·
That's true but Grover search shows that quantum computers can give big speedups so I don't know why I would believe BPP=BQP.
by wbl 7y ago
That's true but Grover search shows that quantum computers can give big speedups so I don't know why I would believe BPP=BQP.
- nabla9 7y agoGrover's algorithm still takes exponentially many operations to solve a search problem that can be brute-forced in exponentially many steps. Much faster, but still in EXPTIME. No jump from exponential to polynomial complexity class.