Speeding Up Number Partitioning with Grover's Algorithm

A number of conceptually important quantum algorithms rely on the use of a black-box device known as an oracle, which is typically difficult to construct without knowing the answer to the problem that the quantum computer is intended to solve. A notable example is Grover's algorithm, which theoretically can offer a quadratic speed-up in search problems. Here we show how Grover's algorithm can be applied to a class of NP-complete decision problems---the subset sum problem and, as a special case, the number partitioning problem---in realistic experiments. Each instance of the problem is encoded in the strengths of couplings of a set of qubits to a central spin or boson, which mediates a collective phase gate consituting the quantum oracle. We propose and analyze implementations in cavity-QED and Rydberg-atom systems.