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

Europhysics Letters (EPL)

Phase matching in quantum search algorithm

Saptarshi Roy Chowdhury, Sudarshan Baruah, Biswaranjan Dikshit

Published Feb 8, 2023• 2 citations
Publisher

Abstract

Abstract We systematically generalize the Grover algorithm in a density matrix formalism by exploiting the underlying two-dimensional subspace of the problem. Using this, we derive analytic expressions for the success probability after arbitrary iterations of the generalized Grover operator with two generic phase angles . We show for the phase matching condition with three iterations, success probability can be achieved only with knowledge about the lower bound , where λ is the ratio of marked to total number of states in the database. This result will improve the quantum search algorithm when applied to databases with unknown number of marked states in the specified regime of λ , at the cost of decreased efficiency in the smaller λ region.

DOI
10.1209/0295-5075/acba41

Related papers

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•1 citation

Multiphase matching in the Grover algorithm

F. Masafumi Toyama, W. van Dijk, Yukihisa Nogami +2 more

Phase matching has been studied for the Grover algorithm as a way of enhancing the efficiency of the quantum search. Recently Li and Li found that a particular form of phase matching yields, with a single Grover operation, a success probability greater than $25/27$ for finding the equal-amplitude superposition of marked states when the fraction of the marked states stored in a database state is greater than $1/3$. Although this single operation eliminates the oscillations of the success probability that occur with multiple Grover operations, the latter oscillations reappear with multiple iterations of Li and Li's phase matching. In this paper we introduce a multiphase matching subject to a certain matching rule by which we can obtain a multiple Grover operation that with only a few iterations yields a success probability that is almost constant and unity over a wide range of the fraction of marked items. As an example we show that a multiphase operation with six iterations yields a success probability between 99.8 and $100\text{ }%$ for a fraction of marked states of $1/10$ or larger.

arXiv:0801.2956•Physical Review A•Apr 30, 2008•30 citations

Phase Matching in Quantum Searching and the Improved Grover Algorithm

Yang Sun

We briefly introduced some of our recent work related to the phase matching condition in quantum searching algorithms and the improved Grover algorithm. When one replaces the two phase inversions in the Grover algorithm with arbitrary phase rotations, the modified algorithm usually fails in searching the marked state unless a phase matching condition is satisfied between the two phases. The Grover algorithm is not 100% in success rate, an improved Grover algorithm with zero-failure rate is given by replacing the phase inversions with angles that depends on the size of the database. Other aspects of the Grover algorithm such as the SO(3) picture of quantum searching, the dominant gate imperfections in the Grover algorithm are also mentioned.

Yuanzihe wuli pinglun•Jan 1, 2004•7 citations

Phase matching in quantum searching

Gui‐Lu Long, Yan Li, Wei Lin Zhang +2 more

Each iteration in Grover’s original quantum search algorithm contains 4 steps: two Hadamard-Walsh transformations and two amplitudes inversions. When the inversion of the marked state is replaced by arbitrary phase rotation θ and the inversion for the prepared state |γ 〉 is replaced by rotation through φ, we found that these phase rotations must satisfy a matching condition θ = φ. Approximate formula for the amplitude of the marked state after an arbitrary number of iterations are also derived. When phase matching is obtained, we found that the generalized quantum search is still a rotation in 2-dimensional space, but with a small angle β ′ ≈ (2sin θ 2)β, where θ is the angle of phase rotation of the marked state and 2β is the angle of U(2) rotation when the phase rotations are the inversions in the original version. We give also a simple explanation of the phase matching requirement.

•Jan 1, 1999•113 citations

Phase Matching in Quantum Searching Algorithm with Weighted Targets

Panchi Li, Shiyong Li

As searching targets in an unordered database with Grover's algorithm,difference in marked items is not taken into consideration.If fraction of marked items is greater than 1/4,success probability of search decreases rapidly with increase of marked items.When the fraction of marked items is greater than 1/2,the algorithm is disabled.Aiming at above problems,an improved Grover's algorithm with weighted targets is proposed in which every target is assigned a weight coefficient according to its significance.With these weight coefficients,targets are represented as quantum superpositions which make probability getting target equal to its weight coefficient.An adaptive phase matching method is proposed based on weighted targets.The directions of phase rotations are contrary,and amplitudes of the two phase rotations are determined by inner-product of target quantum superposition and initial state of the system.As the inner-product is greater than(((3-5)/8)~(1/2),) success probability is equal to 1 with two steps of Grover iteration at most.The improved quantum searching algorithm and the new phase matching are verified by an example.

Jisuan wuli•Jan 1, 2008•1 citation

Adaptive Phase Matching in Grover’s Algorithm

Panchi Li, Kaoping Song

When the Grover’s algorithm is applied to search an unordered database, the successful probability usually decreases with the increase of marked items. In order to solve this problem, an adaptive phase matching is proposed. With application of the new phase matching, when the fraction of marked items is greater , the successful probability is equal to 1 with at most two Grover iterations. The validity of the new phase matching is verified by a search example.

Journal of Quantum Information Science•Jan 1, 2011•4 citations
Abstract We systematically generalize the Grover algorithm in a density matrix formalism by exploiting the underlying two-dimensional subspace of the problem. Using this, we derive analytic expressions for the success probability after arbitrary iterations of the generalized Grover operator with two generic phase angles . We show for the phase matching condition with three iterations, success probability can be achieved only with knowledge about the lower bound , where λ is the ratio of marked to total number of states in the database. This result will improve the quantum search algorithm when applied to databases with unknown number of marked states in the specified regime of λ , at the cost of decreased efficiency in the smaller λ region.
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.
Phase matching has been studied for the Grover algorithm as a way of enhancing the efficiency of the quantum search. Recently Li and Li found that a particular form of phase matching yields, with a single Grover operation, a success probability greater than 25/2725/2725/27 for finding the equal-amplitude superposition of marked states when the fraction of the marked states stored in a database state is greater than 1/31/31/3. Although this single operation eliminates the oscillations of the success probability that occur with multiple Grover operations, the latter oscillations reappear with multiple iterations of Li and Li's phase matching. In this paper we introduce a multiphase matching subject to a certain matching rule by which we can obtain a multiple Grover operation that with only a few iterations yields a success probability that is almost constant and unity over a wide range of the fraction of marked items. As an example we show that a multiphase operation with six iterations yields a success probability between 99.8 and 100 100\text{ }%100  for a fraction of marked states of 1/101/101/10 or larger.
We briefly introduced some of our recent work related to the phase matching condition in quantum searching algorithms and the improved Grover algorithm. When one replaces the two phase inversions in the Grover algorithm with arbitrary phase rotations, the modified algorithm usually fails in searching the marked state unless a phase matching condition is satisfied between the two phases. The Grover algorithm is not 100% in success rate, an improved Grover algorithm with zero-failure rate is given by replacing the phase inversions with angles that depends on the size of the database. Other aspects of the Grover algorithm such as the SO(3) picture of quantum searching, the dominant gate imperfections in the Grover algorithm are also mentioned.
Each iteration in Grover’s original quantum search algorithm contains 4 steps: two Hadamard-Walsh transformations and two amplitudes inversions. When the inversion of the marked state is replaced by arbitrary phase rotation θ and the inversion for the prepared state |γ 〉 is replaced by rotation through φ, we found that these phase rotations must satisfy a matching condition θ = φ. Approximate formula for the amplitude of the marked state after an arbitrary number of iterations are also derived. When phase matching is obtained, we found that the generalized quantum search is still a rotation in 2-dimensional space, but with a small angle β ′ ≈ (2sin θ 2)β, where θ is the angle of phase rotation of the marked state and 2β is the angle of U(2) rotation when the phase rotations are the inversions in the original version. We give also a simple explanation of the phase matching requirement.
As searching targets in an unordered database with Grover's algorithm,difference in marked items is not taken into consideration.If fraction of marked items is greater than 1/4,success probability of search decreases rapidly with increase of marked items.When the fraction of marked items is greater than 1/2,the algorithm is disabled.Aiming at above problems,an improved Grover's algorithm with weighted targets is proposed in which every target is assigned a weight coefficient according to its significance.With these weight coefficients,targets are represented as quantum superpositions which make probability getting target equal to its weight coefficient.An adaptive phase matching method is proposed based on weighted targets.The directions of phase rotations are contrary,and amplitudes of the two phase rotations are determined by inner-product of target quantum superposition and initial state of the system.As the inner-product is greater than(((3-5)/8)~(1/2),) success probability is equal to 1 with two steps of Grover iteration at most.The improved quantum searching algorithm and the new phase matching are verified by an example.