A press release claims: 'Our quantum processor solved a scheduling problem with…
PHYSICS · Multi-part · Fermi University Physics · Quantum Information & Technology · The quantum circuit model and quantum algorithms · The quantum circuit model and quantum algorithms
Quantum Information and Technology, Ch What quantum computers can compute efficiently
Problem
A press release claims: 'Our quantum processor solved a scheduling problem with 300 yes/no scheduling decisions in 2s; the fastest classical supercomputer needed 63 years. That is a speed-up of about a billion.' The scheduling problem, stated as a decision problem (can all 300 tasks be scheduled subject to the given constraints?), is known to be NP-complete.
((a)) Treating the 300 scheduling decisions as 300 Boolean variables in a satisfiability-style formulation, estimate the number of Grover iterations needed to search for a satisfying assignment, and the time this would take at an assumed 1μs per iteration. Compare this with both the claimed 2s quantum runtime and the quoted 63 years classical runtime.
((b)) State whether a billion-fold speed-up on an NP-complete problem is consistent with what is known and proved about quantum algorithms for such problems, and say what this implies about the quantum runtime, the classical comparator, or the instance itself.
((c)) In one paragraph, evaluate the press claim: name the problem, the comparator it should have been measured against, and the evidence that would be needed before accepting 'a billion times faster' as a claim about quantum computation rather than about one instance and one classical program.