Transcript SLIDES-C-2005-q-0062

Grover. Part 2
Components of Grover Loop
• The Oracle -- O
• The Hadamard Transforms -- H
• The Zero State Phase Shift -- Z
O is an
H is
Oracle
Hadamards
Grover Iterate
Z is
Zero State
Phase Shift
H is
Hadamards
Inputs oracle
This is
action of
quantum
oracle
We need to
initialize in a
superposed state
This is a
typical way
how oracle
operates
Encodes input combination
with changed sign in a
superposition of all
This is a
typical way
how oracle
operation is
described
Role of Oracle
• We want to encode input combination with
changed sign in a superposition of all
states.
• This is done by Oracle together with
Hadamards.
• We need a circuit to distinguish somehow
globally good and bad states.
Vector of
Hadamards
Notation Reminder
a
a
Control
with
value
a=1
Control
with
value
a=0
a
equivalent
All
information
of oracle is
in the phase
but how to
read it?
This is just
an
example
of a single
minterm,
but can be
any
function
Zero State Phase Shift Circuit
Flips the
data phase
This is
value of
oracle bit
Flips the
oracle bit
when all bits
are zero
This is state
of all zeros
Rewriting matrix
Z to Dirac
notation, you
can change
phase globally
2 0 0 0
0 0 0 0
0 0 0 0
With accuracy
to phase
0 0 0 0
-1 0
+
0
0
0
-1 0
0
0
0
-1 0
0
0
0
-1
=
1 0 0 0
0 -1 0 0
0 0 -1 0
0 0 0 -1
Here you have
all components
of Grover’s loop
This is a global
view of Grover.
Repeatitions of G
In each G
Generality
• Observe that a problem is described only
by Oracle.
• So by changing the Oracle you can have
your own quantum algorithm.
• You can still improve the Grover loop for
particular special cases
Here we explain
in detail what
happens inside G.
This can be
generalized to Glike circuits
proof
Grover iterate has
two tasks: (1) invert
the solution states
and (2) invert all
states about the
mean
Will be
explained
in next
slide
Explanation
of the first
part of
Grover
iterate
formula
Here we prove that |> <  | used
inside HZH calculates the mean
a
Vector of
mean values
From previous
slide
(
)
(
This proof is easy and it only uses formalisms that
we already know.
)
What does it mean invert all
states about the mean?
Positive or
negative
amplitudes in
other
explanations
Amplitudes
of bits after
Hadamard
For
every bit
All possible states
Amplitudes of
bits after one
stage of G
This
value
based on
previous
slide
This slides
explains the
basic
mechanism
of the
Grover-like
algorithms
Additional
Exercise
This is a lot calculations, requires
matrix multiplication
You can verify it also in simulation
Here we
calculate
analytically
when to stop
For marked state
For unmarked
state
The equations
taken from the
previous slides
“Grover Iterate”
recursion
We want to
find how
many times
to iterate
We found k
from these
equations
But you can do better if you have knowledge, for instance the upper
bound of chromatic number in graph coloring
Grover search example.
• Here is an example of Grover search for n
= 3 qubits, where N = 2n =8.
– We omit reference to qubit n+1, which is in
state 1 /√2 (|0>−|1>i) and does not change.
• The dimension of the unitary operators for
this example is thus 2n = 8 also.)
oracle
• (Remember that
numbering
starts with 0
and ends with
7, so that the -1
here is in the
slot for |5>.)
• This matrix
reverses the
sign on state
|5>, and leaves
the other states
unchanged.
•Suppose the unknown
number is |a> = |5>.
•The matrix or black box
oracle Ufa is
•The Walsh matrix W8 is
Now we use
normalization
The matrix −Uf0 is
This matrix changes the sign on all states except |0>.
Finally, we have the repeated
Grover algorithm:
hadamards
oracle
shift
step RsRa in the
After second rotation
we get
Summary and our work
When you know anything about the problem (symmetry, observation, bounds, function
within some classification class) you can design a better Grover like algorithm but for
your data only.
This is enough in real life like CAD or Image Processing, since data are always specific,
not the worst case data as in Mathematic proofs
Problem for students
• Build the Grover algorithm for ternary
quantum logic.
• First you need to generalize Hadamard
transform to Chrestenson transform.
• Next you need to have some kind of
ternary reversible gates to build oracle.
• The same gates will be used for Zero
State Phase Shift circuit.