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 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 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 O(N) for large N, the asymptote is not a good indicator of the optimal number of iterations when 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≤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 N and M, 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.