Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Open Systems & Information Dynamics

Method for Organizing Grover's Quantum Oracle

Hideaki Ito, Saburou Iida

Published Dec 1, 2014• 2 citations
Publisher

Abstract

In a quantum computation, some algorithms use oracles (black boxes) for abstract computational objects. This paper presents an example for organizing Grover's quantum oracle by synthesizing several unitary gates such as CNOT gates, Toffoli gates, and Hadamard gates. As an example, we show a concrete quantum circuit for the knapsack problem, which belongs to the class of NP-complete problems. The time complexity of an oracle for the knapsack problem is estimated to be O(n2), where n is the number of variables. And the same order is obtained for space complexity.

DOI
10.1142/s1230161214500115

Related papers

Automatic generation of Grover quantum oracles for arbitrary data structures

Raphael Seidel, Colin Kai‐Uwe Becker, Sebastian Bock +3 more

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.

arXiv:2110.07545•Quantum Science and Technology•Jan 3, 2023•30 citations

Quantum-based algorithm and circuit design for bounded Knapsack optimization problem

Wenjun Hou, Marek A. Perkowski

The Knapsack Problem is a prominent problem that is used in resource allocation and cryptography. This paper presents an oracle and a circuit design that verifies solutions to the decision problem form of the Bounded Knapsack Problem. This oracle can be used by Grover Search to solve the optimization problem form of the Bounded Knapsack Problem. This algorithm leverages the quadratic speed-up offered by Grover Search to achieve a quantum algorithm for the Knapsack Problem that shows improvement with regard to classical algorithms. The quantum circuits were designed using the Microsoft Q# Programming Language and verified on its local quantum simulator. The paper also provides analyses of the complexity and gate cost of the proposed oracle. The work in this paper is the first such proposed method for the Knapsack Optimization Problem.

Quantum Information and Computation•Aug 1, 2020•6 citations

An adiabatic oracle for Grover's algorithm

Bin Yan, Nikolai A. Sinitsyn

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.

arXiv:2207.05665•Jul 12, 2022•5 citations

An Oracle Design for Grover’s Quantum Search Algorithm for Solving the Exact String Matching Problem

Jeffrey A. Aborot

Grover’s quantum search algorithm is a template for doing quantum search in unstructured search spaces. The details of the oracle in Grover’s algorithm is abstracted for the purpose of analyzing the bound on the number of queries the algorithm must make in order to find the target element of the search space. In order for Grover’s quantum search algorithm to be usable in a specific unstructured search problem, one must provide details on the inner workings of the oracle. Specifically, we present a high-level and basic design of the oracle using the quantum computing model specific to the exact string matching problem. We describe our design using the quantum circuit model of computing and show that the gate complexity of the circuit is linear with respect to the product of the length of the pattern and the size of the alphabet. We have suggested a quantum memory structure for storage and retrieval of the input text. The quantum circuit we presented requires scratch qubits linear to the product of the length of the pattern and the size of the alphabet to reduce the size of the scratch register without exponential increase in the count of elementary gates required for the computation.

Workshop on Computation: Theory and Practice (WCTP)•Dec 1, 2018•3 citations

Grover-algorithm-like operator using only single-qubit gates

Go Kato

We propose a quantum circuit for the quantum search problem. The quantum circuit is superior to Grover's algorithm in some realistic cases. The reasons for the superiority are in short as follows: In the quantum circuit proposed in this paper, all the operators except for the oracle can be written as direct products of single-qubit gates. Such separable operators can be executed much faster than multiparticle operators, such as controlled-NOT gates and Toffoli gates, in many realistic systems. The idea of this quantum circuit is inspired by the Hamiltonian used in the adiabatic quantum computer. In addition, the scaling of the number of oracle calls for this circuit is the same as that for Grover's algorithm, i.e., $O({2}^{n∕2})$.

arXiv:quant-ph/0508081•Physical Review A•Sep 15, 2005•10 citations

Automated quantum oracle synthesis with a minimal number of qubits

Jessie M. Henderson, Elena R. Henderson, Aviraj Sinha +2 more

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.

arXiv:2304.03829•Jun 13, 2023•10 citations
In a quantum computation, some algorithms use oracles (black boxes) for abstract computational objects. This paper presents an example for organizing Grover's quantum oracle by synthesizing several unitary gates such as CNOT gates, Toffoli gates, and Hadamard gates. As an example, we show a concrete quantum circuit for the knapsack problem, which belongs to the class of NP-complete problems. The time complexity of an oracle for the knapsack problem is estimated to be O(n2), where n is the number of variables. And the same order is obtained for space 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 Knapsack Problem is a prominent problem that is used in resource allocation and cryptography. This paper presents an oracle and a circuit design that verifies solutions to the decision problem form of the Bounded Knapsack Problem. This oracle can be used by Grover Search to solve the optimization problem form of the Bounded Knapsack Problem. This algorithm leverages the quadratic speed-up offered by Grover Search to achieve a quantum algorithm for the Knapsack Problem that shows improvement with regard to classical algorithms. The quantum circuits were designed using the Microsoft Q# Programming Language and verified on its local quantum simulator. The paper also provides analyses of the complexity and gate cost of the proposed oracle. The work in this paper is the first such proposed method for the Knapsack Optimization Problem.
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 quantum search algorithm is a template for doing quantum search in unstructured search spaces. The details of the oracle in Grover’s algorithm is abstracted for the purpose of analyzing the bound on the number of queries the algorithm must make in order to find the target element of the search space. In order for Grover’s quantum search algorithm to be usable in a specific unstructured search problem, one must provide details on the inner workings of the oracle. Specifically, we present a high-level and basic design of the oracle using the quantum computing model specific to the exact string matching problem. We describe our design using the quantum circuit model of computing and show that the gate complexity of the circuit is linear with respect to the product of the length of the pattern and the size of the alphabet. We have suggested a quantum memory structure for storage and retrieval of the input text. The quantum circuit we presented requires scratch qubits linear to the product of the length of the pattern and the size of the alphabet to reduce the size of the scratch register without exponential increase in the count of elementary gates required for the computation.
We propose a quantum circuit for the quantum search problem. The quantum circuit is superior to Grover's algorithm in some realistic cases. The reasons for the superiority are in short as follows: In the quantum circuit proposed in this paper, all the operators except for the oracle can be written as direct products of single-qubit gates. Such separable operators can be executed much faster than multiparticle operators, such as controlled-NOT gates and Toffoli gates, in many realistic systems. The idea of this quantum circuit is inspired by the Hamiltonian used in the adiabatic quantum computer. In addition, the scaling of the number of oracle calls for this circuit is the same as that for Grover's algorithm, i.e., O(2n∕2)O({2}^{n∕2})O(2n∕2).
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.