Lean, informalized

Nielsen & Chuang · Chapter 6, Quantum search algorithms · p. 251

Exercise 6.2 - The reflection about the uniform superposition sends each amplitude to twice the mean minus itself

Each amplitude is reflected through the mean.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Exercise

Take a system whose state space has NN orthonormal basis states |0⟩,…,|N−1⟩|0\rangle, \dots, |N-1\rangle, and let |ψ⟩|\psi\rangle be the uniform superposition of all of them, as in Grover’s search algorithm. The exercise is to show that the operator 2|ψ⟩⟨ψ|−I2|\psi\rangle\langle \psi| - I acts on a state ∑kαk|k⟩\sum_k \alpha_k |k\rangle by sending each amplitude αk\alpha_k to −αk+2⟨α⟩-\alpha_k + 2\langle\alpha\rangle, where ⟨α⟩\langle\alpha\rangle is the mean of the amplitudes. Since −αk+2⟨α⟩=⟨α⟩−(αk−⟨α⟩)-\alpha_k + 2\langle\alpha\rangle = \langle\alpha\rangle - (\alpha_k - \langle\alpha\rangle), each amplitude is reflected through the mean, and the operator is called the inversion about the mean.

Amplitudes and Reflections

The state space is ℂN\mathbb{C}^N with its computational basis |0⟩,…,|N−1⟩|0\rangle, \dots, |N-1\rangle, so that a vector is given by its NN complex amplitudes and an operator by an N×NN \times N complex matrix.

The mean of the amplitudes of a vector |α⟩=∑kαk|k⟩|\alpha\rangle = \sum_k \alpha_k |k\rangle of ℂN\mathbb{C}^N is the complex number ⟨α⟩=1N∑k=0N−1αk.\langle\alpha\rangle = \frac{1}{N} \sum_{k=0}^{N-1} \alpha_k .(1)✦

The uniform superposition |ψ⟩|\psi\rangle of ℂN\mathbb{C}^N is the vector whose NN amplitudes all equal 1/N1/\sqrt{N}: |ψ⟩=1N∑k=0N−1|k⟩.|\psi\rangle = \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} |k\rangle .(2)✦

The reflection about a vector |u⟩=∑kuk|k⟩|u\rangle = \sum_k u_k |k\rangle of ℂN\mathbb{C}^N is the N×NN \times N complex matrix, with II the identity and δjk\delta_{jk} the Kronecker delta, 2|u⟩⟨u|−I,(2|u⟩⟨u|−I)jk=2ujuk*−δjk.2|u\rangle\langle u| - I, \qquad \bigl(2|u\rangle\langle u| - I\bigr)_{jk} = 2 u_j u_k^* - \delta_{jk} .(3)✦

The inversion about the mean in dimension NN is the reflection (3) about the uniform superposition (2): 2|ψ⟩⟨ψ|−I.2|\psi\rangle\langle\psi| - I .(4)✦

The Claim

Theorem 1. Let |α⟩=∑kαk|k⟩|\alpha\rangle = \sum_k \alpha_k |k\rangle be a vector of ℂN\mathbb{C}^N and ⟨α⟩\langle\alpha\rangle the mean of its amplitudes. Then for each kk, the amplitude of |k⟩|k\rangle in the image of |α⟩|\alpha\rangle under the inversion about the mean is ⟨k|(2|ψ⟩⟨ψ|−I)|α⟩=−αk+2⟨α⟩.\langle k| \bigl(2|\psi\rangle\langle\psi| - I\bigr) |\alpha\rangle = -\alpha_k + 2\langle\alpha\rangle .(5)✦

Multiplied by |k⟩|k\rangle and summed over kk, (5) gives the exercise’s identity, for every vector of ℂN\mathbb{C}^N and not only for normalized states.

What Is Checked

The claim is stated over four constructions: the uniform superposition (2), the reflection about a vector (3), the inversion about the mean (4), and the mean of the amplitudes (1).

What the library proves about them is the identity (5), in every dimension NN and for each amplitude kk.