3 ms·
> We note that there exist heuristic classical algorithms that can solve most instances of Chimera structured problems in a timescale comparable to the D-Wave 2
by toxikitty_ 10y ago
> We note that there exist heuristic classical algorithms that can solve most instances of Chimera structured problems in a timescale comparable to the D-Wave 2X. However, we believe that such solvers will become ineffective for the next generation of annealers currently being designed.
From the abstract.
- maxander 10y agoI 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.
- nickpsecurity 10y agoI was wondering if these exist. My last counter of D-Wave is they could be using a good algorithm with specialized ASIC's or regular HPC hardware in a cluster. As in, they're certainly accelerating things but making up the quantum part. That possibility has to be eliminated. That there's classical algorithms that might get a similar speedup, esp if on custom hardware, validates my prior concern.