  Numerous conceptually important quantum algorithms rely on a black-box device
known as an oracle, which is typically difficult to construct without knowing
the answer to the problem that the algorithm is intended to solve. A notable
example is Grover's search algorithm. Here we propose a Grover search for
solutions to a class of NP-complete decision problems known as subset sum
problems, including the special case of number partitioning. Each problem
instance is encoded in the couplings of a set of qubits to a central spin or
boson, which enables a realization of the oracle without knowledge of the
solution. The algorithm provides a quantum speedup across a known phase
transition in the computational complexity of the partition problem, and we
identify signatures of the phase transition in the simulated performance.
Whereas the naive implementation of our algorithm requires a spectral
resolution that scales exponentially with system size for NP-complete problems,
we also present a recursive algorithm that enables scalability. We propose and
analyze implementation schemes with cold atoms, including Rydberg-atom and
cavity-QED platforms.
