Deutsch-Jozsa Algorithm

Table of Contents

1. Introduction
2. Background and Motivation
3. Problem Statement
4. Classical vs Quantum Complexity
5. The Deutsch-Jozsa Oracle
6. Structure of the Algorithm
7. Input and Output Qubits
8. Initial State Preparation
9. Applying Hadamard Transform
10. Oracle Application in Superposition
11. Final Hadamard Transform
12. Measurement and Interpretation
13. Example with n = 2
14. Balanced and Constant Case Outcomes
15. Algebraic Understanding
16. Matrix Formalism
17. Visualizing the Circuit
18. Geometric Interpretation
19. Quantum Speedup Explained
20. Generalization to Arbitrary n
21. Relevance in Quantum Complexity Theory
22. Qiskit Implementation Example
23. Limitations and Practical Use
24. Educational Significance
25. Conclusion

1. Introduction

The Deutsch-Jozsa Algorithm was one of the first quantum algorithms to demonstrate an exponential speedup over classical approaches. It builds on the concepts of superposition, quantum parallelism, and interference.

2. Background and Motivation

The Deutsch-Jozsa problem generalizes the original Deutsch problem from 1-bit functions to \( n \)-bit input functions. It provides a clear and early example of how quantum computing can outperform classical computing in query complexity.

3. Problem Statement

Given a function \( f: \{0,1\}^n \rightarrow \{0,1\} \) that is:

• Constant: \( f(x) \) is the same for all \( x \)
• Balanced: \( f(x) = 0 \) for exactly half of inputs, and \( f(x) = 1 \) for the other half

Determine which case it is using only one call to the oracle.

4. Classical vs Quantum Complexity

• Classical (deterministic): Requires up to \( 2^{n-1} + 1 \) evaluations in the worst case.
• Quantum: Solves the problem with just one oracle call.

5. The Deutsch-Jozsa Oracle

The oracle is a black-box unitary operation:

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

It flips the output qubit conditioned on \( f(x) \).

6. Structure of the Algorithm

Steps:

1. Initialize \( n \) input qubits in \( |0\rangle \) and 1 output qubit in \( |1\rangle \)
2. Apply Hadamard to all qubits
3. Apply oracle \( U_f \)
4. Apply Hadamard to input qubits again
5. Measure the input qubits

7. Input and Output Qubits

• Input register: \( n \) qubits \( |0\rangle^{\otimes n} \)
• Output register: 1 qubit \( |1\rangle \)

Initial state:

\[
|\psi_0\rangle = |0\rangle^{\otimes n} \otimes |1\rangle
\]

8. Initial State Preparation

Apply Hadamard gates:

\[
H^{\otimes n} |0\rangle^{\otimes n} = \frac{1}{\sqrt{2^n}} \sum_{x=0}^{2^n – 1} |x\rangle
\]
\[
H |1\rangle = \frac{1}{\sqrt{2}}(|0\rangle – |1\rangle)
\]

Resulting state:

\[
|\psi_1\rangle = \frac{1}{\sqrt{2^{n+1}}} \sum_x |x\rangle (|0\rangle – |1\rangle)
\]

9. Applying Hadamard Transform

The Hadamard transform spreads the amplitudes equally, allowing the oracle to encode \( f(x) \) as a phase:

\[
U_f |x\rangle (|0\rangle – |1\rangle) = (-1)^{f(x)} |x\rangle (|0\rangle – |1\rangle)
\]

10. Oracle Application in Superposition

This results in:

\[
|\psi_2\rangle = \frac{1}{\sqrt{2^{n+1}}} \sum_x (-1)^{f(x)} |x\rangle (|0\rangle – |1\rangle)
\]

Note: The output qubit is now separable and unentangled.

11. Final Hadamard Transform

Apply Hadamard gates to the input register:

\[
H^{\otimes n} \sum_x (-1)^{f(x)} |x\rangle = \sum_z \left[ \frac{1}{2^n} \sum_x (-1)^{f(x) + x \cdot z} \right] |z\rangle
\]

The amplitude for \( |0\rangle^{\otimes n} \) is:

\[
\frac{1}{2^n} \sum_x (-1)^{f(x)}
\]

12. Measurement and Interpretation

Measure the input qubits:

• If output is \( |0\rangle^{\otimes n} \): function is constant
• Else: function is balanced

13. Example with n = 2

Constant case:

\[
f(00) = f(01) = f(10) = f(11) = 0 \Rightarrow \text{Measurement result: } 00
\]

Balanced case:

\[
f(00) = f(01) = 0, \quad f(10) = f(11) = 1 \Rightarrow \text{Output: Not } 00
\]

14. Balanced and Constant Case Outcomes

• Constant: All terms interfere constructively at \( |0\rangle^{\otimes n} \)
• Balanced: Destructive interference makes amplitude zero at \( |0\rangle^{\otimes n} \)

15. Algebraic Understanding

If \( f \) is constant:
\[
\sum_x (-1)^{f(x)} = \pm 2^n
\]
If balanced:
\[
\sum_x (-1)^{f(x)} = 0
\]

16. Matrix Formalism

Each Hadamard, oracle, and measurement can be modeled with matrix multiplication. Though exact matrices grow large with \( n \), simulation is feasible for small systems.

17. Visualizing the Circuit

q_0: ──H──────■──────H────M──
              │
q_1: ──H──────X──────────────

Generalized to \( n \) qubits with multiple H, control lines, and measurements.

18. Geometric Interpretation

Hadamards map state to equator of Bloch sphere. Oracle flips phase. Final Hadamards recombine amplitudes. If constructive at \( |0\rangle^{\otimes n} \), then constant; otherwise, not.

19. Quantum Speedup Explained

Classical: \( \mathcal{O}(2^{n-1} + 1) \) queries
Quantum: 1 query suffices

This is an exponential speedup in query complexity.

20. Generalization to Arbitrary n

Deutsch-Jozsa scales to any number of qubits. It is exact — no probabilistic error — and is one of the few quantum algorithms with provable exponential advantage.

21. Relevance in Quantum Complexity Theory

It demonstrates separation between BPP (bounded-error classical) and EQP (exact quantum). While not practical, it’s theoretically significant.

22. Qiskit Implementation Example

from qiskit import QuantumCircuit, Aer, execute

n = 2
qc = QuantumCircuit(n + 1, n)
qc.x(n)
qc.h(range(n + 1))
qc.cz(0, n)  # Oracle example
qc.cz(1, n)  # Balanced function
qc.h(range(n))
qc.measure(range(n), range(n))

backend = Aer.get_backend('qasm_simulator')
result = execute(qc, backend, shots=1024).result()
counts = result.get_counts()
print(counts)

23. Limitations and Practical Use

• Oracle must be promised to be either constant or balanced
• Problem is artificial; not commonly encountered in real-world applications

24. Educational Significance

Ideal for teaching:

• Quantum interference
• Quantum parallelism
• Query complexity
• Circuit design and oracle structure

25. Conclusion

The Deutsch-Jozsa Algorithm exemplifies the unique capabilities of quantum computing. Though not useful for practical problems, it plays a foundational role in understanding how quantum systems outperform classical counterparts in certain scenarios. It’s a perfect introduction to the power of quantum algorithms.