Implementing and Analyzing the Deutsch-Jozsa Algorithm

Hello! Welcome to the first lesson in our module on foundational quantum algorithms.

In the previous module, we established the fundamental language of quantum computing: qubits, gates, superposition, entanglement, and measurement. Now, we'll start using that language to build algorithms that can outperform classical computers on specific tasks.

Our goal for this lesson is to implement the Deutsch-Jozsa algorithm and analyze its quantum advantage over classical algorithms. This algorithm was one of the first to demonstrate that a quantum computer could solve a problem exponentially faster than any deterministic classical computer. While the problem it solves is quite specific, its study reveals core principles like quantum parallelism and interference that are central to more advanced algorithms.

Let's begin by formally defining the problem that the Deutsch-Jozsa algorithm addresses.

1. The Problem: Constant vs. Balanced Functions

The algorithm operates within a computational framework known as the query model. In this model, we are given access to a function f as a "black box" or "oracle." We can provide an input x to the oracle and receive the output f(x), but we cannot see the internal workings of the function. Our goal is to determine a global property of the function f using the minimum number of queries.

The Deutsch-Jozsa problem is defined as follows:

• Given: A function $f:\{0,1{\}}^n\to \{0,1\}$.
• Promise: The function is guaranteed to be either constant or balanced.
  • A constant function returns the same output for all inputs (e.g., $f(x)=0$ for all $x$, or $f(x)=1$ for all $x$).
  • A balanced function returns 0 for exactly half of the inputs and 1 for the other half.
• Task: Determine whether $f$ is constant or balanced.

Classical Complexity

How many times would a classical computer need to query the function to solve this problem?

• Deterministic Approach: In the worst-case scenario, you could query the function for half of all possible inputs ($2^{n-1}$ queries) and get the same output every time. At this point, you still can't be certain. The function could be constant, or it could be balanced and you just happened to pick all the inputs that give the same output. You must make one more query, for a total of $2^{n-1}+1$, to be 100% certain. For large $n$, this is an exponential number of queries.

• Probabilistic Approach: If we allow for a small probability of error, we can do much better. If we query the function for a few random inputs, say $k$ times, and get different outputs, we know immediately that the function is balanced. If we get the same output every time, the function is likely constant. The probability of getting the same output $k$ times from a balanced function is $1/2^{k-1}$. By choosing a reasonably small $k$ (e.g., k=10), we can be almost certain of the answer.

This distinction between deterministic and probabilistic classical strategies is crucial for appreciating the nature of the quantum advantage we're about to see.

2. The Quantum Solution

The quantum approach solves this problem deterministically with just a single query to the oracle. To understand how, we first need to formalize the idea of a quantum query.

The following video by Prof. John Watrous provides an excellent introduction to the query model and the formal definition of a quantum oracle. It then uses these concepts to build up to the Deutsch-Jozsa algorithm, starting with the simpler n=1 case (Deutsch's algorithm).

The Deutsch-Jozsa Circuit and its Analysis

As you saw in the video, the key ideas are to use Hadamard gates to prepare a superposition of all possible inputs (quantum parallelism), encode the function's output into the phase of the quantum state (phase kickback), and then use another set of Hadamard gates to cause these phases to interfere, revealing the global property of the function.

Let's generalize this to $n$ qubits. The circuit is as follows:

Let's trace the state of the system through the circuit:

1. Initial State $|{\psi }_0⟩$: We start with $n$ qubits in the $|0⟩$ state and one ancilla qubit in the $|1⟩$ state.

   $$|{\psi }_0⟩=|0{⟩}^{\otimes n}|1⟩$$

2. After First Hadamards $|{\psi }_1⟩$: We apply Hadamard gates to all $n+1$ qubits. The first $n$ qubits go into an equal superposition of all $2^n$ computational basis states. The ancilla qubit becomes $H|1⟩=\frac{1}{\sqrt{2}}(|0⟩-|1⟩)=|-⟩$.

   $$|{\psi }_1⟩=\left(\frac{1}{\sqrt{2^n}}\sum _{x\in \{0,1{\}}^n}|x⟩\right)\otimes |-⟩$$

3. After Oracle $U_f$ $|{\psi }_2⟩$: The oracle $U_f$ acts on a state $|x⟩|y⟩$ as $|x⟩|y\oplus f(x)⟩$. Because our ancilla is in the special state $|-⟩$, the "phase kickback" trick applies. The function value $f(x)$ is "kicked back" into the phase of the corresponding $|x⟩$ state.

   $$U_f(|x⟩|-⟩)=|x⟩\frac{1}{\sqrt{2}}(|0\oplus f(x)⟩-|1\oplus f(x)⟩)=(-1{)}^{f(x)}|x⟩|-⟩$$

   Applying this to our superposition gives:

   $$|{\psi }_2⟩=\frac{1}{\sqrt{2^n}}\sum _{x\in \{0,1{\}}^n}(-1{)}^{f(x)}|x⟩\otimes |-⟩$$

   At this point, we have queried the function once and simultaneously encoded the information about $f(x)$ for all $2^n$ values of $x$ into the phases of our state. The ancilla qubit $|-⟩$ is no longer needed and can be ignored.

4. After Final Hadamards $|{\psi }_3⟩$: The final step is to apply Hadamard gates to the first $n$ qubits. This operation, $H^{\otimes n}$, is its own inverse and acts as a kind of Fourier transform over the group ${\mathbb{Z}}_2^n$. It maps a computational basis state $|x⟩$ as follows:

   $$H^{\otimes n}|x⟩=\frac{1}{\sqrt{2^n}}\sum _{z\in \{0,1{\}}^n}(-1{)}^{x\cdot z}|z⟩$$

   where $x\cdot z=x_1{z}_1+x_2{z}_2+\cdots +x_n{z}_n(\mathrm{mod}2)$ is the bitwise dot product. Applying this to $|{\psi }_2⟩$ gives the final state before measurement:

   $$|{\psi }_3⟩=\frac{1}{2^n}\sum _{x\in \{0,1{\}}^n}(-1{)}^{f(x)}\sum _{z\in \{0,1{\}}^n}(-1{)}^{x\cdot z}|z⟩=\frac{1}{2^n}\sum _{z\in \{0,1{\}}^n}\left(\sum _{x\in \{0,1{\}}^n}(-1{)}^{f(x)+x\cdot z}\right)|z⟩$$

5. Measurement: We measure the first $n$ qubits. Let's consider the amplitude of the all-zeros state, $|0{⟩}^{\otimes n}$, which corresponds to $z=00\dots 0$. For this state, the dot product $x\cdot z$ is always 0. The amplitude is:

   $${\alpha }_{00\dots 0}=\frac{1}{2^n}\sum _{x\in \{0,1{\}}^n}(-1{)}^{f(x)}$$

   Now, we use our promise about the function $f$:

   • If $f$ is constant, $f(x)=c$. The sum becomes ${\sum }_x(-1{)}^c=2^n(-1{)}^c$. The amplitude is ${\alpha }_{00\dots 0}=\pm 1$. The probability of measuring $|0{⟩}^{\otimes n}$ is $|{\alpha }_{00\dots 0}{|}^2=1$.
   • If $f$ is balanced, exactly half the $f(x)$ values are 0 and half are 1. The sum ${\sum }_x(-1{)}^{f(x)}$ will have $2^{n-1}$ terms of $+1$ and $2^{n-1}$ terms of $-1$, so the sum is 0. The amplitude ${\alpha }_{00\dots 0}$ is 0. The probability of measuring $|0{⟩}^{\otimes n}$ is 0.

Therefore, a single run of the circuit and a measurement of the first $n$ qubits is sufficient:

• If the result is $00\dots 0$, the function is constant.
• If the result is anything else, the function is balanced.

For a more condensed mathematical derivation, you can refer to these lecture notes.

3. Implementation and Quantum Advantage

Now let's turn to the practical implementation using Qiskit. The following guide from IBM Quantum Learning provides the full code to build the Deutsch-Jozsa circuit, including a function to generate a random oracle that is guaranteed to be either constant or balanced.

Analyzing the Quantum Advantage

As we've seen, the Deutsch-Jozsa algorithm provides a striking advantage.

Algorithm Type	Queries Required	Certainty
Classical Deterministic	$2^{n-1}+1$	100%
Classical Probabilistic	$O(1)$	High
Quantum (Deutsch-Jozsa)	1	100%

The Deutsch-Jozsa algorithm demonstrates an exponential speedup over any deterministic classical algorithm for this problem. This was a landmark result, proving that quantum computers could, in principle, solve some problems dramatically faster.

However, it's also important to note that the speedup over a probabilistic classical algorithm is less dramatic. A classical computer can solve the problem with high probability using only a few queries. This nuance is important: the power of quantum algorithms often lies in providing deterministic solutions to problems where classical deterministic solutions are intractable.

Conclusion

In this lesson, we have dissected the Deutsch-Jozsa algorithm, one of the foundational examples of quantum computational advantage.

Key Takeaways:

• The algorithm distinguishes between constant and balanced functions, a problem that is hard for deterministic classical computers.
• It achieves its power by combining quantum parallelism (evaluating the function for all inputs at once in a superposition) with quantum interference (using a final layer of Hadamard gates to make the desired information readable).
• The core physical mechanism enabling this is phase kickback, where an operation on a target qubit (the ancilla) induces a phase shift on a control qubit (the input register).
• The result is an exponential speedup over deterministic classical algorithms, achieved with a single query to the oracle.

The Deutsch-Jozsa problem is often described as being "cooked up" specifically to show off a quantum advantage. In our next lesson, we will explore Grover's search algorithm, which addresses a much more practical and general problem: finding a "marked" item in an unstructured database. While its speedup is not exponential, it is provably better than any possible classical algorithm, highlighting another facet of quantum advantage.