Transcript DEUTSCH`S ALGORITHM - METU Computer Engineering

Algorithms
Computer Science is no more about computers than astronomy is about telescopes.
E.W. Dijkstra
Algorithms
• Quantum Algorithms :
• S6.1 : Deutsch’s algorithm that determines a property of functions from {0, 1}
to {0, 1}.
• S6.2 : Generalize above algorithm to the Deutsch–Jozsa algorithm, which
deals with a similar property for functions from {0, 1} to {0, 1}.
• S6.3 : Simon’s periodicity algorithm: determine patterns of a function from {0,
1}^n to {0, 1}^n
• S6.4 : Grover’s search algorithm that can search an unordered array of size n
in √n time as opposed to the usual n time.
• S6.5 : Shor’s factoring algorithm: factor numbers in polynomial time. There
are no known classical algorithms that can perform this feat in such time.
n
DEUTSCH’S ALGORITHM
• All quantum algorithms work with the following framework:
• The system will start with the qubits in a particular classical state.
• From there the system is put into a superposition of many states.
• This is followed by acting on this superposition with several unitary
operations.
• And finally, a measurement of the qubits.
• Of course, there will be several variations of this theme. Nevertheless,
it will be helpful to keep this general scheme in mind as we proceed.
DEUTSCH’S ALGORITHM
• This algorithm is concerned with functions from the set {0, 1} to the set {0,
1}. There are four such functions that might be visualized as
• Call a function f : {0, 1} → {0, 1} :
• balanced if f (0) ≠ f (1), i.e., it is one to one.
• constant if f (0) = f (1).
• Of the four functions, two are balanced and two are constant.
• Deutsch’s algorithm solves the following problem:
• Given a function f : {0, 1} → {0, 1} as a black box, where one can evaluate an input,
but cannot “look inside” and “see” how the function is defined, determine if the
function is balanced or constant.
DEUTSCH’S ALGORITHM
• With a classical computer, one would have to first evaluate f on one input, then
evaluate f on the second input, and finally, compare the outputs.
• The following decision tree shows what a classical computer must do:
• The point is that with a classical computer, f must be evaluated twice. Can we do
better with a quantum computer?
DEUTSCH’S ALGORITHM
• A quantum computer can be in a superposition of two basic states at the same
time.
• We shall use this superposition of states to evaluate both inputs at one time.
• Such a function can be thought of as a matrix acting on the input. For instance,
the function is equivalent to the matrix.
• Multiplying state |0 on the right of this matrix would result in state |1, and
multiplying state |1 on the right of this matrix would result in state |0. The
column name is to be thought of as the input and the row name as the output.
DEUTSCH’S ALGORITHM
• However, this will not be enough for a quantum system.
• every gate must be unitary (and thus reversible), i.e. given the output, we must be able to
find the input.
• If f is the name of the function, then the following black-box Uf will be the
quantum gate that we shall employ to evaluate input:
• The top input, |x, will be the qubit value that one wishes to evaluate and the
bottom input, |y, controls the output.
• The top output will be the same as the input qubit |x and the bottom output will
be the qubit |y ⊕ f (x).
DEUTSCH’S ALGORITHM
• We are going to write from left to right the top qubit first and then the
bottom. So we say that this function takes the state |x, y to the state |x, y
⊕ f (x).
• If y = 0, this simplifies |x, 0 to |x, 0 ⊕ f (x) =|x, f (x).
• State |x, y goes to |x, y ⊕ f (x) , which further goes to
• |x, (y ⊕ f (x)) ⊕ f (x) = |x, y ⊕ ( f (x) ⊕ f (x)) = |x, y ⊕ 0 = |x, y,
DEUTSCH’S ALGORITHM
• In quantum systems, evaluating f is equivalent to multiplying a state by the
unitary matrix Uf .
• For function given earlier,
• the corresponding unitary matrix, Uf , is :
• Remember that columns corresponds to the input |x, y and rows
corresponds to the outputs |x , y.
DEUTSCH’S ALGORITHM
• Rather than evaluating f twice, try trick of superposition of states.
• Hadamard matrix can place a qubit in such a state:
• The obvious state to put
the bottom input into is
state |0, the quantum
circuit:
The
s will be used to
describe the state of the
qubits at each time click
DEUTSCH’S ALGORITHM
• In terms of matrices :
• The entire circuit is then (note that the right hand-side is the tensor
product |0, 0 ):
• The system starts in
• Then apply Hadamard only to the top:
• After multiplying with Uf :
DEUTSCH’S ALGORITHM
• Then the state
would be
• If we measure the top qubit, there will be a 50–50 chance of finding it in
state |0 and |1.
• Similarly, there is no real information to be gotten by measuring the bottom
qubit. So the obvious algorithm does not work.
DEUTSCH’S ALGORITHM
• Rather than leaving the bottom qubit in state |0, let us put it in the
superposition state:
• We can get to this superposition of states by multiplying state |1 with the
Hadamard matrix. We shall leave the top qubit as an ambiguous |x.
DEUTSCH’S ALGORITHM
• Rather than leaving the bottom qubit in state |0, let us put it in the
superposition state:
• We can get to this superposition of states by multiplying state |1 with the
Hadamard matrix. We shall leave the top qubit as an ambiguous |x.
DEUTSCH’S ALGORITHM
• Let us look how the states of the qubits change.
• Again, we do not gain any information if we measure the top qubit or the bottom qubit. The top
qubit will be in state |x and the bottom qubit will be either in state |0 or in state |1.
DEUTSCH’S ALGORITHM
• Deutsch’s algorithm works by putting both the top and the bottom qubits
into a superposition.
• We will also put the results of the top qubit through a Hadamard matrix.
MATRIX FORMS
*
*
DEUTSCH’S ALGORITHM
• at each point of the algorithm, the states are as follows:
• When we put the bottom qubit into a superposition and then multiply by Uf
DEUTSCH’S ALGORITHM
• For a general function f ,
• If f is constant , then
• If f is balanced, then
• Summing up:
DEUTSCH’S ALGORITHM
• Now, we simply measure the top qubit. If it is in state |0, then we know
that f is a constant function, otherwise it is a balanced function.
• This was all accomplished with only one function evaluation as opposed to
the two evaluations that the classical algorithm demands.
• Did we perform a magic trick here? Did we gain information that was not
there?
• Not really. There are four possible functions, with a classical computer we needed
two bits of information to determine which of the four functions we were given.
• What we are really doing here is changing around the information.
• We might determine which of the four functions is the case by asking the following
two questions:
• “Is the function balanced or constant?” and “What is the value of the function on 0?”
DEUTSCH’S ALGORITHM
• The Hadamard matrices are changing the question that we are asking
(change of basis).
• The intuition behind the Deutsch algorithm is that we are really just
performing a change of basis problem.
• We might rewrite quantum circuit we talked about as
DEUTSCH’-JOZSA ALGORITHM
• Consider functions f : {0, 1}n → {0, 1}.
• balanced if half of the inputs go to 0 (and the other half go to 1).
• constant if all the inputs go to 0 or 1.
• The Deutsch–Jozsa algorithm solves the following problem:
• Suppose you are given a function from : {0, 1}n → {0, 1} which you can evaluate but cannot “see” the way it
is defined. Suppose further that you are assured that the function is either balanced or constant.
Determine if the function is balanced or constant.
• Classically, this algorithm can be solved by evaluating the function on different inputs.
• The best case scenario is when the first two different inputs have different outputs, which assures us that
the function is balanced.
• In contrast, to be sure that the function is constant, one must evaluate the function on more than half the
possible inputs.
• So the worst case scenario requires
• Can we do better?
function evaluations.
• we solve the problem by entering a superposition of all 2n possible input states.
DEUTSCH’-JOZSA ALGORITHM
• The function f will be given as a unitary matrix :
Example :
DEUTSCH’-JOZSA ALGORITHM
• In order to place a single qubit in a superposition of |0 and |1, we used a
single Hadamard matrix.
• To place n qubits in a superposition, use tensor product of n Hadamard matrices.
DEUTSCH’-JOZSA ALGORITHM
DEUTSCH’-JOZSA ALGORITHM
What happens if we multiply a state with this matrix?
DEUTSCH’-JOZSA ALGORITHM
DEUTSCH’-JOZSA ALGORITHM
DEUTSCH’-JOZSA ALGORITHM
SIMON’S PERIODICITY ALGORITHM
• Consider functions f : {0, 1}n → {0, 1}n .
• We are further assured that there exists a secret (hidden) binary string
such that for all strings x, y ∈ {0, 1} , we have
n
SIMON’S PERIODICITY ALGORITHM
• How would one solve this problem classically?
• We would have to evaluate f on different binary strings. After each evaluation, check to see if that output has
already been found.
• If one finds two inputs x1 and x2 such that f (x1) = f (x2), then we are assured that
• If the function is a two-to-one function, then we will not have to evaluate more than half the inputs before
we get a repeat.
• If we evaluate more than half the strings and still cannot find a match, then we know that f is one to one and that c = 0n.
• So, in the worst case
• function evaluations will be needed
SIMON’S PERIODICITY ALGORITHM
The quantum part of Simon’s algorithm basically consists of performing the following operations several times:
SIMON’S PERIODICITY ALGORITHM
SIMON’S PERIODICITY ALGORITHM
EXAMPLE
SIMON’S PERIODICITY ALGORITHM
EXAMPLE