Number Partitioning With Grover’s Algorithm in Central Spin Systems
Galit Anikeeva, Ognjen Marković, Victoria Borish, Jacob Hines, S. Rajagopal, Eric S. Cooper, Avikar Periwal, Amir H. Safavi‐Naeini, Emily J. Davis, Monika Schleier-Smith
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.
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.
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.
Graph partitioning is a fundamental problem in computer science with applications in diverse fields like network design, compiler optimization, and data analysis. Traditional algorithms for graph partitioning often suffer from computational complexity, particularly when dealing with large graphs. This paper explores the potential of utilizing quantum computing to accelerate graph partitioning. Specifically, we investigate the application of Grover's algorithm, a quantum search algorithm, to the problem. Our core claim is that by leveraging the superposition and interference capabilities inherent in quantum mechanics, a quantum solution can achieve a provable speedup compared to classical approaches. We present a theoretical framework outlining the algorithm's operation and derive the expected speedup. The key mathematical formulation involves representing the graph partitioning problem as an unstructured search problem amenable to Grover's algorithm. We define the problem as minimizing the cut size, represented by the objective function: *f(S) = Σi∈S Σj∈Sc d(i, j)* where *S* is a subset of vertices, *Sc* is the complement of *S* in the graph, and *d(i, j)* is the shortest path distance between vertices *i* and *j*. The algorithm then constructs a quantum oracle that maps the problem state to a superposition of all possible partitions. Grover's algorithm is then applied to amplify the amplitude of the solution state, resulting in a high probability of finding an optimal or near-optimal partition. The speedup is directly proportional to the square root of the number of iterations performed by Grover's algorithm, which is influenced by the problem size and the quality of the oracle. We analyze the complexity of the quantum algorithm and compare it to the complexity of the best-known classical algorithms, demonstrating a potential for significant speedup. Further research will focus on optimizing the oracle construction and exploring other quantum algorithms suitable for graph partitioning.
We investigate the implementation of an oracle for the Subset Sum problem for quantum search using Grover's algorithm. Our work concerns reducing the number of qubits, gates, and multi-controlled gates required by the oracle. We describe the compilation of a Subset Sum instance into a quantum oracle, using a Python library we developed for Qiskit and have published in GitHub. We then present techniques to conserve qubits and gates along with experiments showing their effectiveness on random instances of Subset Sum. These techniques include moving from fixed to varying-width arithmetic, using partial sums of a set's integers to determine specific integer widths, and sorting the set to obtain provably the most efficient partial sums. We present a new method for computing bit-string comparisons that avoids arbitrarily large multiple-control gates, and we introduce a simple modification to the oracle that allows for approximate solutions to the Subset Sum problem via Grover search.
Grover’s algorithm is one of the primary algorithms offered as evidence that quantum computers can provide an advantage over classical computers. It involves an “oracle” (external quantum subroutine), which must be specified for a given application and whose internal structure is not part of the formal scaling of the quadratic quantum speedup guaranteed by the algorithm. Grover’s algorithm also requires exponentially many calls to the quantum oracle (approximately 2 n calls where n is the number of qubits) to succeed, raising the question of its implementation on both noisy and error-corrected quantum computers. In this work, we construct a quantum-inspired algorithm executable on a classical computer that performs Grover’s task in a linear number of calls to (simulations of) the oracle—an exponentially smaller number than Grover’s algorithm—and demonstrate this algorithm explicitly for Boolean satisfiability problems. The complexity of our algorithm depends on the cost to simulate the oracle once, which may or may not be exponential, depending on its internal structure. Indeed, Grover’s algorithm does not have an quantum speedup as soon as one is given access to the “source code” of the oracle, which may reveal an internal structure of the problem. Our findings illustrate this point explicitly, as our algorithm exploits the structure of the quantum circuit used to program the quantum computer to speed up the search. There are still problems where Grover’s algorithm would provide an asymptotic speedup if it could be run accurately for large enough sizes. Our quantum-inspired algorithm provides lower bounds, in terms of the quantum-circuit complexity, for the quantum hardware to beat classical approaches for these problems. These estimates, combined with the unfavorable scaling of the success probability of Grover’s algorithm, which in the presence of noise decays as the exponential of the exponential of the number of qubits, makes a practical speedup unrealistic even under extremely optimistic assumptions of the evolution of both hardware quality and availability. Published by the American Physical Society 2024
This paper presents an enhancement to Grover's search algorithm for instances where the number of items (or the size of the search problem) N is not a power of 2. By employing an efficient algorithm for the preparation of uniform quantum superposition states over a subset of the computational basis states, we demonstrate that a considerable reduction in the number of oracle calls (and Grover's iterations) can be achieved in many cases. For special cases (i.e., when N is of the form such that it is slightly greater than an integer power of 2), the reduction in the number of oracle calls (and Grover's iterations) asymptotically approaches 29.33\%. This improvement is significant compared to the traditional Grover's algorithm, which handles such cases by rounding N up to the nearest power of 2. The key to this improvement is our algorithm for the preparation of uniform quantum superposition states over a subset of the computational basis states, which requires gate complexity and circuit depth of only $ O (\log_2 (N)) $, without using any ancilla qubits.
The Grover quantum search algorithm is a hallmark application of a quantum computer with a well-known speedup over classical searches of an unsorted database. Here, we report results for a complete three-qubit Grover search algorithm using the scalable quantum computing technology of trapped atomic ions, with better-than-classical performance. Two methods of state marking are used for the oracles: a phase-flip method employed by other experimental demonstrations, and a Boolean method requiring an ancilla qubit that is directly equivalent to the state marking scheme required to perform a classical search. We also report the deterministic implementation of a Toffoli-4 gate, which is used along with Toffoli-3 gates to construct the algorithms; these gates have process fidelities of 70.5% and 89.6%, respectively.