Chapter 11: Quantum Parallelism and Interference — How Quantum Algorithms Get Their Speedup

"The quantum computer does not try all possibilities at once. It does something far more subtle — and far more powerful."

Learning Objectives

After completing this chapter, you will be able to:

• Explain what quantum parallelism actually is and dispel the common "trying everything at once" myth
• Derive how the Hadamard transform creates a uniform superposition over all computational basis states
• Understand quantum interference as the mechanism that extracts useful information from superpositions
• Analyze Deutsch's problem as the simplest oracle-based quantum algorithm
• Describe the general structure of quantum speedup: superposition → oracle query → interference → measurement
• Explain why measurement destroys parallelism and how amplitude amplification circumvents this
• Implement quantum parallelism and interference in Qiskit
• Derive the Hadamard transform formula for arbitrary basis states and compute interference patterns explicitly
• Connect phase kickback to the broader principle of encoding classical information in quantum phases
• Distinguish between exponential, polynomial, and quadratic quantum speedups and explain why each occurs

11.1 The Great Misconception: What Quantum Parallelism Is Not

Ask a popular science article how quantum computers work, and you will almost certainly read: "A quantum computer tries all possible answers at once." This is wrong. It is not merely a simplification — it is a fundamental misunderstanding that obscures the true mechanism of quantum speedup.

If a quantum computer genuinely evaluated all $2^n$ inputs simultaneously and then simply read out the answer, quantum algorithms would be trivial to design and quantum computers would solve NP-complete problems in polynomial time. They do not. The reason reveals the deep structure of quantum computation.

Common Misconception: "Quantum computers try all possibilities at once"

This is the single most persistent myth about quantum computing. It suggests that quantum computation is like parallel classical computation — that each branch of the superposition independently solves the problem and we simply pick the best answer. This is impossible because measurement collapses the superposition to a single outcome. The art of quantum algorithm design is not in creating superpositions (that part is easy) but in engineering interference patterns that extract the right answer with high probability.

What quantum parallelism actually is: A quantum computer can evaluate a function $f(x)$ on a superposition of inputs, producing a superposition of input-output pairs:

$$U_f : \frac{1}{\sqrt{2^n}} \sum_{x \in \{0,1\}^n} |x\rangle|0\rangle \quad\longrightarrow\quad \frac{1}{\sqrt{2^n}} \sum_{x \in \{0,1\}^n} |x\rangle|f(x)\rangle$$

This is genuinely remarkable. In a single application of $U_f$, the quantum computer has computed $f(x)$ for exponentially many values of $x$. A classical computer would need $\Omega(2^n)$ separate evaluations. This is the essence of quantum parallelism.

The catch: When you measure the output register, you get one randomly chosen value $f(x)$ for one randomly chosen $x$. The exponential information is there, but it is locked inside the amplitudes. You cannot simply read it out. The art of quantum algorithm design is the art of manipulating amplitudes so that the information you want becomes overwhelmingly likely to appear when you finally measure.

To understand why measurement is so destructive, consider what happens if we measure the input register of the state $\frac{1}{\sqrt{2^n}} \sum_x |x\rangle|f(x)\rangle$ in the computational basis. The probability of obtaining outcome $|x_0\rangle|f(x_0)\rangle$ is $\frac{1}{2^n}$ — exactly the same as if we had picked $x_0$ uniformly at random and evaluated $f(x_0)$ classically. No advantage whatsoever. The superposition is destroyed, and we learn nothing about the global structure of $f$.

Key Insight: Quantum parallelism gives you exponential computation in a box. Quantum interference gives you the key to open the box and extract what you need.

Historical Context: The idea that quantum mechanics might offer computational advantages traces back to Richard Feynman's 1982 lecture "Simulating Physics with Computers," where he observed that simulating quantum systems on a classical computer seems to require exponential resources. David Deutsch formalized this insight in his 1985 paper, proposing the quantum Turing machine and posing the first problem (Deutsch's problem) where a quantum algorithm provably outperforms any classical one. The key insight was not that quantum computers evaluate many inputs at once — classical randomized algorithms can also sample many inputs — but that quantum amplitudes can interfere in ways that classical probabilities cannot.

11.2 The Hadamard Transform: Creating Superposition Over All Inputs

The workhorse of quantum parallelism is the Hadamard gate $H$, defined by its action on computational basis states:

$$H|0\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle), \qquad H|1\rangle = \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$$

In matrix form:

$$H = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$$

Notice that $H = H^\dagger = H^{-1}$, so $H^2 = I$. The Hadamard gate is its own inverse — applying it twice returns you to the original state. This seemingly trivial property has profound consequences: it means the Hadamard transform can be used both to create superpositions and to convert phase information back into computational basis information.

When we apply $H$ to each of $n$ qubits initialized to $|0\rangle$, we obtain the uniform superposition over all $2^n$ basis states:

$$H^{\otimes n} |0\rangle^{\otimes n} = \frac{1}{\sqrt{2^n}} \sum_{x \in \{0,1\}^n} |x\rangle$$

Proof by induction. For $n=1$, $H|0\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$. Assume true for $n-1$. Then:

$$H^{\otimes n}|0\rangle^{\otimes n} = (H \otimes H^{\otimes (n-1)})(|0\rangle \otimes |0\rangle^{\otimes (n-1)})$$

$$= \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle) \otimes \frac{1}{\sqrt{2^{n-1}}} \sum_{y \in \{0,1\}^{n-1}} |y\rangle$$

$$= \frac{1}{\sqrt{2^n}} \left( \sum_{y \in \{0,1\}^{n-1}} |0y\rangle + \sum_{y \in \{0,1\}^{n-1}} |1y\rangle \right)$$

$$= \frac{1}{\sqrt{2^n}} \sum_{x \in \{0,1\}^n} |x\rangle$$

This is the foundation. With $n$ Hadamard gates, we prepare a state that encodes all $2^n$ possible inputs simultaneously. The cost is linear in $n$; the representational power is exponential.

11.2.1 The Hadamard Transform on Arbitrary Basis States

The Hadamard transform also acts on an arbitrary basis state $|x\rangle$ (where $x \in \{0,1\}^n$):

$$H^{\otimes n}|x\rangle = \frac{1}{\sqrt{2^n}} \sum_{y \in \{0,1\}^n} (-1)^{x \cdot y} |y\rangle$$

where $x \cdot y = x_1 y_1 \oplus x_2 y_2 \oplus \cdots \oplus x_n y_n$ is the bitwise inner product modulo 2.

Proof. We factor the tensor product:

$$H^{\otimes n}|x\rangle = \bigotimes_{i=1}^{n} H|x_i\rangle = \bigotimes_{i=1}^{n} \frac{1}{\sqrt{2}}(|0\rangle + (-1)^{x_i}|1\rangle)$$

Expanding the tensor product:

$$= \frac{1}{\sqrt{2^n}} \sum_{y \in \{0,1\}^n} \prod_{i=1}^{n} (-1)^{x_i y_i} |y\rangle = \frac{1}{\sqrt{2^n}} \sum_{y \in \{0,1\}^n} (-1)^{x \cdot y} |y\rangle$$

This formula is crucial. It shows that the Hadamard transform encodes the binary string $x$ into a phase pattern over all basis states $|y\rangle$. The phase $(-1)^{x \cdot y}$ depends on the parity of the bitwise AND of $x$ and $y$. This is the mechanism by which the final Hadamard in Deutsch-Jozsa and Bernstein-Vazirani converts phase information into measurable results.

Try It Yourself: Compute $H^{\otimes 2}|10\rangle$ by hand. Write $x = (1,0)$, and compute $x \cdot y$ for all four values of $y$. Verify that you get $\frac{1}{2}(|00\rangle - |01\rangle + |10\rangle - |11\rangle)$.

11.2.2 The Hadamard Transform as a Change of Basis

The Hadamard transform can be understood as a change from the computational basis to the Hadamard basis (also called the Fourier basis over $\mathbb{Z}_2^n$). The Hadamard basis states are:

$$|x_H\rangle = H^{\otimes n}|x\rangle = \frac{1}{\sqrt{2^n}} \sum_{y} (-1)^{x \cdot y} |y\rangle$$

Any state $|\psi\rangle = \sum_x \alpha_x |x\rangle$ can be expressed in the Hadamard basis as $|\psi\rangle = \sum_x \tilde{\alpha}_x |x_H\rangle$, where:

$$\tilde{\alpha}_x = \frac{1}{\sqrt{2^n}} \sum_y (-1)^{x \cdot y} \alpha_y$$

This is the Walsh-Hadamard transform of the coefficient vector. The relationship between computational and Hadamard basis coefficients is:

$$\tilde{\alpha} = H^{\otimes n} \alpha$$

Since $H^{\otimes n}$ is its own inverse ($H^{\otimes n} H^{\otimes n} = I^{\otimes n}$), applying it twice returns the original coefficients. This self-inverse property is what makes the Hadamard transform both a tool for creating superpositions and for converting phases to computational basis information.

ASCII Circuit Diagram — Hadamard Transform on $n$ Qubits:

q_0: |0> ---[H]---+--------
                    |
q_1: |0> ---[H]---+--------
                    |
q_2: |0> ---[H]---+--------
                    |
...               ...
                    |
q_{n-1}: |0> -[H]-+--------

Output: (1/√(2^n)) Σ |x⟩   (uniform superposition)

Worked Example: Hadamard Transform on 3 Qubits

Let's compute $H^{\otimes 3}|000\rangle$ explicitly:

$$H^{\otimes 3}|000\rangle = H|0\rangle \otimes H|0\rangle \otimes H|0\rangle$$

$$= \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle) \otimes \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle) \otimes \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$$

$$= \frac{1}{\sqrt{8}}(|000\rangle + |001\rangle + |010\rangle + |011\rangle + |100\rangle + |101\rangle + |110\rangle + |111\rangle)$$

$$= \frac{1}{\sqrt{8}} \sum_{x=0}^{7} |x\rangle$$

Each of the 8 basis states has amplitude $\frac{1}{\sqrt{8}} = \frac{1}{2\sqrt{2}}$, and measurement yields each with equal probability $\frac{1}{8}$.

Now let's compute $H^{\otimes 3}|101\rangle$. Using the formula:

$$H^{\otimes 3}|101\rangle = \frac{1}{\sqrt{8}} \sum_{y \in \{0,1\}^3} (-1)^{101 \cdot y} |y\rangle$$

Computing the inner products: - $101 \cdot 000 = 0$, so the coefficient of $|000\rangle$ is $+\frac{1}{\sqrt{8}}$ - $101 \cdot 001 = 1$, so the coefficient of $|001\rangle$ is $-\frac{1}{\sqrt{8}}$ - $101 \cdot 010 = 0$, so the coefficient of $|010\rangle$ is $+\frac{1}{\sqrt{8}}$ - $101 \cdot 011 = 1$, so the coefficient of $|011\rangle$ is $-\frac{1}{\sqrt{8}}$ - $101 \cdot 100 = 1$, so the coefficient of $|100\rangle$ is $-\frac{1}{\sqrt{8}}$ - $101 \cdot 101 = 0 \oplus 0 \oplus 1 = 1$... wait, let me recompute: $1 \cdot 1 + 0 \cdot 0 + 1 \cdot 1 = 1 + 0 + 1 = 2 \equiv 0 \pmod{2}$, so the coefficient of $|101\rangle$ is $+\frac{1}{\sqrt{8}}$ - $101 \cdot 110 = 1 \cdot 1 + 0 \cdot 1 + 1 \cdot 0 = 1$, so the coefficient of $|110\rangle$ is $-\frac{1}{\sqrt{8}}$ - $101 \cdot 111 = 1 + 0 + 1 = 0 \pmod{2}$, so the coefficient of $|111\rangle$ is $+\frac{1}{\sqrt{8}}$

$$H^{\otimes 3}|101\rangle = \frac{1}{\sqrt{8}}(|000\rangle - |001\rangle + |010\rangle - |011\rangle - |100\rangle + |101\rangle - |110\rangle + |111\rangle)$$

The key observation: the sign pattern encodes the binary string $x = 101$. The Hadamard transform has converted position information (which basis state) into phase information (the sign pattern).

11.3 Quantum Interference: The Engine of Speedup

If superposition is the fuel, interference is the engine. Quantum interference is the phenomenon by which amplitudes combine — sometimes constructively, sometimes destructively — to shape the probability distribution that emerges upon measurement.

11.3.1 The Mathematics of Interference

Consider two paths to the same computational basis state $|y\rangle$, with amplitudes $\alpha_1$ and $\alpha_2$. The total amplitude is $\alpha_1 + \alpha_2$, and the probability of measuring $|y\rangle$ is:

$$P(y) = |\alpha_1 + \alpha_2|^2 = |\alpha_1|^2 + |\alpha_2|^2 + 2\,\text{Re}(\alpha_1^* \alpha_2)$$

The cross term $2\,\text{Re}(\alpha_1^* \alpha_2)$ is the interference term. When $\alpha_1$ and $\alpha_2$ have the same phase, we get constructive interference (probability increases). When they have opposite phases, we get destructive interference (probability decreases, potentially to zero).

This is fundamentally different from classical probability, where the probability of reaching an outcome via two mutually exclusive paths is always $P_1 + P_2$ (the sum rule). In quantum mechanics, the amplitudes add first, then the probability is computed. The difference between $|\alpha_1 + \alpha_2|^2$ and $|\alpha_1|^2 + |\alpha_2|^2$ is precisely the interference term.

Worked Example: Two-Path Interference

Suppose a quantum system can reach state $|y\rangle$ via two paths with equal-magnitude amplitudes $\alpha_1 = \frac{1}{\sqrt{2}}$ and $\alpha_2 = \frac{1}{\sqrt{2}} \cdot e^{i\phi}$, where $\phi$ is a relative phase.

$$P(y) = \left|\frac{1}{\sqrt{2}} + \frac{e^{i\phi}}{\sqrt{2}}\right|^2 = \frac{1}{2}\left|1 + e^{i\phi}\right|^2 = \frac{1}{2}(2 + 2\cos\phi) = 1 + \cos\phi$$

• $\phi = 0$: $P(y) = 2$ (full constructive interference, probability 2 — but wait, this must be normalized; the point is that constructive interference doubles the probability relative to incoherent addition)
• $\phi = \pi$: $P(y) = 0$ (full destructive interference, complete cancellation)
• $\phi = \pi/2$: $P(y) = 1$ (no interference, probabilities simply add)

This simple calculation captures the essence of all quantum algorithms: by controlling the relative phases of different paths, we can arrange for wrong answers to cancel and right answers to reinforce.

11.3.2 Interference in the Hadamard Basis

The Hadamard transform is the simplest example of quantum interference. Consider what happens when we apply $H$ to the state $\frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$:

$$H \cdot \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle) = \frac{1}{\sqrt{2}}(H|0\rangle + H|1\rangle) = \frac{1}{\sqrt{2}}\left(\frac{|0\rangle + |1\rangle}{\sqrt{2}} + \frac{|0\rangle - |1\rangle}{\sqrt{2}}\right)$$

$$= \frac{1}{2}(|0\rangle + |1\rangle + |0\rangle - |1\rangle) = \frac{1}{2}(2|0\rangle) = |0\rangle$$

The amplitude of $|1\rangle$ cancels to zero (destructive interference), while the amplitude of $|0\rangle$ doubles (constructive interference). This is the core mechanism of the Deutsch-Jozsa algorithm.

Now consider $H$ applied to $\frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$:

$$H \cdot \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle) = \frac{1}{\sqrt{2}}(H|0\rangle - H|1\rangle) = \frac{1}{\sqrt{2}}\left(\frac{|0\rangle + |1\rangle}{\sqrt{2}} - \frac{|0\rangle - |1\rangle}{\sqrt{2}}\right)$$

$$= \frac{1}{2}(|0\rangle + |1\rangle - |0\rangle + |1\rangle) = |1\rangle$$

Now $|0\rangle$ cancels and $|1\rangle$ reinforces. The Hadamard transform has converted a phase difference (between $|0\rangle + |1\rangle$ and $|0\rangle - |1\rangle$) into a computational basis difference (between $|0\rangle$ and $|1\rangle$). This conversion — phase to position — is the fundamental trick of quantum algorithms.

11.3.3 Multi-Qubit Interference

For $n$ qubits, the interference pattern becomes much richer. After applying $H^{\otimes n}$ to a state $\sum_x \alpha_x |x\rangle$, the amplitude of each output basis state $|y\rangle$ is:

$$\beta_y = \frac{1}{\sqrt{2^n}} \sum_x (-1)^{x \cdot y} \alpha_x$$

Each output amplitude involves a sum over all $2^n$ input amplitudes, with signs determined by the parity of $x \cdot y$. Whether $\beta_y$ is large or small depends on whether the signs $(-1)^{x \cdot y}$ are arranged to constructively or destructively interfere with the input amplitudes $\alpha_x$.

Worked Example: Interference for a Constant Function

Consider a 2-qubit system where the oracle has encoded a constant function: all amplitudes have the same phase. The state after the oracle is:

$$|\psi\rangle = \frac{1}{2}(|00\rangle + |01\rangle + |10\rangle + |11\rangle)$$

Applying $H^{\otimes 2}$:

$$H^{\otimes 2}|\psi\rangle = \frac{1}{2} \cdot \frac{1}{2} \sum_y \left(\sum_x (-1)^{x \cdot y} \cdot 1\right) |y\rangle$$

For $y = 00$: $\sum_x (-1)^{x \cdot 00} = 1 + 1 + 1 + 1 = 4$, so amplitude = $\frac{1}{4} \cdot 4 = 1$. For $y \neq 00$: $\sum_x (-1)^{x \cdot y} = 0$ (destructive interference cancels everything).

Result: $|00\rangle$ with probability 1. All the amplitude concentrates on a single output.

Worked Example: Interference for a Balanced Function

Now suppose the oracle encodes a balanced function, e.g., $f(x) = x_1$ (first bit):

$$|\psi\rangle = \frac{1}{2}(|00\rangle - |01\rangle + |10\rangle - |11\rangle)$$

Applying $H^{\otimes 2}$:

For $y = 00$: $\sum_x (-1)^{x \cdot y} \alpha_x = 1 + (-1) + 1 + (-1) = 0$ (destructive interference). For $y = 01$: $\sum_x (-1)^{x \cdot y} \alpha_x = 1 \cdot 1 + (-1) \cdot (-1) + 1 \cdot 1 + (-1) \cdot (-1)$... let me compute this more carefully using the formula.

$$\beta_{00} = \frac{1}{2}(1 \cdot 1 + (-1) \cdot 1 + 1 \cdot 1 + (-1) \cdot 1) = 0$$

All the amplitude is distributed among non-zero basis states. The state $|00\rangle$ has zero probability.

The algorithmic template for virtually all quantum algorithms is:

1. Superposition: Use $H^{\otimes n}$ to create a uniform superposition over all inputs.
2. Oracle Query: Apply $U_f$ to compute $f(x)$ in superposition, entangling input and output registers.
3. Interference: Apply a carefully designed unitary that causes amplitudes for "wrong" answers to cancel destructively and amplitudes for "right" answers to interfere constructively.
4. Measurement: Measure the register. With high probability, you obtain the answer.

|0>^n  --[H^⊗n]--+--[ U_f ]--+--[Interference]--+--[Measure]--> result
                    |            |                   |
|0>^m  -----------+------------+-------------------+
                   input      oracle              output

Recurring Theme — Quantum is Linear Algebra, Not Magic: Quantum interference is not mysterious. It is a direct consequence of the linearity of quantum mechanics. Amplitudes add like vectors in a linear space, and probabilities are the squared norms of those vectors. The "magic" of quantum algorithms is not in the physics — it is in the clever choice of unitary operations that steer amplitude toward the correct answer and away from wrong answers. All of this is just linear algebra.

11.4 Deutsch's Problem: The Simplest Quantum Algorithm

In 1985, David Deutsch posed a problem so simple it seems almost trivial — yet it was the first problem for which a quantum algorithm provably outperforms any classical algorithm.

The problem: You are given a black box (oracle) that computes a function $f: \{0,1\} \to \{0,1\}$. There are four possible functions:

The question: Is $f$ constant ($f(0) = f(1)$) or balanced ($f(0) \neq f(1)$)?

Classical solution: You must query the oracle twice — evaluate both $f(0)$ and $f(1)$ — to determine the answer with certainty. One query tells you nothing about the other input. If you query $f(0)$ and get 1, you don't know whether $f$ is constant-1 or balanced-NOT. You need a second query.

Quantum solution (Deutsch's algorithm): One query suffices.

Historical Context: Deutsch's 1985 result was primarily conceptual — it showed that quantum computers could outperform classical ones, even if only for an artificial problem. The significance was philosophical: it was the first rigorous demonstration that quantum mechanics provides computational power beyond classical physics. This inspired the development of more practical algorithms like Shor's and Grover's.

Why This Matters: Deutsch's problem is important not for its practical utility — no one needs to determine if a 1-bit function is constant or balanced — but because it isolates the essential mechanism of quantum speedup: interference. The same mechanism, scaled up, powers all known quantum algorithms.

The circuit:

q_0: |0> ---[H]---[●]---[H]---[Measure]
                   |              
q_1: |1> ---[H]---[U_f]---------

Step-by-step analysis:

Step 1 — Initial state: $$|\psi_0\rangle = |0\rangle \otimes |1\rangle = |01\rangle$$

Step 2 — Apply Hadamard to both qubits: $$|\psi_1\rangle = H|0\rangle \otimes H|1\rangle = \frac{|0\rangle + |1\rangle}{\sqrt{2}} \otimes \frac{|0\rangle - |1\rangle}{\sqrt{2}}$$

$$= \frac{1}{2}\big(|0\rangle|0\rangle - |0\rangle|1\rangle + |1\rangle|0\rangle - |1\rangle|1\rangle\big)$$

Notice that the second qubit is in the state $|-\rangle = \frac{|0\rangle - |1\rangle}{\sqrt{2}}$. This is not arbitrary — it is crucial for the phase kickback mechanism.

Step 3 — Apply the oracle $U_f$. Recall that $U_f|x\rangle|y\rangle = |x\rangle|y \oplus f(x)\rangle$. A crucial trick: when the target qubit is in the state $\frac{|0\rangle - |1\rangle}{\sqrt{2}}$, the oracle imparts a phase:

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

Let us verify this explicitly for both values of $f(x)$:

• If $f(x) = 0$: $U_f|x\rangle|-\rangle = |x\rangle \frac{|0 \oplus 0\rangle - |1 \oplus 0\rangle}{\sqrt{2}} = |x\rangle \frac{|0\rangle - |1\rangle}{\sqrt{2}} = (+1)|x\rangle|-\rangle$
• If $f(x) = 1$: $U_f|x\rangle|-\rangle = |x\rangle \frac{|0 \oplus 1\rangle - |1 \oplus 1\rangle}{\sqrt{2}} = |x\rangle \frac{|1\rangle - |0\rangle}{\sqrt{2}} = (-1)|x\rangle|-\rangle$

In both cases: $U_f|x\rangle|-\rangle = (-1)^{f(x)}|x\rangle|-\rangle$. This is the phase kickback trick. The oracle effectively multiplies the input state by $(-1)^{f(x)}$:

$$|\psi_2\rangle = \frac{1}{2}\big((-1)^{f(0)}|0\rangle + (-1)^{f(1)}|1\rangle\big) \otimes \frac{|0\rangle - |1\rangle}{\sqrt{2}}$$

Step 4 — Apply Hadamard to the first qubit:

$$|\psi_3\rangle = H\Big(\frac{(-1)^{f(0)}|0\rangle + (-1)^{f(1)}|1\rangle}{\sqrt{2}}\Big) \otimes \frac{|0\rangle - |1\rangle}{\sqrt{2}}$$

Using $H|x\rangle = \frac{1}{\sqrt{2}}(|0\rangle + (-1)^x|1\rangle)$:

$$|\psi_3\rangle = \frac{1}{2}\Big[(-1)^{f(0)}(|0\rangle + |1\rangle) + (-1)^{f(1)}(|0\rangle - |1\rangle)\Big] \otimes \frac{|0\rangle - |1\rangle}{\sqrt{2}}$$

$$= \frac{1}{2}\Big[\big((-1)^{f(0)} + (-1)^{f(1)}\big)|0\rangle + \big((-1)^{f(0)} - (-1)^{f(1)}\big)|1\rangle\Big] \otimes \frac{|0\rangle - |1\rangle}{\sqrt{2}}$$

Step 5 — Measure the first qubit:

• If $f$ is constant ($f(0) = f(1)$): the coefficient of $|1\rangle$ is zero. We measure $|0\rangle$ with probability 1.
• If $f$ is balanced ($f(0) \neq f(1)$): the coefficient of $|0\rangle$ is zero. We measure $|1\rangle$ with probability 1.

One query, certain answer. The interference at the final Hadamard gate is what makes this work: the amplitudes for the "wrong" answer cancel perfectly.

Common Misconception: "Deutsch's algorithm evaluates $f$ on both inputs simultaneously"

While it's true that the oracle is queried on a superposition, the algorithm doesn't simply "read out $f(0)$ and $f(1)$." Instead, it encodes the relationship between $f(0)$ and $f(1)$ — whether they're equal or different — into a global phase pattern, and then uses interference to convert that pattern into a measurement outcome. The quantum computer never learns the individual values $f(0)$ and $f(1)$; it only learns whether they are the same or different. This is a global property, not two local evaluations.

11.4.1 Detailed Worked Example: Each Oracle Type

Let us trace Deutsch's algorithm for each of the four possible oracles:

Case 1: $f(x) = 0$ (constant)

After oracle: $|\psi_2\rangle = \frac{1}{2}((+1)|0\rangle + (+1)|1\rangle) \otimes |-\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle) \otimes |-\rangle$

After final $H$: $H \cdot \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle) = |0\rangle$

Measurement: outcome 0 (constant). Correct.

Case 2: $f(x) = 1$ (constant)

After oracle: $|\psi_2\rangle = \frac{1}{2}((-1)|0\rangle + (-1)|1\rangle) \otimes |-\rangle = \frac{-1}{\sqrt{2}}(|0\rangle + |1\rangle) \otimes |-\rangle$

After final $H$: $H \cdot \frac{-1}{\sqrt{2}}(|0\rangle + |1\rangle) = -|0\rangle$

Measurement: outcome 0 (the global phase $-1$ is unobservable). Correct.

Case 3: $f(x) = x$ (balanced)

After oracle: $|\psi_2\rangle = \frac{1}{2}((+1)|0\rangle + (-1)|1\rangle) \otimes |-\rangle = \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle) \otimes |-\rangle$

After final $H$: $H \cdot \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle) = |1\rangle$

Measurement: outcome 1 (balanced). Correct.

Case 4: $f(x) = 1 \oplus x$ (balanced, NOT)

After oracle: $|\psi_2\rangle = \frac{1}{2}((-1)|0\rangle + (+1)|1\rangle) \otimes |-\rangle = \frac{1}{\sqrt{2}}(-|0\rangle + |1\rangle) \otimes |-\rangle$

After final $H$: $H \cdot \frac{1}{\sqrt{2}}(-|0\rangle + |1\rangle) = \frac{1}{2}(-|0\rangle - |1\rangle + |0\rangle - |1\rangle) = -|1\rangle$

Measurement: outcome 1 (balanced). Correct.

All four cases are determined correctly with a single oracle query.

11.5 Qiskit Implementation: Deutsch's Algorithm

from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
from qiskit_aer import AerSimulator
from qiskit.visualization import plot_histogram

def deutsch_algorithm(oracle_type='constant_0'):
    """
    Implements Deutsch's algorithm for a 1-qubit oracle.
    oracle_type: 'constant_0', 'constant_1', 'balanced_id', 'balanced_not'
    """
    qr = QuantumRegister(2, 'q')
    cr = ClassicalRegister(1, 'c')
    qc = QuantumCircuit(qr, cr)

    # Step 1: Prepare |0⟩|1⟩
    qc.x(1)  # Flip second qubit to |1⟩

    # Step 2: Apply Hadamard to both
    qc.h(0)
    qc.h(1)

    # Step 3: Oracle
    if oracle_type == 'constant_0':
        pass  # f(x) = 0, U_f = I
    elif oracle_type == 'constant_1':
        qc.x(1)  # f(x) = 1, flip target
    elif oracle_type == 'balanced_id':
        qc.cx(0, 1)  # f(x) = x
    elif oracle_type == 'balanced_not':
        qc.x(0)
        qc.cx(0, 1)  # f(x) = NOT x
        qc.x(0)

    # Step 4: Final Hadamard on first qubit
    qc.h(0)

    # Step 5: Measure
    qc.measure(0, 0)

    return qc

# Run all four cases
simulator = AerSimulator()
for oracle in ['constant_0', 'constant_1', 'balanced_id', 'balanced_not']:
    qc = deutsch_algorithm(oracle)
    result = simulator.run(qc, shots=1024).result()
    counts = result.get_counts()
    result_bit = '0' if oracle.startswith('constant') else '1'
    print(f"Oracle {oracle:15s}: measured {max(counts, key=counts.get)} "
          f"(expected {result_bit}), counts={counts}")

Expected output:

Oracle constant_0     : measured 0 (expected 0), counts={'0': 1024}
Oracle constant_1     : measured 0 (expected 0), counts={'0': 1024}
Oracle balanced_id    : measured 1 (expected 1), counts={'1': 1024}
Oracle balanced_not   : measured 1 (expected 1), counts={'1': 1024}

11.5.1 Qiskit Implementation: Statevector Analysis of Deutsch's Algorithm

To see the interference explicitly, we can use the statevector simulator to track the quantum state at each step:

from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator
from qiskit.quantum_info import Statevector
import numpy as np

def deutsch_statevector_trace(oracle_type='balanced_id'):
    """Trace the statevector through Deutsch's algorithm step by step."""
    qc = QuantumCircuit(2)

    # Initial state: |01⟩
    qc.x(1)
    state = Statevector(qc)
    print(f"After initialization: {np.round(state, 3)}")

    # Hadamard on both qubits
    qc.h(0)
    qc.h(1)
    state = Statevector(qc)
    print(f"After H⊗2:           {np.round(state, 3)}")

    # Oracle
    if oracle_type == 'balanced_id':
        qc.cx(0, 1)
    elif oracle_type == 'balanced_not':
        qc.x(0)
        qc.cx(0, 1)
        qc.x(0)
    elif oracle_type == 'constant_1':
        qc.x(1)

    state = Statevector(qc)
    print(f"After oracle:        {np.round(state, 3)}")

    # Final Hadamard on first qubit
    qc.h(0)
    state = Statevector(qc)
    print(f"After final H:       {np.round(state, 3)}")
    print(f"\nProbability of measuring 0: {abs(state[0])**2 + abs(state[2])**2:.4f}")
    print(f"Probability of measuring 1: {abs(state[1])**2 + abs(state[3])**2:.4f}")

# Trace balanced (identity) oracle
print("=== Balanced (identity) oracle ===")
deutsch_statevector_trace('balanced_id')

print("\n=== Constant-0 oracle ===")
deutsch_statevector_trace('constant_0')

Expected output:

=== Balanced (identity) oracle ===
After initialization: [0+0j 0+0j 1+0j 0+0j]
After H⊗2:           [ 0.5+0j -0.5+0j  0.5+0j -0.5+0j]
After oracle:        [ 0.5+0j -0.5+0j -0.5+0j  0.5+0j]
After final H:       [0+0j 1+0j 0+0j 0+0j]

Probability of measuring 0: 0.0000
Probability of measuring 1: 1.0000

=== Constant-0 oracle ===
After initialization: [0+0j 0+0j 1+0j 0+0j]
After H⊗2:           [ 0.5+0j -0.5+0j  0.5+0j -0.5+0j]
After oracle:        [ 0.5+0j -0.5+0j  0.5+0j -0.5+0j]
After final H:       [1+0j 0+0j 0+0j 0+0j]

Probability of measuring 0: 1.0000
Probability of measuring 1: 0.0000

Notice how the oracle flips the sign of specific amplitudes (phase kickback), and the final Hadamard converts this phase pattern into a definite computational basis outcome.

11.5.2 Qiskit Implementation: Visualizing Interference Patterns

import numpy as np
from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator
from qiskit.quantum_info import Statevector

def visualize_interference(n_qubits=3, marked_states=None):
    """
    Create a uniform superposition, apply a phase oracle marking
    specific states, then show how interference redistributes
    probability amplitude.
    """
    if marked_states is None:
        marked_states = [0, 3, 5]

    # Step 1: Create uniform superposition
    qc = QuantumCircuit(n_qubits)
    qc.h(range(n_qubits))
    state_before = Statevector(qc)
    probs_before = np.abs(state_before) ** 2

    # Step 2: Apply phase oracle (flip sign of marked states)
    for state in marked_states:
        binary = format(state, f'0{n_qubits}b')
        for i, bit in enumerate(binary):
            if bit == '0':
                qc.x(i)
        qc.h(n_qubits - 1)
        qc.mcx(list(range(n_qubits - 1)), n_qubits - 1)
        qc.h(n_qubits - 1)
        for i, bit in enumerate(binary):
            if bit == '0':
                qc.x(i)

    state_after_oracle = Statevector(qc)

    # Step 3: Apply Hadamard transform (interference)
    qc.h(range(n_qubits))
    state_after_interference = Statevector(qc)
    probs_after = np.abs(state_after_interference) ** 2

    # Display results
    print("State probabilities (uniform superposition):")
    for i in range(2**n_qubits):
        bar = '█' * int(probs_before[i] * 50)
        print(f"  |{i:03b}⟩: {probs_before[i]:.4f} {bar}")

    print(f"\nAfter phase oracle (marked: {marked_states}):")
    amplitudes = np.array(state_after_oracle)
    for i in range(2**n_qubits):
        phase = '⊕' if amplitudes[i].real < 0 else ' '
        bar = '█' * int(probs_before[i] * 50)
        print(f"  |{i:03b}⟩: amp={amplitudes[i]:+.4f} {phase}")

    print(f"\nAfter Hadamard interference:")
    for i in range(2**n_qubits):
        bar = '█' * int(probs_after[i] * 50)
        print(f"  |{i:03b}⟩: {probs_after[i]:.4f} {bar}")

visualize_interference(3, marked_states=[0, 3, 5])

11.6 Why Measurement Destroys Parallelism

The central tension in quantum computing is this: quantum parallelism computes $f(x)$ for all $x$ simultaneously, but measurement collapses the state to a single basis vector. If we simply measure after the oracle, we get:

$$P(\text{obtaining } (x, f(x))) = \frac{1}{2^n}$$

This is no better than classical random guessing. The exponential information is there, encoded in the amplitudes, but measurement gives us only $\log_2(2^n) = n$ bits — the same amount of information as a single classical evaluation.

11.6.1 The Holevo Bound and Information-Theoretic Limits

The Holevo bound formalizes this limitation. It states that the maximum amount of classical information that can be extracted from $n$ qubits is $n$ bits, regardless of the quantum state they encode. Specifically, if Alice encodes a classical random variable $X$ into a quantum state $\rho_X$ and sends it to Bob, then:

$$I(X : Y) \leq S(\rho) \leq n$$

where $I(X:Y)$ is the mutual information between $X$ and Bob's measurement outcome $Y$, $S(\rho)$ is the von Neumann entropy, and $n$ is the number of qubits.

This means that even though a quantum state $\frac{1}{\sqrt{2^n}} \sum_x |x\rangle|f(x)\rangle$ contains $2^n$ function evaluations, no measurement can extract more than $n$ bits of classical information from it. Quantum parallelism is powerful, but it does not violate information-theoretic limits.

The resolution: We must not measure immediately. Instead, we apply additional unitary operations that cause the amplitudes to interfere. The goal is to concentrate probability mass onto a small set of basis states that encode the answer. Only then do we measure.

This is why quantum algorithm design is hard. You must find an interference pattern that: 1. Can be implemented efficiently (polynomial number of gates) 2. Amplifies the correct answer's amplitude to near 1 3. Suppresses all other amplitudes to near 0

11.6.2 The No-Cloning Theorem and Parallelism

Another fundamental limitation is the no-cloning theorem: there is no unitary operation that can copy an unknown quantum state. Formally, there is no unitary $U$ such that $U|\psi\rangle|0\rangle = |\psi\rangle|\psi\rangle$ for all $|\psi\rangle$.

Proof: Suppose such a $U$ exists. Then $U|0\rangle|0\rangle = |0\rangle|0\rangle$ and $U|1\rangle|0\rangle = |1\rangle|1\rangle$. By linearity:

$$U\left(\frac{|0\rangle + |1\rangle}{\sqrt{2}}\right)|0\rangle = \frac{U|0\rangle|0\rangle + U|1\rangle|0\rangle}{\sqrt{2}} = \frac{|00\rangle + |11\rangle}{\sqrt{2}}$$

But if cloning worked:

$$\left(\frac{|0\rangle + |1\rangle}{\sqrt{2}}\right) \otimes \left(\frac{|0\rangle + |1\rangle}{\sqrt{2}}\right) = \frac{|00\rangle + |01\rangle + |10\rangle + |11\rangle}{2}$$

These are different states, contradicting linearity.

The no-cloning theorem means we cannot make copies of the superposition $\sum_x |x\rangle|f(x)\rangle$ to extract more information. Each copy of the state is a precious resource, and the algorithm must extract the maximum information from a single copy.

Recurring Theme — Noise is the Enemy: In practice, the problem is even harder than the theory suggests. Quantum states are fragile — decoherence destroys superpositions and entanglement. Each additional gate introduces noise. A quantum algorithm must not only find the right interference pattern but must do so with a circuit shallow enough that decoherence doesn't destroy the result before measurement. This is why error correction and fault-tolerant quantum computing are essential for large-scale algorithms.

11.7 Amplitude Amplification: Intuition

Consider a search problem: among $N = 2^n$ items, exactly $M$ are "marked" (solutions). In a uniform superposition, the total probability of measuring a solution is $M/N$. If $M \ll N$, this is vanishingly small.

Amplitude amplification (the core of Grover's algorithm, which we study in Chapter 13) is a technique that repeatedly applies two operations:

1. Oracle reflection: Flip the sign of amplitudes for solution states: $|x\rangle \to -|x\rangle$ if $x$ is a solution.
2. Diffusion (inversion about the mean): Reflect all amplitudes about their average value.

Each iteration increases the amplitude of solution states. Geometrically, this is a rotation in a 2-dimensional plane spanned by the uniform superposition of solutions and the uniform superposition of non-solutions.

11.7.1 Detailed Geometric Derivation

Let us derive this more carefully. Define:

$$|\alpha\rangle = \frac{1}{\sqrt{N-M}} \sum_{x \notin S} |x\rangle \qquad \text{(uniform superposition over non-solutions)}$$

$$|\beta\rangle = \frac{1}{\sqrt{M}} \sum_{x \in S} |x\rangle \qquad \text{(uniform superposition over solutions)}$$

The initial uniform superposition decomposes as:

$$|s\rangle = \sqrt{\frac{N-M}{N}}|\alpha\rangle + \sqrt{\frac{M}{N}}|\beta\rangle$$

Define $\sin\theta = \sqrt{M/N}$, so $\cos\theta = \sqrt{(N-M)/N}$. Then $|s\rangle = \cos\theta|\alpha\rangle + \sin\theta|\beta\rangle$.

The oracle $O_\omega$ reflects about $|\alpha\rangle$: it flips the sign of $|\beta\rangle$ while leaving $|\alpha\rangle$ unchanged. In the $\{|\alpha\rangle, |\beta\rangle\}$ basis:

$$O_\omega = I - 2|\beta\rangle\langle\beta| = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}$$

This maps $\cos\theta|\alpha\rangle + \sin\theta|\beta\rangle \to \cos\theta|\alpha\rangle - \sin\theta|\beta\rangle$.

The diffusion operator $D$ reflects about $|s\rangle$: $D = 2|s\rangle\langle s| - I$.

The composition $G = D \cdot O_\omega$ is a rotation. To see this, note that the composition of two reflections is a rotation by twice the angle between the reflection axes. The angle between $|\alpha\rangle$ and $|s\rangle$ is $\theta$, so $G$ rotates by $2\theta$ in the $\{|\alpha\rangle, |\beta\rangle\}$ plane.

After $k$ iterations:

$$G^k|s\rangle = \cos((2k+1)\theta)|\alpha\rangle + \sin((2k+1)\theta)|\beta\rangle$$

The probability of measuring a solution is:

$$P_{\text{success}}(k) = \sin^2((2k+1)\theta) \approx \sin^2\left(\frac{(2k+1) \cdot 2}{\sqrt{N}}\right)$$

for $M = 1$ (single solution), where $\theta \approx 2/\sqrt{N}$ for large $N$.

Geometric intuition (ASCII diagram):

        |β⟩ (solutions)
        ^
       /|
      / |
     /  |
    /   |  G|s⟩ = rotate by 2θ
   /    |  G²|s⟩ = rotate by 4θ
  /     |  G³|s⟩ = rotate by 6θ
 /      |
/ θ     |
/_______|___________⟩ |α⟩ (non-solutions)
|s⟩
(initial uniform superposition)

Each Grover iteration rotates the state vector by $2\theta$ toward $|\beta\rangle$. We want to stop when the state is as close to $|\beta\rangle$ as possible — that is, when the total rotation has brought us to angle $\pi/2$ from the $|\alpha\rangle$ axis.

Numerical example: For $N = 16$ and $M = 1$: - $\sin\theta = 1/\sqrt{16} = 1/4$, so $\theta \approx 0.2527$ radians - After 1 iteration: angle $= 3\theta \approx 0.7581$, probability $= \sin^2(0.7581) \approx 0.478$ - After 2 iterations: angle $= 5\theta \approx 1.2635$, probability $= \sin^2(1.2635) \approx 0.864$ - After 3 iterations: angle $= 7\theta \approx 1.7689$, probability $= \sin^2(1.7689) \approx 0.961$

The optimal number of iterations is $k_{\text{opt}} = \lfloor \frac{\pi}{4}\sqrt{N/M} \rfloor = \lfloor \frac{\pi}{4} \cdot 4 \rfloor = 3$.

After approximately $\frac{\pi}{4}\sqrt{N/M}$ iterations, the state is almost entirely within the solution subspace, and measurement yields a solution with high probability.

Try It Yourself: For $N = 64$ and $M = 1$, compute $\theta$, $k_{\text{opt}}$, and the success probability after $k_{\text{opt}}$ iterations. Verify that $k_{\text{opt}} \approx 6$ and the success probability is close to 1.

11.8 The General Structure of Quantum Speedup

All known quantum algorithms that achieve superpolynomial speedup follow the same template. Understanding this template is more important than memorizing any individual algorithm.

The Quantum Algorithmic Framework:

The interference transform $U_{\text{interference}}$ is algorithm-specific:

• Deutsch-Jozsa: Final Hadamard gates (Hadamard is its own inverse, and the Hadamard transform converts phase differences into computational basis states)
• Bernstein-Vazirani: Final Hadamard gates (the Hadamard is the Fourier transform over $\mathbb{Z}_2^n$, and it converts a character into a delta function)
• Grover's algorithm: Repeated oracle + diffusion steps
• Shor's algorithm: Quantum Fourier Transform (QFT)
• Quantum simulation: Trotterized time evolution + QFT for phase estimation

11.8.1 Taxonomy of Quantum Speedups

Not all quantum speedups are created equal. Understanding the type of speedup helps clarify what quantum computers can and cannot do:

Exponential speedup: The quantum algorithm solves the problem in time polynomial in $n$, while the best classical algorithm requires time exponential in $n$. Examples: Shor's factoring algorithm, quantum simulation of local Hamiltonians, Deutsch-Jozsa (promise problem).

Polynomial speedup: The quantum algorithm is faster than the best classical algorithm by a polynomial factor. Example: Grover's search ($O(\sqrt{N})$ vs. $O(N)$, a quadratic speedup).

No speedup: Some problems provably admit no quantum speedup at all. For example, the query complexity of computing the OR of $n$ bits is $\Theta(n)$ for both classical and quantum algorithms (up to constant factors), and the search problem in a sorted database is $O(\log n)$ for both.

Recurring Theme — Quantum Advantage is Problem-Specific: Quantum computers are not universally faster than classical computers. They achieve speedups only for specific problems where the structure of the problem aligns with the capabilities of quantum mechanics (superposition, interference, entanglement). For many problems, quantum computers offer no advantage at all.

11.8.2 Why Quantum Speedups Occur: Three Perspectives

Perspective 1 — Interference of Paths: Classical computation follows one path. Quantum computation explores many paths simultaneously, and interference allows the "right" paths to reinforce while "wrong" paths cancel. This is the most common explanation and is essentially correct, though it understates the difficulty of engineering the right interference pattern.

Perspective 2 — Fourier Analysis: Many quantum algorithms can be understood as computing a Fourier transform of some function and extracting global properties (periodicity, parity, hidden subgroup structure). The QFT (and its special case, the Hadamard transform) converts phase information — which encodes the global property — into measurable position information.

Perspective 3 — Algebraic Structure: The deepest perspective is that quantum speedups arise from the representation theory of the underlying group. The algorithms that achieve exponential speedup (Shor's, Simon's) exploit the hidden subgroup structure of the problem: the function $f$ is constant on cosets of a hidden subgroup, and the QFT over the appropriate group reveals this subgroup structure.

Recurring Theme — We're at the Beginning: The quantum algorithms we know — Deutsch-Jozsa, Bernstein-Vazirani, Shor's, Grover's — represent only a tiny fraction of what quantum computers might eventually do. New quantum algorithms are being discovered regularly (quantum machine learning, quantum optimization, quantum chemistry), and we are far from understanding the full scope of quantum computational advantage.

11.9 The Phase Kickback: A Deeper Look

Phase kickback is one of the most important techniques in quantum computing. It appears in Deutsch-Jozsa, Bernstein-Vazirani, Grover's algorithm, Shor's algorithm, and quantum phase estimation. Here we formalize it and explore its generalizations.

11.9.1 The Basic Phase Kickback

Consider an oracle $U_f$ acting on $|x\rangle|y\rangle$:

$$U_f|x\rangle|y\rangle = |x\rangle|y \oplus f(x)\rangle$$

If we set the target qubit to $|-\rangle = \frac{|0\rangle - |1\rangle}{\sqrt{2}}$:

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

When $f(x) = 0$: $\frac{|x\rangle|0\rangle - |x\rangle|1\rangle}{\sqrt{2}} = |x\rangle|-\rangle$

When $f(x) = 1$: $\frac{|x\rangle|1\rangle - |x\rangle|0\rangle}{\sqrt{2}} = -|x\rangle|-\rangle$

In both cases: $U_f|x\rangle|-\rangle = (-1)^{f(x)}|x\rangle|-\rangle$

The target qubit remains unchanged, but the phase of the control qubit acquires a factor of $(-1)^{f(x)}$. The function value $f(x)$ has been "kicked back" into the phase of the control register.

11.9.2 Generalized Phase Kickback

The phase kickback generalizes beyond the single-qubit case. If the target register is prepared in the state $|u\rangle$ where $U_f|x\rangle|u\rangle = e^{i\theta_x}|x\rangle|u\rangle$ (i.e., $|u\rangle$ is an eigenstate of the oracle restricted to input $x$), then the phase $e^{i\theta_x}$ kicks back to the input register.

More generally, consider an $n$-qubit input register and an $m$-qubit output register. If the output register is prepared in the state $\frac{1}{\sqrt{2^m}} \sum_{y} (-1)^{y \cdot z} |y\rangle$ for some fixed $z \in \{0,1\}^m$ (a Hadamard-Fourier state), then:

$$U_f|x\rangle \left(\frac{1}{\sqrt{2^m}} \sum_{y} (-1)^{y \cdot z} |y\rangle\right) = (-1)^{f(x) \cdot z} |x\rangle \left(\frac{1}{\sqrt{2^m}} \sum_{y} (-1)^{y \cdot z} |y\rangle\right)$$

This is because $U_f|x\rangle|y\rangle = |x\rangle|y \oplus f(x)\rangle$, and:

$$\sum_y (-1)^{y \cdot z} |y \oplus f(x)\rangle = \sum_y (-1)^{(y \oplus f(x)) \cdot z} |y\rangle = (-1)^{f(x) \cdot z} \sum_y (-1)^{y \cdot z} |y\rangle$$

where we used the substitution $y' = y \oplus f(x)$ and the fact that $(-1)^{y' \cdot z} = (-1)^{(y \oplus f(x)) \cdot z}$.

Special case $m = 1, z = 1$: This gives the original phase kickback $(-1)^{f(x)}$.

Special case $m = 1, z = 0$: The output register is in $|+\rangle = \frac{|0\rangle + |1\rangle}{\sqrt{2}}$, and no phase is kicked back — the oracle simply copies $f(x)$ into the output without phase modification.

11.9.3 Phase Kickback and Eigenvalue Estimation

The phase kickback is a special case of a more general phenomenon: eigenvalue kickback. If $U$ is a unitary with eigenvector $|u\rangle$ and eigenvalue $e^{2\pi i \phi}$, then:

$$U|u\rangle = e^{2\pi i \phi}|u\rangle$$

In the controlled-$U$ circuit:

$$CU|+\rangle|u\rangle = \frac{1}{\sqrt{2}}(|0\rangle U|u\rangle + |1\rangle|u\rangle) = \frac{1}{\sqrt{2}}(|0\rangle + e^{2\pi i \phi}|1\rangle)|u\rangle$$

The eigenvalue $e^{2\pi i \phi}$ has been "kicked back" into the phase of the control qubit. This is the basis of quantum phase estimation (Chapter 16), which estimates $\phi$ by applying $CU$ multiple times with different control qubits and then using the inverse QFT to convert the accumulated phases into a computational basis measurement.

Try It Yourself: Consider a 2-qubit oracle $U_f$ with $f: \{0,1\}^2 \to \{0,1\}$. If $f(x) = x_1 \cdot x_2$ (AND of the two bits), compute the state after phase kickback. How many distinct phase patterns are there? Can you determine $f$ from the phase pattern alone?

11.10 Superposition, Entanglement, and Quantum Parallelism

It is worth carefully distinguishing three related but distinct quantum phenomena that are often conflated:

Superposition is the ability of a quantum system to be in a linear combination of basis states: $|\psi\rangle = \alpha|0\rangle + \beta|1\rangle$. This is a property of individual qubits (or quantum systems) and is necessary but not sufficient for quantum speedup.

Entanglement is the property of a multi-qubit state that cannot be written as a tensor product of individual qubit states: $|\psi\rangle \neq |\phi_1\rangle \otimes |\phi_2\rangle \otimes \cdots \otimes |\phi_n\rangle$. Entanglement is necessary for exponential speedup in most known algorithms (Jozsa and Linden, 2003 proved that pure-state quantum algorithms achieving exponential speedup must use entanglement), but entanglement alone is not sufficient.

Quantum parallelism is the specific mechanism by which a quantum computer evaluates a function on a superposition of inputs. It requires superposition (to encode multiple inputs) and produces entanglement (between input and output registers), but the speedup comes from the interference that follows.

The relationship can be summarized as:

$$\text{Quantum speedup} = \text{Superposition} + \text{Entanglement} + \text{Interference}$$

Remove any one of these, and you lose the speedup. Superposition without interference gives you random guessing (the measurement problem). Entanglement without superposition is trivial. Interference without entanglement gives at most a constant factor improvement (as in the single-qubit Deutsch algorithm).

11.10.1 Why Classical Randomness Doesn't Suffice

A natural question: can we achieve similar speedups using classical randomized algorithms? The answer is no, for a fundamental reason: classical probabilities are non-negative and add linearly, while quantum amplitudes can be negative (or complex) and add with interference.

Consider a classical randomized algorithm that queries $f$ on a random input $x$. The probability of learning a global property of $f$ (like "is $f$ constant or balanced?") from one random query is at most $1/2$ — because one query reveals $f(x)$ for one value of $x$, and there are many functions consistent with that one evaluation.

In quantum computing, amplitudes for different outcomes can cancel. The Hadamard transform doesn't just combine probabilities — it combines amplitudes with signs, enabling destructive interference that eliminates wrong answers. This is why quantum algorithms can extract global information that classical algorithms cannot.

Worked Example: Classical vs. Quantum for Deutsch's Problem

Classical: Query $f(0)$ and $f(1)$ separately. Need 2 queries.

Quantum: Query $f$ on a superposition. The oracle produces $(-1)^{f(0)}|0\rangle + (-1)^{f(1)}|1\rangle$ (after phase kickback). The Hadamard gate then interferes these two terms. If $f(0) = f(1)$, they constructively interfere at $|0\rangle$; if $f(0) \neq f(1)$, they destructively interfere at $|0\rangle$ and constructively interfere at $|1\rangle$. The key: the interference pattern depends on the relationship between $f(0)$ and $f(1)$, not on their individual values.

11.11 Qiskit Demonstration: Parallelism and Interference

The following code demonstrates the core principle: we create a superposition, apply a phase oracle that marks certain states, then use interference (Hadamard gates) to reveal the pattern.

from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
from qiskit_aer import AerSimulator
import numpy as np

def demonstrate_interference(n_qubits=3, marked_states=None):
    """
    Demonstrates quantum parallelism and interference.
    Creates superposition over 2^n states, applies a phase oracle
    marking specific states, then uses Hadamard transform to
    produce interference that reveals information about the marking.
    """
    if marked_states is None:
        marked_states = [0, 3, 5]

    qr = QuantumRegister(n_qubits, 'q')
    cr = ClassicalRegister(n_qubits, 'c')
    qc = QuantumCircuit(qr, cr)

    # Stage 1: Create uniform superposition
    for i in range(n_qubits):
        qc.h(i)

    # Stage 2: Phase oracle — flip sign of marked states
    for state in marked_states:
        binary = format(state, f'0{n_qubits}b')
        for i, bit in enumerate(binary):
            if bit == '0':
                qc.x(i)
        qc.h(n_qubits - 1)
        qc.mcx(list(range(n_qubits - 1)), n_qubits - 1)
        qc.h(n_qubits - 1)
        for i, bit in enumerate(binary):
            if bit == '0':
                qc.x(i)

    # Stage 3: Interference — Hadamard transform
    for i in range(n_qubits):
        qc.h(i)

    # Stage 4: Measure
    qc.measure(range(n_qubits), range(n_qubits))

    return qc

# Run the demonstration
qc = demonstrate_interference(3, marked_states=[0, 3, 5])
simulator = AerSimulator()
result = simulator.run(qc, shots=8192).result()
counts = result.get_counts()

print("Measurement results after interference:")
for state, count in sorted(counts.items(), key=lambda x: -x[1]):
    print(f"  |{state}⟩: {count:4d} shots ({100*count/8192:.1f}%)")

11.11.1 Qiskit: Comparing Constant vs. Balanced Oracles

from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator
from qiskit.quantum_info import Statevector
import numpy as np

def compare_oracle_interference(n_qubits=3):
    """
    Compare the interference patterns produced by constant vs. balanced oracles
    on n qubits, showing how the Hadamard transform distinguishes them.
    """
    N = 2**n_qubits

    for oracle_type in ['constant', 'balanced']:
        print(f"\n=== {oracle_type.upper()} ORACLE ===")

        qc = QuantumCircuit(n_qubits)
        qc.h(range(n_qubits))

        if oracle_type == 'constant':
            pass  # Phase of all states is +1
        elif oracle_type == 'balanced':
            # Mark first half of states with -1 phase
            # f(x) = 1 if x < N/2, else 0
            for state in range(N // 2):
                binary = format(state, f'0{n_qubits}b')
                for i, bit in enumerate(binary):
                    if bit == '0':
                        qc.x(i)
                qc.h(n_qubits - 1)
                qc.mcx(list(range(n_qubits - 1)), n_qubits - 1)
                qc.h(n_qubits - 1)
                for i, bit in enumerate(binary):
                    if bit == '0':
                        qc.x(i)

        state_after_oracle = Statevector(qc)
        print(f"  After oracle, amplitude of |000⟩: {state_after_oracle[0]:.4f}")

        qc.h(range(n_qubits))
        state_after_h = Statevector(qc)
        probs = np.abs(np.array(state_after_h)) ** 2

        print(f"  After Hadamard:")
        for i in range(N):
            if probs[i] > 0.001:
                binary = format(i, f'0{n_qubits}b')
                print(f"    |{binary}⟩: probability = {probs[i]:.4f}")

compare_oracle_interference(3)

Expected behavior: - For the constant oracle, all probability concentrates on $|000\rangle$. - For the balanced oracle, $|000\rangle$ has zero probability and probability is distributed among other states.

11.12 Worked Examples

Worked Example 1: Three-Qubit Hadamard Transform on a Computational Basis State

Compute $H^{\otimes 3}|110\rangle$ using the formula $H^{\otimes n}|x\rangle = \frac{1}{\sqrt{2^n}} \sum_y (-1)^{x \cdot y} |y\rangle$.

Here $x = 110$ and we compute $x \cdot y$ for all $y \in \{0,1\}^3$:

Wait, let me recompute. $x = 110$ means $x_1 = 1, x_2 = 1, x_3 = 0$.

• $x \cdot 000 = 1 \cdot 0 + 1 \cdot 0 + 0 \cdot 0 = 0$
• $x \cdot 001 = 1 \cdot 0 + 1 \cdot 0 + 0 \cdot 1 = 0$
• $x \cdot 010 = 1 \cdot 0 + 1 \cdot 1 + 0 \cdot 0 = 1$
• $x \cdot 011 = 1 \cdot 0 + 1 \cdot 1 + 0 \cdot 1 = 1$
• $x \cdot 100 = 1 \cdot 1 + 1 \cdot 0 + 0 \cdot 0 = 1$
• $x \cdot 101 = 1 \cdot 1 + 1 \cdot 0 + 0 \cdot 1 = 1$
• $x \cdot 110 = 1 \cdot 1 + 1 \cdot 1 + 0 \cdot 0 = 0$
• $x \cdot 111 = 1 \cdot 1 + 1 \cdot 1 + 0 \cdot 1 = 0$

Therefore:

$$H^{\otimes 3}|110\rangle = \frac{1}{\sqrt{8}}(|000\rangle + |001\rangle - |010\rangle - |011\rangle - |100\rangle - |101\rangle + |110\rangle + |111\rangle)$$

Worked Example 2: Verifying $H^{\otimes n} H^{\otimes n} = I$

By the formula:

$$H^{\otimes n} H^{\otimes n}|x\rangle = H^{\otimes n} \left( \frac{1}{\sqrt{2^n}} \sum_y (-1)^{x \cdot y} |y\rangle \right) = \frac{1}{2^n} \sum_z \sum_y (-1)^{x \cdot y + y \cdot z} |z\rangle$$

The inner sum $\sum_y (-1)^{x \cdot y + y \cdot z} = \sum_y (-1)^{y \cdot (x \oplus z)}$. By the orthogonality relation:

$$\sum_{y \in \{0,1\}^n} (-1)^{y \cdot z} = \begin{cases} 2^n & \text{if } z = 0^n \\ 0 & \text{otherwise} \end{cases}$$

Therefore $H^{\otimes n} H^{\otimes n}|x\rangle = |x\rangle$, confirming $H^{\otimes 2n} = I$.

Worked Example 3: Interference Pattern from a Phase Oracle on 2 Qubits

Consider a 2-qubit system. We apply $H^{\otimes 2}$ to $|00\rangle$, then a phase oracle that flips the sign of $|01\rangle$, then $H^{\otimes 2}$ again.

Step 1: $H^{\otimes 2}|00\rangle = \frac{1}{2}(|00\rangle + |01\rangle + |10\rangle + |11\rangle)$

Step 2: After phase oracle (flip sign of $|01\rangle$):

$$|\psi\rangle = \frac{1}{2}(|00\rangle - |01\rangle + |10\rangle + |11\rangle)$$

Step 3: Apply $H^{\otimes 2}$:

$$H^{\otimes 2}|\psi\rangle = \frac{1}{4}\sum_y \sum_x (-1)^{x \cdot y} \cdot \alpha_x |y\rangle$$

where $\alpha_{00} = 1, \alpha_{01} = -1, \alpha_{10} = 1, \alpha_{11} = 1$.

Computing each $\beta_y$:

• $\beta_{00} = \frac{1}{4}(1 \cdot 1 + (-1) \cdot 1 + 1 \cdot 1 + 1 \cdot 1) = \frac{1}{4}(1 - 1 + 1 + 1) = \frac{2}{4} = \frac{1}{2}$
• $\beta_{01} = \frac{1}{4}(1 \cdot 1 + (-1) \cdot (-1) + 1 \cdot 1 + 1 \cdot (-1)) = \frac{1}{4}(1 + 1 + 1 - 1) = \frac{1}{2}$
• $\beta_{10} = \frac{1}{4}(1 \cdot 1 + (-1) \cdot 1 + 1 \cdot (-1) + 1 \cdot (-1)) = \frac{1}{4}(1 - 1 - 1 - 1) = -\frac{1}{2}$
• $\beta_{11} = \frac{1}{4}(1 \cdot 1 + (-1) \cdot (-1) + 1 \cdot (-1) + 1 \cdot 1) = \frac{1}{4}(1 + 1 - 1 + 1) = \frac{1}{2}$

Result: $\frac{1}{2}|00\rangle + \frac{1}{2}|01\rangle - \frac{1}{2}|10\rangle + \frac{1}{2}|11\rangle$

Measurement probabilities: $P(|00\rangle) = P(|01\rangle) = P(|11\rangle) = 1/4$, $P(|10\rangle) = 1/4$.

Wait — all outcomes have equal probability 1/4. But the phases reveal information about the oracle. This is because the Hadamard transform of a single-phase-flip oracle distributes the information across all amplitudes. This illustrates a key point: for general phase patterns, a single application of $H^{\otimes n}$ may not concentrate probability on a single outcome. More sophisticated interference patterns (like in Grover's algorithm) are needed.

11.13 The No-Cloning Theorem and Its Implications for Parallelism

The no-cloning theorem is a fundamental result that limits what quantum parallelism can achieve. It states that there is no unitary operation that can copy an unknown quantum state. Formally, there is no unitary $U$ such that $U|\psi\rangle|0\rangle = |\psi\rangle|\psi\rangle$ for all $|\psi\rangle$.

Proof: Suppose such a $U$ exists. Then $U|0\rangle|0\rangle = |0\rangle|0\rangle$ and $U|1\rangle|0\rangle = |1\rangle|1\rangle$. By linearity:

$$U\left(\frac{|0\rangle + |1\rangle}{\sqrt{2}}\right)|0\rangle = \frac{1}{\sqrt{2}}(U|0\rangle|0\rangle + U|1\rangle|0\rangle) = \frac{|00\rangle + |11\rangle}{\sqrt{2}}$$

But if cloning worked:

$$\left(\frac{|0\rangle + |1\rangle}{\sqrt{2}}\right) \otimes \left(\frac{|0\rangle + |1\rangle}{\sqrt{2}}\right) = \frac{|00\rangle + |01\rangle + |10\rangle + |11\rangle}{2}$$

These are different states, contradicting linearity. Therefore, cloning is impossible.

Implications for quantum parallelism: The no-cloning theorem means we cannot make copies of the superposition $\sum_x |x\rangle|f(x)\rangle$ to extract more information. If we could clone this state, we could make $O(n)$ copies, measure each, and determine $f$ on exponentially many inputs. The no-cloning theorem prevents this, forcing us to use interference instead.

The no-cloning theorem and the measurement collapse postulate are closely related. Both theorems ensure that quantum parallelism provides exponential computation but not exponential readout. Without either theorem, we could extract exponentially more information from a quantum state than is classically possible, violating the Holevo bound.

Try It Yourself: Suppose a quantum cloning device existed. Design a protocol that would use cloning plus measurement to violate the query complexity lower bound for Deutsch's problem. (Hint: Clone the state $\frac{1}{\sqrt{2}}(|0\rangle|f(0)\rangle + |1\rangle|f(1)\rangle)$ and measure both copies.)

11.14 Entanglement as a Resource for Quantum Parallelism

Quantum parallelism creates entanglement between the input and output registers. The state $\frac{1}{\sqrt{2^n}} \sum_x |x\rangle|f(x)\rangle$ is entangled whenever $f$ is not constant — the input and output registers cannot be written as a tensor product of independent states.

Example: Entangled oracle output. For $f(x) = x$ (identity function on 1 qubit), the oracle output is:

$$\frac{1}{\sqrt{2}}(|0\rangle|0\rangle + |1\rangle|1\rangle)$$

This is a Bell state — maximally entangled. If we trace out the output qubit, the reduced density matrix of the input is $\frac{1}{2}(|0\rangle\langle 0| + |1\rangle\langle 1|) = \frac{I}{2}$, which is maximally mixed. The input qubit alone carries no information about $f$; the information is in the entanglement between the two qubits.

For a constant function $f(x) = 0$, the oracle output is:

$$\frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)|0\rangle$$

This is a product state — no entanglement. The input register is still in a superposition, but it is not entangled with the output.

The Jozsa-Linden theorem (2003): Any pure-state quantum algorithm that achieves an exponential speedup over classical algorithms must use entanglement across a number of qubits that grows with the input size. Specifically, if the entanglement is bounded by a constant, the algorithm can be efficiently simulated classically.

This provides a rigorous connection between entanglement and quantum advantage: without sufficient entanglement, no exponential speedup is possible.

Recurring Theme — Noise is the Enemy: Entanglement is fragile. Decoherence rapidly destroys entanglement, converting pure entangled states into mixed product states. This is why quantum error correction is essential for large-scale quantum algorithms — without it, the entanglement that powers quantum speedup degrades too quickly to be useful.

11.14.1 Quantifying Entanglement in the Oracle Output

The entanglement in the oracle output can be quantified using the von Neumann entropy of the reduced density matrix. For the state $\frac{1}{\sqrt{2^n}} \sum_x |x\rangle|f(x)\rangle$, the reduced density matrix of the input register is:

$$\rho_{\text{input}} = \text{Tr}_{\text{output}}\left(\frac{1}{2^n}\sum_{x,y} |x\rangle\langle y| \otimes |f(x)\rangle\langle f(y)|\right)$$

If $f$ is a constant function, this reduces to $\rho_{\text{input}} = \frac{1}{2^n}\sum_x |x\rangle\langle x|$, which has entropy $n$ bits — but this entropy comes from the superposition, not from entanglement. The state is a product state.

If $f$ is balanced (equal numbers of 0 and 1 outputs), the reduced density matrix is maximally mixed on a subspace, and the entanglement entropy depends on the specific function. For $f(x) = x$ (1 qubit), the entanglement entropy is 1 bit (the Bell state is maximally entangled).

11.15 Connections Between Chapters: The Unifying Framework

The concepts introduced in this chapter — superposition, phase kickback, interference, and the algorithmic template — form the foundation for all subsequent quantum algorithms. Here is how they connect:

Deutsch-Jozsa and Bernstein-Vazirani (Chapter 12): These algorithms are direct applications of the template: superposition → oracle (with phase kickback) → Hadamard transform → measurement. The Hadamard transform serves as both the superposition-creation step and the interference step. The key insight is that the Hadamard transform is the Fourier transform over $\mathbb{Z}_2^n$, and it converts phase patterns (which encode the oracle's function) into measurable computational basis information.

Grover's Algorithm (Chapter 13): Grover's algorithm replaces the Hadamard-based interference step with a more powerful interference pattern: repeated oracle + diffusion iterations. The diffusion operator $D = 2|s\rangle\langle s| - I$ is a reflection about the uniform superposition, and each Grover iteration rotates the state toward the target by angle $\theta$. The key concepts from this chapter — amplitude amplification, the role of interference, and the measurement bottleneck — are all present in Grover's algorithm.

Quantum Fourier Transform (Chapter 14): The QFT generalizes the Hadamard transform from $\mathbb{Z}_2^n$ to $\mathbb{Z}_{2^n}$. Instead of phases that are $\pm 1$ (roots of unity of order 2), the QFT uses phases $e^{2\pi i / 2^k}$ (roots of unity of order $2^n$). This enables the QFT to detect periodicity in the full range $0$ to $2^n - 1$, rather than just parity.

Shor's Algorithm (Chapter 15): Shor's algorithm combines quantum parallelism (modular exponentiation on a superposition), the QFT (to detect the period), and classical post-processing (continued fractions). The quantum speedup comes from the QFT's ability to extract the period from a single quantum measurement, which classical algorithms cannot do.

The recurring pattern: All quantum algorithms that achieve speedup follow the template: encode information into phases (quantum parallelism), use interference (Hadamard, QFT, or diffusion) to convert phase information into measurable amplitude information, and measure. The specific choice of interference transform determines the type of speedup.

11.16 Summary of Mathematical Tools

This chapter introduced several mathematical tools that will be used throughout the rest of the book: