Prove by induction on that for every , H^ n |x = 2^ -n/2 _ y 0,1 ^n (-1)^ x y |y

PHYSICS · Multi-part · Fermi University Physics · Quantum Information & Technology · The quantum circuit model and quantum algorithms · The quantum circuit model and quantum algorithms

Quantum Information and Technology, Ch Oracles, quantum parallelism and the first algorithms

Problem

Prove by induction on nn that for every x∈{0,1}nx\in\{0,1\}^n, H⊗n∣x⟩=2−n/2∑y∈{0,1}n(−1)x⋅y∣y⟩,H^{\otimes n}|x\rangle = 2^{-n/2}\sum_{y\in\{0,1\}^n}(-1)^{x\cdot y}|y\rangle, taking as the base case the single-qubit identity H∣x1⟩=2−1/2∑y1(−1)x1y1∣y1⟩H|x_1\rangle = 2^{-1/2}\sum_{y_1}(-1)^{x_1y_1}|y_1\rangle. ((a)) Give the inductive step, showing explicitly how x⋅yx\cdot y for n+1n+1 bits splits into the nn-bit dot product plus one extra term. ((b)) Use the proved identity to compute the amplitude of ∣0101⟩|0101\rangle in H⊗4∣1011⟩H^{\otimes4}|1011\rangle.

Browse the problem library