Deutsch Algorithm¶

The Deutsch algorithm is historically important as the first example of a provable quantum advantage. It shows that quantum computers can outperform classical ones even on simple tasks. Specifically, it determines whether a black-box Boolean function is constant or balanced. Classically, this requires two evaluations of the function. The quantum algorithm solves it with a single query using superposition and interference.

Objectives

What task solves the Deutsch algorithm
What is the quantum advantage of the Deutsch algorithm
How does Deutsch algorithm work

Instructor note

90 min teaching/type-along
0 min exercising

Symbolic Example with `sympy`¶

This notebook implements the Deutsch algorithm step by step using SymPy in Dirac notation. SymPy is used as a symbolic tool to manipulate quantum states and gates analytically.

Caution

Note that, in SymPy, qubit ordering is reversed with respect to the standard convention, so care is needed when interpreting states and measurements.

We focus on the particular case of the balanced function $f(b) = b$.

First, we import the needed dependencies. Then, we initialize the quantum system in the state $|01\rangle$.

from sympy import latex, expand, simplify
from sympy.physics.quantum.qubit import Qubit, measure_all
from sympy.physics.quantum.gate import H, CNOT
from sympy.physics.quantum.qapply import qapply

from IPython.display import display, Math

def show(label, expr):
    display(Math(r"%s = %s" % (label, latex(expr))))

# Initial state |0>|1>
# In SymPy, Qubit('01') means:
# - left qubit = qubit 1
# - right qubit = qubit 0
psi0 = Qubit('01')
show(r"\psi_0", psi0)

\[\displaystyle \psi_0 = {\left|01\right\rangle }\]

In the first layer, we apply Hadamard gates on both the qubits.

# Step 1: apply H to both qubits
psi1 = qapply(H(1) * H(0) * psi0)
psi1 = expand(psi1)
show(r"\psi_1", expand(psi1))

\[\displaystyle \psi_1 = \frac{{\left|00\right\rangle }}{2} - \frac{{\left|01\right\rangle }}{2} + \frac{{\left|10\right\rangle }}{2} - \frac{{\left|11\right\rangle }}{2}\]

In the second layer, the oracle function is applied. The oracle, in the case $f(b)=b$, is just a $CNOT$ from data qubit to computation qubit.

# Step 2: oracle for f(b) = b
# This is a CNOT with control = first qubit, target = second qubit
# With SymPy indexing convention, that is CNOT(1, 0)
psi2 = qapply(CNOT(1, 0) * psi1)
psi2 = expand(psi2)
show(r"\psi_2", expand(psi2))

\[\displaystyle \psi_2 = \frac{{\left|00\right\rangle }}{2} - \frac{{\left|01\right\rangle }}{2} - \frac{{\left|10\right\rangle }}{2} + \frac{{\left|11\right\rangle }}{2}\]

Finally, in the last layer we apply an Hadamard gate to the data qubit.

# Step 3: final Hadamard on the first qubit only
psi3 = qapply(H(1) * psi2)
psi3 = expand(psi3)
show(r"\psi_3", expand(psi3))

\[\displaystyle \psi_3 = \frac{\sqrt{2} {\left|10\right\rangle }}{2} - \frac{\sqrt{2} {\left|11\right\rangle }}{2}\]

Remember that the data qubit is represented by the leftmost bit in the bitstrings.

You can notice that the data qubit is always 1. This means that the function we considered is balanced.

Keypoints¶

In this episode, we have seen:

What is the problem solved by Deutsch algorithm and its classical query complexity.
How superposition, interference and phase kickback enable the classification of the oracle.
How Deutsch algorithm works step by step for a given oracle.
How to calculate and interpret the measurement outcome to determine whether the function is constant or balanced.

Deutsch Algorithm¶

Symbolic Example with sympy¶

Keypoints¶

Symbolic Example with `sympy`¶