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.
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 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
Quantum search is one of the most important algorithmic developments in quantum computing because it demonstrates how quantum principles can improve the efficiency of solving unstructured search problems. Grover’s algorithm provides a quadratic speed-up over classical linear search by reducing query complexity from O(N) to O(√N), where N represents the size of the search space. This review examines the principles, performance, and applications of Grover’s algorithm, with emphasis on its theoretical foundation and practical relevance. The discussion covers the roles of superposition, quantum interference, oracle operations, diffusion operators, and amplitude amplification in increasing the probability of measuring a desired solution. The manuscript also reviews the computational performance of quantum search in comparison with classical search methods and considers its relevance to database searching, combinatorial optimisation, cryptography, machine learning, bioinformatics, quantum chemistry, and materials science. The review highlights that Grover’s algorithm is not limited to database retrieval, as many computationally intensive problems can be reformulated as search or optimisation tasks. However, practical implementation remains constrained by current quantum hardware limitations, including decoherence, quantum noise, limited qubit availability, circuit depth, and the difficulty of designing efficient oracles. Despite these challenges, continuing progress in quantum hardware, error correction, cloud-based quantum platforms, and hybrid quantum-classical architectures suggests that quantum search will remain an important area of research. Overall, Grover’s algorithm represents a foundational quantum algorithm with significant theoretical value and potential long-term application in computational domains involving large and unstructured search spaces.
The steadily growing research interest in quantum computing - together with the accompanying technological advances in the realization of quantum hardware - fuels the development of meaningful real-world applications, as well as implementations for well-known quantum algorithms. One of the most prominent examples till today is Grover's algorithm, which can be used for efficient search in unstructured databases. Quantum oracles that are frequently masked as black boxes play an important role in Grover's algorithm. Hence, the automatic generation of oracles is of paramount importance. Moreover, the automatic generation of the corresponding circuits for a Grover quantum oracle is deeply linked to the synthesis of reversible quantum logic, which - despite numerous advances in the field - still remains a challenge till today in terms of synthesizing efficient and scalable circuits for complex boolean functions. In this paper, we present a flexible method for automatically encoding unstructured databases into oracles, which can then be efficiently searched with Grover's algorithm. Furthermore, we develop a tailor-made method for quantum logic synthesis, which vastly improves circuit complexity over other current approaches. Finally, we present another logic synthesis method that considers the requirements of scaling onto real world backends. We compare our method with other approaches through evaluating the oracle generation for random databases and analyzing the resulting circuit complexities using various metrics.
Grover's algorithm, orginally conceived as a means of searching an unordered database, can also be used to extract solutions from the result sets generated by quantum computations. The Grover algorithm exploits the concept of an oracle function, which abstracts the process of matching a search item (returning 1 for a match and 0 otherwise), where searching for 1 target item in a search space of size N scales as O(N) oracle queries. In this article, we explore the idea of associating a separate oracle with each bit of the matching condition, obtaining multiple partial oracle functions which can be tested independently. Exploring this idea leads to a multi-stage hybrid search algorithm, whose performance can fall within a wide range, anywhere between O(N) (same as Grover) or O(log(N)). The algorithm is validated against the simplest kind of search scenario, where the incoming index bits are scrambled using a permutation operation.
Abstract The steadily growing research interest in quantum computing—together with the accompanying technological advances in the realization of quantum hardware—fuels the development of meaningful real-world applications, as well as implementations for well-known quantum algorithms. One of the most prominent examples till today is Grover’s algorithm, which can be used for efficient search in unstructured databases. Quantum oracles that are frequently masked as black boxes play an important role in Grover’s algorithm. Hence, the automatic generation of oracles is of paramount importance. Moreover, the automatic generation of the corresponding circuits for a Grover quantum oracle is deeply linked to the synthesis of reversible quantum logic, which—despite numerous advances in the field—still remains a challenge till today in terms of synthesizing efficient and scalable circuits for complex Boolean functions. In this paper, we present a flexible method for automatically encoding unstructured databases into oracles, which can then be efficiently searched with Grover’s algorithm. Furthermore, we develop a tailor-made method for quantum logic synthesis, which vastly improves circuit complexity over other current approaches. Finally, we present another logic synthesis method that considers the requirements of scaling onto real world backends. We compare our method with other approaches through evaluating the oracle generation for random databases and analyzing the resulting circuit complexities using various metrics.