arXiv:2001.00214 · Quantum Information and Computation

Grover's algorithm in natural settings

Apoorva D. Patel

Published Jul 14, 2021• 5 citations

Abstract

The execution of Grover's quantum search algorithm needs rather limited resources without much fine tuning. Consequently, the algorithm can be implemented in a variety of physical set-ups, which involve wave dynamics but may not need other quantum features. Several of these set-ups are described, pointing out that some of them occur quite naturally. In particular, it is entirely possible that the algorithm played a key role in the selection of the universal structure of genetic languages.

DOI: 10.26421/qic21.11-12-3

Related papers

Quantum Algorithms and the Genetic Code

Apoorva D. Patel

Replication of DNA and synthesis of proteins are studied from the view-point of quantum database search. Identification of a base-pairing with a quantum query gives a natural (and first ever!) explanation of why living organisms have 4 nucleotide bases and 20 amino acids. It is amazing that these numbers arise as solutions to an optimisation problem. Components of the DNA structure which implement Grovers algorithm are identified, and a physical scenario is presented for the execution of the quantum algorithm. It is proposed that enzymes play a crucial role in maintaining quantum coherence of the process. Experimental tests that can verify this scenario are pointed out.

Feb 14, 200069 citations

Quantum Search Algorithm

Che‐Ming Li, Jin-Yuan Hsieh, Der-San Chuu

IntroductionFor a search problem associated with a unsorted database, the remarkable Grover's quantum algorithm (1) provides a quadratic speedup over its classical counterpart.The search problem can be described as follows: for a given function f , there exists one unknown element in the set {0, 1, ..., N -1} that satisfies f (x)=-1, say x = τ, whereas the other N -1o n e sg i v e f (x)=1.How many times of evaluations of f are required to determine the element τ for f (τ)=-1?Through a conventional algorithm, one needs O(N) trials to achieve this aim.How about the utility of quantum algorithm for the search?For the scenario in the quantum world, the search problem can be rephrased in the quantum mechanical language: for a given unitary operator I τ , that is sometimes called the oracle operator, and a set of state vectors (orthonormal basis): s = {|0 , |1 , ..., |N -1 }, I τ |x = |x for all states in the set except I τ |x = -|x for x = τ.H owma n yqueriesofI τ are required to determine |τ ?By Grover's algorithm, one needs only O( √ N) quantum mechanical steps to find the marked state |τ out.It has been shown that Grover's algorithm is optimal since it needs minimal oracle calls to perform a quantum search (2).The quantum searching process will be briefly reviewed as follows.The first step of Grover's algorithm is to prepare a superposition state of all elements with uniform probability amplitude:Then apply the Grover kernel G = -I η I τ to |s ,w h er eI η is a unitary operator and contains no bias against the marked state.For large N,a f t e ra b o u tm = π √ N/4 repetitions of G operations, the probability to observe |τ is close to one, i.e., G m |s ∼ |τ .( 2 ) Since every single G involves one query of I τ ,onlyO( √ N) searching steps are required for a quantum search task.In what follows, we will first investigate on the general SU(2) formulation for the kernel of Grover's searching operator G.The discussions of quantum searching certainty, robustness, and the analog analogue version of the Grover's algorithm will be given afterwards.

InTech eBooksApr 26, 20110 citations

Modelling of Grover’s quantum search algorithms: implementations of Simple quantum simulators on classical computers

Sergey Victorovich Ulyanov, Andrey G. Reshetnikov, Olga Tyatyushkina

Models of Grover’s search algorithm is reviewed to build the foundation for the other algorithms. Thereafter, some preliminary modifications of the original algorithms by others are stated, that increases the applicability of the search procedure. A general quantum computation on an isolated system can be represented by a unitary matrix. In order to execute such a computation on a quantum computer, it is common to decompose the unitary into a quantum circuit, i.e., a sequence of quantum gates that can be physically implemented on a given architecture. There are different universal gate sets for quantum computation. Here we choose the universal gate set consisting of CNOT and single-qubit gates. We measure the cost of a circuit by the number of CNOT gates as they are usually more difficult to implement than single qubit gates and since the number of single-qubit gates is bounded by about twice the number of CNOT’s.

System Analysis in Science and EducationSep 30, 20204 citations

Quantum Algorithms for Searching Manifolds

Hooman Sherkat-Massoom

Quantum computing is a system of computation that exploits the quantum-mechanical nature of reality at nano-scales in order to perform certain operations in a way that can scale better than is possible with classical computing. While the hardware sideof quantum computing is still in its infancy, many quantum algorithms - sets of instructions to run on a quantum computer in order to complete particular tasks - have been designed and analyzed. One of the most famous of these is Grover’s algorithm, an algorithm for searching a database. Two types of generalizations of Grover’s algorithm have been studied: spatial search algorithms (algorithms for searching discrete spaces) and “analog” search algorithms (algorithms performed by the evolution of physical systems). We develop and analyze algorithms that are generalizations of both those generalizations – an analog search algorithm for searching continuous, rather than discrete, spaces.

Jan 1, 20180 citations

Implementing quantum genetic algorithms

Mihai Udrescu, Lucian Prodan, Mircea Vlăduţiu

This paper presents a new methodology for running Genetic Algorithms on a Quantum Computer. To the best of our knowledge and according to reference [6]there are no feasible solutions for the implementation of the Quantum Genetic Algorithms (QGAs). We present a new perspective on how to build the corresponding QGA architecture. It turns out that the genetic strategy is not particularly helpful in our quantum computation approach; therefore our solution consists of designing a special-purpose oracle that will work with a modified version of an already known algorithm (maximum finding [1]), in order to reduce the QGAs to a Grover search. Quantum computation offers incentives for this approach, due to the fact that the qubit representation of the chromosome can encode the entire population as a superposition of basis-state values.

ACM International Conference on Computing Frontiers (CF)May 3, 200635 citations

Simulating a Quantum Computer : Grover's Search Algorithm with Error Correction

Martin Sjöborg, Hanna Linn

Classical simulations of quantum computers give us an insight into various things such as what quantum algorithms can achieve, whether it is possible to verify that they function as postulated, the difficulties that have to be overcome before quantum computers can be realized, as well as how we can handle these difficulties. We build a Python library to simulate a quantum computer that can perform all quantum algorithms by defining an universal gate set, from which all quantum gates – and thereby all circuits – can be constructed. We implement two algorithms that both highlight two important aspects of quantum computing: Grover’s quantum search algorithm, which demonstrates the efficiency of quantum algorithms and their superiority over their classical counterparts by searching an unsorted list quadratically faster; and an error correcting code, the Shor code, which highlights the cost of correcting the possible errors in a quantum computer.We test the rigidity of Grover’s algorithm by introducing errors without correction, and find that the algorithm shows resilience to smaller 1-qubit Pauli errors, but looses its efficiency under larger errors and thus the need for Pauli error correction arise.

Jan 1, 20180 citations