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

Physical Review E

Measuring peptide mass spectrum correlation using the quantum Grover algorithm

Keng Wah Choo

Published Mar 30, 2007• 2 citations
Publisher

Abstract

We investigated the use of the quantum Grover algorithm in the mass-spectrometry-based protein identification process. The approach coded the mass spectra on a quantum register and uses the Grover search algorithm for searching multiple solutions to find matches from a database. Measurement of the fidelity between the input and final states was used to quantify the similarity between the experimental and theoretical spectra. The optimal number of iteration is proven to be pi/4sqrt[N/k] , where k refers to the number of marked states. We found that one iteration is sufficient for the search if we let more that 62% of the N states be marked states. By measuring the fidelity after only one iteration of Grover search, we discovered that it resembles that of the correlation-based measurement used in the existing protein identification software. We concluded that the quantum Grover algorithm can be adapted for a correlation-based mass spectra database search, provided that decoherence can be kept to a minimum.

DOI
10.1103/physreve.75.031919

Related papers

Fast quantum search algorithms in protein sequence comparisons: Quantum bioinformatics

Lloyd C. L. Hollenberg

Quantum search algorithms are considered in the context of protein sequence comparison in bioinformatics. Given a sample protein sequence of length m (i.e., m residues), the problem considered is to find an optimal match in a large database containing N residues. Initially, Grover's quantum search algorithm is applied to a simple illustrative case-namely, where the database forms a complete set of states over the 2(m) basis states of a m qubit register, and thus is known to contain the exact sequence of interest. This example demonstrates explicitly the typical O(square root of [N]) speedup on the classical O(N) requirements. An algorithm is then presented for the (more realistic) case where the database may contain repeat sequences, and may not necessarily contain an exact match to the sample sequence. In terms of minimizing the Hamming distance between the sample sequence and the database subsequences the algorithm finds an optimal alignment, in O(square root of [N]) steps, by employing an extension of Grover's algorithm, due to Boyer et al. for the case when the number of matches is not a priori known.

arXiv:quant-ph/0002076•Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics•Nov 1, 2000•33 citations

Quantum search algorithm in unstructured database

A. D. Kozhukhivskyi

Grover's quantum algorithm was developed to solve the problem of searching an unstructured database for a certain unique element. In general, this problem can be formulated as follows: an unstructured database consists of elements and contains one unique element that has a certain property that can be tested with polynomial complexity, and which must be found with minimal time and complexity. Classical methods require querying the database to find the desired element, while Grover's algorithm allows you to perform only approximately steps, which are iterations of the procedure, to the database and be sure that the resulting element will be exactly the desired element with a probability close to 1. As in quantum algorithms aimed at cryptanalysis of symmetric transformations, Grover's algorithm repeats the procedure (Grover's iteration) to increase the probability of obtaining the correct result. Similarly to such algorithms in Grover's method, when iterations are continued after reaching the required number of iterations, the probability of obtaining the correct result decreases. This is due to the fact that during the execution of Grover's iteration, a rotation is performed in the complex space. Thus, each iteration, making a turn, brings the register closer and closer to the desired state, but at a certain point a maximum closeness is reached, at which the continued use of iterations will lead to a turn past the desired state, which will move the state of the system away from the desired state. The database for this algorithm can be any search space consisting of a certain number of elements. So, for example, it can be applied to find a secret key for a symmetric cryptograms formation or to find a collision for a hashing function.

Scientific Notes of the State University of Telecommunications•Jan 1, 2022•1 citation

Entanglement in the Grover's Search Algorithm

Shantanav Chakraborty, Subhashish Banerjee, Satyabrata Adhikari +1 more

Quantum Algorithms have long captured the imagination of computer scientists and physicists primarily because of the speed up achieved by them over their classical counterparts using principles of quantum mechanics. Entanglement is believed to be the primary phenomena behind this speed up. However their precise role in quantum algorithms is yet unclear. In this article, we explore the nature of entanglement in the Grover's search algorithm. This algorithm enables searching of elements from an unstructured database quadratically faster than the best known classical algorithm. Geometric measure of entanglement has been used to quantify and analyse entanglement across iterations of the algorithm. We reveal how the entanglement varies with increase in the number of qubits and also with the number of marked or solution states. Numerically, it is seen that the behaviour of the maximum value of entanglement is monotonous with the number of qubits. Also, for a given value of the number of qubits, a change in the marked states alters the amount of entanglement. The amount of entanglement in the final state of the algorithm has been shown to depend solely on the nature of the marked states. Explicit analytical expressions are given showing the variation of entanglement with the number of iterations and the global maximum value of entanglement attained across all iterations of the algorithm.

arXiv:1305.4454•May 20, 2013•9 citations

Exact results on Quantum search algorithm

Saptarshi Roy Chowdhury, Swarupananda Pradhan

We generalize Grover algorithm with two arbitrary phases in a density matrix set up. We give exact analytic expressions for the success probability after arbitrary number of iteration of the generalized Grover operator as a function of number of iterations, two phase angles (α, \{beta}) and parameter ξ introduced in the off diagonal terms of the density matrix in a sense to capture the coherence present in the initial quantum register. We extend Li and Li's idea and show for the phase matching condition α = -\{beta} = 0.35π with two iterations and ξ = 1, we can achieve success probability >= 0.8 only with a knowledge about the lower bound of λ = 0.166 where λ is the ratio of marked to total number states in the database. Finally we quantify success probability of the algorithm with decrease in coherence of the initial quantum state against modest noise in this simple model.

arXiv:2207.09762•Jul 20, 2022•0 citations

Analysis of Grover’s quantum search algorithm as a dynamical system

Ofer Biham, Daniel Shapira, Yishai Shimoni

Grover's quantum search algorithm is analyzed for the case in which the initial state is an arbitrary pure quantum state $|\ensuremath{\varphi}〉$ of n qubits. It is shown that the optimal time to perform the measurement is independent of $|\ensuremath{\varphi}〉,$ namely, it is identical to the optimal time in the original algorithm in which $|\ensuremath{\varphi}〉=|0〉,$ with the same number of marked states, r. The probability of success ${P}_{\mathrm{s}}$ is obtained in terms of the amplitudes of the state $|\ensuremath{\varphi}〉$ and is shown to be independent of r. A class of states, which includes fixed points and cycles of the Grover iteration operator, is identified. The relevance of these results in the context of using the success probability as an entanglement measure is discussed. In particular, the Groverian entanglement measure, previously limited to a single marked state, is generalized to the case of several marked states.

arXiv:quant-ph/0307141•Physical Review A•Aug 29, 2003•15 citations

QUANTUM COMPUTING, GROVER'S SEARCH ALGORITHM AND ITS APPLICATIONS IN BIOINFORMATICS

Keng Wah Choo

This article reviews quantum computing and quantum algorithms. Some insights into its potential in speeding up computations are covered, with emphasis on the use of Grover's Search. In the last section, we discuss applications of quantum algorithm to bioinformatics. In particular, the extension of quantum counting algorithm to protein mass spectra counting is proposed.

COSMOS•May 1, 2006•6 citations
We investigated the use of the quantum Grover algorithm in the mass-spectrometry-based protein identification process. The approach coded the mass spectra on a quantum register and uses the Grover search algorithm for searching multiple solutions to find matches from a database. Measurement of the fidelity between the input and final states was used to quantify the similarity between the experimental and theoretical spectra. The optimal number of iteration is proven to be pi/4sqrt[N/k] , where k refers to the number of marked states. We found that one iteration is sufficient for the search if we let more that 62% of the N states be marked states. By measuring the fidelity after only one iteration of Grover search, we discovered that it resembles that of the correlation-based measurement used in the existing protein identification software. We concluded that the quantum Grover algorithm can be adapted for a correlation-based mass spectra database search, provided that decoherence can be kept to a minimum.
Quantum search algorithms are considered in the context of protein sequence comparison in bioinformatics. Given a sample protein sequence of length m (i.e., m residues), the problem considered is to find an optimal match in a large database containing N residues. Initially, Grover's quantum search algorithm is applied to a simple illustrative case-namely, where the database forms a complete set of states over the 2(m) basis states of a m qubit register, and thus is known to contain the exact sequence of interest. This example demonstrates explicitly the typical O(square root of [N]) speedup on the classical O(N) requirements. An algorithm is then presented for the (more realistic) case where the database may contain repeat sequences, and may not necessarily contain an exact match to the sample sequence. In terms of minimizing the Hamming distance between the sample sequence and the database subsequences the algorithm finds an optimal alignment, in O(square root of [N]) steps, by employing an extension of Grover's algorithm, due to Boyer et al. for the case when the number of matches is not a priori known.
Grover's quantum algorithm was developed to solve the problem of searching an unstructured database for a certain unique element. In general, this problem can be formulated as follows: an unstructured database consists of elements and contains one unique element that has a certain property that can be tested with polynomial complexity, and which must be found with minimal time and complexity. Classical methods require querying the database to find the desired element, while Grover's algorithm allows you to perform only approximately steps, which are iterations of the procedure, to the database and be sure that the resulting element will be exactly the desired element with a probability close to 1. As in quantum algorithms aimed at cryptanalysis of symmetric transformations, Grover's algorithm repeats the procedure (Grover's iteration) to increase the probability of obtaining the correct result. Similarly to such algorithms in Grover's method, when iterations are continued after reaching the required number of iterations, the probability of obtaining the correct result decreases. This is due to the fact that during the execution of Grover's iteration, a rotation is performed in the complex space. Thus, each iteration, making a turn, brings the register closer and closer to the desired state, but at a certain point a maximum closeness is reached, at which the continued use of iterations will lead to a turn past the desired state, which will move the state of the system away from the desired state. The database for this algorithm can be any search space consisting of a certain number of elements. So, for example, it can be applied to find a secret key for a symmetric cryptograms formation or to find a collision for a hashing function.
Quantum Algorithms have long captured the imagination of computer scientists and physicists primarily because of the speed up achieved by them over their classical counterparts using principles of quantum mechanics. Entanglement is believed to be the primary phenomena behind this speed up. However their precise role in quantum algorithms is yet unclear. In this article, we explore the nature of entanglement in the Grover's search algorithm. This algorithm enables searching of elements from an unstructured database quadratically faster than the best known classical algorithm. Geometric measure of entanglement has been used to quantify and analyse entanglement across iterations of the algorithm. We reveal how the entanglement varies with increase in the number of qubits and also with the number of marked or solution states. Numerically, it is seen that the behaviour of the maximum value of entanglement is monotonous with the number of qubits. Also, for a given value of the number of qubits, a change in the marked states alters the amount of entanglement. The amount of entanglement in the final state of the algorithm has been shown to depend solely on the nature of the marked states. Explicit analytical expressions are given showing the variation of entanglement with the number of iterations and the global maximum value of entanglement attained across all iterations of the algorithm.
We generalize Grover algorithm with two arbitrary phases in a density matrix set up. We give exact analytic expressions for the success probability after arbitrary number of iteration of the generalized Grover operator as a function of number of iterations, two phase angles (α, \{beta}) and parameter ξ introduced in the off diagonal terms of the density matrix in a sense to capture the coherence present in the initial quantum register. We extend Li and Li's idea and show for the phase matching condition α = -\{beta} = 0.35π with two iterations and ξ = 1, we can achieve success probability >= 0.8 only with a knowledge about the lower bound of λ = 0.166 where λ is the ratio of marked to total number states in the database. Finally we quantify success probability of the algorithm with decrease in coherence of the initial quantum state against modest noise in this simple model.
Grover's quantum search algorithm is analyzed for the case in which the initial state is an arbitrary pure quantum state $|\ensuremath{\varphi}〉$ of n qubits. It is shown that the optimal time to perform the measurement is independent of $|\ensuremath{\varphi}〉,$ namely, it is identical to the optimal time in the original algorithm in which $|\ensuremath{\varphi}〉=|0〉,$ with the same number of marked states, r. The probability of success Ps{P}_{\mathrm{s}}Ps​ is obtained in terms of the amplitudes of the state $|\ensuremath{\varphi}〉$ and is shown to be independent of r. A class of states, which includes fixed points and cycles of the Grover iteration operator, is identified. The relevance of these results in the context of using the success probability as an entanglement measure is discussed. In particular, the Groverian entanglement measure, previously limited to a single marked state, is generalized to the case of several marked states.