Module 4

• Finding prime factors has been a hard problem for centuries.

• The Factoring Problem is one of the unsolved problems in Computer
Science.
• It may take a few seconds to find prime factors of 51, however finding
prime factors of a 100 digit number might take years to factorize using
multiple traditional computers working in parallel to each other.
• Many encryption algorithms used for security in credit cards, and similar
financial transactions, benefit by exploiting this "factoring problem".
• It is believed that if this factoring problem can be solved, so can the
cracking of an encryption algorithm like RSA.
• A single quantum computer could easily solve this problem by executing
Shor’s algorithm.
• Shor’s algorithm can work only on computers with large set of quantum bits.
• In various quantum systems, many attempts have been made to implement
Shor's algorithm;
• however, none has come close to implementing it with a few quantum bits.
• It is said that Shor’s algorithm is one of the most challenging algorithms in
quantum computing known to date.
• Many encryption schemes assume that factorization of large numbers is
impossible in polynomial time.
• If it was possible, then encryption algorithms like RSA could have been broken.
• This is leading to the rise of new concepts such as post quantum cryptography
and Quantum hacking.
• Shor’s algorithm will take 10243 operations to factorize a 1024-bit
number.
• However, with a quantum computer running at 100 MIPS can
factorize a 1024 bit number in seconds.
• To achieve a single, entangled state, it works by using 2 registers, of
size 2048 and 1024 qubits respectively, that work coherently, to get a
single entangled state.
How Shor’s algorithm work?
• Factoring numbers with Shor’s algorithm begins with selecting a
random integer smaller than the number to be factored.
• The classically-calculated greatest common divisor (GCD) of these two
numbers, the random number and the target number, is then used to
determine whether the target number has already been factored
accidentally.
• We start with the large number we are factoring, N, and an initial
guess, g.
• There are two cases for this starting guess.
• In case one, either g is a factor of N or it shares a common factor
with N.
• In this case, using Euclid’s Algorithm, a method of checking or finding
common factors using subtraction or modulo, respectively.
• To find a factor of N, we don’t have to strictly guess a factor, but one
that shares factors with N works, too.
• If g is neither a factor of N nor shares a common factor, then we move on
to transforming this guess into a better one.
• For any two whole numbers, A and B, there exists a power p and
multiple m, such that Ap=m∗B+1.
• We can demonstrate this with some primes, say 3 and 7.
• 32=9=1∗7+2
• 33=27=3∗7+6
• 34=81=11∗7+4
• 35=243=34∗7+5
• 36=729=104∗7+13
• We can write our relationship with our terms:
gp=m∗N+1.
• Once we subtract 1 from both sides, getting
gp−1=m∗N, we can rewrite this as (gp/2+1)(gp/2 ​−1)=m∗N.
• This is where quantum computers take over.
• To reiterate, we are searching for a power to which we raise our initial
bad guess.
• When subtracting the large number term, m∗N, from this
exponentiated term, gp, we need a remainder of 1, or gp−m∗N=1.
• So our system is as follows.
• Input superposition of powers into exponentiation:
• ∣x⟩→[gx]→∣x,gx⟩.
• Input superposition of exponentiations into difference of the large
number term to find remainder:
• ∣x, gx ⟩→[>m∗N]→∣x,+r⟩.
• And we want this remainder to equal 1.
• We now take advantage of a structural relationship between
exponentiation and modular arithmetic.
• gx =m∗N+r → gx+p = m1∗N+r → gx+2p =m2∗N+r
• The remainder stays the same regardless of linear changes to the
exponent, meaning there is a repeating property with some period.
• Take this example with different powers creating different remainders
combining to have the same remainder.
• gp+10=gpg10
• =(mN+2)(m1N+4)
• =m m1 N2+4mN+2 m1 N + 8
• =(m m1 N/2+2m+ m1 )N+4⇒SOMETHING N+4
• =(m m1 N/4+m+m1 /2 )N+2⇒SOMETHING N+2.
• When we input a superposition through our system and measure the
remainder, we get a superposition of all possible powers that result in
only that remainder.
• And this remaining superposition repeats with a period of the
power p or has a frequency of f=1/p​.
• Just as a classical Fourier Transform translates a wave as a function of
time into a function of frequency, so too does a Quantum Fourier
Transform (QFT), with a superposition as an output with a frequency
of the input
• So, if we input a single state into a QFT, the output will be a
superposition of states with varying weights or probabilities that form
a wave with the input state as the frequency.
• And if we input multiple states into a QFT, the output will be a
superposition of superposition - with destructive and constructive
interference combining superposition into one wave.
• And if our input to the QFT is a superposition with period p,
destructive interference leaves only 1/p.
Grover’s Algorithm
• Grover’s algorithm i.e the quantum algorithm solves one of the
complex scenarios in the area of computing.
• It’s the second major algorithm proposed for quantum computing.
• It solves the problem of searching through unstructured data.
• let’s consider a situation where you have a list of unsorted numbers
N, where you want to find a value w (Red Box) from it that possesses
some unique properties.
• So how could you find w?
• Classical approach:
• In classical computing, we would have to check on average N/2 of
these items in the list.
• In simple terms you would have to verify each of them one by one
• In which you will require N steps i.e O(N).
• If random access and presort are added to implement binary search
on ordered data, it will require log(N) steps i.e O(log(N)).
• However, using a quantum algorithm will just roughly take √N steps i.e
O(√N) for finding w.
• For instance, let's take a list of 25 elements and we want to search for a
value from the list.
• So classically it will take N steps.
• With the quantum algorithm, it will take √N steps.
• Classically it will take 25 steps.
• Quadratically it will take √25=5 steps.
• It utilizes superposition and phase interference to improve the search.
• It’s the amplitude amplification that plays a very spatial role in searching
the element we want.
• The amplitude amplification is a procedure that increases the
probability amplitude of the value to be searched and decreased the
rest of the probability amplitudes.
• Consider the below Kets (k1, k2, k3,…..kn) in a balanced
superposition, we want to hunt kw.
• so we can do it by performing amplitude amplification.
• When the kets are sent for amplification process, the first oracle flips
the kw ket upside down to negative phase from the probability of .0
to -.5 which separates it from other kets.
Diffuser
• The second oracle inverts all the amplitude by calculating its mean i.e the
average.
• This leads to a decrease in the amplitude A∉ kw.
• And increases the kw ket such that the kw becomes 1 and the rest of the kets
becomes 0
• At the final stage, the states from the second oracle are measured
with encoded values relating to the item in the list.
• And it maps the resulting state back to the database.
• If the answer is incorrect the steps are repeated.
• The error probability is O(1/N).
• Here you can assume oracle and diffuser are simply two black boxes
that perform certain operations on the qubits.
• Firstly, oracle is denoted as Uf and the second one as Uφ, which is
Grover’s diffusion operator.
• These oracles are repeated √N times.
• If the matches are multiple m, then the oracles are repeated √(N/t)
times.
• Grover search can also be used to search multiple elements.
• The algorithm works as follows
1. Pick a random value you want search from the qubits.
2. Put all the qubits to superposition by passing it to Hadamard gate H.

• Construct oracle f that flips the amplitude of the object to be searched.

• Construct the Diffuser that inverts around the mean.

• Repeat the oracle √N times for a single target and √(N/t) for multiple
targets.
• Finally, validate the states with the values in the database.
Deutsch’s Algorithm
• The problem concerns functions of just one variable.
• The input can be either 0 or 1.
• The output also just takes the values of 0 or 1.
• There are four of these functions that we will denote f0, f1, f2 and f3
• The function f0 sends both inputs to 0 i.e. f0(0)=0 and f0(1)=0
• The function f1 sends 0 to 0 and 1 to 1 i.e. f0(0)=0 and f0(1)=1
• The function f2 sends 0 to 1 and 1 to 0 i.e. f0(0)=1 and f0(1)=0
• The function f3 sends both inputs to 1 i.e. f0(0)=1 and f0(1)=1
• The functions f0 and f3 are called constant functions.
• The output is the same value for both inputs—the output is constant.
• A function is called balanced if it sends half its inputs to 0 and the
other half to 1.
• Both f1and f2 are balanced.
• The question that Deutsch posed is: Given one of these four functions
at random, how many function evaluations do we have to make to
determine whether the function is constant or balanced?
• The classical analysis is as follows.
• We can evaluate our given function at either 0 or 1.
• Supposing that we choose to evaluate it by plugging in 0, then there are
two possible outcomes—either we get 0 or we get 1.
• If we get 0, all we know is f (0 )=0 . The function could be either f0 or f1.
• Since one is constant and the other is balanced, we are forced to evaluate
our function again to decide between them.
• Classically, to answer the question we have to plug both 0 and 1 into the
function.
• We need to make two function evaluations.
• Quantum Version:
• First, we construct gates that correspond to the four functions.
• This says that: If we input |0> ⊗ |0> , it outputs 0 ⊕ fi(0 ) .
• If we input |0> ⊗ |1> , it outputs 0 ⊗ |fi(0 ) ⊕ 1>.
• If we input |1> ⊗ |0> , it outputs 1 ⊗ |fi(1 )>.
• If we input |1> ⊗ |1> , it outputs 1 ⊗ |fi(1 ) ⊕ 1>.
• Notice that for each i, one of fi (0 ) and fi (0)⊕ 1 is equal to 0 and the other
is equal to 1,
• and one of fi (1 ) and fi (1)⊕ 1 is equal to 0 and the other is equal to 1.
• This means that the four outputs always give us the standard basis
elements.

• The little meter symbol at the right end of the top wire means that we are
going to measure this qubit.
• The lack of the meter symbol on the second wire tells us that we won’t be
measuring the second output qubit.
• The qubits 0 ⊗ 1 are input.
• They go through the Hadamard gates, which puts them in the state
• 1/√2 (|0>+ |1>) ⊗ 1/√2 (|0> - |1>) =1/2(|00>-|01>+|10>-|11>).
• These then go through the Fi gate.
• The state become
• ½ (|0>⊗ |fi(0)> −|0> ⊗ |fi(0)> ⊕ |1> + |1>⊗ |fi(1)> −|1> ⊗ |fi(1)>
⊕ |1> )
• This can be rearanged to give
• ½ (|0>⊗ |fi(0)> -|fi(0)> ⊕ |1>) + |1>⊗ (|fi(1)> −|fi(1)> ⊕ |1>)
• |fi(0)> -|fi(0)> ⊕ |1>) is either |0>-|1> or |1> - |0> depending on
whether fi(0) is 0 or 1.
• |fi(0)> -|fi(0)> ⊕ |1>= (-1) fi(0) (|0> - |1>)
• |fi(1)> -|fi(1)> ⊕ |1>= (-1) fi(1) (|0> - |1>)
• The state of our qubits after passing through the Fi gate can then be
written as
• ½ (|0> ⊗ ((-1)fi(0) (|0>-|1>) ) + |1> ⊗ ((-1)fi(1) (|0>-|1>) )
• ½ ((-1)fi(0) (|0> ⊗ ((|0>-|1>) ) + ((-1)fi(1) (|1> ⊗ ((|0>-|1>)))
• ½ ((-1)fi(0) |0>+ (-1)fi(1) |1> ⊗ (|0>-|1>)
• 1/√2 (-1)fi(0) |0>+ (-1)fi(1) |1> ⊗ 1/√2 (|0>-|1>)
• This shows that the two qubits are not entangled, and the top qubit has
state 1/√2 (-1)fi(0) |0>+ (-1)fi(1) |1>
• Let’s examine this state for each of the four possibilities for fi.
• For f0, we have f0(0) =f0(1)=0 so the qubit is (1/√2)(|0>+|1>)
• For f1, we have f1(0)=0 and f1(0)=1 so the qubit is (1/√2)(|0>-|1>)
• For f2, we have f2(0)=1 and f2(0)=0 so the qubit is (-1/√2)(|0>-|1>)
• For f3, we have f3(0)=1=f3(1)=1 so the qubit is (-1/√2)(|0>+|1>)
• The next step in the circuit is to send our qubit through the Hadamard
gate.
• This gate sends (1/√2)(|0>+|1>) to |0> and (1/√2)(|0>-|1>) to |1>.
• If i=0, the qubit is |0>.
• If i=1, the qubit is |1>.
• If i=2, the qubit is -|1>.
• If i=3, the qubit is - |0>.
• If we now measure the qubit in the standard basis, we will get 0 if i is either 0 or
3,
• and we will get 1 if i is either 1 or 2.
• f0 and f3 are the constant functions
• f1 and f2are the balanced.
• So, if after measuring we get 0, we know with certainty that the original function
was constant.
• If we get 1, we know that the original function was balanced.
• For Deutsch’s problem there is therefore a slight speedup using a
quantum algorithm.
• This algorithm has no real practical applications, but, as we noted
earlier, it was the first example of proving that there are quantum
algorithms faster than classical ones.
The Deutsch-Jozsa Algorithm
• Deutsch’s algorithm looked at functions of one variable.
• You were given one of these and had to determine whether it was a constant or
balanced function.
• The Deutsch-Jozsa problem is a generalization of this.
• We now have functions of n variables.
• The inputs for each of these variables can be either 0 or 1.
• The output is either 0 or 1.
• We are told that our function is either constant—all the inputs get sent to 0, or all the
inputs get sent to 1.
• or it is balanced—half the inputs get sent to 0 and the other half to 1.
• If we are given one of these functions at random, how many function evaluations do we
need to determine whether the function belongs to the constant group or to the
balanced group?
• We consider the case when n = 3.
• Our function takes three inputs, each of which can take two values.
• This means that there are 23, or 8, possible inputs: (0,0,0), (0,0,1),
(0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1).
• From the fact that f(0,0,0)= 1, f (0,0,1)= 1, f(0,1,0)= 1, f(0,1,1)= 1, we
cannot determine whether or not the function is balanced.
• We need to ask one more question.
• If the answer to the next question is also 1, then we know the
function is constant.
• If the answer is 0, then we know the function is balanced.
• This analysis works in general.
• Given a function of n variables, there will be 2n possible input strings.
• In the best-case scenario we can obtain the answer with just two
questions to the oracle, but in the worst case it will take us 2n−1 + 1
questions.
• Since the n−1 appears as an exponent, the function is exponential.
• In the worst case it requires an exponential number of inquiries to the
oracle.
• The Deutsch-Jozsa algorithm is a quantum algorithm that just
requires one question to the oracle, so the speedup is substantial!
• Given any function f(x0, x1, ….xn-1)− that has n boolean inputs and has
just one boolean output,
• We construct the gate F given by the following circuit, where the
slashes with n on the top lines indicate that we have n wires in
parallel.
Step 1. The Qubits Pass through the Hadamard Gate

• The top n inputs are all |0>.

• For n=2, this is |00>.

• It gives a superposition of all possible states.

• Each of the basis kets has the same probability amplitude (1/2 in this case).
• This calculation works for every value of n.
• After the n qubits have passed through H⊗n they are in superposition of all
possible states, each of which has the same probability amplitude: (1/√2)n.
• The bottom entry is just 1.
• This becomes (1/√2)(|0>-|1>) after passing through the Hadamard
gate.
• At this stage, our three input qubits will be in the following state
Step 2. The Qubits Pass through the F Gate
• After passing through the F gate the qubits will be in the following state.
• 1/2√2|00> ⊗(|f(0,0)>-|f(0,0) ⊕ 1>)
+ 1/2√2|01> ⊗(|f(0,1)>-|f(0,1) ⊕ 1>)
+ 1/2√2|10> ⊗(|f(1,0)>-|f(1,0) ⊕ 1>)
+ 1/2√2|11> ⊗(|f(1,1)>-|f(1,1) ⊕ 1>)
• We now use the fact that that if a is either 0 or 1 we have the following |a>
- |a ⊕ 1> = (-1 )d (|0>-|1>) to rewrite the state as
(-1)f(0,0)1/2|00> ⊗1/√2(|0>-|1>)
+(-1)f(0,1)1/2|01> ⊗1/√2(|0>-|1>)
+ (-1)f(1,0)1/2|10> ⊗1/√2(|0>-|1>)
+ (-1)f(1,1)1/2|11> ⊗1/√2(|0>-|1>)
• The bottom qubit is not entangled with the top qubits.
• We just look at the top two qubits.
• These top two are in state
• 1/2 ((-1)f(0,0)|00>+(-1)f(0,1)|01>+(-1)f(1,0)|10>+(-1)f(1,1)|11>
Step 3. The Top Qubits Pass through the Hadamard Gate
• The standard method is to convert our state to a column vector and then
multiply by the appropriate Kronecker product of the Hadamard matrix.
• This gives

• 1/ 4 ((-1)f(0,0) +(-1)f(0,1) +(-1)f(1,0) (-1)f(1,1)

• This is the probability amplitude of the ket |00> .
• We calculate this amplitude for the possible functions.
• If f is constant and sends everything to 0, the probability amplitude is 1.
• If f is constant and sends everything to 1, the probability amplitude is −1.
• For the balanced functions, the probability amplitude is 0
Step 4: Measure the top 4 qubits
• When we measure the top qubits we will get one of 00, 01, 10, or 11.
• If the function is constant, then we will with probability 1.
• If the function is balanced, we get it with probability 0.
• So, if the result of measuring gives 00, we know our function was
constant. If the result is not 00, then the function is balanced
• As with n=2, this number will be ±1 if f is constant and 0 if f is
balanced.
• So, if every measurement gives 0, the function is constant.
• If at least one of the measurements is 1, the function is balanced.
• Consequently, we can solve the Deutsch-Jozsa problem for any value
n with just one use of the circuit.
• We only need to ask the oracle one ques tion.
• In the classical case, that in the worst case it required 2n-1+1
questions, so the improvement is dramatic