Re:Google Announced their D-Wave 2X Quantum Computer Works (...
by maxander on Tuesday May 10, 2016 @04:26PM
(#11670374)
I was about to post the very same quotation.
Its not naively clear where the line is drawn between "speedup that could be obtained through clever heuristic/nondeterministic/whatever classical algorithms" and "speedup that is necessarily the domain of quantum computation." I suspect the question is a deep (open?) one in computational complexity theory.
Its not naively clear where the line is drawn between "speedup that could be obtained through clever heuristic/nondeterministic/whatever classical algorithms" and "speedup that is necessarily the domain of quantum computation." I suspect the question is a deep (open?) one in computational complexity theory.