4 ms·
> It's possible that quantum optimizers could be exponentially faster than existing optimization techniques by evaluating multiple minima simultaneously. Is th
by typon 5y ago
> It's possible that quantum optimizers could be exponentially faster than existing optimization techniques by evaluating multiple minima simultaneously.
Is there any known quantum algorithm that gives a speedup over classical algorithms? I don't mean "call Grover as a subroutine" during your standard classical optimization algorithm.
- anon_tor_12345 5y agoI don't understand this question? Grover's algorithm is itself faster than classical search algos. It is as of yet unknown whether quantum computers are more powerful than classical computers; there is no proof that BQP is strictly bigger than P. There is oracle separation but that's not the same thing.
- sgt101 5y agoI think that BQP > P is not so important. Exponential advantage of known qalg vs known c_alg when the hardware is available is what's important.
- anon_tor_12345 5y agothat's what everyone says but imagine 10 years from now someone proves BQP < P. since that proof will entail a ptime reduction you'll immediately have a ptime shor's and etc.
- sgt101 5y agoWe have a p time Shor's ! I don't think BQP<P makes sense... BQP <NP? I think you may be mocking me :(
- sgt101 5y agoOh sure, Shore's. Also a bunch more.