DEUTSCH-JOZSA ALGORITHMS
D-J Algorithms is used to identify whether a given function is either
balanced or constant.
If half of the inputs are becomes zero and remaining half of the inputs are
becomes one after given to oracle function then we can say that the
function is balanced.
If for inputs the output is either zero or one after given to oracle function
then we can say that the function is constant.
f(x)
This algorithm depends on phase kick back, that is
(x) (1)
↑ information
some
of f(x)
1 -
>
f(x)
The flow diagram of this D-J algorithm is
S
Initialize-----------Apply Hadamard gate-------oracle
> function
X
Hadamard gate-------measure
7
Quantum circuit of D-J algorithm is
10) # # T
Of
1 >
117 I
-
Oracle .
The main advantage with D-J algorithm is superposition and interference.
Superposition allows evaluating all inputs at once and interference amplifies the
correct answer.
In the D-J algorithm circuit, the second qubit is initially prepared as |-> . This
ensures the phase kick back effect on the oracle, which encodes f(x) into the
phase of the first qubit.
The role of Hadmard transform in D-J algorithm is to map computational basis
to uniform superposition.
After applying oracle function (Uf )with |-> , the output is
(−1) 𝑓(𝑥) |𝑥 > ⨂ |−>
The second qubit remains |-> but first qubit phase changes depending on f(x)
Classically, in the worst case, 2n-1 +1 evaluations are needed to determine if the
function is constant or balanced. Quantum computer evaluate in one
evaluations
Calculations:
APPLICATIONS:
1. Demonstrate quantum advantage.
2. Form the basis for more complex algorithms like simon’s and shor’s.
3. useful for understanding phase kickback and interface in quantum
algorithms.
SHOR’S ALGORITHM
Shor’s Algorithm is a quantum algorithm than can efficiently find the prime
factors of large composite number in polynomial time, which is consider
classically hard.
The algorithm uses quantum properties like superposition and
entanglement to solve the problem.
Quantum fourier transform (QFT) to find the period of a function.
The key steps in the shor’s algorithm
1. Pick a number ‘a’ and compute a repeating pattern using ax Mod N
2. Use a quantum computer to find the period of that pattern.
3. use that period to compute the prime factors of N.
4. Result: A task that takes millions of years classically can be done in
seconds on a quantum theory.
Quantum circuit diagram of D-J Algorithms:
GROVER’S ALGORITHM:
It is used to searching an unstructured database.
If a database contains N times, Grover’s algorithms will find the desired item
with order of √𝑁 , where classically having order of N.
The main building block of Grover’s algorithm is oracle and diffusion operator.
In Grover’s algorithm, the oracle Uf act as
𝑈𝑓 |𝑥 >= (−1)𝑓(𝑥) |𝑥 >
The oracle flips the phase of the target states by multiplying by -1 when f(x) =1
Diffusion opertors rotates the state vector towards the solution state.
1. Superposition:
The algorithms begins by putting all possible states into a uniform
superposition using Hadamard gates.
2. Oracle:
A quantum oracle is applied, which marks the items by flipping the
phase of their corresponding quantum states. The oracle function f(x) returns 1
if x is target and 0 other wise.
3. Amplitude Amplification:
A diffusion operator is then applied. This operator amplifies the
amplitude of the marked states and decreases the amplitude of the unmarked
states.
4. Steps 2 and 3 are repeated times. This iterative process progressively
increases the probability of measuring the target state.
5. Measurement: Finally a measurement is performed on the quantum state,
which with probability will yield the marked items.
Example:
Consider a 2- qubit system, which can represent four possible states
|00>,|01>,|10>.|11> .Let’s say we want to find the state |11>
Intialisation:
Apply Hadamard gates to both qubits to create a uniform superposition of all
four states
1
|𝜓0 > = 2 (|00 > +|01 > +|10 > +|11 >)
Oracle:
Design an oracle that flips the phase of the target state |11> for this purpose
using CZ gate in oracle.
1
|𝜓1 > = 2 (|00 > +|01 > +|10 > −|11 >)
Diffusion operator:
This amplitude the amplitude of |11> and reduces the amplitudes of the other
states.
Measurement:
After one interaction, measuring the qubits will yield|11> with high probability.