Fixed Phase Quantum Search Algorithm
Fixed Phase Quantum Search Algorithm
Ahmed Younes∗
Department of Math. & Comp. Science
Faculty of Science
Alexandria University
Alexandria, Egypt
October 24, 2018
Abstract
Building quantum devices using fixed operators is a must to simplify the hardware con-
struction. Quantum search engine is not an exception. In this paper, a fixed phase quantum
search algorithm that searches for M matches in an unstructured search space of size N
will be presented. Selecting phase shifts of 1.91684π in the standard amplitude amplification
will make the technique perform better so as to get probability of success at least 99.58% in
better than any know fixed operator quantum search algorithms. The algorithm
will be able to handle either a single match or multiple matches in the search space. The
algorithm will find a match in O
whether the number of matches is known or not
in advance.
1 Introduction
In 1996, Lov Grover [10] presented an algorithm that quantum mechanically searches an unstruc-
tured list assuming that a unique match exists in the list with quadratic speed-up over classical
algorithms. To be able to define the target problem of this paper, we have to organize the ef-
forts done by others in that field. The unstructured search problem targeted by Grover’s original
algorithm is deviated in the literature to the following four major problems:
• Unstructured list with a unique match.
• Unstructured list with one or more matches, where the number of matches is known
• Unstructured list with one or more matches, where the number of matches is unknown.
• Unstructured list with strictly multiple matches.
The efforts done in all the above cases, similar to Grover’s original work, used quantum paral-
lelism by preparing superposition that represents all the items in the list. The superposition could
be uniform or arbitrary. The techniques used in most of the cases to amplify the amplitude(s) of
the required state(s) have been generalized to an amplitude amplification technique that iterates
∗ayounes2@yahoo.com
http://arxiv.org/abs/0704.1585v2
the operation URs (φ)U
†Rt (ϕ), on U |s〉 where U is unitary operator, Rs (φ) = I− (1− eiφ) |s〉 〈s|,
Rt (ϕ) = I − (1− eiϕ) |t〉 〈t|, |s〉 is the initial state of the system, |t〉 represents the target state(s)
and I is the identity operator.
Grover’s original algorithm replaces U be W , where W is the Walsh-Hadamard transform, pre-
pares the superpositionW |0〉 (uniform superposition) and iteratesWRs (π)WRt (π) for O
where N is the size of the list, which was shown be optimal to get the highest probability with the
minimum number of iterations [23], such that there is only one match in the search space.
In [11, 15, 9, 17, 1], Grover’s algorithm is generalized by showing that U can be replaced by
almost any arbitrary superposition and the phase shifts φ and ϕ can be generalized to deal with the
arbitrary superposition and/or to increase the probability of success even with a factor increase
in the number of iterations to still run in O(
N). These give a larger class of algorithms for
amplitude amplification using variable operators from which Grover’s algorithm was shown to be
a special case.
In another direction, work has been done trying to generalize Grover’s algorithm with a uniform
superposition for known number of multiple matches in the search space [3, 8, 7, 6], where it was
shown that the required number of iterations is approximately π/4
N/M for small M/N , where
M is the number of matches. The required number of iterations will increase for M > N/2,
i.e. the problem will be harder where it might be excepted to be easier [19]. Another work has
been done for known number of multiple matches with arbitrary superposition and phase shifts
[18, 2, 4, 14, 16] where the same problem for multiple matches occurs. In [5, 18, 4], a hybrid
algorithm was presented to deal with this problem by applying Grover’s fixed operators algorithm
for π/4
N/M times then apply one more step using specific φ and ϕ according to the knowledge
of the number of matches M to get the solution with probability close to certainty. Using this
algorithm will increase the hardware cost since we have to build one more Rs and Rt for each
particular M . For the sake of practicality, the operators should be fixed for any given M and are
able to handle the problem with high probability whether or notM is known in advance. In [21, 22],
Younes et al presented an algorithm that exploits entanglement and partial diffusion operator to
perform the search and can perform in case of either a single match or multiple matches where
the number of matches is known or not [22] covering the whole possible range, i.e. 1 ≤ M ≤ N .
Grover described this algorithm as the best quantum search algorithm [12]. It can be shown that
we can get the same probability of success of [21] using amplitude amplification with phase shifts
φ = ϕ = π/2, although the amplitude amplification mechanism will be different. The mechanism
used to manipulate the amplitudes could be useful in many applications, for example, superposition
preparation and error-correction.
For unknown number of matches, an algorithm for estimating the number of matches (quantum
counting algorithm) was presented [5, 18]. In [3], another algorithm was presented to find a match
even if the number of matches is unknown which will be able to work if M lies within the range
1 ≤M ≤ 3N/4 [22].
For strictly multiple matches, Younes et al [20] presented an algorithm which works very ef-
ficiently only in case of multiple matches within the search space that splits the solution states
over more states, inverts the sign of half of them (phase shift of -1) and keeps the other half
unchanged every iteration. This will keep the mean of the amplitudes to a minimum for multiple
matches. The same result was rediscovered by Grover using amplitude amplification with phase
shifts φ = ϕ = π/3 [13], in both algorithms the behavior will be similar to the classical algorithms
in the worst case.
In this paper, we will propose a fixed phase quantum search algorithm that runs inO
This algorithm is able to handle the range 1 ≤ M ≤ N for both known and unknown number of
matches more reliably than known fixed operator quantum search algorithms that target this case.
The plan of the paper is as follows: Section 2 introduces the general definition of the target
unstructured search problem. Section 3 presents the algorithm for both known and unknown
number of matches. The paper will end up with a general conclusion in Section 4.
2 Unstructured Search Problem
Consider an unstructured list L of N items. For simplicity and without loss of generality we will
assume that N = 2n for some positive integer n. Suppose the items in the list are labeled with the
integers {0, 1, ..., N − 1}, and consider a function (oracle) f which maps an item i ∈ L to either
0 or 1 according to some properties this item should satisfy, i.e. f : L → {0, 1}. The problem
is to find any i ∈ L such that f(i) = 1 assuming that such i exists in the list. In conventional
computers, solving this problem needs O (N/M) calls to the oracle (query),where M is the number
of items that satisfy the oracle.
3 Fixed Phase Algorithm
3.1 Known Number of Matches
Assume that the system is initially in state |s〉 = |0〉. Assume that
denotes a sum over i
which are desired matches, and
denotes a sum over i which are undesired items in the list.
So, Applying U |s〉 we get,
∣ψ(0)
= U |s〉 = 1√
′ |i〉+ 1√
′′ |i〉, (1)
where U =W and the superscript in
∣ψ(0)
represents the iteration number.
Let M be the number of matches, sin(θ) =
M/N and 0 < θ ≤ π/2, then the system can be
re-written as follows,
∣ψ(0)
= sin(θ) |ψ1〉+ cos(θ) |ψ0〉 , (2)
where |ψ1〉 = |t〉 represents the matches subspace and |ψ0〉 represents the non-matches subspace.
Let D = URs (φ)U
†Rt (ϕ), Rs (φ) = I − (1 − eiφ) |s〉 〈s|, Rt (ϕ) = I − (1 − eiϕ) |t〉 〈t| and set
φ = ϕ as the best choice [14]. Applying D on
∣ψ(0)
we get,
∣ψ(1)
∣ψ(0)
= a1 |ψ1〉+ b1 |ψ0〉 , (3)
such that,
a1 = sin(θ)(2 cos (δ) e
iφ + 1), (4)
b1 = e
iφ cos(θ)(2 cos (δ) + 1), (5)
where cos (δ) = 2 sin2(θ) sin2(φ
)− 1.
Let q represents the required number of iterations to get a match with the highest possible
probability. After q applications of D on
∣ψ(0)
we get,
∣ψ(q)
∣ψ(0)
= aq |ψ1〉+ bq |ψ0〉 , (6)
such that,
aq = sin(θ)
eiqφUq (y) + e
i(q−1)φUq−1 (y)
, (7)
bq = cos(θ)e
i(q−1)φ (Uq (y) + Uq−1 (y)) , (8)
where y = cos(δ) and Uq is the Chebyshev polynomial of the second kind defined as follows,
Uq (y) =
sin ((q + 1) δ)
sin (δ)
. (9)
Let P qs represents the probability of success to get a match after q iterations and P
ns is the
probability not to get a match after applying measurement, so P qs = |aq|
and P qns = |bq|
that P qs +P
ns = 1. To calculate the required number of iterations q to get a match with certainty,
one the following two approaches might be followed:
• Analytically. The usual approach used in the literature when the number of matches M is
known in advance is to equate P qs to 1 or P
ns to 0 and then find an algebraic formula that
represents the required number of iterations, as well as, the phase shifts φ and ϕ in terms on
M . Using this approach is not possible for the case that the phase shifts should be fixed for
an arbitrary M such that 1 ≤M ≤ N as shown in the following theorem.
Theorem 3.1 (No Certainty Principle) Let D be an amplitude amplification operator
such that D = URs (φ)U
†Rt (ϕ), where U is unitary operator, Rs (φ) = I − (1 − eiφ) |s〉 〈s|,
Rt (ϕ) = I − (1 − eiϕ) |t〉 〈t|, |s〉 is the initial state of the system, |t〉 represents the target
state(s) and I is the identity operator. Let D performs on a system initially set to U |s〉.
If the phase shifts φ and ϕ should be fixed, then iterating D an arbitrary number of times
will not find a match with certainty for an arbitrary known number of matches M such that
1 ≤M ≤ N .
Proof To prove this theorem, we will use the usual approach, i.e. start with P qs = 1 or
P qns = 0 and calculate the required number of iterations q.
Since P qs = |aq|
and from Eqn.7, we can re-write P qs as follows setting φ = ϕ as the best
choice [14],
P qs =
sin2 (θ)
sin2 (δ)
(1− cos (δ) cos ((2q + 1) δ) + 2 cos (φ) sin ((q + 1) δ) sin (qδ)) . (10)
Setting P qs = 1 and using simple trigonometric identities we get, q =
, i.e. the required
number of iterations is independent of M , φ and ϕ, and represents an impossible value for a
required number of iterations.
• Direct Search. The alternative approach used in this paper is to empirically assume an
algebraic form for the required number of iterations that satisfy the quadratic speed-up of
the known quantum search algorithms and use a computer program to search for the best
phase shift φ that satisfy the condition,
max (min (P qs (φ))) such that 0 ≤ φ ≤ 2π and, 1 ≤ M ≤ N. (11)
i.e. find the value of φ that maximize the minimum value of P qs over the range 1 ≤M ≤ N .
0 0.2 0.4 0.6 0.8 1
0.991
0.992
0.993
0.994
0.995
0.996
0.997
0.998
0.999
Probability of Success Probability lower bound
Figure 1: The probability of success the proposed algorithm after the required number of iterations.
Assume that q =
sin(θ)
. Using this form for q, a computer program has been
written using C language to find the best φ with precision 10−15 that satisfy the conditions shown
in Eqn. 11. The program shows that using φ = 6.021930660106538 ≈ 1.91684π, the minimum
probability of success will be at least 99.58% compared with 87.88 % for Younes et al [22] and
50% for the original Grover’s algorithm [3] as shown in Fig. 2. To prove these results, using
φ = 1.91684π, the lower bound for the probability of success is as follows as shown in Fig. 1.
P qs =
sin2(θ)
sin2(δ)
(1− cos (δ) cos ((2q + 1) δ) + 2 cos (φ) sin ((q + 1) δ) sin (qδ))
sin2(θ)
sin2(δ)
(1− cos (δ) cos ((2q + 1) δ) + cos (φ) cos (δ)− cos (φ) cos ((2q + 1) δ))
≥ sin
sin2(δ)
(1 + cos2 (δ) + 2 cos (φ) cos (δ)) ≥ 0.9958.
where, cos (δ) = 2 sin2(θ) sin2(φ
)− 1, 0 < θ ≤ π/2, and cos ((2q + 1) δ) ≤ −cos(δ).
3.2 Unknown Number of Matches
In case we do not know the number of matches M in advance, we can apply the algorithm shown
in [3] for 1 ≤M ≤ N by replacing Grover’s step with the proposed algorithm. The algorithm can
be summarized as follows,
1- Initialize m = 1 and λ = 8/7. (where λ can take any value between 1 and 4/3)
2- Pick an integer j between 0 and m− 1 in a uniform random manner.
3- Run j iterations of the proposed algorithm on the state
∣ψ(0)
∣ψ(j)
∣ψ(0)
. (13)
0 0.2 0.4 0.6 0.8 1
Grover’s
Younes et al[21]
Fixed Phase
Figure 2: The probability of success of Grover’s algorithm, Younes et al algorithm [21] and the
proposed algorithm after the required number of iterations.
4- Measure the register
∣ψ(j)
and assume i is the output.
5- If f(i) = 1, then we found a solution and exit.
6- Set m = min
and go to step 2.
where m represents the range of random numbers (step 2), j represents the random number of
iterations (step3), and λ is a factor used to increase the range of random numbers after each trial
(step 6).
For the sake of simplicity and to be able to compare the performance of this algorithm with
that shown in [3], we will try to follow the same style of analysis used in [3]. Before we construct
the analysis, we need the following lemmas.
Lemma 3.2 For any positive integer m and real numbers θ, δ such that cos (δ) = c sin2(θ) − 1,
0 < θ ≤ π/2 where c = 2 sin2(φ
) is a constant,
sin2 ((q + 1) δ) + sin2 (qδ) = m− cos (δ) sin (2mδ)
2 sin (δ)
Proof By mathematical induction.
Lemma 3.3 For any positive integer m and real numbers θ, δ such that cos (δ) = c sin2(θ) − 1,
0 < θ ≤ π/2 where c = 2 sin2(φ
) is a constant,
sin ((q + 1) δ) sin (qδ) =
cos (δ)− sin (2mδ)
4 sin (δ)
Proof By mathematical induction.
Lemma 3.4 AssumeM is the unknown number of matches such that 1 ≤M ≤ N . Let θ, δ be real
numbers such that cos (δ) = 2 sin2(θ) sin2(φ
)− 1, sin2(θ) =M/N , φ = 1.91684π and 0 < θ ≤ π/2.
Let m be any positive integer. Let q be any integer picked in a uniform random manner between
0 and m− 1. Measuring the register after applying q iterations of the proposed algorithm starting
from the initial state, the probability Pm of finding a solution is as follows,
c (1− cos (δ))
1 + cos (δ) cos (φ)− (cos (δ) + cos (φ)) sin (2mδ)
2m sin (δ)
where c = 2 sin2(φ
), then Pm ≥ 1/4 for m ≥ 1/ sin (δ) and small M/N .
Proof The average probability of success when applying q iterations of the proposed algorithm
when 0 ≤ q ≤ m is picked in a uniform random manner is as follows,
sin2(θ)
m sin2(δ)
sin2 ((q + 1) δ) + sin2 (qδ) + 2 cos (φ) sin ((q + 1) δ) sin (qδ)
sin2(θ)
m sin2(δ)
m− cos(δ) sin(2mδ)
2 sin(δ)
+ cos (φ) cos (δ)− cos(φ) sin(2mδ)
2 sin(δ)
c(1−cos(δ))
1 + cos (δ) cos (φ)− (cos(δ)+cos(φ)) sin(2mδ)
2m sin(δ)
If m ≥ 1/ sin (δ) and M ≪ N then cos (δ) ≈ −1, so,
1− cos (φ)− (cos (φ)− 1) sin (2mδ)
1− cos (φ)− (1− cos (φ))
= 0.25
where −1 ≤ sin (2mδ) ≤ 1 for 0 < θ ≤ π/2.
We calculate the total expected number of iterations as done in Theorem 3 in [3]. Assume that
mq ≥ 1/ sin (δ), and vq = ⌈logλmq⌉. Notice that, mq = O
for 1 ≤M ≤ N , then:
1- The total expected number of iterations to reach the critical stage, i.e. when m ≥ mq:
λv−1 ≤ 1
2 (λ− 1)
mq = 3.5mq. (14)
2- The total expected number of iterations after reaching the critical stage:
λvq+u =
2 (1− 0.75λ)
mq = 3.5mq. (15)
The total expected number of iterations whether we reach to the critical stage or not is 7mq
which is in O(
N/M) for 1 ≤M ≤ N .
When this algorithm employed Grover’s algorithm, and based on the conditionmG ≥ 1/ sin (2θG) =
for M ≤ 3N/4,the total expected number of iterations is approximately 8mG for
1 ≤ M ≤ 3N/4. Employing the proposed algorithm instead, and based on the condition
0 0.2 0.4 0.6 0.8 1
s Fixed Phase
Younes et al[22]
Grover’s
Figure 3: The actual behavior of the functions representing the total expected number of iterations
for Grover’s algorithm, Younes et al algorithm [22] and the proposed algorithm taking λ = 8/7,
where the number of iterations is the flooring of the values (step function).
mq ≥ 1/ sin (δ) = O
,the total expected number of iterations is approximately 7mq
for 1 ≤M ≤ N , i.e. the algorithm will be able to handle the whole range, since mq will be able to
act as a lower bound for q over 1 ≤ M ≤ N . Fig. 3 compares between the total expected number
of iterations for Grover’s algorithm, Younes et al algorithm [22] and the Fixed Phase algorithm
taking λ = 8/7.
4 Conclusion
To be able to build a practical search engine, the engine should be constructed from fixed operators
that can handle the whole possible range of the search problem, i.e. whether a single match or
multiple matches exist in the search space. It should also be able to handle the case where the
number of matches is unknown. The engine should perform with the highest possible probability
after performing the required number of iterations.
In this paper, a fixed phase quantum search algorithm is presented. It was shown that selecting
the phase shifts to 1.91684π could enhance the searching process so as to get a solution with
probability at least 99.58%. The algorithm still achieves the quadratic speed up of Grover’s
original algorithm. It was shown that Younes et al algorithm [22] might perform better in case
the number of matches is unknown, although the presented algorithm might scale similar with an
acceptable delay. i.e. both run in O
. In that sense, the Fixed Phase algorithm can act
efficiently in all the possible classes of the unstructured search problem.
References
[1] E. Biham and D. Dan Kenigsberg. Grover’s quantum search algorithm for an arbitrary initial
mixed state. Physical Review A, 66:062301, 2002.
[2] D. Biron, O. Biham, E. Biham, M. Grassl, and D. A. Lidar. Generalized Grover search
algorithm for arbitrary initial amplitude distribution. arXiv e-Print quant-ph/9801066, 1998.
[3] M. Boyer, G. Brassard, P. Høyer, and A. Tapp. Tight bounds on quantum searching.
Fortschritte der Physik, 46:493, 1998.
[4] G. Brassard, P. Høyer, M. Mosca, , and A. Tapp. Quantum amplitude amplification and
estimation. arXiv e-Print quant-ph/0005055, 2000.
[5] G. Brassard, P. Høyer, and A. Tapp. Quantum counting. arXiv e-Print quant-ph/9805082,
1998.
[6] G. Chen and S. Fulling. Generalization of Grover’s algorithm to multiobject search in quantum
computing, part II: General unitary transformation. arXiv e-Print quant-ph/0007124, 2000.
[7] G. Chen, S. Fulling, and J. Chen. Generalization of Grover’s algorithm to multiobject search
in quantum computing, part I: Continuous time and discrete time. arXiv e-Print quant-
ph/0007123, 2000.
[8] G. Chen, S. Fulling, and M. Scully. Grover’s algorithm for multiobject search in quantum
computing. arXiv e-Print quant-ph/9909040, 1999.
[9] A. Galindo and M. A. Martin-Delgado. Family of Grover’s quantum-searching algorithms.
Physical Review A, 62:062303, 2000.
[10] L. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the
28th Annual ACM Symposium on the Theory of Computing, pages 212–219, 1996.
[11] L. Grover. Quantum computers can search rapidly by using almost any transformation.
Physical Review Letters, 80(19):4329–4332, 1998.
[12] L. Grover. A different kind of quantum search. arXiv e-Print quant-ph/0503205, 2005.
[13] L. Grover. Fixed-point quantum search. Phys. Rev. Lett., 95(15):150501, 2005.
[14] P. Høyer. Arbitrary phases in quantum amplitude amplification. Physical Review A,
62:052304, 2000.
[15] R. Jozsa. Searching in Grover’s algorithm. arXiv e-Print quant-ph/9901021, 1999.
[16] C. Li, C. Hwang, J. Hsieh, and K. Wang. A general phase matching condition for quantum
searching algorithm. arXiv e-Print quant-ph/0108086, 2001.
[17] G. L. Long. Grover algorithm with zero theoretical failure rate. arXiv e-Print quant-
ph/0106071, 2001.
[18] M. Mosca. Quantum searching, counting and amplitude amplification by eigenvector anal-
ysis. In Proceedings of Randomized Algorithms, Workshop of Mathematical Foundations of
Computer Science, pages 90–100, 1998.
[19] M. Nielsen and I. Chuang. Quantum Computation and Quantum Information. Cambridge
University Press, Cambridge, United Kingdom, 2000.
[20] A. Younes, J. Rowe, and J. Miller. A hybrid quantum search engine: A fast quantum algo-
rithm for multiple matches. In Proceedings of the 2nd International Computer Engineering
Conference, 2003.
[21] A. Younes, J. Rowe, and J. Miller. Quantum search algorithm with more reliable behaviour
using partial diffusion. In Proceedings of the 7th International Conference on Quantum Com-
munication, Measurement and Computing, 2004.
[22] A. Younes, J. Rowe, and J. Miller. Quantum searching via entangelment and partial diffusion.
Technical Report CSR-04-9, University of Birmingham, School of Computer Science, arXiv
e-Print quant-ph/0406207, June 2004.
[23] C. Zalka. Grover’s quantum searching algorithm is optimal. Physical Review A, 60(4):2746–
2751, 1999.
	Introduction
	Unstructured Search Problem
	Fixed Phase Algorithm
	Known Number of Matches
	Unknown Number of Matches
	Conclusion
