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

arXiv:2001.06575 · IEEE Transactions on Quantum Engineering

Subdivided Phase Oracle for NISQ Search Algorithms

Takahiko Satoh, Yasuhiro Ohkura, Rodney Van Meter

Published Jan 1, 2020• 25 citations
arXivHTMLPDF

Abstract

Because noisy intermediate-scale quantum (NISQ) machines accumulate errors quickly, we need new approaches to designing NISQ-aware algorithms and assessing their performance. Algorithms with characteristics that appear less desirable under ideal circumstances, such as lower success probability, may in fact outperform their ideal counterparts on existing hardware. We propose an adaptation of Grover's algorithm, subdividing the phase flip into segments to replace a digital counter and complex phase flip decision logic. We applied this approach to obtain the best solution of the MAX-CUT problem in sparse graphs, utilizing multicontrol, Toffoli-like gates with residual phase shifts. We implemented this algorithm on IBM Q processors and succeeded in solving a five-vertex MAX-CUT problem, demonstrating amplitude amplification on four qubits. This approach will be useful for a range of problems, and may shorten the time to reaching quantum advantage.

DOI
10.1109/tqe.2020.3012068

Related papers

Quantum search on noisy intermediate-scale quantum devices

Kun Zhang, Kwangmin Yu, V. E. Korepin

Abstract Quantum search algorithm (also known as Grover's algorithm) lays the foundation for many other quantum algorithms. Although it is very simple, its implementation is limited on noisy intermediate-scale quantum (NISQ) processors. Grover's algorithm was designed without considering the physical resources, such as depth, in the real implementations. Therefore, Grover's algorithm can be improved for NISQ devices. In this paper, we demonstrate how to implement quantum search algorithms better on NISQ devices. We present detailed benchmarks of the five-qubit quantum search algorithm on different quantum processors, including IBMQ, IonQ, and Honeywell quantum devices. We report the highest success probability of the five-qubit search algorithm compared to previous works. Our results show that designing the error-aware quantum search algorithms is possible, which can maximally harness the power of NISQ computers.

arXiv:2202.00122•Europhysics Letters (EPL)•Sep 9, 2022•19 citations

Noisy intermediate-scale quantum computing algorithm for solving an n -vertex MaxCut problem with log( n ) qubits

Marko J. Rančić

Quantum computers are devices, which allow more efficient solutions of problems as compared to their classical counterparts.As the timeline to developing a quantum-error corrected computer is unclear, the quantum computing community has dedicated much attention to developing algorithms for currently available noisy intermediate-scale quantum computers (NISQ).Thus far, within NISQ, optimization problems are one of the most commonly studied and are quite often tackled with the quantum approximate optimization algorithm (QAOA).This algorithm is best known for computing graph partitions with a maximal separation of edges (MaxCut), but can easily calculate other problems related to graphs.Here, I present a novel quantum optimization algorithm, which uses exponentially less qubits as compared to the QAOA while requiring a significantly reduced number of quantum operations to solve the MaxCut problem.Such an improved performance allowed me to partition graphs with 32 nodes on publicly available 5 qubit gate-based quantum computers without any preprocessing such as division of the graph into smaller subgraphs.These results represent a 40% increase in graph size as compared to state-of-art experiments on gate-based quantum computers such as Google Sycamore.The obtained lower bound is 54.9% on the solution for actual hardware benchmarks and 77.6% on ideal simulators of quantum computers.Furthermore, large-scale optimization problems represented by graphs of a 128 nodes are tackled with simulators of quantum computers, again without any predivision into smaller subproblems and a lower solution bound of 67.9% is achieved.The study presented here paves way to using powerful genetic optimizer in synergy with quantum computers.

arXiv:2110.10788•Physical Review Research•Feb 15, 2023•20 citations

Practical Quantum Search by Variational Quantum Eigensolver on Noisy Intermediate-Scale Quantum Hardware

Chen-Yu Liu

Grover search is a renowned quantum search algorithm that leverages quantum superposition to find a marked item with quadratic speedup. However, when implemented on Noisy Intermediate-scale Quantum (NISQ) hardware, the required repeated iterations of the oracle and diffusion operators increase exponentially with the number of qubits, resulting in significant noise accumulation. To address this, we propose a hybrid quantum-classical architecture that replaces quantum iterations with updates from a classical optimizer. This optimizer minimizes the expectation value of an oracle Hamiltonian with respect to a parameterized quantum state representing the target bit string. Our parameterized quantum circuit is much shallower than Grover search circuit, and we found that it outperforms Grover search on noisy simulators and NISQ hardware. When the number of qubits is greater than 5, our approach still maintains usable success probability, while the success probability of Grover search is at the same level as random guessing.

arXiv:2304.03747•International Conference on Computational Science and Computational Intelligence (CSCI)•Dec 13, 2023•12 citations

Utilizing Novel Quantum Counters for Grover's Algorithm to Solve the Dominating Set Problem

Jehn‐Ruey Jiang, Qiao-Yi Lin

Grover's algorithm is a well-known unstructured quantum search algorithm run on quantum computers. It constructs an oracle and calls the oracle O($\sqrt N$) times to locate specific data out of N unsorted data. This represents a quadratic speedup compared to the classical unstructured data sequential search algorithm, which requires to call the oracle O(N) times. We are currently in the noisy intermediate-scale quantum (NISQ) era in which quantum computers have a limited number of qubits, short decoherence time, and low gate fidelity. It is thus desirable to design quantum components with three good properties: (i) a reduced number of qubits, (ii) shorter quantum depth, and (iii) fewer gates. This paper utilizes novel quantum counters with the above-mentioned three good properties to construct the oracle of Grover's algorithm to efficiently solve the dominating set problem (DSP), as defined below. For a given graph G=(V, E), a dominating set (DS) D is a subset of the vertex set V, such that every vertex is in D or has an adjacent vertex in D. The DSP is to decide for a given graph G and an integer k whether there exists a DS with size k. Algorithms solving the DSP have many applications. For example, they can be applied to check whether k routers suffice to connect all computers in a computer network. The DSP is an NP-complete problem, indicating that no classical algorithm exists to solve the DSP with polynomial time complexity in the worst case. Therefore, using quantum algorithms, such as Grover's algorithm, to exploit the potent computational capabilities of quantum computers to solve the DSP is highly promising. We execute the whole quantum circuit of Grover's algorithm using novel quantum counters through the IBM Quantum Lab service to validate that the circuit can solve the DSP efficiently and correctly.

arXiv:2312.09388•Dec 14, 2023•1 citation

Practical Guide to Quantum Computing: Grover's Algorithm # 4

Mikhail Pavlov

Abstract This guide is based on the IBM Quantum course Phase Estimation and Factoring and focuses on Grover’s algorithm, a quantum algorithm for unstructured search problems that provides a quadratic speedup over classical approaches. In an unstructured search problem, we are given a function (often represented as an oracle) that marks one or more “correct” solutions among NNN possible candidates. A classical algorithm requires on the order of O(N)O(N)O(N) evaluations in the worst case. In contrast, Grover’s algorithm finds a solution using only O(N)O(\sqrt{N})O(N) oracle queries. This quadratic improvement implies: The quantum algorithm requires roughly the square root of the number of operations needed classically. Any classical algorithm for unstructured search must have cost at least quadratic relative to Grover’s quantum procedure. Core Idea of the Algorithm Grover’s algorithm relies on: Preparation of a uniform superposition (typically using Hadamard gates). An oracle that marks valid solutions via phase inversion. The Grover diffusion operator, which amplifies the probability amplitude of the marked states through interference. By repeatedly applying the Grover operator, the amplitude of the desired solution grows while others diminish, allowing measurement to reveal the correct answer with high probability. Practical Considerations Despite its theoretical elegance and wide applicability, the quadratic speedup of Grover’s algorithm is unlikely to yield near-term practical advantage. Modern classical hardware operates at extremely high clock rates and is vastly more mature than current quantum devices. For problem sizes accessible to today’s quantum computers, classical systems remain dominant. However, history shows that even sub-quadratic classical improvements — such as: Fast Fourier Transform (FFT) Efficient sorting algorithms like quicksort and mergesort have had transformative practical impact. The crucial distinction is that Grover’s algorithm depends on fundamentally different hardware — quantum processors — which are still in early development. Long-Term Perspective As quantum hardware advances in qubit count, coherence time, and error correction, Grover’s quadratic advantage may become practically significant for: Cryptographic key search Optimization heuristics Combinatorial search problems Amplitude amplification subroutines in broader quantum algorithms Through hands-on experimentation on IBM Q, this lesson demonstrates how theoretical amplitude amplification translates into executable quantum circuits, reinforcing the relationship between interference, probability amplitudes, and computational complexity.

•Mar 4, 2026•0 citations

Novel Quantum Circuit Designs for the Oracle of Grover’s Algorithm to Solve the Vertex Cover Problem

Jehn‐Ruey Jiang, Wei-Han Yan

We propose new quantum circuit designs for the Grover oracle, i.e., the oracle of Grover’s algorithm, to solve the vertex cover problem (VCP) efficiently. Grover’s algorithm is an unstructured quantum search algorithm to search a target data item out of N data pieces by calling the oracle $\mathrm{O}(\sqrt{N})$ times. It represents a quadratic speedup compared to the classical unstructured data sequential search algorithm, which requires O(N) oracle calls. We are in the noisy intermediate-scale quantum (NISQ) era in which quantum computers have a limited number of qubits, short decoherence time, and low gate fidelity. It is thus desirable to design quantum circuits with three properties: (1) a reduced number of qubits, (2) shorter quantum depth, and (3) fewer gates. We created novel designs of a quantum counter and a quantum semaphore to be applied to the Grover oracle to have the three properties. Through the IBM Quantum Lab service, we executed Grover’s algorithm with the novel quantum circuit designs to solve the VCP to validate the design correctness.

IEEE Eurasia Conference on IOT, Communication and Engineering (ECICE)•Oct 27, 2023•5 citations
Because noisy intermediate-scale quantum (NISQ) machines accumulate errors quickly, we need new approaches to designing NISQ-aware algorithms and assessing their performance. Algorithms with characteristics that appear less desirable under ideal circumstances, such as lower success probability, may in fact outperform their ideal counterparts on existing hardware. We propose an adaptation of Grover's algorithm, subdividing the phase flip into segments to replace a digital counter and complex phase flip decision logic. We applied this approach to obtain the best solution of the MAX-CUT problem in sparse graphs, utilizing multicontrol, Toffoli-like gates with residual phase shifts. We implemented this algorithm on IBM Q processors and succeeded in solving a five-vertex MAX-CUT problem, demonstrating amplitude amplification on four qubits. This approach will be useful for a range of problems, and may shorten the time to reaching quantum advantage.
Abstract Quantum search algorithm (also known as Grover's algorithm) lays the foundation for many other quantum algorithms. Although it is very simple, its implementation is limited on noisy intermediate-scale quantum (NISQ) processors. Grover's algorithm was designed without considering the physical resources, such as depth, in the real implementations. Therefore, Grover's algorithm can be improved for NISQ devices. In this paper, we demonstrate how to implement quantum search algorithms better on NISQ devices. We present detailed benchmarks of the five-qubit quantum search algorithm on different quantum processors, including IBMQ, IonQ, and Honeywell quantum devices. We report the highest success probability of the five-qubit search algorithm compared to previous works. Our results show that designing the error-aware quantum search algorithms is possible, which can maximally harness the power of NISQ computers.
Quantum computers are devices, which allow more efficient solutions of problems as compared to their classical counterparts.As the timeline to developing a quantum-error corrected computer is unclear, the quantum computing community has dedicated much attention to developing algorithms for currently available noisy intermediate-scale quantum computers (NISQ).Thus far, within NISQ, optimization problems are one of the most commonly studied and are quite often tackled with the quantum approximate optimization algorithm (QAOA).This algorithm is best known for computing graph partitions with a maximal separation of edges (MaxCut), but can easily calculate other problems related to graphs.Here, I present a novel quantum optimization algorithm, which uses exponentially less qubits as compared to the QAOA while requiring a significantly reduced number of quantum operations to solve the MaxCut problem.Such an improved performance allowed me to partition graphs with 32 nodes on publicly available 5 qubit gate-based quantum computers without any preprocessing such as division of the graph into smaller subgraphs.These results represent a 40% increase in graph size as compared to state-of-art experiments on gate-based quantum computers such as Google Sycamore.The obtained lower bound is 54.9% on the solution for actual hardware benchmarks and 77.6% on ideal simulators of quantum computers.Furthermore, large-scale optimization problems represented by graphs of a 128 nodes are tackled with simulators of quantum computers, again without any predivision into smaller subproblems and a lower solution bound of 67.9% is achieved.The study presented here paves way to using powerful genetic optimizer in synergy with quantum computers.
Grover search is a renowned quantum search algorithm that leverages quantum superposition to find a marked item with quadratic speedup. However, when implemented on Noisy Intermediate-scale Quantum (NISQ) hardware, the required repeated iterations of the oracle and diffusion operators increase exponentially with the number of qubits, resulting in significant noise accumulation. To address this, we propose a hybrid quantum-classical architecture that replaces quantum iterations with updates from a classical optimizer. This optimizer minimizes the expectation value of an oracle Hamiltonian with respect to a parameterized quantum state representing the target bit string. Our parameterized quantum circuit is much shallower than Grover search circuit, and we found that it outperforms Grover search on noisy simulators and NISQ hardware. When the number of qubits is greater than 5, our approach still maintains usable success probability, while the success probability of Grover search is at the same level as random guessing.
Grover's algorithm is a well-known unstructured quantum search algorithm run on quantum computers. It constructs an oracle and calls the oracle O(N\sqrt NN​) times to locate specific data out of N unsorted data. This represents a quadratic speedup compared to the classical unstructured data sequential search algorithm, which requires to call the oracle O(N) times. We are currently in the noisy intermediate-scale quantum (NISQ) era in which quantum computers have a limited number of qubits, short decoherence time, and low gate fidelity. It is thus desirable to design quantum components with three good properties: (i) a reduced number of qubits, (ii) shorter quantum depth, and (iii) fewer gates. This paper utilizes novel quantum counters with the above-mentioned three good properties to construct the oracle of Grover's algorithm to efficiently solve the dominating set problem (DSP), as defined below. For a given graph G=(V, E), a dominating set (DS) D is a subset of the vertex set V, such that every vertex is in D or has an adjacent vertex in D. The DSP is to decide for a given graph G and an integer k whether there exists a DS with size k. Algorithms solving the DSP have many applications. For example, they can be applied to check whether k routers suffice to connect all computers in a computer network. The DSP is an NP-complete problem, indicating that no classical algorithm exists to solve the DSP with polynomial time complexity in the worst case. Therefore, using quantum algorithms, such as Grover's algorithm, to exploit the potent computational capabilities of quantum computers to solve the DSP is highly promising. We execute the whole quantum circuit of Grover's algorithm using novel quantum counters through the IBM Quantum Lab service to validate that the circuit can solve the DSP efficiently and correctly.
Abstract This guide is based on the IBM Quantum course Phase Estimation and Factoring and focuses on Grover’s algorithm, a quantum algorithm for unstructured search problems that provides a quadratic speedup over classical approaches. In an unstructured search problem, we are given a function (often represented as an oracle) that marks one or more “correct” solutions among NNN possible candidates. A classical algorithm requires on the order of O(N)O(N)O(N) evaluations in the worst case. In contrast, Grover’s algorithm finds a solution using only O(N)O(\sqrt{N})O(N) oracle queries. This quadratic improvement implies: The quantum algorithm requires roughly the square root of the number of operations needed classically. Any classical algorithm for unstructured search must have cost at least quadratic relative to Grover’s quantum procedure. Core Idea of the Algorithm Grover’s algorithm relies on: Preparation of a uniform superposition (typically using Hadamard gates). An oracle that marks valid solutions via phase inversion. The Grover diffusion operator, which amplifies the probability amplitude of the marked states through interference. By repeatedly applying the Grover operator, the amplitude of the desired solution grows while others diminish, allowing measurement to reveal the correct answer with high probability. Practical Considerations Despite its theoretical elegance and wide applicability, the quadratic speedup of Grover’s algorithm is unlikely to yield near-term practical advantage. Modern classical hardware operates at extremely high clock rates and is vastly more mature than current quantum devices. For problem sizes accessible to today’s quantum computers, classical systems remain dominant. However, history shows that even sub-quadratic classical improvements — such as: Fast Fourier Transform (FFT) Efficient sorting algorithms like quicksort and mergesort have had transformative practical impact. The crucial distinction is that Grover’s algorithm depends on fundamentally different hardware — quantum processors — which are still in early development. Long-Term Perspective As quantum hardware advances in qubit count, coherence time, and error correction, Grover’s quadratic advantage may become practically significant for: Cryptographic key search Optimization heuristics Combinatorial search problems Amplitude amplification subroutines in broader quantum algorithms Through hands-on experimentation on IBM Q, this lesson demonstrates how theoretical amplitude amplification translates into executable quantum circuits, reinforcing the relationship between interference, probability amplitudes, and computational complexity.
We propose new quantum circuit designs for the Grover oracle, i.e., the oracle of Grover’s algorithm, to solve the vertex cover problem (VCP) efficiently. Grover’s algorithm is an unstructured quantum search algorithm to search a target data item out of N data pieces by calling the oracle O(N)\mathrm{O}(\sqrt{N})O(N​) times. It represents a quadratic speedup compared to the classical unstructured data sequential search algorithm, which requires O(N) oracle calls. We are in the noisy intermediate-scale quantum (NISQ) era in which quantum computers have a limited number of qubits, short decoherence time, and low gate fidelity. It is thus desirable to design quantum circuits with three properties: (1) a reduced number of qubits, (2) shorter quantum depth, and (3) fewer gates. We created novel designs of a quantum counter and a quantum semaphore to be applied to the Grover oracle to have the three properties. Through the IBM Quantum Lab service, we executed Grover’s algorithm with the novel quantum circuit designs to solve the VCP to validate the design correctness.