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:1209.0637 · Physical Review A

Effect of qubit losses on Grover's quantum search algorithm

D. D. Bhaktavatsala Rao, Klaus Mølmer

Published Oct 18, 2012• 12 citations
arXivHTMLPDF

Abstract

We investigate the performance of Grover's quantum search algorithm on a register that is subject to a loss of particles that carry qubit information. Under the assumption that the basic steps of the algorithm are applied correctly on the correspondingly shrinking register, we show that the algorithm converges to mixed states with 50% overlap with the target state in the bit positions still present. As an alternative to error correction, we present a procedure that combines the outcome of different trials of the algorithm to determine the solution to the full search problem. The procedure may be relevant for experiments where the algorithm is adapted as the loss of particles is registered and for experiments with Rydberg blockade interactions among neutral atoms, where monitoring of atom losses is not even necessary.

DOI
10.1103/physreva.86.042321

Related papers

Efficient Grover search with Rydberg blockade

Klaus Mølmer, Larry Isenhower, Mark E. Saffman

We present efficient methods to implement the quantum computing Grover search algorithm using the Rydberg blockade interaction. We show that simple π-pulse excitation sequences between ground and Rydberg excited states readily produce the key conditional phase shift and inversion-about-the-mean unitary operations for the Grover search. Multi-qubit implementation schemes suitable for different properties of the atomic interactions are identified and the error scaling of the protocols with system size is found to be promising for experimental investigation.

arXiv:1102.3573•Journal of Physics B Atomic Molecular and Optical Physics•Sep 14, 2011•58 citations

Grover search algorithm with Rydberg-blockaded atoms: quantum Monte Carlo simulations

David Petrosyan, Mark E. Saffman, Klaus Mølmer

Abstract We consider the Grover search algorithm implementation for a quantum register of size N = 2 k using k (or k + 1 ) microwave- and laser-driven Rydberg-blockaded atoms, following the proposal by Mølmer et al (2011 J. Phys. B 44 184016 ). We suggest some simplifications for the microwave and laser couplings, and analyze the performance of the algorithm for up to k = 4 multilevel atoms under realistic experimental conditions using quantum stochastic (Monte Carlo) wavefunction simulations.

arXiv:1512.05588•Journal of Physics B Atomic Molecular and Optical Physics•Apr 14, 2016•18 citations

Grover's search algorithm for nnn qubits with optimal number of iterations

Simanraj Sadana

The success probability of a search of $M$ targets from a database of size $N$, using Grover's search algorithm depends critically on the number of iterations of the composite operation of the oracle followed by Grover's diffusion operation. Although the required number of iterations scales as $\mathcal{O}(\sqrt{N})$ for large $N$, the asymptote is not a good indicator of the optimal number of iterations when $\sqrt{M/N}$ is not small. A scheme for the determination of the exact number of iterations, subject to a threshold set for the success probability of the search (probability of detecting the target state(s)), is crucial for the efficacy of the algorithm. In this work, a general scheme for the construction of $n$-qubit Grover's search algorithm with $1 \leq M \leq N$ target states is presented, along with the procedure to find the optimal number of iterations for a successful search. It is also shown that for given $N$ and $M$, there is an upper-bound on the success probability of the algorithm.

arXiv:2011.04051•Nov 8, 2020•4 citations

Quantum search simulation with Wolfram Mathematica

Alexander N. Prokopenya

We consider Grover's algorithm of quantum search for one or several integers out of N = 2n, where n is a number of quantum bits in the memory register. There is a black-box or subroutine containing information about hidden integers and it can easily recognize these integers but we do not know which ones out of N they are. To find the hidden items we can do no better with a classical computer than to apply the subroutine repeatedly to all possible integers until we hit on the special one and in the worst case we have to repeat this procedure N times. We have analyzed the Grover algorithm carefully and showed that it enables to speed up this search quadratically, although its realization requires to know a number of hidden items. The lower bound for the probability of successful solving the search problem has been obtained. The validity of the results was demonstrated by simulation of the Grover search algorithm using the package QuantumCircuit written in the Wolfram Mathematica language.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Sep 28, 2016•0 citations

A guide on Grover search algorithms for solving QUBO problems

Jannes Weghake, Freyja Ullinger, Matthias Zimmermann

Typical industry-related optimizations, like routing, packing, or scheduling, can be reformulated as a quadratic unconstrained binary optimization (QUBO) problem [1]. In the fault-tolerant quantum computing era, a promising approach to solve these problems is the Grover Adaptive Search [2]. The Grover Adaptive Search is able to solve QUBOs with a quadratic speed-up in comparison to classical algorithms. Here different Grover runs are chained together in order to identify the optimal solution. In this poster, we present a comprehensive guide with intuitive visuals, a theoretical background and a walkthrough to help non-expert to apply the Grover Adaptive Search. In particular, we demonstrate how to parse the QUBOs into a Grover oracle - the quantum dictionary [3] - and what this implies for the different quantum registers involved. [1] G. Kochenberger, J.-K. Hao, F. Glover, M. Lewis, Z. Lü, H. Wang, and Y. Wang, J. Comb. Optim. 28, 58 (2014). [2] W. P. Baritompa, D. W. Bulger, and G. R. Wood, SIAM J. Optim. 15, 1170 (2005). [3] A. Gilliam, C. Venci, S. Muralidharan, V. Dorum, E. May, R. Narasimhan, and C. Gonciulea, arXiv:1907.11513 (2019).

•Mar 5, 2026•0 citations

INNOVATIVE TECHNOLOGIES AND METHODS OF PROFESSIONAL TRAINING OF QUANTUM COMPUTERS USING DIGITAL SCHEMATIC TECHNIQUES

Олена Михайлівна Трифонова, Mykola Sadovyі

The article is devoted to the actual problem of teaching methods of the subjects of the educational process of modern information and computer science. The contribution of Ukrainian scientists to the development of electronic computing machines, their programming and teaching methods, prospects for further research are briefly considered. In the natural sciences, elementary units are widely used for various measurements. In particular, Planck’s constant is the smallest portion, quantum of energy, quantum of action, which is used in quantum mechanics. It is also known from the course of physics that the smallest portion of energy in classical mechanics is the energy per one degree of freedom. Logically created mathematical models and theories describing the relevant properties of matter using the specified units. Similarly, emphasis is placed on clarifying the difference between a classical computer and quantum units of information. The concepts of bit of information, qubit and trit are revealed, and depending on the defined units of information, types of computers are distinguished: classical and quantum. The concepts of qubit and trit are considered mainly as a mathematical entity, and attention is not focused on the content of the physics of quantum objects, a comparison of the indicated units of quantum information with a traditional bit of information in the quantum world is given. A historical-genetic analysis of the registers of elementary logic systems, a theoretical study of the principles of superposition and interaction between quantum states, and experimental methods of implementing qubits and their connections have been carried out. An important field for the use of quantum computers is cryptology, for solving the problems of which Grover’s method has already been created. With Grover’s quantum algorithm, it is possible to quickly search for the necessary element in an unsorted database with 2nN (n is the length of the search space of the quantum register - the number of qubits in it; N is the size of the search space). However, although the quantum simulator gives a high probability of the correct result, experimental studies also show large discrepancies. Therefore, there is a problem for further research. Quantum computers can influence each other through the phenomenon of entanglement.

Academic Notes Series Pedagogical Science•Jan 1, 2023•3 citations
We investigate the performance of Grover's quantum search algorithm on a register that is subject to a loss of particles that carry qubit information. Under the assumption that the basic steps of the algorithm are applied correctly on the correspondingly shrinking register, we show that the algorithm converges to mixed states with 50% overlap with the target state in the bit positions still present. As an alternative to error correction, we present a procedure that combines the outcome of different trials of the algorithm to determine the solution to the full search problem. The procedure may be relevant for experiments where the algorithm is adapted as the loss of particles is registered and for experiments with Rydberg blockade interactions among neutral atoms, where monitoring of atom losses is not even necessary.
We present efficient methods to implement the quantum computing Grover search algorithm using the Rydberg blockade interaction. We show that simple π-pulse excitation sequences between ground and Rydberg excited states readily produce the key conditional phase shift and inversion-about-the-mean unitary operations for the Grover search. Multi-qubit implementation schemes suitable for different properties of the atomic interactions are identified and the error scaling of the protocols with system size is found to be promising for experimental investigation.
The success probability of a search of MMM targets from a database of size NNN, using Grover's search algorithm depends critically on the number of iterations of the composite operation of the oracle followed by Grover's diffusion operation. Although the required number of iterations scales as O(N)\mathcal{O}(\sqrt{N})O(N​) for large NNN, the asymptote is not a good indicator of the optimal number of iterations when M/N\sqrt{M/N}M/N​ is not small. A scheme for the determination of the exact number of iterations, subject to a threshold set for the success probability of the search (probability of detecting the target state(s)), is crucial for the efficacy of the algorithm. In this work, a general scheme for the construction of nnn-qubit Grover's search algorithm with 1≤M≤N1 \leq M \leq N1≤M≤N target states is presented, along with the procedure to find the optimal number of iterations for a successful search. It is also shown that for given NNN and MMM, there is an upper-bound on the success probability of the algorithm.
We consider Grover's algorithm of quantum search for one or several integers out of N = 2n, where n is a number of quantum bits in the memory register. There is a black-box or subroutine containing information about hidden integers and it can easily recognize these integers but we do not know which ones out of N they are. To find the hidden items we can do no better with a classical computer than to apply the subroutine repeatedly to all possible integers until we hit on the special one and in the worst case we have to repeat this procedure N times. We have analyzed the Grover algorithm carefully and showed that it enables to speed up this search quadratically, although its realization requires to know a number of hidden items. The lower bound for the probability of successful solving the search problem has been obtained. The validity of the results was demonstrated by simulation of the Grover search algorithm using the package QuantumCircuit written in the Wolfram Mathematica language.
Typical industry-related optimizations, like routing, packing, or scheduling, can be reformulated as a quadratic unconstrained binary optimization (QUBO) problem [1]. In the fault-tolerant quantum computing era, a promising approach to solve these problems is the Grover Adaptive Search [2]. The Grover Adaptive Search is able to solve QUBOs with a quadratic speed-up in comparison to classical algorithms. Here different Grover runs are chained together in order to identify the optimal solution. In this poster, we present a comprehensive guide with intuitive visuals, a theoretical background and a walkthrough to help non-expert to apply the Grover Adaptive Search. In particular, we demonstrate how to parse the QUBOs into a Grover oracle - the quantum dictionary [3] - and what this implies for the different quantum registers involved. [1] G. Kochenberger, J.-K. Hao, F. Glover, M. Lewis, Z. Lü, H. Wang, and Y. Wang, J. Comb. Optim. 28, 58 (2014). [2] W. P. Baritompa, D. W. Bulger, and G. R. Wood, SIAM J. Optim. 15, 1170 (2005). [3] A. Gilliam, C. Venci, S. Muralidharan, V. Dorum, E. May, R. Narasimhan, and C. Gonciulea, arXiv:1907.11513 (2019).
The article is devoted to the actual problem of teaching methods of the subjects of the educational process of modern information and computer science. The contribution of Ukrainian scientists to the development of electronic computing machines, their programming and teaching methods, prospects for further research are briefly considered. In the natural sciences, elementary units are widely used for various measurements. In particular, Planck’s constant is the smallest portion, quantum of energy, quantum of action, which is used in quantum mechanics. It is also known from the course of physics that the smallest portion of energy in classical mechanics is the energy per one degree of freedom. Logically created mathematical models and theories describing the relevant properties of matter using the specified units. Similarly, emphasis is placed on clarifying the difference between a classical computer and quantum units of information. The concepts of bit of information, qubit and trit are revealed, and depending on the defined units of information, types of computers are distinguished: classical and quantum. The concepts of qubit and trit are considered mainly as a mathematical entity, and attention is not focused on the content of the physics of quantum objects, a comparison of the indicated units of quantum information with a traditional bit of information in the quantum world is given. A historical-genetic analysis of the registers of elementary logic systems, a theoretical study of the principles of superposition and interaction between quantum states, and experimental methods of implementing qubits and their connections have been carried out. An important field for the use of quantum computers is cryptology, for solving the problems of which Grover’s method has already been created. With Grover’s quantum algorithm, it is possible to quickly search for the necessary element in an unsorted database with 2nN (n is the length of the search space of the quantum register - the number of qubits in it; N is the size of the search space). However, although the quantum simulator gives a high probability of the correct result, experimental studies also show large discrepancies. Therefore, there is a problem for further research. Quantum computers can influence each other through the phenomenon of entanglement.