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:2010.03841

Efficient unstructured search implementation on current ion-trap quantum processors

Vladyslav Hlembotskyi, Rafał Burczyński, Witold Jarnicki, Adam Szady, Jan Tułowiecki

Published Oct 8, 2020• 7 citations
arXivHTMLPDF

Abstract

So far, only the results on 3 qubit spaces (both on superconducting and ion-trap realisations of quantum processors) have beaten the classical unstructured search in the expected number of oracle calls using optimal protocols in both settings. We present experimental results on running unstructured search in spaces defined by 4, 5 and 6 qubits on ion-trapped quantum processor. Our best circuits obtained respectively 66\%, 26\% and 6\% average probability of measuring the marked element. In the case of 4 and 5 qubit spaces we obtained fewer expected number of oracle calls required to find a marked element than any classical approach. Viability of the theoretical result by Grover at these qubit counts is, to authors' knowledge demonstrated experimentally for the first time. Also at 6 qubits, a circuit using a single oracle call returned a measured probability of success exceeding any possible classical approach. These results were achieved using a variety of unstructured search algorithms in conjunction with recent developments in reducing the number of entangling gates. The latter are currently considered to be a dominating source of errors in quantum computations. Some of these improvements have been made possible by using mid-circuit measurements. To our knowledge the latter feature is currently available only on the H0 quantum processor we run on.

DOI
10.48550/arxiv.2010.03841

Related papers

Benchmarking 16-element quantum search algorithms on superconducting quantum processors

Jan Gwinner, Marcin Briański, Wojciech Burkot +2 more

We present experimental results on running 4-qubit unstructured search on IBM quantum processors. Our best attempt attained probability of success around 24.5%. We try several algorithms and use the most recent developments in quantum search to reduce the number of entangling gates that are currently considered the main source of errors in quantum computations. Comparing theoretical expectations of an algorithm performance with the actual data, we explore the hardware limits, showing sharp, phase-transition-like degradation of performance on quantum processors. We conclude that it is extremely important to design hardware-aware algorithms and to include any other low level optimizations on NISQ devices.

arXiv:2007.06539•Jul 13, 2020•17 citations

Optimization of 16-Element Quantum Search on IBMQ

Wei Zi, Shuai Yang, Cheng Guo +1 more

Unstructured searching, which is to find the marked element from a given unstructured data set, is a widely studied problem in computer science. It is well known that Grover algorithm provides a quadratic speedup to solve unstructured search problem compared with the classical algorithm. This algorithm has received a lot of attention due to the strong versatility. In this manuscript, we report experimental results of searching a unique target from 16 elements on five different quantum devices of IBM quantum Experience (IBMQ). We first implement the original Grover algorithm on these devices. However, the experiment probability of success of finding the correct target is almost the same as random choice. We then optimize the quantum circuit size of the search algorithm. The oracle operator and diffusion operator are two of the most costly operators in Grover algorithm. For the 16-element quantum search algorithm, both the oracle operator and diffusion operator consist of a triple controlled [Formula: see text] gate ([Formula: see text]) and some single-qubit gates. So we optimize the implementation of the [Formula: see text] gate according to the qubits layout of different quantum devices. On the ibmq_santiago, the experimental success rate of the 16-element quantum search algorithm is increased to [Formula: see text] by the optimization, which is better than all the published experiments implemented on IBMQ devices. For other IBMQ devices, the experimental success rate of 16-element quantum search also has been significantly improved. We then try to further reduce the size of the quantum circuit by modifying the Grover algorithm, with a tolerable loss of the theoretical success probability. On ibmq_quito, the experimental success rate is further improved from 25.23% to 27.56% after optimization. These experimental results show the importance of circuit optimization and algorithm optimization in the Noisy-Intermediate-Scale Quantum (NISQ) era.

SPIN•Sep 1, 2021•1 citation

Implementation of Grover’s quantum search algorithm in a scalable system

Kathy-Anne Brickman, P. C. Haljan, P. J. Lee +3 more

We report the implementation of Grover's quantum search algorithm in the scalable system of trapped atomic ion quantum bits. Any one of four possible states of a two-qubit memory is marked, and following a single query of the search space, the marked element is successfully recovered with an average probability of 60(2)%. This exceeds the performance of any possible classical search algorithm, which can only succeed with a maximum average probability of 50%.

arXiv:quant-ph/0510066•Physical Review A•Nov 30, 2005•183 citations

Classical vs Quantum Search: Experimental Performance Analysis of Grover's Algorithm on Real IBM Quantum Hardware

Kundan Kumar Sahu

Grover's quantum search algorithm provides a proven quadratic speedup over classical linear search for unstructured databases. While its theoretical advantage is well established, experimental validation on real noisy intermediate-scale quantum (NISQ) hardware remains limited by noise, decoherence, and hardware constraints. In this work, we present an experimental comparison between classical linear search and Grover's quantum search algorithm executed on IBM Quantum real superconducting hardware using Qiskit Runtime. A four-qubit implementation corresponding to a 16-element search space is evaluated across multiple experimental runs. The results demonstrate consistent amplitude amplification, achieving an average success probability of 54.25% and an amplification factor of 8.68× over random guessing. Although classical execution remains faster in wall-clock time due to quantum hardware overhead, the experiment empirically validates the algorithmic advantage of Grover's search and quantifies the performance gap between ideal and real quantum processors in the NISQ era.

•Dec 29, 2025•1 citation

Introducing structure to expedite quantum searching

Marcin Briański, Jan Gwinner, Vladyslav Hlembotskyi +3 more

We present a quantum algorithm for solving the unstructured search problem with one marked element. Our algorithm allows generating quantum circuits that use asymptotically fewer additional quantum gates than the famous Grover's algorithm and may be successfully executed on noisy intermediate-scale quantum devices. We prove that our algorithm is optimal in the total number of elementary gates up to a multiplicative constant. As many NP-hard problems are, in fact, not unstructured, we also describe the partial uncompute technique which exploits the oracle structure and allows a significant reduction in the number of elementary gates required to find the solution. Combining these results allows us to use an asymptotically smaller number of elementary gates than Grover's algorithm in various applications, keeping the number of queries to the oracle essentially the same. We show how the results can be applied to solve hard combinatorial problems, for example, Unique $k$-SAT. Additionally, we show how to asymptotically reduce the number of elementary gates required to solve the unstructured search problem with multiple marked elements.

arXiv:2006.05828•Physical Review A•Jun 28, 2021•18 citations

Accelerating Unstructured Text Search with Grover's Algorithm: A Performance Analysis on Simulated and Real-Time Quantum Computers

SaiPrasath B, SasiKumar R, A Dineshkumar

Target item searching in large-scale, unstructured text databases is a major computational task for traditional systems and usually requires algorithms whose time complexity is on the order of$O(N)$. Quantum computing presents a strong competitor by using Grover's algorithm, where theoretically the search complexity comes down to$O(\sqrt{N})$, making faster retrieval possible. This research considers the design and assessment of Grover's algorithm as it is used to find a target word in a paragraph. The process entails encoding a group of unique words into a quantum register and implementing a circuit that incorporates a bespoke oracle and a diffusion operator to amplify the probability amplitude of the target state. Performance was evaluated in two situations: an ideal noise-free simulation with Qiskit's AerSimulator and a real-world run on IBM's quantum hardware. Simulation results demonstrated always-high accuracy in identifying the target word. But tests on real quantum machines indicated that the reliability of the algorithm decreases with an increase in qubits. Though circuits of up to five qubits had tolerable accuracy, larger configurations were plagued by noise, gate errors, and decoherence effects. These results highlight both the potential of quantum search algorithms for text processing and the limitations of NISQ today.

International Conference on Applied Artificial Intelligence and Computing (ICAAIC)•Dec 17, 2025•0 citations
So far, only the results on 3 qubit spaces (both on superconducting and ion-trap realisations of quantum processors) have beaten the classical unstructured search in the expected number of oracle calls using optimal protocols in both settings. We present experimental results on running unstructured search in spaces defined by 4, 5 and 6 qubits on ion-trapped quantum processor. Our best circuits obtained respectively 66%, 26% and 6% average probability of measuring the marked element. In the case of 4 and 5 qubit spaces we obtained fewer expected number of oracle calls required to find a marked element than any classical approach. Viability of the theoretical result by Grover at these qubit counts is, to authors' knowledge demonstrated experimentally for the first time. Also at 6 qubits, a circuit using a single oracle call returned a measured probability of success exceeding any possible classical approach. These results were achieved using a variety of unstructured search algorithms in conjunction with recent developments in reducing the number of entangling gates. The latter are currently considered to be a dominating source of errors in quantum computations. Some of these improvements have been made possible by using mid-circuit measurements. To our knowledge the latter feature is currently available only on the H0 quantum processor we run on.
We present experimental results on running 4-qubit unstructured search on IBM quantum processors. Our best attempt attained probability of success around 24.5%. We try several algorithms and use the most recent developments in quantum search to reduce the number of entangling gates that are currently considered the main source of errors in quantum computations. Comparing theoretical expectations of an algorithm performance with the actual data, we explore the hardware limits, showing sharp, phase-transition-like degradation of performance on quantum processors. We conclude that it is extremely important to design hardware-aware algorithms and to include any other low level optimizations on NISQ devices.
Unstructured searching, which is to find the marked element from a given unstructured data set, is a widely studied problem in computer science. It is well known that Grover algorithm provides a quadratic speedup to solve unstructured search problem compared with the classical algorithm. This algorithm has received a lot of attention due to the strong versatility. In this manuscript, we report experimental results of searching a unique target from 16 elements on five different quantum devices of IBM quantum Experience (IBMQ). We first implement the original Grover algorithm on these devices. However, the experiment probability of success of finding the correct target is almost the same as random choice. We then optimize the quantum circuit size of the search algorithm. The oracle operator and diffusion operator are two of the most costly operators in Grover algorithm. For the 16-element quantum search algorithm, both the oracle operator and diffusion operator consist of a triple controlled [Formula: see text] gate ([Formula: see text]) and some single-qubit gates. So we optimize the implementation of the [Formula: see text] gate according to the qubits layout of different quantum devices. On the ibmq_santiago, the experimental success rate of the 16-element quantum search algorithm is increased to [Formula: see text] by the optimization, which is better than all the published experiments implemented on IBMQ devices. For other IBMQ devices, the experimental success rate of 16-element quantum search also has been significantly improved. We then try to further reduce the size of the quantum circuit by modifying the Grover algorithm, with a tolerable loss of the theoretical success probability. On ibmq_quito, the experimental success rate is further improved from 25.23% to 27.56% after optimization. These experimental results show the importance of circuit optimization and algorithm optimization in the Noisy-Intermediate-Scale Quantum (NISQ) era.
Grover's quantum search algorithm provides a proven quadratic speedup over classical linear search for unstructured databases. While its theoretical advantage is well established, experimental validation on real noisy intermediate-scale quantum (NISQ) hardware remains limited by noise, decoherence, and hardware constraints. In this work, we present an experimental comparison between classical linear search and Grover's quantum search algorithm executed on IBM Quantum real superconducting hardware using Qiskit Runtime. A four-qubit implementation corresponding to a 16-element search space is evaluated across multiple experimental runs. The results demonstrate consistent amplitude amplification, achieving an average success probability of 54.25% and an amplification factor of 8.68× over random guessing. Although classical execution remains faster in wall-clock time due to quantum hardware overhead, the experiment empirically validates the algorithmic advantage of Grover's search and quantifies the performance gap between ideal and real quantum processors in the NISQ era.
We present a quantum algorithm for solving the unstructured search problem with one marked element. Our algorithm allows generating quantum circuits that use asymptotically fewer additional quantum gates than the famous Grover's algorithm and may be successfully executed on noisy intermediate-scale quantum devices. We prove that our algorithm is optimal in the total number of elementary gates up to a multiplicative constant. As many NP-hard problems are, in fact, not unstructured, we also describe the partial uncompute technique which exploits the oracle structure and allows a significant reduction in the number of elementary gates required to find the solution. Combining these results allows us to use an asymptotically smaller number of elementary gates than Grover's algorithm in various applications, keeping the number of queries to the oracle essentially the same. We show how the results can be applied to solve hard combinatorial problems, for example, Unique kkk-SAT. Additionally, we show how to asymptotically reduce the number of elementary gates required to solve the unstructured search problem with multiple marked elements.
Target item searching in large-scale, unstructured text databases is a major computational task for traditional systems and usually requires algorithms whose time complexity is on the order ofO(N)O(N)O(N). Quantum computing presents a strong competitor by using Grover's algorithm, where theoretically the search complexity comes down toO(N)O(\sqrt{N})O(N​), making faster retrieval possible. This research considers the design and assessment of Grover's algorithm as it is used to find a target word in a paragraph. The process entails encoding a group of unique words into a quantum register and implementing a circuit that incorporates a bespoke oracle and a diffusion operator to amplify the probability amplitude of the target state. Performance was evaluated in two situations: an ideal noise-free simulation with Qiskit's AerSimulator and a real-world run on IBM's quantum hardware. Simulation results demonstrated always-high accuracy in identifying the target word. But tests on real quantum machines indicated that the reliability of the algorithm decreases with an increase in qubits. Though circuits of up to five qubits had tolerable accuracy, larger configurations were plagued by noise, gate errors, and decoherence effects. These results highlight both the potential of quantum search algorithms for text processing and the limitations of NISQ today.