Lean, informalized

Nielsen & Chuang · Chapter 7, Quantum computers: physical realization · p. 346

Problem 7.1 - A linear map that runs through every nonzero string of nn bits, built from quadratically many controlled-NOT gates

Cycling the nonzero bit strings with quadratically many gates.

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

A register of n≥2n \ge 2 qubits has the computational basis states |x⟩|x\rangle, one for each string x=(x1,…,xn)x = (x_1, \dots, x_n) of zeros and ones. The exercise asks for a permutation of these states that leaves |0⋯0⟩|0\cdots0\rangle in place and carries the other 2n−12^n - 1 around a single cycle, so that applying it often enough takes any nonzero string to any other. The permutation is to be linear in the bits, with addition modulo 22, and built from controlled-NOT gates, each flipping one bit when another is 11. The number of gates should grow no faster than n2n^2.

The Field with 2n2^n Elements

The library states the exercise for 𝔽2n\mathbb{F}_{2^n}, the finite field with 2n2^n elements, taken as a vector space over 𝔽2={0,1}\mathbb{F}_2 = \{0, 1\}, the integers modulo 22. A basis b=(b1,…,bn)b = (b_1, \dots, b_n) of 𝔽2n\mathbb{F}_{2^n} over 𝔽2\mathbb{F}_2 writes each element in exactly one way as x=∑i=1nxibi,xi∈𝔽2,x = \sum_{i=1}^{n} x_i \, b_i , \qquad x_i \in \mathbb{F}_2 ,(1) and the coefficients (x1,…,xn)(x_1, \dots, x_n) are the string of the register; the element 00 is the string of zeros.

The matrix [L]b[L]_b of a linear map LL of 𝔽2n\mathbb{F}_{2^n} in the basis bb is the n×nn \times n matrix over 𝔽2\mathbb{F}_2 whose jjth column holds the coordinates (1) of LbjL b_j: Lbj=∑i=1n([L]b)ijbi.L b_j = \sum_{i=1}^{n} \bigl([L]_b\bigr)_{ij} \, b_i .(2)

An invertible linear map of 𝔽2n\mathbb{F}_{2^n} permutes its 2n2^n elements.

A permutation σ\sigma of a set is a cycle when the points it moves form a single orbit: some point xx has σx≠x\sigma x \ne x, and every point yy with σy≠y\sigma y \ne y equals σkx\sigma^k x for some integer kk.

A transvection Tij(c)T_{ij}(c) of size nn over 𝔽2\mathbb{F}_2, for indices i≠ji \ne j and a coefficient c∈𝔽2c \in \mathbb{F}_2, is the n×nn \times n matrix Tij(c)=I+cEij,T_{ij}(c) = I + c \, E_{ij} ,(3) where II is the identity and EijE_{ij} has a single entry 11, in row ii and column jj. On a column of coordinates it adds cxjc \, x_j to xix_i and leaves the other entries alone. For c=1c = 1 it is the controlled-NOT gate with control jj and target ii, for c=0c = 0 the identity.

The Claim

Theorem 1. Let n≥2n \ge 2 be an integer. Then there are an invertible linear map LL of 𝔽2n\mathbb{F}_{2^n} over 𝔽2\mathbb{F}_2, a basis bb of 𝔽2n\mathbb{F}_{2^n} over 𝔽2\mathbb{F}_2 with nn elements, and transvections T1,…,TmT_1, \dots, T_m of size nn over 𝔽2\mathbb{F}_2, such that LL fixes 00, LL is a cycle as a permutation of 𝔽2n\mathbb{F}_{2^n}, every nonzero xx is carried to every nonzero yy by some power, Lkx=yL^k x = y with k≥0k \ge 0, and [L]b=T1T2⋯Tm,m≤2n2.[L]_b = T_1 T_2 \cdots T_m , \qquad m \le 2n^2 .(4)✦ 2n2=O(n2)(n→∞).2n^2 = O(n^2) \qquad (n \to \infty) .(5)✦

Read gate by gate, (4) is a circuit of controlled-NOT gates for LL, and this is the exercise.

What Is Checked

The claim is stated over the field 𝔽2n\mathbb{F}_{2^n} as a vector space over 𝔽2\mathbb{F}_2, with its invertible linear maps, its bases, the matrix (2) of a linear map in a basis and the transvections (3) of size nn.