Results on programmable circuits, block matrices and gate words

The course proves the statements below; each link leads to the statement with its assumptions and its proof. The lessons are self-checked by the writing AI; independent mathematical review is not complete.

• Polynomial-time unitary synthesis — Theorem 2.1. A polynomial-time generated quantum oracle circuit over H, T, T*, CNOT with polynomial resources approximates every n-qubit unitary within diamond-norm distance 1/2 for a suitable Boolean oracle.
• Spectral theorem for Hermitian matrices — Lemma 3.1. Every Hermitian matrix has an orthonormal basis of eigenvectors with real eigenvalues, by maximizing the Rayleigh quotient.
• Trace norm of Hermitian matrices — Lemma 3.2. Variational formula, triangle inequality, contraction under partial trace, and ||aa* - bb*||_1 <= 2||a - b|| for unit vectors.
• From operator norm to diamond norm — Proposition 4.2. A circuit implementing U with clean-workspace error delta has output channel within 2 delta of U in the diamond norm.
• State preparation — Lemma 2.1. u + 1 programmable slots prepare any family of unit vectors on u qubits, controlled by labels.
• Basis permutations — Lemma 2.2. 5u slots with u clean temporary qubits apply any family of permutations of the computational basis.
• Fourier transforms — Lemma 2.3. The Fourier transform on b qubits is a fixed circuit of 2b + 3 floor(b/2) slots.
• A matrix sign estimate — Lemma 1.2. E||sum eps_i L_i|| <= 2 h^(1/2a) sqrt((2a - 1)v) for Hermitian h x h matrices L_i, v = ||sum L_i^2||, independent random signs.
• A block of small norm — Proposition 2.1. Permutations, diagonal signs and Walsh-Hadamard transforms bring every unitary of order d to a block form with internal block of norm at most 3/4 and size s >= d/(4M).
• The number of reductions — Lemma 2.2. Fewer than 8M(n+1) removals of the internal block reach dimension one.
• Closing the internal coordinates — Lemma 1.1. F = A + BZ(I - DZ)^-1 C is unitary for every diagonal unitary Z, and FE* = R*V.
• Nearly isometric field maps — Proposition 2.1. The truncated field maps satisfy (1 - r^2L) I <= T*T <= I and intertwine V with the controlled F(z) up to 2 r^L/(1 - r).
• Row sparsity — Proposition 3.2. In Fourier coordinates every row of both field maps has at most L nonzero entries, because power sums determine multisets.
• Row-sparse nearly isometric maps — Lemma 1.1. A map with at most L nonzero entries per row and (1 - eps) I <= T*T <= I is applied by slots and amplitude amplification with error at most 5 eps.
• The field encoders — Proposition 2.1. The two field maps are implemented by slot circuits with error at most 5 r^2L.
• One synthesis step — Lemma 3.1. One call of a circuit for the controlled smaller unitaries F(z), between the two encoders, synthesizes V with an added error 2 r^L/(1 - r) + 10 r^2L.
• Uniform programmable synthesis — Proposition 4.1. A uniformly generated skeleton with t + O((n+1)^10) qubits and O((n+1)^13) slots solves every controlled synthesis task with error below 1/100.
• Density of determinant-one words — Proposition 1.4. The determinant-one words in H, T, T* are dense in SU(2).
• Short words — Lemma 2.1. Every element of SU(2) is within xi of a determinant-one word of length at most K_w xi^-3.
• Exact controlled symbols — Lemma 3.1. With clean scratch, the doubly controlled Z, the Toffoli gate and the singly controlled H, T, T* are exact circuits over H, T, T*, CNOT.
• Compilation of slots — Proposition 4.1. A skeleton of S slots is compiled into a circuit with one Boolean oracle storing approximating words, with error at most S eta and polynomial resources.
• Proof of the synthesis theorem — Theorem 4.2. The compiled recursion gives clean-workspace error below 1/50 and diamond-norm error below 1/25.

Reading order

Six lessons, to be read in order. Every step is proved in the course; the inverse function theorem is cited from the core course Real Analysis II.