Lean, informalized

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

Exercise 6.15 - How far, in sum, a unit vector lies from the members of an orthonormal set

A lower bound on squared distances to an orthonormal set.

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

Let |ψ⟩|\psi\rangle be a normalized state vector, and let |x⟩|x\rangle be NN orthonormal vectors of the same state space, the label xx running over NN values. Each |x⟩|x\rangle lies at some distance from |ψ⟩|\psi\rangle. The exercise bounds the sum of the squares of these NN distances from below by a quantity that depends on NN alone, whatever the state |ψ⟩|\psi\rangle and whatever the orthonormal vectors.

Unit and Orthonormal Vectors

The vectors lie in an inner product space ℋ\mathcal{H}. The length of a vector |ϕ⟩|\phi\rangle of ℋ\mathcal{H} is its norm, ∥|ϕ⟩∥=⟨ϕ|ϕ⟩,\big\| |\phi\rangle \big\| = \sqrt{\langle \phi | \phi \rangle},(1) and the distance between two vectors is the norm of their difference. A unit vector |ψ⟩|\psi\rangle of ℋ\mathcal{H} is a vector of norm one.

A family of vectors |x⟩|x\rangle of ℋ\mathcal{H}, indexed by a finite set of NN labels, is orthonormal when ⟨x|y⟩=δxy\langle x | y \rangle = \delta_{xy}(2) for all labels xx and yy.

The Claim

Theorem 1. Let |x⟩|x\rangle, for xx in a finite set of NN labels, be an orthonormal family of vectors of an inner product space ℋ\mathcal{H}, and let |ψ⟩|\psi\rangle be a unit vector of ℋ\mathcal{H}. Then the squared distances from |ψ⟩|\psi\rangle to the |x⟩|x\rangle satisfy ∑x∥|ψ⟩−|x⟩∥2≥2N−2N.\sum_x \big\| |\psi\rangle - |x\rangle \big\|^2 \;\ge\; 2N - 2\sqrt{N}.(3)✦

What Is Checked

The claim is stated over an inner product space ℋ\mathcal{H} whose scalars are the real or the complex numbers, a unit vector |ψ⟩|\psi\rangle in it, and an orthonormal family |x⟩|x\rangle indexed by any finite set, with NN the number of its labels. The family need not span ℋ\mathcal{H}.

About these objects the library proves the inequality (3), for every unit vector and every finite orthonormal family of ℋ\mathcal{H}.