 Solution

ID: past-exam-of-the-introduction-to-quantum-information-course-of-the-university-of-oxford/2015/1/a/solution

Apply one Hadamard gate to each of the

n

qubits, with all gates acting in parallel. This quantum circuit implements the tensor product

H^{\otimes n}

; it needs

n

single-qubit gates and one layer. For one qubit,

H ∣ x_{j} ⟩ = \frac{1}{2} \sum_{y_{j} = 0}^{1} (- 1)^{x_{j} y_{j}} ∣ y_{j} ⟩ .

Taking the tensor product of these expressions multiplies the probability amplitudes and adds their exponents, giving

H^{\otimes n} ∣ x ⟩ = 2^{- n /2} y \in {0, 1}^{n} \sum (- 1)^{x \cdot y} ∣ y ⟩ .

In particular, an initially zero quantum register becomes the uniform quantum superposition

H^{\otimes n} ∣ 0^{n} ⟩ = 2^{- n /2} x \sum ∣ x ⟩ .

This is useful at the start of a quantum algorithm because a subsequent quantum oracle acts on all these components coherently. Later quantum interference can reveal a global property of the function. Measuring immediately would merely produce a uniformly random binary string; the useful resource is the preserved quantum coherence, rather than the ability to read every function value in one run.

 New to topics? Read the docs here!