Transcript and f(1) - Electrical & Computer Engineering

Review of basic quantum
and Deutsch-Jozsa.
Can we generalize Deutsch-Jozsa
algorithm?
Marek Perkowski, Department of Electrical
Engineering, Portland State University, 2005
Basic quantum circuits
These topics were illustrated on the blackboard:
•
•
•
•
•
•
•
Reversible functions
Gates. NOT, CNOT, CCNOT
General controlled gates.
Hadamard, square root of not
Kronecker Product.
Parallel and serial connections of gates.
Analysis of quantum circuits in Heisenberg and Dirac
notations.
– Tricks for fast computing.
• Entanglement.
• Toffoli gate from quantum primitives.
Deutsch’s
Problem
… everything started with small circuit of Deutsch…...
Deutsch’s Problem
(1985) ’85)
(Deutsch
David Deutsch
Delphi
Deutsch’s Problem
Determine whether f(x) is constant or balanced using as few
queries to the oracle as possible.
Classical Deutsch
Classically we need to query the oracle two times to solve Deutsch’s Problem
0
f
1
f

f(0)  f(1)
1 for balanced, 0 for constants
How would we use a Classical Oracle?
Classical circuit
1
1
0
f
1
f
0
0
Patterns of
constants

f(0)  f(1)
1 for balanced, 0 for constants
Classification means
recognizing patterns
and separating them
0
1
to categories.
1
0
Patterns of balanced functions of
single variable
Hadamard Transform
Single qubit

=
1/2
=
1
1
1
1
1
-1 1
1
1
1
-1
-1
1 -1
-1
1
Here I calculated Kronecker
product of two Hadamards
H
H
H
Parallel connection of
two Hadamard gates is
calculated by Kronecker
Product (tensor product)
Use of Hadamard gate
In Deutsch Circuit to create “Karnaugh
Map”
1
0

0
1
How to calculate
the initial state
=
0
1
0
0
1/2
How to calculate the
state after Hadamard
1
1
1
1
1
-1 1
-1
1
1
-1
-1
1 -1
-1
1
0
1 = 1/2
0
0
State after
Hadamard
State before
Hadamards
measure
Transform of
Hadamards
State after
Hadamards in
Dirac notation
State after oraqcle in Dirac notation
State after
Hadamards
in
Heisenberg
notation
1
-1
1
-1
Remarks
• We use both Heisenberg and Dirac notation because some things
are easier to prove in Dirac and some in Heisenberg.
• You can verify everything in Heisenberg, which is easy, but takes
many matrix calculations.
• Dirac notation introduces many transformations that may be not
obvious, if you are in doubt, just verify in Heisenberg notation.
• Because Dirac notation introduces symbol manipulation, you can
avoid repeated calculation. In next stages some standard
transforms of Dirac notation will be useful, but they are useful
only to prove facts, rather than invent facts.
• You can verify the state after oracle by yourself from definition,
but on the next page we will show everything step-by-step. In
future we will skip sometimes such obvious transformations.
Deutsch Circuit
Derivation of formula
from previous page
|xy>|x yf(x)>
|00>  |0 0 f(0)> = |0 f(0)>
How to calculate state
after oracle?
|01>  |0 1f(x)> = |0 f(0)>
|10>  |1 0 f(1)> = |1 f(1)>
|11>  |1 1 f(1)> = |1 f(1)>
measure
½ (|00> - |01> + |10> - |11>) 
½ (|0 f(0)> - |0 f(0)> + |1 f(1)> - |1 f(1)> )
Such derivations
should be done for
every quantum
algorithm.
Important general principle
Here, after oracle we
have all information
about the function
(Kmap) but we cannot
access it as is
Here, is the place to build a
circuit that transforms phaseencoded information to find
some boolean properties, here
we use Hadamard again.
measure
Common to many quantum
algorithms
We will
discuss how
can be
generalized!
Deutsch Circuit: four possible oracles
measure
x
f(x)
Quantum Deutsch: first explanation
1.
2.
Substitute f
3.
100 % |01>
100 % |01>
100 % |11>
100 % |11>
Conclusion from Deutsch
• Quantum computer can distinguish in a single function
evaluation (measurement) two classes of Boolean
functions that would require two evaluations
(measurements) in a classical computer.
• Quantum computer is fundamentally faster than classical
computer, because the number of function evaluations is
the most basic way of evaluating algorithm complexity.
• Complexity of calculation is not a mathematical but
physical property.
Quantum Deutsch: second explanation
This kind of proof is often
faster and more intuitive
but it is better to check
using matrices because
you likely can make errors
Here we present case
of constant
f(x) = 1
This circuit is replaced
by this
Z
rotation
Quantum Deutsch: second explanation
This is
obtained after
connecting
Hadamards
and
simplifying
Generalize these ideas
• So, we can distinguish by
measurement between first two
circuits from bottom and
second two circuits from
bottom.
f(0) = 0
yes
• This method is very general,
we can build various oracles
and check :
– how they can be distinguished?
– distinguished by how many tests?
no
f(1) = 0
yes
f(1) = 0
no
no
yes
• In this case, we just need one
test, but in a more general case
we can have a decision tree for
decision making.
Constant
Balanced
Quantum Deutsch:
third explanation
This method introduces
the concept of phase
kickback or encoding
information in phase
f : {0,1}  {0,1}
Find f(0) f(1) using only 1 evaluation of
a reversible “black-box” circuit for f
x
b
|y>
x
 f(x)
b f(xf(x)>
)
|y
The phase
depends on
function f(x)
Phase “kick-back” trick
( 1)
x
0 1
 f(x)
f( x )
x
0 1
x ( 0  1 )  x ( f(x)  f(x)  1 )
f( x )
 x ( 1) ( 0  1 )
Remember that for |y>:
|0>  f(x)
|1>  f(x) 1
 ( 1)
f( x )
x(0  1)
x ( 0  1 )  x ( f(x)  f(x)  1 )
f( x )
 x ( 1) ( 0  1 )
 ( 1)
Check for f(x)=0:
|0> - |1>
Because 0 1 = 1
f( x )
x(0  1)
For careful proof
checkers.
Check for f(x)=1:
|1> - |0>
Because 1 1 = 0 and next (1) (|0>-|1>)
In next slide we will rewrite
this formulat for |x>=0 and
|x>=1, since H creates all
possible values of cells.
A Deutsch quantum algorithm:
third explanation continued
0  1
( 1) f( 0 ) 0  ( 1) f(1) 1
(1)f( 0) f(0)  f(1)
 ( 1) f( 0) ( 0  ( 1) f( 0 )f(1) 1 )
We apply one
Hadamard to
create all cells
(minterms)
0
0 1
In Hilbert space
After measurement
H
H
f(0)  f(1)
Remember that phase is lost
in measurement
 f(x)
…here we reduce the number of H gates...
0 1
…we have also only one measurement...
Deutsch Algorithm Philosophy



Since we can prepare a superposition of all the inputs, we
can learn a global property of f (i.e. a property that
depends on all the values of f(x)) by only applying f once
The global property is encoded in the phase information,
which we learn via interferometry
Classically, one application of f will only allow us to probe its
value on one input
We use just one quantum evaluation by, in effect, computing f(0) and f(1) simultaneously
• The Circuit:
H
x
x
H
M
Uf
Not
always
H
y
y f(x)
Many variants of
Deutsch algorithm can
be created to provide
explanation of various
principles
Deutsch’s Algorithm
|0
|1
|0
H
x
M
H
x
Uf
H
y
|1
y f(x)
measurement
|2
|3
|0 = constant; |1 = balanced
• Initialize with |0 = |01
• Create superposition of x states using the first
Hadamard (H) gate. Set y control input using the
second H gate
• Compute f(x) using the special unitary circuit Uf
• Interfere the |2 states using the third H gate
• Measure the x qubit
Deutsch’s Algorithm with single
qubit measurement
|0
H
|0
|1
0   0
1 
x
Uf
|1
H
y
H
x
|2
M
|3
y f(x)
 0  1  0  1 
1  
 2 

 2 

 0

1f (0) 0  1 f (1) 1 0  1   

2 


 


2

 2  0
 
 

0  1 
 0 
 2 
 if f(0) = f(1)
3  
0  1 

1




 2 
 if f(0) ≠ f(1)

1
2
1
2
0



0



1
2
1
2


 if f(0) = f(1)


 if f(0) ≠ f(1)
Deutsch In Perspective
Quantum theory allows us to do in a
single query what classically requires two
queries.
What about problems where the
computational complexity is
exponentially more efficient?
Balanced Functions
Balanced functions have each possible value equal number of times.
In binary, half zeros, half ones
In ternary, 1/3 rd zeros, 1/3 ones, 1/3 twos.
2n-1+1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
Global
property
1
Constant one
0
balanced
Extended Deutsch’s Problem
• Given black-box f:{0,1}n{0,1},
– and a guarantee that f is either constant or balanced (1 on
exactly ½ of inputs)
– Which is it?
– Minimize number of calls to f.
• Classical algorithm, worst-case:
– Order 2n time!
• What if the first 2n-1 cases examined are all 0?
– Function could be either constant or balanced.
• Case number 2n-1+1: if 0, constant; if 1, balanced.
• Quantum algorithm is exponentially faster!
– (Deutsch & Jozsa, 1992.)
Deutsch-Jozsa Problem
(1992)
Deutsch-Jozsa Problem
Determine whether f(x) is constant or balanced using as few queries
to the oracle as possible.
Classical Deutsch Jozsa
1
0
x
1
0
x
This slide only presents another way of visualizing constant
and balanced functions.
Both visualization as a waveform (as above) and as Karnaugh
Map (truth Table) have heuristic value to find analogies with
signal processing and logic design
Getting good feeling
• Before we prove formally Deutsch-Jozsa, we
will analyze few examples for few variables,
just to get intuitive feeling.
• Next we will prove the theorem formally, using
Dirac notation.
• You can use Heisenberg notation as well, but it
takes more space.
1.
As you remember, we encode information in phase.
2.
We will encode Boolean “0” using phase plus (complex number 1)
3.
We will encode Boolean “1” using phase minus (complex number -1).
4.
This is the so-called S encoding of spectral theory. It is better for many
applications than R encoding that I do not introduce yet.
Balanced and constant functions as seen by
Ones in Kmap
Hadamard
This is number of
encoded by “-1”,
zeros by “1”
1
1
Constant 0
1
1
1
1
-1
1
-1
1
1
1
-1
-1
1
1
-1
-1
1
1
Matrix M
Vector V
minterms “0” in the
function
4
This is
measure of
correlation
with other
rows of M
0
=
0
0
Vector S
Observations
• The first row of the Hadamard matrix has all ones.
This means that we calculate the global value
corresponding to the number of ones in the first
spectral parameter.
• The other than first rows of Hadamard matrix have
equal number of ones and minus ones, which
means that they check correlations of data vectors
to certain balanced functions.
Balanced and constant functions as seen by
Hadamard
This is number of
Constant 1
1
1
1
1
-1
1
-1
1
-1
-1
1
1
-1
-1
-1
1
-1
-1
1
-1
Matrix M
Vector V
minterms “1” in the
function
-4
This is
measure of
correlation
with other
rows of M
0
=
0
0
Vector S
Balanced and constant functions as seen by
This means we
Hadamard
balanced
This row describes certain balanced
function
1
1
1
1
1
0
1
-1
1
-1
-1
4
1
1
-1
-1
1
1
-1
-1
Matrix M of
Hadamard transform
1
=
-1
Vector V of
encoded data
have half “1”
and half “0s”
0
0
Vector S of
spectral
coefficients
(normalization
coeficient
removed)
What are those balanced functions?
ab
00
01
10
a b0
0 0
1
11
1
1
1
1
1
-1
1
-1
a b0
1
-1
0 0
1
1
1
1
1
1
-1
-1
-1
Matrix M
1
Function a
0
0
a b
0
1
0 0
1
0
1
1
1
0
0
Function 0
Function b
Function ab
a b0 1
0 0 1
1
1
0
Conclusion on Hadamard Matrix
• First row represents function (constant) 0
• All other rows represent linear functions.
Linear functions
Negated Linear functions
0
1 0
a
1a
b
1b
ab
1  ab
Affine functions
Now formal
proof
Quantum DJ
This slide shows that I can read
function in phase encoding.
But this is of not much use itself.
This just comes from
generalization of third
method example
Now we additionally apply
Hadamard in output of the function
This is like a Kmap with
every true minterm (1)
encoded by -1
And every false minterm (0)
encoded by 1
We can say that Hadamard gates before the oracle
create the Kmap of the function, setting the function in
each of its possible minterms (cells) in parallel
Motivating calculations for 3 variables
• As we remember, these are transformations of Hadamard gate:
|0>
H
|0> + |1>
|1>
H
|0> - |1>
In general:
|x>
H
|0> + (-1) x |1>
For 3 bits, vector of 3 Hadamards works as follows:
|abc> 
(|0>+(-1)a|1>) (|0>+(-1)b|1>) (|0>+(-1)c|1>) =
From
multiplication
|000> +(-1)c |001> +(-1)b |001>+(-1)b+c |001>000> +(-1)a |001> +
(-1)a+c |001> + (-1)a+b |001> (-1)a+b+c |001>
We can formalize this as in the next slide:
An n-bit Hadamard transform can be written in the following form:
Here we use normalizing
coefficient
We were able to
observe these
properties in the 2variable example
=
Recall our
example
1
1
1
1
-1
-4
1
-1
1
-1
-1
0
1
1
-1
-1
1
-1
-1
1
Matrix M
*
-1
-1
Vector V
=
0
0
Thus we get |0> in
measurement
Full Quantum DJ - conclusion
If the reading is |00..0> then function is
constant
If reading is other than |00..)> then the
function is balanced
Solves DJ with a SINGLE
query vs 2n-1+1 classical
deterministic!!!!!!!!!
Deutsch-Josza Algorithm (contd)
• This algorithm distinguishes constant from
balanced functions in one evaluation of f, versus
2n–1 + 1 evaluations for classical deterministic
algorithms
• Balanced functions have many interesting and
some useful properties
– K. Chakrabarty and J.P. Hayes, “Balanced Boolean
functions,” IEE Proc: Digital Techniques, vol. 145, pp
52 - 62, Jan. 1998.
Conclusion on Deutsch-Jozsa
• We can test in one measurement if the circuit is balanced or not,
assuming that we know that the circuit is balanced or constant.
• We can test in one measurement if the circuit is affine or not,
assuming that we know that the circuit is affine (including
constants).
• We can test with some probability what the circuit is if we have
no any knowledge of the circuit.
• How to design methods to learn about the circuit if we do not
know anything about it?
Can you
build a
classical
computer
which will
distinguish
patterns
like these
in one
evaluation?
The answer is:
• No, you cannot on a standard
(classical) computer
• You can, using a ternary quantum
computer
I leave this exercise to you, or it will
be shown next lecture.
Local patterns for Affine
functions
cd
00 01 11 10
ab
00 1 0 1
01 0 1 0
11 1 0 1
10
0 1 0
0
1
0
1
1
0
1
0
1
0
1
0
0
1
0
1
0
1
0
1
In red we show
cells for which
measurements
should be done in
classical
computing to find
the pattern.
a  b  c d 1
Classically we need 5 tests (arbitrary cell and
its all 4 Hamming distance-1 neighbors.
Quantumly we need just one test.
Conclusion and questions
• We can test in one measurement if the circuit is
balanced or not, assuming that we know that the
circuit is balanced or constant.
• We can test in one measurement if the circuit is
affine or not, assuming that we know that the
circuit is affine (including constants).
• We can test with some probability what the circuit
is if we have no any knowledge of the circuit.
• How to design methods to learn about the circuit if
we do not know anything about it.
Open Research Questions
• What if other transform are used?
– Reed-Muller, Haar, Fourier, Chrestenson?
• How to use these methods for decomposition and
synthesis of Boolean functions?
• Can this be extended to multiple-valued functions?
• How to build oracles for other NP problems:
–
–
–
–
–
Graph coloring
Set covering
SAT
Hamiltonian path
ESOP minimization
Open Research Questions
• How to build Quantum Hough Transform?
• How to build efficient image processing
algorithms?
• How to emulate them on standard FPGAs?
• How to emulate General Quantum Computers
and Grover – like algorithms using FPGAs?
• How to use heuristic knowledge, such as a
chromatic number to improve the speed of
Grover Algorithm?
Open Research Questions
• How to test quantum circuits?
• How to design quantum circuits to make them
even more highly testable?
• How to simulate quantum circuits more
efficiently?
• How to invent quantum circuits for problems of
Computational Intelligence?
• How to use quantum circuits to control robots?
The
end