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

Parallel Processing Letters

Abnormal Quantum State Search Based on Parallel Phase Comparison

Guanlei Xu, Xiaogang Xu, Xiaotong Wang

Published Nov 9, 2021• 0 citations
Publisher

Abstract

We discuss the problem of filtering out abnormal states from a larger number of quantum states. For this type of problem with [Formula: see text] items to be searched, both the traditional search by enumeration and classical Grover search algorithm have the complexity about [Formula: see text]. In this letter a novel quantum search scheme with exponential speed up is proposed for abnormal states. First, a new comprehensive quantum operator is well-designed to extract the superposition state containing all abnormal states with unknown number [Formula: see text] with complexity [Formula: see text] in probability 1 via well-designed parallel phase comparison. Then, every abnormal state is achieved respectively from [Formula: see text] abnormal states via [Formula: see text] times’ measurement. Finally, a numerical example is given to show the efficiency of the proposed scheme.

DOI
10.1142/s0129626421500225

Related papers

Generalized quantum search with parallelism

Robert M. Gingrich, Colin P. Williams, Nicolas J. Cerf

We generalize Grover's unstructured quantum search algorithm to enable it to work with arbitrary starting superpositions and arbitrary unitary operators. We show that the generalized quantum search algorithm, when cast in a special orthonormal basis, can be understood as performing an exact rotation of a starting superposition into a target superposition. We derive a formula for the success probability of the generalized quantum search algorithm after n rounds of amplitude amplification. We then use this formula to determine the optimal strategy for a punctuated quantum search algorithm, i.e., one in which the amplitude amplified state is observed before the point of maximum success probability. On average, the optimal strategy is about 12% better than the naive use of Grover's algorithm. The speedup obtained is not dramatic but it illustrates that a hybrid use of quantum computing and classical computing techniques can yield a performance that is better than either alone. In addition, we show that a punctuated quantum algorithm that takes the same average computation time as Grover's standard algorithm only requires half the coherence time. We then extend the analysis to the case of a society of k quantum searches acting in parallel. We derive an analytic formula that connects the degree of parallelism with the expected computation time for k-parallel quantum search. The resulting parallel speedup scales as $O(\sqrt{k}),$ while the minimum number of agents needed to ensure success, k, decreases as the inverse of the square of the achievable coherence time. This result has practical significance for the design of rudimentary quantum computers that are likely to have a limited coherence time.

arXiv:quant-ph/9904049•Physical Review A•Apr 19, 2000•46 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 eBooks•Apr 26, 2011•1 citation

Generalized quantum walk search algorithm

Pulak Ranjan Giri

Quantum walk search on graphs is primarily limited to real evolution operators, although there is no restriction for using the complex unitary matrix as the evolution operator. In the context of quantum search, several studies on the Grover’s search utilize the complex unitary matrix as an evolution operator, which allows for efficient searching of marked elements. However, the generalization of the quantum walk search to complex space has largely been overlooked. In this paper, we extend existing discrete-time coined quantum walk search algorithms on one- and two-dimensional periodic lattices to complex space by introducing two phase parameters, [Formula: see text], and [Formula: see text], into the coin and oracle operators, respectively, for four different discrete-time coined quantum walk search algorithms. One of the advantages of this generalization is that it enables the Grover and SKW coins with specific values of the phase parameters [Formula: see text], and [Formula: see text] to search for the exceptional configurations on a two-dimensional periodic lattice with high success probability, which is otherwise impossible to search using the real Grover and SKW coins operators.

International Journal of Quantum Information•Jul 24, 2026•0 citations

Search algorithm of abnormal structure on complete graph: Discussion of classical algorithm merged into the quantum computing thinking

H Chen, Wenbo Li, Zi-Fan Liu +1 more

© 2017, Editorial Department of Journal of Southeast University. All right reserved. Quantum computing thinking is used to explore new search methods for graph structures. A search algorithm for structural anomalies on complete graphs based on scattering quantum walk is proposed. Adding a pendant vertex to a complete graph, in which the number of vertices is N, breaks the symmetry of the complete graph and indicates the change of the topology of the complete graph. First, the precise definition of the evolutionary unitary operator U of scattering quantum walk in the complete graph is presented. The Hilbert space in which the walk occurs is projected to a lower-dimensional invariant subspace S, and the action of the evolutionary operator in the subspace US is given. Then, the equal superposition of all the basis states in the complete graph is chosen as the initial state. The eigenvalues and the eigenstates of US is calculated by using the perturbation theory, and the final state (pendants) of the algorithm is solved. Finally, the time complexity and the success probability of the algorithm are analyzed. The algorithm analysis and the Matlab simulation results show that the quantum search algorithm using scattering quantum walk can find the anomaly in O(N1/2) steps with the probability near to 1. However, the time complexity of the classical algorithm for searching the anomaly by the adjacency list is O(N). Therefore, the search algorithm based on scattering quantum walk can provide a quadric speed up over the classical algorithm for this specific problem.

•Sep 20, 2017•0 citations

A Fast Measurement based fixed-point Quantum Search Algorithm

Ashish Mani, C. Patvardhan

Generic quantum search algorithm searches for target entity in an unsorted database by repeatedly applying canonical Grover’s quantum rotation transform to reach near the vicinity of the target entity represented by a basis state in the Hilbert space associated with the qubits. Thus, when qubits are measured, there is a high probability of finding the target entity. However, the number of times quantum rotation transform is to be applied for reaching near the vicinity of the target is a function of the number of target entities present in the unsorted database, which is generally unknown. A wrong estimate of the number of target entities can lead to overshooting or undershooting the targets, thus reducing the success probability. Some proposals have been made to overcome this limitation. These proposals either employ quantum counting to estimate the number of solutions or fixed point schemes. This paper proposes a new scheme for stopping the application of quantum rotation transformation on reaching near the targets by measurement and subsequent processing to estimate the distance of the state vector from the target states. It ensures a success probability, which is at least greater than half for all the ratios of the number of target entities to the total number of entities in a database, which are less than half. The search problem is trivial for remaining possible ratios. The proposed scheme is simpler than quantum counting and more efficient than the known fixed-point schemes. It has same order of computational complexity as canonical Grover`s search algorithm but is slow by a factor of two and requires an additional ancilla qubit.

arXiv:1102.2332•International Conference on Quantum Information•Jan 1, 2011•4 citations

Two improvements in Grover's algorithm

Kai Kang

Grover search algorithm is applied to the current number of objectives in quantum unsorted database, the meaning of each goal difference is not taken into account. When the target is more than a quarter of the total items, the probability of the target falls quickly identify and target increases, and when the target is more than half of the total items, the algorithm will fail. To solve these problems, first of all, based on a weighted index improvement is proposed in which each target in accordance with the right given to the importance of the weight coefficient. These different weight coefficients, we give all the target state, which may make the probability of each target equal weights of the quantum superposition. Secondly, an improved phase matching is proposed the phase rotation in both directions is the same, and the inner product of two states by the target amplitude superposition and initial state of the system is determined. When this inner product is 1/2 or more, when using the improved phase matching, the target may be 100% probability and by only one Grover iteration. Finally, the effectiveness of these measures by a simple search instance validation.

Chinese Control and Decision Conference (CCDC)•May 1, 2015•5 citations
We discuss the problem of filtering out abnormal states from a larger number of quantum states. For this type of problem with [Formula: see text] items to be searched, both the traditional search by enumeration and classical Grover search algorithm have the complexity about [Formula: see text]. In this letter a novel quantum search scheme with exponential speed up is proposed for abnormal states. First, a new comprehensive quantum operator is well-designed to extract the superposition state containing all abnormal states with unknown number [Formula: see text] with complexity [Formula: see text] in probability 1 via well-designed parallel phase comparison. Then, every abnormal state is achieved respectively from [Formula: see text] abnormal states via [Formula: see text] times’ measurement. Finally, a numerical example is given to show the efficiency of the proposed scheme.
We generalize Grover's unstructured quantum search algorithm to enable it to work with arbitrary starting superpositions and arbitrary unitary operators. We show that the generalized quantum search algorithm, when cast in a special orthonormal basis, can be understood as performing an exact rotation of a starting superposition into a target superposition. We derive a formula for the success probability of the generalized quantum search algorithm after n rounds of amplitude amplification. We then use this formula to determine the optimal strategy for a punctuated quantum search algorithm, i.e., one in which the amplitude amplified state is observed before the point of maximum success probability. On average, the optimal strategy is about 12% better than the naive use of Grover's algorithm. The speedup obtained is not dramatic but it illustrates that a hybrid use of quantum computing and classical computing techniques can yield a performance that is better than either alone. In addition, we show that a punctuated quantum algorithm that takes the same average computation time as Grover's standard algorithm only requires half the coherence time. We then extend the analysis to the case of a society of k quantum searches acting in parallel. We derive an analytic formula that connects the degree of parallelism with the expected computation time for k-parallel quantum search. The resulting parallel speedup scales as O(k),O(\sqrt{k}),O(k​), while the minimum number of agents needed to ensure success, k, decreases as the inverse of the square of the achievable coherence time. This result has practical significance for the design of rudimentary quantum computers that are likely to have a limited coherence time.
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.
Quantum walk search on graphs is primarily limited to real evolution operators, although there is no restriction for using the complex unitary matrix as the evolution operator. In the context of quantum search, several studies on the Grover’s search utilize the complex unitary matrix as an evolution operator, which allows for efficient searching of marked elements. However, the generalization of the quantum walk search to complex space has largely been overlooked. In this paper, we extend existing discrete-time coined quantum walk search algorithms on one- and two-dimensional periodic lattices to complex space by introducing two phase parameters, [Formula: see text], and [Formula: see text], into the coin and oracle operators, respectively, for four different discrete-time coined quantum walk search algorithms. One of the advantages of this generalization is that it enables the Grover and SKW coins with specific values of the phase parameters [Formula: see text], and [Formula: see text] to search for the exceptional configurations on a two-dimensional periodic lattice with high success probability, which is otherwise impossible to search using the real Grover and SKW coins operators.
© 2017, Editorial Department of Journal of Southeast University. All right reserved. Quantum computing thinking is used to explore new search methods for graph structures. A search algorithm for structural anomalies on complete graphs based on scattering quantum walk is proposed. Adding a pendant vertex to a complete graph, in which the number of vertices is N, breaks the symmetry of the complete graph and indicates the change of the topology of the complete graph. First, the precise definition of the evolutionary unitary operator U of scattering quantum walk in the complete graph is presented. The Hilbert space in which the walk occurs is projected to a lower-dimensional invariant subspace S, and the action of the evolutionary operator in the subspace US is given. Then, the equal superposition of all the basis states in the complete graph is chosen as the initial state. The eigenvalues and the eigenstates of US is calculated by using the perturbation theory, and the final state (pendants) of the algorithm is solved. Finally, the time complexity and the success probability of the algorithm are analyzed. The algorithm analysis and the Matlab simulation results show that the quantum search algorithm using scattering quantum walk can find the anomaly in O(N1/2) steps with the probability near to 1. However, the time complexity of the classical algorithm for searching the anomaly by the adjacency list is O(N). Therefore, the search algorithm based on scattering quantum walk can provide a quadric speed up over the classical algorithm for this specific problem.
Generic quantum search algorithm searches for target entity in an unsorted database by repeatedly applying canonical Grover’s quantum rotation transform to reach near the vicinity of the target entity represented by a basis state in the Hilbert space associated with the qubits. Thus, when qubits are measured, there is a high probability of finding the target entity. However, the number of times quantum rotation transform is to be applied for reaching near the vicinity of the target is a function of the number of target entities present in the unsorted database, which is generally unknown. A wrong estimate of the number of target entities can lead to overshooting or undershooting the targets, thus reducing the success probability. Some proposals have been made to overcome this limitation. These proposals either employ quantum counting to estimate the number of solutions or fixed point schemes. This paper proposes a new scheme for stopping the application of quantum rotation transformation on reaching near the targets by measurement and subsequent processing to estimate the distance of the state vector from the target states. It ensures a success probability, which is at least greater than half for all the ratios of the number of target entities to the total number of entities in a database, which are less than half. The search problem is trivial for remaining possible ratios. The proposed scheme is simpler than quantum counting and more efficient than the known fixed-point schemes. It has same order of computational complexity as canonical Grover`s search algorithm but is slow by a factor of two and requires an additional ancilla qubit.
Grover search algorithm is applied to the current number of objectives in quantum unsorted database, the meaning of each goal difference is not taken into account. When the target is more than a quarter of the total items, the probability of the target falls quickly identify and target increases, and when the target is more than half of the total items, the algorithm will fail. To solve these problems, first of all, based on a weighted index improvement is proposed in which each target in accordance with the right given to the importance of the weight coefficient. These different weight coefficients, we give all the target state, which may make the probability of each target equal weights of the quantum superposition. Secondly, an improved phase matching is proposed the phase rotation in both directions is the same, and the inner product of two states by the target amplitude superposition and initial state of the system is determined. When this inner product is 1/2 or more, when using the improved phase matching, the target may be 100% probability and by only one Grover iteration. Finally, the effectiveness of these measures by a simple search instance validation.