Skip to content

Lesson 9: Quantum Parallelism, Interference and the No-Cloning Theorem

9.1 Learning Outcomes

By the end of this hour a student will be able to:

  1. Construct the oracle unitary \(U_f\) for a classical Boolean function and explain why the extra register is needed.
  2. State what quantum parallelism does and, crucially, what it does not give you.
  3. Explain constructive and destructive interference of amplitudes and identify it in a circuit.
  4. Prove the no-cloning theorem and state the related no-deleting and no-broadcasting results.
  5. Describe the consequences of no-cloning for error correction, eavesdropping (BB84) and classical intuition.

9.2 Making Classical Functions Quantum

The reversibility problem

Consider \(f : \{0,1\}^n \to \{0,1\}^m\). Most such functions are not injective, so the map \(|x\rangle \mapsto |f(x)\rangle\) is not invertible and cannot be unitary. Example: \(f(x) = 0\) for all \(x\) would map every basis state onto one state — that collapses the space.

Solution: the standard oracle construction. Use two registers and record the answer with XOR:

\[ \boxed{\ U_f\,|x\rangle|y\rangle = |x\rangle\,|y \oplus f(x)\rangle\ } \]

where \(\oplus\) is bitwise XOR.

\(U_f\) is always unitary. It is a permutation of the computational basis, and it is its own inverse:

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

since \(a\oplus a = 0\). So \(U_f^2 = I\), i.e. \(U_f = U_f^{-1} = U_f^\dagger\). \(\blacksquare\)

Reading out \(f(x)\). Set \(y = 0\): \(U_f|x\rangle|0\rangle = |x\rangle|f(x)\rangle\).

Terminology. \(|x\rangle\) is the query/input register; \(|y\rangle\) is the ancilla/output register. In the query complexity model we count calls to \(U_f\), ignoring the cost of the internal gates — this is how all Unit II speed-ups are stated and proved.

Physical implementation. Any Boolean circuit made of AND, OR, NOT is converted into Toffoli and CNOT gates, with ancillas for intermediate results, which are then uncomputed (run the circuit backwards) to free them. Uncomputation is essential: leftover "garbage" ancillas remain entangled with the input and destroy the interference the algorithm depends on.

9.3 Quantum Parallelism

Prepare the input register in a uniform superposition and apply \(U_f\) once:

\[ |0\rangle^{\otimes n}|0\rangle \xrightarrow{H^{\otimes n}\otimes I} \frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1}|x\rangle|0\rangle \]
\[ \xrightarrow{\ U_f\ } \frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1}|x\rangle\,|f(x)\rangle \]

A single application of \(U_f\) has produced a state containing all \(2^n\) input–output pairs simultaneously. This is quantum parallelism.

The catch — and it is a big one

Measuring this state gives one random pair \((x, f(x))\) — exactly what one classical evaluation of \(f\) at a random point would give. Quantum parallelism by itself provides zero advantage.

The central insight of the whole course. The exponentially many values of \(f\) are present in the amplitudes but are not accessible. A useful algorithm must apply further unitaries that make the amplitudes of undesired answers cancel and those of the desired answer add. That mechanism is interference, and it — not parallelism — is where the speed-up comes from.

Formally, this is why every algorithm in Unit II has the shape:

\[ \text{superpose} \ \to\ \text{query } U_f \ \to\ \textbf{interfere} \ \to\ \text{measure} \]

9.4 Interference

Because amplitudes are complex numbers, they can cancel. Probabilities never can.

Classical: \(\Pr[\text{outcome}] = \sum_{\text{paths}} \Pr[\text{path}] \ge 0\) — contributions only accumulate.

Quantum: \(\Pr[\text{outcome}] = \left|\sum_{\text{paths}} A_{\text{path}}\right|^2\) — amplitudes add first, and can cancel.

The minimal example

Consider \(H\) applied twice to \(|0\rangle\).

\[ |0\rangle \xrightarrow{H} \tfrac{1}{\sqrt2}|0\rangle + \tfrac{1}{\sqrt2}|1\rangle \xrightarrow{H} \tfrac{1}{\sqrt2}\left(\tfrac{|0\rangle+|1\rangle}{\sqrt2}\right) + \tfrac{1}{\sqrt2}\left(\tfrac{|0\rangle-|1\rangle}{\sqrt2}\right) \]

Collect terms:

\[ |0\rangle: \ \tfrac12 + \tfrac12 = 1 \qquad \text{(constructive)} \]
\[ |1\rangle: \ \tfrac12 - \tfrac12 = 0 \qquad \text{(destructive)} \]
\[ H^2|0\rangle = |0\rangle . \]

The two paths to \(|1\rangle\) cancel exactly. A classical random walk taking two fair coin flips would land on 1 with probability \(\frac12\); the quantum version lands on 0 with certainty.

Amplitude bookkeeping

For a circuit \(U = U_T\cdots U_2U_1\), the amplitude to go from \(|i\rangle\) to \(|j\rangle\) is a sum over all computational paths:

\[ \langle j|U|i\rangle = \sum_{k_1,\dots,k_{T-1}} \langle j|U_T|k_{T-1}\rangle\cdots\langle k_1|U_1|i\rangle . \]

Designing a quantum algorithm = arranging the phases along these paths so that everything except the answer cancels. This is exactly what the Grover diffusion operator (L21) and the QFT (L18) do.

9.5 The No-Cloning Theorem

Theorem (Wootters–Zurek, Dieks, 1982). There is no unitary \(U\) such that for every state \(|\psi\rangle\),

\[ U\big(|\psi\rangle \otimes |s\rangle\big) = |\psi\rangle\otimes|\psi\rangle \]

for some fixed blank state \(|s\rangle\).

Proof. Suppose such a \(U\) existed. Take two arbitrary states \(|\psi\rangle\) and \(|\phi\rangle\):

\[ U|\psi\rangle|s\rangle = |\psi\rangle|\psi\rangle, \qquad U|\phi\rangle|s\rangle = |\phi\rangle|\phi\rangle . \]

Take the inner product of the two left-hand sides. Since \(U\) is unitary it preserves inner products:

\[ \big(\langle\psi|\langle s|\big)U^\dagger U\big(|\phi\rangle|s\rangle\big) = \langle\psi|\phi\rangle\,\langle s|s\rangle = \langle\psi|\phi\rangle . \]

Now the right-hand sides:

\[ \big(\langle\psi|\langle\psi|\big)\big(|\phi\rangle|\phi\rangle\big) = \langle\psi|\phi\rangle^2 . \]

Equating, and writing \(z = \langle\psi|\phi\rangle\):

\[ z = z^2 \ \Longrightarrow\ z(z-1) = 0 \ \Longrightarrow\ z = 0 \text{ or } z = 1 . \]

So cloning is possible only if the two states are orthogonal (\(z=0\)) or identical (\(z=1\)). A universal cloner would have to work for all pairs, including those with \(0 < |z| < 1\). Contradiction. \(\blacksquare\)

What no-cloning does and does not forbid

Allowed Forbidden
Copying known states (just re-prepare them) Copying an unknown state
Copying states from a known orthonormal set Copying non-orthogonal states
Copying classical bits (they are orthogonal) Perfect universal cloning
Approximate cloning (best fidelity \(5/6\) for qubits) Perfect cloning
Moving a state (teleportation) Duplicating a state

Note that CNOT does copy basis states: \(\mathrm{CNOT}|x\rangle|0\rangle = |x\rangle|x\rangle\) for \(x\in\{0,1\}\). But applied to a superposition,

\[ \mathrm{CNOT}\big(\alpha|0\rangle+\beta|1\rangle\big)|0\rangle = \alpha|00\rangle + \beta|11\rangle \ \ne\ \big(\alpha|0\rangle+\beta|1\rangle\big)^{\otimes2} . \]

It produces entanglement, not a copy. This is the concrete way no-cloning shows up in practice.

Companion theorems

  • No-deleting theorem (Pati–Braunstein, 2000): given two copies of an unknown state, you cannot unitarily delete one.
  • No-broadcasting theorem: the mixed-state generalisation — a set of non-commuting density matrices cannot be broadcast.
  • No-hiding theorem: information lost from a system must be present somewhere in the environment — the basis of black-hole information arguments.

9.6 Consequences of No-Cloning

(a) Quantum error correction must be indirect. The classical repetition code copies a bit three times. That is illegal here. Instead, QEC encodes one logical qubit into an entangled state of several physical qubits and measures stabilisers — operators that reveal the error without revealing (and hence collapsing) the encoded state. Developed in L10.

(b) Quantum cryptography becomes possible. In BB84, Alice sends qubits in randomly chosen bases. Eve cannot copy them to measure later; any measurement she makes disturbs the state and introduces a detectable error rate (25 % if she measures every qubit in a random basis). Security rests on a law of physics, not on computational hardness.

(c) No superluminal signalling. If cloning were possible, Alice could make many copies of her half of a Bell pair and infer Bob's measurement basis instantly. No-cloning closes that loophole.

(d) Amplification is impossible. A weak quantum signal cannot be amplified without noise, which is why long-distance quantum communication needs quantum repeaters rather than amplifiers.

9.7 Solved Problems

Problem 1 — Building an oracle

Let \(f:\{0,1\}^2 \to \{0,1\}\) with \(f(x_1x_2) = x_1 \wedge x_2\). Write the action of \(U_f\) on all basis states, give a circuit, and compute \(U_f\) applied to a uniform superposition.

Solution.

Action \(U_f|x_1x_2\rangle|y\rangle = |x_1x_2\rangle|y\oplus (x_1\wedge x_2)\rangle\):

Input \(\lvert x_1x_2 y\rangle\) \(f(x)\) Output
\(\lvert 000\rangle\) 0 \(\lvert 000\rangle\)
\(\lvert 010\rangle\) 0 \(\lvert 010\rangle\)
\(\lvert 100\rangle\) 0 \(\lvert 100\rangle\)
\(\lvert 110\rangle\) 1 \(\lvert 111\rangle\)
\(\lvert 111\rangle\) 1 \(\lvert 110\rangle\)

Circuit: a single Toffoli gate with controls \(x_1,x_2\) and target \(y\). (This is why Toffoli is the universal classical gate — AND is realised directly.)

Applying to the uniform superposition with \(y = 0\):

\[ U_f\left(\frac12\sum_{x\in\{0,1\}^2}|x\rangle\right)|0\rangle = \frac12\big(|00\rangle|0\rangle + |01\rangle|0\rangle + |10\rangle|0\rangle + |11\rangle|1\rangle\big) . \]

All four input–output pairs, produced by one call to \(U_f\). But measuring returns a single random pair — parallelism without interference is worthless.

Problem 2 — Interference in a two-path circuit

A qubit starts in \(|0\rangle\). Apply \(H\), then \(P(\phi) = \mathrm{diag}(1, e^{i\phi})\), then \(H\). Find \(\Pr[0]\) as a function of \(\phi\), and evaluate at \(\phi = 0, \pi/2, \pi\).

Solution.

\[ |0\rangle \xrightarrow{H} \tfrac{1}{\sqrt2}(|0\rangle + |1\rangle) \xrightarrow{P(\phi)} \tfrac{1}{\sqrt2}(|0\rangle + e^{i\phi}|1\rangle) \]
\[ \xrightarrow{H} \tfrac{1}{2}\big[(|0\rangle+|1\rangle) + e^{i\phi}(|0\rangle - |1\rangle)\big] \]
\[ = \frac{1+e^{i\phi}}{2}|0\rangle + \frac{1-e^{i\phi}}{2}|1\rangle \]
\[ \Pr[0] = \left|\frac{1+e^{i\phi}}{2}\right|^2 = \frac{(1+\cos\phi)^2 + \sin^2\phi}{4} = \frac{2+2\cos\phi}{4} = \cos^2\frac{\phi}{2} \]
\(\phi\) \(\Pr[0]\) Interference
\(0\) \(1\) Fully constructive on \(\lvert 0\rangle\)
\(\pi/2\) \(0.5\) Partial
\(\pi\) \(0\) Fully destructive on \(\lvert 0\rangle\)

This is the quantum interferometer, and \(\Pr[0] = \cos^2(\phi/2)\) is the fringe pattern. A phase written in the middle of the circuit becomes a measurable probability at the end. Every algorithm in Unit II is an instance of this template: the oracle writes a phase, and the final Hadamards read it out.

Problem 3 — Applying the no-cloning proof

Show explicitly that no unitary can clone both \(|0\rangle\) and \(|+\rangle\).

Solution. Assume \(U|0\rangle|0\rangle = |0\rangle|0\rangle\) and \(U|+\rangle|0\rangle = |+\rangle|+\rangle\).

Take inner products of the inputs:

\[ \big(\langle 0|\langle 0|\big)\big(|+\rangle|0\rangle\big) = \langle 0|+\rangle\langle0|0\rangle = \frac{1}{\sqrt2}\cdot 1 = \frac{1}{\sqrt2} \approx 0.7071 \]

Take inner products of the outputs:

\[ \big(\langle0|\langle0|\big)\big(|+\rangle|+\rangle\big) = \langle0|+\rangle^2 = \left(\frac{1}{\sqrt2}\right)^2 = \frac12 = 0.5 \]

Unitaries preserve inner products, so we would need \(0.7071 = 0.5\). Contradiction.

Alternative constructive argument. Suppose \(U\) clones the basis, i.e. \(U|x\rangle|0\rangle = |x\rangle|x\rangle\) for \(x \in \{0,1\}\). Then by linearity,

\[ U|+\rangle|0\rangle = \tfrac{1}{\sqrt2}\big(U|0\rangle|0\rangle + U|1\rangle|0\rangle\big) = \tfrac{1}{\sqrt2}\big(|00\rangle + |11\rangle\big) = |\Phi^+\rangle . \]

But a true clone would be

\[ |+\rangle|+\rangle = \tfrac12\big(|00\rangle+|01\rangle+|10\rangle+|11\rangle\big) . \]

Overlap: \(\langle\Phi^+|{+}{+}\rangle = \frac{1}{\sqrt2}\cdot\frac12(1 + 1) = \frac{1}{\sqrt2}\), not 1. Linearity itself forbids cloning — you get entanglement instead.

Problem 4 — Eavesdropping in BB84

In BB84, Alice sends a qubit in a basis chosen at random from \(\{Z, X\}\). Eve intercepts, measures in a random basis, and re-sends the collapsed state. Bob measures in Alice's basis. What is the probability that Bob's bit differs from Alice's?

Solution. Condition on Eve's basis choice.

Case 1: Eve picks the same basis as Alice (probability \(\frac12\)). Her measurement returns Alice's bit and leaves the state unchanged. Bob then gets the correct bit with probability 1. Error probability = 0.

Case 2: Eve picks the wrong basis (probability \(\frac12\)). Say Alice sent \(|0\rangle\) and Eve measures in \(X\). She gets \(|+\rangle\) or \(|-\rangle\) with probability ½ each and re-sends it. Bob measures in \(Z\):

\[ \Pr[\text{Bob gets }1 \mid \text{state } |\pm\rangle] = \tfrac12 . \]

Error probability = ½.

Total:

\[ \Pr[\text{error}] = \tfrac12\cdot 0 + \tfrac12\cdot\tfrac12 = \boxed{\tfrac14 = 25\%} \]

Significance. Alice and Bob publicly compare a random sample of their bits. A 25 % mismatch rate where 0 % is expected exposes Eve immediately. Eve cannot avoid this by cloning the qubit and measuring later — no-cloning forbids it. The security is information-theoretic, not computational: a quantum computer does not help Eve.

Problem 5 — Why parallelism alone fails

A student proposes: "Prepare \(\frac{1}{\sqrt{2^n}}\sum_x |x\rangle|f(x)\rangle\), then measure the second register; if I see \(f(x)=1\) the first register collapses to the superposition of all solutions, so I have solved SAT." Identify the flaw and quantify it.

Solution. The mechanics are correct. Measuring the second register and obtaining 1 leaves the first register in

\[ \frac{1}{\sqrt{M}}\sum_{x : f(x)=1}|x\rangle , \]

where \(M\) is the number of solutions. Two things then go wrong.

(1) The probability of seeing 1 is tiny.

\[ \Pr[f(x)=1] = \frac{M}{2^n} . \]

For a hard SAT instance with, say, a unique solution and \(n = 100\):

\[ \Pr = \frac{1}{2^{100}} \approx 7.9\times10^{-31} . \]

Expected number of repetitions before success: \(2^{100}\) — exactly the classical brute-force cost. No speed-up whatsoever.

(2) Even after a successful projection, measuring the first register returns one uniformly random solution — which is all you wanted, but you paid \(2^n\) attempts to get there.

What actually works. Grover's algorithm (L21–L22) does not measure the ancilla. It uses the oracle to write a phase on solutions and then applies the diffusion operator to grow their amplitudes gradually, reaching near-certainty after only

\[ \frac{\pi}{4}\sqrt{\frac{2^n}{M}} \]

iterations — a quadratic improvement, and it comes entirely from interference.

Conclusion. Superposition is free; interference is the algorithm.

9.8 Practice Problems

  1. Construct \(U_f\) for \(f(x) = x \oplus 1\) (NOT) on one qubit. Which gate is it? [Ans: CNOT then \(X\) on the target]
  2. Show \(U_f^\dagger = U_f\) for any Boolean \(f\).
  3. In the interferometer of Problem 2, what \(\phi\) gives \(\Pr[1] = 0.25\)? [Ans: \(\phi = \pi/3\)]
  4. Prove that cloning would allow superluminal signalling using a shared Bell pair.
  5. If Eve measures only 50 % of the qubits in BB84, what error rate do Alice and Bob observe? [Ans: 12.5 %]
  6. Explain why \(\mathrm{CNOT}|\psi\rangle|0\rangle\) is not a clone for a general \(|\psi\rangle\), using concurrence.
  7. Why must ancilla qubits be uncomputed before the final interference step?

9.9 Summary

  • Classical \(f\) becomes the unitary oracle \(U_f|x\rangle|y\rangle = |x\rangle|y\oplus f(x)\rangle\); it is self-inverse and is built from Toffoli/CNOT gates.
  • Quantum parallelism evaluates \(f\) on all \(2^n\) inputs with one query — but measurement returns only one random pair, so it gives no advantage by itself.
  • Interference — amplitudes adding and cancelling — is the actual source of quantum speed-up. Template: superpose → query → interfere → measure.
  • No-cloning: unitarity and linearity forbid copying an unknown state; only orthogonal or identical states can be cloned.
  • Consequences: error correction must use stabiliser measurements rather than copies; BB84 gains physics-based security; no superluminal signalling; no noiseless amplification.

Next lesson: L10 — Quantum teleportation, superdense coding and error correction.

Practise now: unit1-qubit-lab.html → Interference Lab: sweep \(\phi\) in the Mach–Zehnder circuit of Problem 2 and watch the fringe pattern \(\cos^2(\phi/2)\) appear.