Transcript A new algorithm for directed quantum search Tathagat Tulsi

A new algorithm for directed
quantum search
Tathagat Tulsi, Lov Grover, Apoorva Patel
Vassilina NIKOULINA, M2R III
Plan
•
•
•
•
Introduction
Direct quantum Search Algorithm
Analysis
Comparison
Introduction
The problem of search
• Database with fraction f of marked items,
we have no precise knowledge of f
• Algorithm returns 1 item from database :
 Marked item -> success
 Otherwise -> error
• The goal :
 Minimize error probability using smaller
number of queries
Introduction
• f - sufficiently small ->


1
 Optimal quantum search algorithm with O f  queries


• f - large ->
 Classical search algorithm may outperform quantum
algorithm

Direct quantum search.
Algorithm
Iterating n times:
Error probability:
cos2  cos2n 2
2n


 2 1
For ε>1/3 => better then Phase-π/3 Search
For ε<1/3 => worse then Phase-π/3 Search
1>ε>1/2 -> probability decrease monotonically
Set lower bound of ½ for ε 
Set upper bound of ½ for f =>
extra ancilla |+> + controlled oracle query
Phase-π/3 Search
Quantum search algorithm
selective inversions
UIsU*It Us
Phase-π/3 Search
Selective π/3-shift
/3 * /3
U
R
R
s
s U
t U
The best performance of Phase-π/3 Search
q   2q1
q(3 1)/2
n
! Limitation : restricted number of oracle queries
Direct quantum search
Algorithm
Goal: Decrease probability of non-target state
Initial state:
U
s
s
i
n

t
c
o
s

t

Ancilla in initial state: 0
Oracle query : t  flip ancilla
Error probability :
 cos 
2
To decrease error -> apply Diffusion operator
i
n
2
t 0
c
o
s
2
0
New state : s
(UI sU * )
cos2 2
Direct quantum search
Algorithm
H
(
H

U

I
)
0
s
0


(
U
s
)
0
(
H

U

I
)
0
s
0


(
U
s
)
0
U
(
H

U

I
)
0
s
0


(
U
s
)
0
Direct quantum search
Analysis
Initial state :
 0 1
 sin  t  cos  t  0
2 

 i  H  U  I  0 s 0  
Initial error probability:  cos2 
0 s 0
i
f
1

sin2
Direct quantum search
Analysis
Joint search space of ancilla-1 and the register j
Non-target states:
0t,0t,1t
Target state:
tj  1 t
 sin 
i  
 2

1 '
 tj 0  t j 0
N

 sin 
cos
cos 

t 'j  N 
0 t 
0 t 
1 t 
2
2
 2

1


N   cos 2   sin 2  
2


1 / 2

2
1 
Direct quantum search
Analysis
 sin  
1
 t j 0  t 'j 0
N
 2 
i  
sin 2 
P(1) 
 f /2
2
P(0)1/ N2
2
'


1


t


t
f
j
j
Direct quantum search
Analysis. Total error
Error probability after 1 iteration
Error probability after q iteration
2
P1 ( t 'j ) 
Pq ( t 'j ) 
N2
 2q
N2
Probability to find the register in non-target state:
2
'

j
2
'

j

2 2
2
0
tt 
1
tt 
N
c
o
s
N
N

N


q
2

22
q
2
q

1
Direct quantum search
Analysis. Total error
• Fixed point : ε=1 instead of ε=0 ->
 Error probability (1- ε)2q+1
• Number of oracle queries
 Directed quantum search to locate: ε=1-f
f

s
m
a
l
l
(
2
q

1
)
f


1

f
o
(
1
)





e

o
(
1
)
2
q

1
 Thus q=O(1/f) < O(1/√f)
Advantages of Algorithm
• Real variables
• Allowed values of q
ε ≤ εth <1
• Directed quantum search: q can take all odd positive numbers
• Phase-π/3 Search: q = (1,4,13,40,121,364,1093…)
• No. of ancilla states
• Directed quantum search: 2
• Phase-π/3 Search: 6 (to obtain phase transformations from binary oracle)
• Improvement when ε has the lower bound
• Instead of |+> we can take initial state
If r<1/2 then ε = 1-1/2r
If r>1/2 then ε =(2r-1)/(2r+1)
1 r 0  r 1
faster then Phase-π/3 Search
Conclusion
• Using irreversible measurement operators
• Superior to the Phase-π/3 Search
• Can be useful in other problems :
 quantum error control
Questions