Deutsch Algorithm

Table of Contents

1. Introduction
2. Classical vs Quantum Approach
3. Problem Statement
4. Overview of the Deutsch Algorithm
5. Mathematical Formulation
6. Oracle Function
7. Quantum Circuit Design
8. Initial State Preparation
9. Applying Hadamard Gates
10. Oracle Application in Superposition
11. Final Hadamard on Input Qubit
12. Measurement and Interpretation
13. Case Analysis: Constant vs Balanced
14. Understanding the Speedup
15. Visualization on the Bloch Sphere
16. Deutsch Algorithm with Truth Table
17. Role of Quantum Interference
18. Matrix Representation of Steps
19. Circuit Diagram of Deutsch Algorithm
20. Physical Implementation
21. Generalization to Deutsch-Jozsa Algorithm
22. Significance in Quantum Computing History
23. Code Implementation (Qiskit Example)
24. Challenges and Limitations
25. Conclusion

1. Introduction

The Deutsch Algorithm is one of the earliest examples showcasing quantum speedup. It solves a very simple problem faster than any classical deterministic algorithm, serving as a cornerstone in the understanding of quantum computation.

2. Classical vs Quantum Approach

Classically, to determine if a function \( f : \{0,1\} \rightarrow \{0,1\} \) is constant or balanced, you need two evaluations.

The Deutsch Algorithm solves it using only one evaluation — demonstrating the power of quantum parallelism and interference.

3. Problem Statement

Given a function \( f(x) \) with input \( x \in \{0, 1\} \) that is either:

• Constant: \( f(0) = f(1) \)
• Balanced: \( f(0) \neq f(1) \)

Determine whether \( f \) is constant or balanced, using only one call to the oracle.

4. Overview of the Deutsch Algorithm

The algorithm:

• Prepares two qubits
• Applies Hadamard transformations
• Applies the oracle function
• Uses interference to reveal the nature of \( f \) in one measurement

5. Mathematical Formulation

We use two qubits:

• Input qubit initialized to \( |0\rangle \)
• Output qubit initialized to \( |1\rangle \)

State:
\[
| \psi_0 \rangle = |0\rangle \otimes |1\rangle
\]

6. Oracle Function

The oracle \( U_f \) is defined as:

\[
U_f|x\rangle|y\rangle = |x\rangle|y \oplus f(x)\rangle
\]

This operation evaluates \( f(x) \) without collapsing the state.

7. Quantum Circuit Design

Steps:

1. Initialize \( |0\rangle \otimes |1\rangle \)
2. Apply Hadamard to both qubits
3. Apply oracle \( U_f \)
4. Apply Hadamard to the input qubit
5. Measure the input qubit

8. Initial State Preparation

\[
|\psi_0\rangle = |0\rangle \otimes |1\rangle
\]

After Hadamards:

\[
|\psi_1\rangle = \left( \frac{|0\rangle + |1\rangle}{\sqrt{2}} \right) \otimes \left( \frac{|0\rangle – |1\rangle}{\sqrt{2}} \right)
\]

9. Applying Hadamard Gates

The Hadamard gate creates superposition:

• Input qubit: probes both \( x = 0 \) and \( x = 1 \)
• Output qubit: serves as phase kickback register

10. Oracle Application in Superposition

Applying \( U_f \) gives:

\[
|\psi_2\rangle = \frac{1}{2} \left[ |0\rangle|f(0) \oplus 1\rangle + |1\rangle|f(1) \oplus 1\rangle \right]
\]

Interference in the output phase encodes the function type.

11. Final Hadamard on Input Qubit

After applying Hadamard again on the input qubit:

• Result will be \( |0\rangle \) if \( f \) is constant
• Result will be \( |1\rangle \) if \( f \) is balanced

12. Measurement and Interpretation

Measure only the first qubit:

• Output 0 ⇒ constant
• Output 1 ⇒ balanced

This measurement resolves the function type in one query.

13. Case Analysis: Constant vs Balanced

Constant Function:

\[
f(0) = f(1) \Rightarrow \text{No phase difference} \Rightarrow \text{constructive interference on } |0\rangle
\]

Balanced Function:

\[
f(0) \neq f(1) \Rightarrow \text{phase flip causes destructive interference on } |0\rangle
\]

14. Understanding the Speedup

The speedup arises from:

• Quantum parallelism: both inputs evaluated simultaneously
• Interference: correct answer amplified, wrong one suppressed

15. Visualization on the Bloch Sphere

The Hadamard gates rotate the state on the Bloch sphere:

• First Hadamard: maps to equator
• Oracle: phase encoding
• Final Hadamard: projects result back to poles

16. Deutsch Algorithm with Truth Table

17. Role of Quantum Interference

Interference is the key to quantum advantage. By manipulating the relative phase, quantum circuits can “cancel out” wrong answers and enhance the correct one.

18. Matrix Representation of Steps

Each step (Hadamard, Oracle, Hadamard) can be represented with matrix multiplication. For small systems like this, it is feasible to simulate entirely using numpy or Qiskit.

19. Circuit Diagram of Deutsch Algorithm

q0: ──H────■────H────M──
           │
q1: ──H────X────────────

• \( q_0 \): input
• \( q_1 \): output qubit (not measured)

20. Physical Implementation

Implemented on:

• Superconducting qubits (IBM, Rigetti)
• Ion traps (IonQ)
• Optical quantum circuits

Due to simplicity, this is often the first quantum program run on real hardware.

21. Generalization to Deutsch-Jozsa Algorithm

The Deutsch Algorithm is a special case of the Deutsch-Jozsa Algorithm, which extends the concept to \( n \)-bit inputs and distinguishes between constant and balanced functions with a single evaluation.

22. Significance in Quantum Computing History

This algorithm was the first to demonstrate a quantum advantage, albeit small, and is a pedagogical tool for introducing:

• Oracles
• Superposition
• Interference
• Quantum speedup

23. Code Implementation (Qiskit Example)

from qiskit import QuantumCircuit, Aer, execute
qc = QuantumCircuit(2, 1)
qc.x(1)
qc.h(0)
qc.h(1)
qc.cx(0,1)  # Oracle for f(x) = x
qc.h(0)
qc.measure(0, 0)
backend = Aer.get_backend('qasm_simulator')
result = execute(qc, backend, shots=1024).result()
counts = result.get_counts()
print(counts)

24. Challenges and Limitations

• Solves a contrived problem
• No real-world utility
• Still useful for learning and hardware testing

25. Conclusion

The Deutsch Algorithm is a simple but powerful illustration of quantum computation’s potential. While limited in scope, it introduces key principles that underlie quantum computing’s power — superposition, interference, and quantum oracles. It’s a foundational step in learning quantum algorithms.