The number partitioning problem (NPP) is one of the NP-complete (nondeterministic polynomial-time complete) computational problems. Its definite exact solution generally requires a check of all $N$ solution candidates, which is exponentially large. Here we describe a path to the fast solution of this problem in $\sqrt{N}$ quasi-adiabatic quantum annealing steps. We argue that the errors due to the finite duration of the quantum annealing can be suppressed if the annealing time scales with $N$ only logarithmically. Moreover, our adiabatic oracle is topologically protected, in the sense that it is robust against small uncertainty and slow time dependence of the physical parameters or the choice of the annealing protocol. We also argue that our approach can solve many other famous NP-complete computational problems in $\sqrt{N}$ steps.
The number partitioning problem (NPP) is one of the NP-complete (nondeterministic polynomial-time complete) computational problems. Its definite exact solution generally requires a check of all N solution candidates, which is exponentially large. Here we describe a path to the fast solution of this problem in N quasi-adiabatic quantum annealing steps. We argue that the errors due to the finite duration of the quantum annealing can be suppressed if the annealing time scales with N only logarithmically. Moreover, our adiabatic oracle is topologically protected, in the sense that it is robust against small uncertainty and slow time dependence of the physical parameters or the choice of the annealing protocol. We also argue that our approach can solve many other famous NP-complete computational problems in N steps.
Numerous conceptually important quantum algorithms rely on a blackbox 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.
Grover's search algorithm was originally proposed for circuit-based quantum computers. A crucial part of it is to query an oracle -- a black-box unitary operation. Generation of this oracle is formally beyond the original algorithm design. Here, we propose a realization of Grover's oracle for a large class of searching problems using a quantum annealing step. The time of this step grows only logarithmically with the size of the database. This suggests an efficient path to application of Grover's algorithm to practically important problems, such as finding the ground state of a Hamiltonian with a spectral gap over its ground state.
Quantum adiabatic optimization (QAO) is performed using a time-dependent Hamiltonian H(s) with spectral gap γ(s). Assuming the existence of an oracle Γ such that $γ_\min = Θ\left(\min_sΓ(s)\right)$, we provide an algorithm that reliably performs QAO in time $O\left(γ_\min^{-1}\right)$ with $O\left(\log(γ_\min^{-1})\right)$ oracle queries, where $γ_\min = \min_s γ(s)$. Our strategy is not heuristic and does not require guessing time parameters or annealing paths. Rather, our algorithm naturally produces an annealing path such that ∥dH/ds∥≈γ(s) and chooses its own runtime to be as close as possible to optimal while promising convergence to the ground state. We then demonstrate the feasibility of this approach in practice by explicitly constructing a gap oracle Γ for the problem of finding the minimum point m=argminuW(u) of the cost function W:V⟶[0,1], restricting ourselves to computational basis measurements and driving Hamiltonian H(0)=I−∣V∣−1∑u,v∈V∣u⟩⟨v∣. Requiring only that W have a constant lower bound on its spectral gap and upper bound κ on its spectral ratio, our QAO algorithm returns m with probability (1−ε)(1−e−1/ε) in time O(ε−1[∣V∣+(κ−1)2/3∣V∣2/3]). This achieves a quantum advantage for all κ, and recovers Grover scaling up to logarithmic factors when κ≈1. We implement the algorithm as a subroutine in an optimization procedure that produces m with exponentially small failure probability and expected runtime O(ε−1[∣V∣+(κ−1)2/3∣V∣2/3]) even when κ is not known beforehand.
Grover's algorithm can solve NP-complete problems on quantum computers faster than all the known algorithms on classical computers. However, Grover's algorithm still needs exponential time. Due to the BBBV theorem, Grover's algorithm is optimal for searches in the domain of a function, when the function is used as a black box. We analyze the NP-complete set {(⟨M⟩,1n,1t)∣ TM M accepts an x∈{0,1}n within t steps}. If t is large enough, then M accepts each word in L(M) with length n within t steps. So, one can use methods from computability theory to show that black box searching is the fastest way to find a solution. Therefore, Grover's algorithm is optimal for NP-complete problems.
The Subset Sum Problem is a member of the NP-complete class, so no known polynomial time algorithm exists for it. Although there are polynomial time approximations and heuristics, these are not always acceptable, yet exact-solution algorithms are unfeasible for large input. Quantum computation offers new insights for not only the Subset Sum Problem but also the entire NP-complete class; most notably, Grover's quantum algorithm for an unstructured database search can be tailored to identify solutions to problems within mathematics and computer science. This paper discusses the physical and conceptual feasibility of quantum computation and demonstrates the utility of quantum search by analyzing the time complexities of the classical dynamic programming algorithm and Grover's algorithm in solving the Subset Sum Problem, evincing the implications this has on the NP-complete class in general.
The Travelling Salesman Problem (TSP) is a classic combinatorial optimisation problem which is NP-hard in optimisation form and NP-complete as a decision problem. The standard question asks for the shortest tour that visits every city exactly once and returns to the origin. This paper studies a threshold-fraction variant, which we call the robust TSP, formulated as a promise problem: given a distance threshold K and a promised fraction p, decide whether at least a fraction p of all tours have total length at most K, or whether no such tour exists. We show that Grover's quantum search algorithm decides this problem using O(1/p) oracle queries, independent of the number of cities N, with each query implemented by a quantum circuit of polynomial size in N. For any fixed robustness level p, the total runtime is therefore polynomial in N. Measured in oracle queries, the quantum algorithm offers a quadratic improvement in the dependence on 1/p over classical random sampling, which needs Θ(1/p) samples; because each quantum query is costly, however, it is faster in total running time only when p is very small (roughly below N−4), where the number of queries is no longer constant. We describe the problem formulation, detail the oracle construction (edge-length loading, sequential quantum addition, and threshold comparison), and analyse the query complexity to achieve the required result.