Quantum Algorithm
Presented by Myo Thu Htet
Introduction
Name : Myo Thu Htet
Student No : SBL-A01759
Company : NCS Pte Ltd (Singapore)
Designation : Business Analyst
Edu Center : Simbolo
Course : Quantum Computing (The Theoretical Minimum)
Batch No : Batch 1
Linkedin : https://sg.linkedin.com/in/myothuhtet
Email :
[email protected]Field of Interest: Technology (Software Development)
25 January 2025 Quantum Algorithm 2
Motivation
• Classical algorithms require two times evaluations to
identify if a function is constant or balanced.
• However, Deutsch's Algorithm utilized quantum
superposition to solve this problem with a single
evaluation.
• Deutsch's Algorithm demonstrates the
computational power of quantum computing and
this will lead to further research for quantum
algorithms that outperform classical computing.
25 January 2025 Quantum Algorithm 3
Deutsch's Algorithm Introduction
• David Deutsch proposed Deutsch's Algorithm in 1985. It is a
pioneering quantum algorithm that solves a simple problem
more efficiently than any classical algorithm. The problem
involves identify whether a function is constant (same output for
all inputs) or balanced (different outputs for different inputs).
• Classical computing require to perform both inputs. Deutsch's
Algorithm can identify this with only one evaluation by
leveraging quantum superposition.
• The algorithm's processing lies in introducing key quantum
computing principles. It becomes the foundation for more
complex algorithms, such as Deutsch-Jozsa, Simon's, and Shor's
algorithms
25 January 2025 Quantum Algorithm 4
Constant and Balanced Functions
For 1-bit input, if x ∈ {0,1}
1. Constant function
A function is constant if it produces the same output for all possible inputs.
eg. f(0) = f(1)
f(0) = 0, f(1) = 0
f(0) = 1, f(1) =1
2. Balanced function
A function is balanced if it produces an equal number of 0 and 1 as output for all possible
inputs.
eg. f(0) ≠ f(1)
f(0) = 0, f(1) = 1
f(0) = 1, f(1) = 0
25 January 2025 Quantum Algorithm 5
Logic Gates
There will be some logic gates in Deutsch’s Algorithm Circuit
1. NOT Gate X
NOT gate (X) is a basic logic gate that inverts the input bit. If the input is 0,
the output is 1.If the input is 1, the output is 0.
eg. X ∣0⟩ = ∣1⟩
X ∣ 1 ⟩ = ∣0 ⟩
25 January 2025 Quantum Algorithm 6
Logic Gates
2. Hadamard Gate H
Hadamard gate (H) transforms a qubit into a superposition of the basis states
∣0⟩ to ∣+⟩ and ∣1⟩ to ∣-⟩ .
eg. H ∣0⟩ = 1/√2 (∣0⟩ + ∣1⟩)
H ∣1⟩ = 1/√2 (∣0⟩ - ∣1⟩)
If Hadamard gate applies to ∣+⟩ and ∣-⟩, H ∣+⟩ to ∣0⟩ and ∣-⟩ to ∣1⟩
eg. H ∣+⟩ = H (1/√2 (∣0⟩ + ∣1⟩)) = ∣0⟩
H ∣-⟩ = H (1/√2 (∣0⟩ - ∣1⟩)) = ∣1⟩
25 January 2025 Quantum Algorithm 7
Logic Gates
3. Phase Oracle Gate Uf
Phase Oracle (Uf) is a unitary operator used in
quantum algorithms to encode a function f(x) into
the phase of quantum states. Unlike traditional
oracles, which may modify the state directly (e.g.,
flipping a qubit), phase oracles leave the quantum
state unchanged except for applying a phase shift
based on the value of f(x).
25 January 2025 Quantum Algorithm 8
Logic Gates
Phase Oracle Example
∣x⟩ ∣x⟩
Uf
∣y⟩ ∣y ⊕ f(x) ⟩
⊕ = binary sum, ⊗ = tensor product
Uf ∣x⟩ ⊗ ∣y⟩ = Uf ∣xy⟩ = ∣x⟩ ⊗ ∣y⊕ f(x) ⟩
If x= 1, y=1, 1⊕1=0
If x= 1, y=0 or x=0, y=1 , 1 ⊕ 0 = 0 ⊕ 1 = 1
If x= 0, y=0, 0⊕0=0
25 January 2025 Quantum Algorithm 9
Logic Gates
Phase Oracle Example
∣0⊕ a⟩ - ∣1⊕ a⟩
If a= 0, ∣0⟩ - ∣1⟩
If a= 1, ∣1⟩ - ∣0⟩
So to summarize this, it will become (-1)a (∣0⟩ - ∣1⟩) for both a=0 and a=1.
25 January 2025 Quantum Algorithm 10
Deutsch's Algorithm Circuit
0 if f(x) is constant
∣0⟩ H H
1 if f(x) is balanced
Uf
∣0⟩ X ∣1⟩ H H
∣ψ1 ⟩ ∣ψ2 ⟩ ∣ψ3 ⟩ ∣ψ4 ⟩ ∣ψ5 ⟩
25 January 2025 Quantum Algorithm 11
Detailed Calculation
1. Initialize Qubits
∣0⟩∣0⟩
∣0⟩ NOT ∣0⟩
∣0⟩ ∣1⟩ (initialization)
∣ψ1⟩ = ∣0⟩ ⊗ ∣1⟩
2. Apply Hadamard Gate
∣ψ2⟩ = H ∣ψ1⟩
= H ∣0⟩ ⊗ H ∣1⟩
= 1/√2 (∣0⟩ + ∣1⟩) ⊗ 1/√2 (∣0⟩ - ∣1⟩)
= 1/2 ( ∣00⟩ - ∣01⟩ + ∣10⟩ - ∣11⟩ )
25 January 2025 Quantum Algorithm 12
Detailed Calculation
3. Apply Phase Oracle Uf
∣ψ3⟩ = Uf ∣ψ2⟩
= 1/2 ( ∣0⟩ ∣0 ⊕ f(0)⟩ - ∣0⟩ ∣1 ⊕ f(0)⟩ + ∣1⟩ ∣0 ⊕ f(1) ⟩ - ∣1⟩ ∣1 ⊕
f(1)⟩ )
= 1/2 ( ∣0⟩ ( ∣0 ⊕ f(0)⟩ - ∣1 ⊕ f(0)⟩ ) + ∣1⟩ ( ∣0 ⊕ f(1) ⟩ - ∣1 ⊕ f(1)⟩ ) )
Observation
= 1/2 ( ∣0⟩ (-1)f(0) ( ∣0⟩ - ∣1⟩ ) + ∣1⟩ (-1)f(1) ( ∣0⟩ - ∣1⟩ ) )
= 1/2 ( ∣0⟩ (-1)f(0) + ∣1⟩ (-1)f(1) ) ( ∣0⟩ - ∣1⟩ )
= 1/√2 ( ∣0⟩ (-1)f(0) + ∣1⟩ (-1)f(1) ) ⊗ 1/√2 ( ∣0⟩ - ∣1⟩ )
4. Apply Hadamard Gate (Hadamard gate applies to ∣+⟩ and ∣-⟩)
∣ψ4⟩ = H ∣ψ3⟩
25 January 2025 Quantum Algorithm 13
Detailed Calculation
Case 1 : if f(0) = f(1), f is constant
Sub-case 1: f(0) = f(1) = 0
∣ψ4⟩ = H 1/√2 ( ∣0⟩ (-1)f(0) + ∣1⟩ (-1)f(1) ) ⊗ H 1/√2 ( ∣0⟩ - ∣1⟩ )
= H 1/√2 ( ∣0⟩ (-1)0 + ∣1⟩ (-1)0 ) ⊗ H 1/√2 ( ∣0⟩ - ∣1⟩ )
= H 1/√2 (∣0⟩ + ∣1⟩) ⊗ H 1/√2 (∣0⟩ - ∣1⟩)
= ∣0⟩ ∣1⟩
Case 2 : if f(0) = f(1) = 1, f is constant
Sub-case 2: f(0) = f(1) = 0
∣ψ4⟩ = - ∣0⟩ ∣1⟩
25 January 2025 Quantum Algorithm 14
Detailed Calculation
Case 3 : if f(0) ≠ f(1), f is balanced
Sub-case 3: f(0) = 0, f(1) = 1
∣ψ4⟩ = H 1/√2 ( ∣0⟩ (-1)f(0) ) + ∣1⟩ (-1)f(1)) ⊗ H 1/√2 ( ∣0⟩ - ∣1⟩ )
= H 1/√2 ( ∣0⟩ (-1)0 + ∣1⟩ (-1)1 ) ⊗ H 1/√2 ( ∣0⟩ - ∣1⟩ )
= H 1/√2 (∣0⟩ - ∣1⟩) ⊗ H 1/√2 (∣0⟩ - ∣1⟩)
= ∣1⟩ ∣1⟩
Case 4 : if f(0) ≠ f(1), f is balanced
Sub-case 4: f(0) = 1, f(1) = 0
∣ψ4⟩ = - ∣1⟩ ∣1⟩
25 January 2025 Quantum Algorithm 15
Detailed Calculation
5. Measurement
∣ψ5⟩ = if first qbit is ∣0⟩, f(x) is constant
if first qbit is ∣1⟩, f(x) is balanced
(Note: Please ignore the +/- sign)
25 January 2025 Quantum Algorithm 16
Application Code
import qiskit
import math from qiskit
import QuantumCircuit, QuantumRegister, transpilefrom qiskit.visualization
import plot_histogramfrom qiskit_aer
import AerSimulatorfrom qiskit.quantum_info
import Statevector
def oracle(n, is_balanced):
qc = QuantumCircuit(n+1, name = 'oracle')
if is_balanced:
for qubit in range(n):
qc.cx(qubit, n)
else:
qc.x(n)
return qc
n=1
oracle_circuit = oracle(n, is_balanced=False)
25 January 2025 Quantum Algorithm 17
Application Code
qc = QuantumCircuit(n+1, n)
qc.x(n)
qc.barrier()
for i in range(n+1):
qc.h(i)
qc.append(oracle_circuit, range(n+1))
for i in range(n+1):
qc.h(i)
qc.barrier()
for qubit in range(n):
qc.measure(qubit, qubit)
qc.save_statevector()
qc.draw('mpl')
25 January 2025 Quantum Algorithm 18
Application Code
simulator = AerSimulator()
qc = transpile(qc,simulator)
result = simulator.run(qc, shots = 1024).result()
counts = result.get_counts()
plot_histogram(counts)
25 January 2025 Quantum Algorithm 19
Thank you
25 January 2025 Quantum Algorithm 20
