Quantum Algorithms

Download Report

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.