Quantum advantage in deciding NP-complete problems

Grover’s unstructured quantum search algorithm gives a quadratic speedup over classical linear search, provided that multiple accesses to the oracle are possible. In this paper, we show that in dealing with NP-complete decision-version problems, the quantum computing paradigm still outperforms classical computation, even if only one invocation of the oracle is allowed. The superiority of the quantum approach under such a restrictive condition can often be maintained even if a simple measurement strategy is chosen. A quantum decider utilizing only Hadamard gates and measurements in the computational basis has a better chance of discriminating between a problem with solution(s) and one without, when compared to the best separation achieved by a classical decider. In addition, the simple quantum measurement strategy is remarkably close to the optimal discriminating measurement, which itself is considerably more complex to devise and implement. If we further require the decider to be unambiguous (any definitive answer must be error-free), then a general positive operator-valued measurement can be devised to classify a problem as unsolvable, with some probability, after one consultation of the oracle. Such a feature remains impossible for a classical decider, even after any less than exhaustive oracle invocations. The inherent probabilistic nature of quantum mechanics seems to be at the heart of the advantage quantum computing exhibits over classical computation, in the context of deciding NP-complete problems based on a single oracle query.