Quantum Search Algorithms For Multiple Solution Problems: EECS 598 Class Presentation Manoj Rajagopalan

Quantum Search Algorithms for
Multiple Solution Problems
EECS 598 Class Presentation

Manoj Rajagopalan
Outline
1. Recap of Grovers algorithm for the unique solution case
2. Grovers algorithm for multiple solutions: multiplicity

known
3. Quantum search algorithm for multiple solutions:
multiplicity unknown
4. Quantum counting to determine multiplicity
References
1. Quantum Computing and Quantum Information textbook
2. A fast quantum mechanical algorithm for database

search, LK Grover, 1996
3. Tight bounds on quantum searching, M Boyer, G
Brassard, P Hoyer, 1996
4. Quantum counting, G Brassard, P Hoyer, A Tapp, 1998
Notation
1. n = # qubits in the system
2. N = # of possible values of n qubits = 2n

3. M = multiplicity of solution
4. k = probability amplitude of system in solution state
5. l = probability amplitude of system in non-solution state

6. A = set of indices that denote solutions (good states)
7. B = set of indices denoting bad states
8. = rotation angle corresponding to Grover operator
Grovers Algorithm for Unique Solution Case

Given F:{0,1}n {0,1}, find i0 F(i0)=1 and i i0 F(i)=0
1. Set up initial state |0 n
2. Apply the Hadamard transform

Hn |0 | =
1
N 1/ 2
Let i0 be the solution:
i
i 0
| = k |i0 +
l
j i 0
3. Grover operator made of 4 steps
Apply the oracle
Apply Hn
Conditional phase shift:
Apply Hn
x
(1) x 0 x
Unique Solution Case Recap (contd)

4. Apply the Grover operator. After j iterations,
(k , l ) (k j , l j )
Gj
N 2
2( N 1)
kj
k j 1
l j 1
k0 1
N
N
N
N 2
2
lj
l j 1 k j 1
l0 1
N
N
N
Need bound on the number of iterations
Unique Solution Case Recap (contd)

Let sin2 = 1
0< 2
1
lj
cos((2 j 1) )
N 1
1
~
=> m
4 2
k j sin(( 2 j 1) )
For km = 1,
(2m+1) = /2
For large N, sin =
1
N
m N
4
Multiple Solutions: Multiplicity known

Given F:{0,1}n {0,1}, find all i{0,1}n F(i)=1
M = number of solutions > 1
Define good states A = {i | F(i) = 1}|A| = M

bad states B = {j | F(j) = 0 }
|B| = N - M
Suffices to tackle good and bad states as groups

k = probability amplitude of each solution (element of set A)
l = probability amplitude of each element of set B
Mk2 + (N-M)l2 = 1

Grovers algorithm for the multiple solution case
Structurally the same as that in the case of unique solution
1. Set up initial state |0 n

2. Apply the Hadamard transform
3. Apply Grover operator repeatedly
Apply the oracle
Apply Hn
Conditional phase shift
Apply Hn
Differs in the oracle implementation: Oracle lends a

relative phase shift of 1 to all solutions

Define
(k , l ) k i l i
i A
iB
After j iterations:
(k , l ) (k j , l j )
Gj
1
kj
sin((2 j 1) )
M
sin 2 M
lj
2
1
cos((2 j 1) )
N M

Let m = upper bound on number of iterations
We want lm = 0
cos ((2m+1)) = 2

m
4
~
mm
=>
1
1
~
m
4 2
| cos(2m+1) | | sin |
Probability of failure after exactly m iterations
(N-M) lm2 = cos2((2m+1)) sin2 = M N
Negligible for M << N

For M << N, sin
4 4 sin 4
Knowing M, we can predetermine the upper bound on the

number of iterations, m.
Unique solution problem is a special case of this for M=1.
Multiple Solutions: unknown Multiplicity

Number of iterations required to obtain a solution with
significant confidence depends on the solutions multiplicity.
If M is not known, then there is no way of telling how many

iterations will suffice.
Take m =
N to be on the safe side? (max # iterations)
No! Probability of success minuscule when M = 4a2 where a

is a small integer.

Modified procedure for unknown M:
1. Initialize m = 1 and = 8/7 (actually 1 < < 4/3)
2. Choose integer j such that 0 j m

3. Apply j iterations of Grovers algorithm
4. Measure and let outcome be i
5. If F(i) == 1 then solution found: exit program
6. Else m = min(m, N ): goto step #2
Theorem: This algorithm finds a solution in O( N / M )

For M > 3N/4 constant expected time by classical sampling
For 0 < M 3N/4, runtime = O( N / M )
For M << N, runtime < 6 times runtime_if_M_were_known
Knowing the number of solutions helps in reducing runtime.
This motivates quantum counting
Quantum Counting
Aim: To determine the number of solutions M to an N item
unstructured search problem
Classical computing consults the oracle (N) times to

determine M
Quantum computing can combine Grovers algorithm and
phase estimation to determine M much faster!
Why count?
Fast estimation of M => rapid solution detection
Is there a solution at all? NP-Complete problems
Quantum Counting
Recall: The computational bases can be partitioned into two
subsets, the good states set A containing all the solutions, and
(k , l ) k i l i
i A
Letting
cos
we get
in the ,
iB
N M
,
N
cos 2
G
sin 2
basis.
N M
M

N
N
sin
sin 2
,
cos 2
M
,
N
Quantum Counting
Eigenvalues of G are ei2 and ei(2-2)
The value of can be determined by phase estimation
From , the value of M can be calculated
PHASE ESTIMATION
Given a unitary operator U and one of its eigenvectors, the
phase of its corresponding eigenvalue ei2 is determined
Quantum Counting
Complexity of phase estimation algorithms
Probability
Error in M
Runtime, P
of success
Absolute, max
Evaluations of F
2
2
MN 2 N
P
P
2
2
M 2
c
c
P4
8
8
c N
((c log log N ) N M )

Quantum Search Algorithms For Multiple Solution Problems: EECS 598 Class Presentation Manoj Rajagopalan

Uploaded by

Copyright:

Available Formats

Quantum Search Algorithms For Multiple Solution Problems: EECS 598 Class Presentation Manoj Rajagopalan

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Quantum Search Algorithms For Multiple Solution Problems: EECS 598 Class Presentation Manoj Rajagopalan

Uploaded by

Copyright:

Available Formats

Quantum Search Algorithms for

Multiple Solution Problems

EECS 598 Class Presentation

2. Grovers algorithm for multiple solutions: multiplicity

2. A fast quantum mechanical algorithm for database

2. N = # of possible values of n qubits = 2n

5. l = probability amplitude of system in non-solution state

Grovers Algorithm for Unique Solution Case

2. Apply the Hadamard transform

Let i0 be the solution:

3. Grover operator made of 4 steps

Apply the oracle

Conditional phase shift:

Unique Solution Case Recap (contd)

Unique Solution Case Recap (contd)

For large N, sin =

Multiple Solutions: Multiplicity known

Define good states A = {i | F(i) = 1}|A| = M

Suffices to tackle good and bad states as groups

Multiple Solutions: Multiplicity known

Structurally the same as that in the case of unique solution

1. Set up initial state |0 n

Apply the oracle

Conditional phase shift

Differs in the oracle implementation: Oracle lends a

Multiple Solutions: Multiplicity known

Multiple Solutions: Multiplicity known

Multiple Solutions: Multiplicity known

Knowing M, we can predetermine the upper bound on the

Multiple Solutions: unknown Multiplicity

If M is not known, then there is no way of telling how many

N to be on the safe side? (max # iterations)

No! Probability of success minuscule when M = 4a2 where a

Multiple Solutions: unknown Multiplicity

2. Choose integer j such that 0 j m

Theorem: This algorithm finds a solution in O( N / M )

Multiple Solutions: unknown Multiplicity

Classical computing consults the oracle (N) times to

Is there a solution at all? NP-Complete problems

You might also like