Project 3: Deutsch’s Algorithm - The First “Quantum Speedup”

Build Deutsch’s algorithm and classify a function with one query.

Project Overview

Attribute Value
Difficulty Level 2: Intermediate
Time Estimate Weekend
Main Language Python
Alternative Languages Q#, Java
Knowledge Area Quantum algorithms
Tools Qiskit or Cirq
Main Book “Quantum Computation and Quantum Information” by Nielsen & Chuang

What you’ll build: A circuit that determines whether a black-box function is constant or balanced with one query.

Why it teaches quantum: Deutsch’s algorithm is the first example of quantum advantage.

Core challenges you’ll face:

  • Building the oracle circuit
  • Setting up interference correctly
  • Interpreting measurement results

Real World Outcome

You will classify test oracles and verify correct results in a single query.

Example Output:

$ python deutsch.py --oracle constant
Result: constant

Verification steps:

  • Test both constant and balanced oracles
  • Confirm classification matches ground truth

The Core Question You’re Answering

“How can quantum interference reduce the number of queries?”

This is the smallest demonstration of quantum speedup.

Concepts You Must Understand First

Stop and research these before coding:

  1. Oracle model
    • What does it mean to query a black-box function?
    • Book Reference: Nielsen & Chuang, Ch. 1
  2. Interference
    • How do Hadamard gates create constructive/destructive interference?
    • Book Reference: Nielsen & Chuang, Ch. 1
  3. Balanced vs constant
    • What makes a function balanced in Deutsch’s problem?
    • Book Reference: Nielsen & Chuang, Ch. 1

Questions to Guide Your Design

  1. Oracle construction
    • Will you implement multiple oracles for testing?
    • How will you validate each oracle’s behavior?
  2. Measurement analysis
    • Will you measure only the first qubit?
    • How will you interpret results with finite shots?

Thinking Exercise

Oracle Truth Table

Write the truth table for a balanced function on 1 bit and for a constant function. How many outputs differ?

Questions while working:

  • Why does one query suffice in the quantum case?
  • Why does a classical approach require two queries?

The Interview Questions They’ll Ask

Prepare to answer these:

  1. “What is Deutsch’s algorithm?”
  2. “What is a quantum oracle?”
  3. “How does interference give a speedup?”
  4. “What is the difference between constant and balanced?”
  5. “Why is this algorithm mostly pedagogical?”

Hints in Layers

Hint 1: Starting Point Set up input as |0> and ancilla as |1>.

Hint 2: Next Level Apply Hadamard gates before and after the oracle.

Hint 3: Technical Details Measure the input qubit; |0> means constant, |1> means balanced.

Hint 4: Tools/Debugging Test all oracle variants and verify results.

Books That Will Help

Topic Book Chapter
Deutsch’s algorithm Nielsen & Chuang Ch. 1
Oracles Nielsen & Chuang Ch. 1
Interference Nielsen & Chuang Ch. 1

Implementation Hints

  • Keep oracle logic modular and testable.
  • Use a simulator to see ideal results.
  • Repeat shots to check stability.

Learning Milestones

  1. First milestone: You can build Deutsch’s circuit.
  2. Second milestone: You can implement multiple oracles.
  3. Final milestone: You can explain the speedup clearly.