Grover’s algorithm is a well-known contribution to quantum computing. It searches one value within an unordered sequence. A fundamental part of this algorithm is the so-called oracle, a quantum circuit that marks the quantum state corresponding to the desired value. In this work we present a classical algorithm that builds an oracle that performs a less-than operation, marking states representing natural numbers smaller than a given one. Results are shown to prove its functionality. This lessthan oracle implementation works on any number of qubits and does not require any ancilla qubits. Regarding depth, the proposed implementation is compared with Qiskit automatic method, Diagonal. We show that the depth of our less-than oracle implementation is always lower. In addition, a comparison with another method for oracle generation in terms of gate count is also conducted to prove the efficiency of our method. The result presented here is part of a research work that aims to achieve reusable quantum operations that can be composed to perform more complex ones.
Grover’s algorithm is a well-known contribution to quantum computing. It searches one value within an unordered sequence. A fundamental part of this algorithm is the so-called oracle, a quantum circuit that marks the quantum state corresponding to the desired value. In this work we present a classical algorithm that builds an oracle that performs a less-than operation, marking states representing natural numbers smaller than a given one. Results are shown to prove its functionality. This lessthan oracle implementation works on any number of qubits and does not require any ancilla qubits. Regarding depth, the proposed implementation is compared with Qiskit automatic method, Diagonal. We show that the depth of our less-than oracle implementation is always lower. In addition, a comparison with another method for oracle generation in terms of gate count is also conducted to prove the efficiency of our method. The result presented here is part of a research work that aims to achieve reusable quantum operations that can be composed to perform more complex ones.
Grover's algorithm is a well-known contribution to quantum computing. It searches one value within an unordered sequence faster than any classical algorithm. A fundamental part of this algorithm is the so-called oracle, a quantum circuit that marks the quantum state corresponding to the desired value. A generalization of it is the oracle for Amplitude Amplification, that marks multiple desired states. In this work we present a classical algorithm that builds a phase-marking oracle for Amplitude Amplification. This oracle performs a less-than operation, marking states representing natural numbers smaller than a given one. Results of both simulations and experiments are shown to prove its functionality. This less-than oracle implementation works on any number of qubits and does not require any ancilla qubits. Regarding depth, the proposed implementation is compared with the one generated by Qiskit automatic method, UnitaryGate. We show that the depth of our less-than oracle implementation is always lower. This difference is significant enough for our method to outperform UnitaryGate on real quantum hardware.
Several prominent quantum computing algorithms—including Grover’s search algorithm and Shor’s algorithm for finding the prime factorization of an integer—employ subcircuits termed ‘oracles’ that embed a specific instance of a mathematical function into a corresponding bijective function that is then realized as a quantum circuit representation. Designing oracles, and particularly, designing them to be optimized for a particular use case, can be a non-trivial task. For example, the challenge of implementing quantum circuits in the current era of NISQ-based quantum computers generally dictates that they should be designed with a minimal number of qubits, as larger qubit counts increase the likelihood that computations will fail due to one or more of the qubits decohering. However, some quantum circuits require that function domain values be preserved, which can preclude using the minimal number of qubits in the oracle circuit. Thus, quantum oracles must be designed with a particular application in mind. In this work, we present two methods for automatic quantum oracle synthesis. One of these methods uses a minimal number of qubits, while the other preserves the function domain values while also minimizing the overall required number of qubits. For each method, we describe known quantum circuit use cases, and illustrate implementation using an automated quantum compilation and optimization tool to synthesize oracles for a set of benchmark functions; we can then compare the methods with metrics including required qubit count and quantum circuit complexity.
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.
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.
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 search task is one of the most difficult when it comes to execution speed, and reducing the latter is important both when working with large data and with small samples, if they need to be processed frequently and in a limited time. Grover's algorithm gave hope to quantum computing and served as an excellent base for all possible implementations and modifications. In this paper, we propose a slightly different algorithm that increases the probability of finding the nearest value by reducing the probability of undesirable values in a controlled manner (in proportion to their difference from the desired value), as well as implementing an oracle that requires a single call without an additional ancilla qubit to redistribute the amplitudes.