Transcript Quantum Algorithms

Debasis Sadhukhan
M.Sc. Physics, IIT Bombay
1.Quantum Algorithm
2. Canonical Grover’s Quantum
Search Algorithm
3. Generalized Quantum Search
Operator: Selective Inversions of
Two States
4. Generalized Quantum Search
Operator: Selective Inversions of
Three States
*An algorithm is a well defined procedure or a set of
instructions to perform an information processing task.
*Complexity Classes: P , NP
*Quantum algorithms are those that uses quantum
mechanical principles at the time of it’s execution.
*Advantage of Quantum Algorithm: Superposition
principle allows a quantum algorithm to exploit an
exponentially large number of quantum components
using only polynomial recourses.
Hard to design !
Unsorted Database Search Problem
A database is nothing but a collection of items.
Number of items: N
Classical Search:
Average number of query to succeed: N/2
In the worst case, we need N-1 query to succeed.
If there are M solutions, then we require O(N/M) trials to
succeed.
But using Grover’s Quantum Search Algorithm
require
only 𝑂
𝑁
𝑀
*
trial to succeed.
1.
2.
Start with 0
⨂𝑛
Apply Hadamard (𝐻 ⨂𝑛 ) gate on each state to get
uniform superposition of all states
1
2𝑛 −1
𝜓 = 𝑛 𝑖=0 |𝑖⟩
2
𝜓 =
3.
Apply 𝐼𝑡 : 1 − 2|𝑡⟩⟨𝑡|
4.
Apply 𝐼𝑠 : 1 − 2 𝑠 𝑠
𝑀
𝑁
t +
*
𝑁−𝑀
|𝜓𝑜𝑡ℎ𝑒𝑟 ⟩
𝑁
*Let’s start with the uniform superposition of all the states.
i.e. the source state |𝑠⟩.
*Our solution is the target state |𝑡⟩.
G = −𝐼𝑠 𝐼𝑡 , where, 𝐼𝑡 : 1 − 2|𝑡⟩⟨𝑡| & 𝐼𝑠 : 1 − 2|𝑠⟩⟨𝑠|
Iteration Required (m):
*
* Now,
𝑠 𝑡 = cos
so,
𝑀
𝑁
𝜋
2
−𝜃
= sin𝜃 ≈ 𝜃
* So, no. of iteration required is 𝑚 = 𝜋4
𝑁
𝑀
−
1
2
≡ 𝑂(
𝑁
)
𝑀
Grover’s algorithm drives a quantum computer from a known initial
state (source state) to an unknown final state (target state) by using
selective phase inversions of these states.
Grover's operator performs the selective inversions only on a unique
source state and a unique target state.
Here, in this project, we make our search operator to perform
selective inversions on more than one source and target states.
The generalized algorithm is simply a successive iteration of the new
Generalized Grover's search operator 𝐺2 = −𝐼𝑠1 ,𝑠2 𝐼𝑡1,𝑡2 , where
𝐼𝑠1,𝑠2 = 1 − 2 𝑠1 𝑠1 − 2 𝑠2 𝑠2 and 𝐼𝑡1,𝑡2 = 1 − 2 𝑡1 𝑡1 − 2|𝑡2 ⟩⟨𝑡2 |
The generalized search operator: Selective phase
inversions of two source states and two target states.
The operator 𝐺2 = −𝐼𝑠1 ,𝑠2 𝐼𝑡1 ,𝑡2 ,
where,
𝐼𝑠1 ,𝑠2 = 1 − 2 𝑠1 𝑠1 − 2 𝑠2 𝑠2
and 𝐼𝑡1 ,𝑡2 = 1 − 2 𝑡1 𝑡1 − 2|𝑡2 ⟩⟨𝑡2 |
Here,
By the property of Walsh-Hadamard transform,
*
Let us take,
We need to construct a four dimensional orthonormal basis to
analyze the operation.
New Basis:
|𝑡⊥1 ⟩, |𝑡⊥ 2 ⟩, |𝑡1 ⟩, |𝑡2 ⟩
Where,
and
*
The Generalized search operator found in the new four dimensional
orthonormal basis is,
=
=
4
𝑁
Where 𝜃 = cos −1 (1 − ).
Analysis is similar to the case of canonical Grover’s Algorithm.
Analysis for all ⟨𝒔𝒊 |𝒕𝒋 ⟩ to be positive or negative:
We choose,
Define,
|𝑠− ⟩ is perpendicular to 𝑡1 , 𝑡2 & 𝑠+ . So, 𝐺2 does not induce any coupling between these
states and |𝑠− ⟩.
Then the search problem effectively reduces to the conventional Grover's search problem
where we have one unique source states |𝑠+ ⟩ and multiple target sates |𝑡1 ⟩ and 𝑡2 .
Summary: The results are mainly distributed in two main category:
1.
The problem is reducible into two Grover's search problem in two different
subspace, spanned by
𝑡⊥1 , 𝑡1 and 𝑡⊥2 , |𝑡2 ⟩ .
2.
The analysis of the problem is similar to a Grover's search problem which can be
analyzed in conventional 𝑡⊥ , |𝑡⟩ basis for all ⟨𝑠𝑖 |𝑡𝑗 ⟩ to be positive or negative.
Formulation:
The new search operator is the selective phase inversions of three source
states and three target states.
The operator 𝐺3 = −𝐼𝑠1 ,𝑠2 ,𝑠3 𝐼𝑡1 ,𝑡2 ,𝑡3 ,
where, 𝐼𝑠1 ,𝑠2 ,𝑠3 = 1 − 2 𝑠1 𝑠1 − 2 𝑠2 𝑠2 − 2 𝑠3 𝑠3
and 𝐼𝑡1 ,𝑡2 ,𝑡3 = 1 − 2 𝑡1 𝑡1 − 2|𝑡2 ⟩⟨𝑡2 | − 2|𝑡3 ⟩⟨𝑡3 |
And
Again we need to find out the new search operator 𝐺3 in a 6 dimensional
orthonormal basis.
But, this problem is hard to analyze analytically, so we perform numerical
calculations on some specific cases.
We find orthogonal basis states 𝑡⊥1 , |𝑡⊥ 2 ⟩, |𝑡⊥ 3 ⟩, using Gram-Schmidt
orthogonalization.
The initial states in the
be
basis will
Now, we construct the matrix 𝐺3 in the new orthonormal basis and find
the eigenvalues and eigenvectors.
Result:
So, for the three states also we can categorized our results in two
different classes.
Now, we have taken some specific examples of this two classes and
analyze them numerically.
*
For the first example we have chosen 𝑓11 = 1, 𝑓12 = 0, 𝑓13 = 1, 𝑓21 =
0, 𝑓22 = 1, 𝑓23 = 0, 𝑓31 = 1, 𝑓32 = 0, 𝑓33 = 1.
This case corresponds to the case of two different 𝜃.
For n=16, we got,
Same for all the target states.
For different n, we have,
Plot:
Formula:
For the second example we have chosen 𝑓11 = 1, 𝑓12 = 1, 𝑓13 = 0, 𝑓21 =
0, 𝑓22 = 1, 𝑓23 = 1, 𝑓31 = 0, 𝑓32 = 0, 𝑓33 = 1.
This case corresponds to the case of three different 𝜃.
For n=16,
Plot: For |𝑡1 ⟩ & |𝑡3 ⟩,
For |𝑡2 ⟩,
For different n, we got
Formula: For 𝑡1 &|𝑡3 ⟩,
For |𝑡2 ⟩,
1.
The maximum amplitude of the target states after the optimal
number of iteration is independent of the dimension of the search
space.
2.
Depending on the maximum amplitude, we need to iterate the
generalized Grover’s operator suitable number of times to make the
maximum amplitude nearly equal to 1.
3.
For each case, the required number of iteration to get the target
states with almost 100% probability is the same as the time taken by
the canonical Grover's search operator.
4.
So, the performance of our new generalized algorithm is the same as
the conventional Grover’s search algorithm that performs selective
inversions only on a unique source state and a unique target state.