two-level unitary

In plain terms

Building a quantum computer means realising an arbitrary operation out of a fixed supply of small ones, so the first question is whether an arbitrary operation can be cut into small pieces at all, exactly rather than approximately. It can, and the pieces are as small as you could hope for.

A two-level operation acts on just two of the state space's basis directions and leaves everything else alone, so it's a rotation in a single plane. The decomposition works like Gaussian elimination. Choose a column of the operation you want, and apply rotations in single planes to knock out its entries one at a time until only one remains, which for a norm-preserving operation must then be one. That column is finished, so the problem has shrunk, and the induction repeats on what's left.

Counting the rotations gives the classical bound. Clearing a block of a given size takes one rotation per entry cleared, and the running total obeys the same arithmetic as counting pairs, so a space of a given dimension needs at most as many rotations as there are pairs of directions in it. That bound is what makes the next step of the universality argument finite: the factors are then rewritten as controlled operations, and controls are built from controlled-not gates.

In CSD

The corpus proves the decomposition and the count, and the count needed no new mathematics once the elimination was set up properly. A rotation in a single plane can be chosen so that the surviving entry carries the norm of the block it just cleared, which for a norm-preserving operation is exactly one, so the row and column come out of each round already in the shape the induction needs and not one factor is spent on fixing a phase. The bookkeeping is then the identity that counting pairs satisfies, and the base case is that on a block of at most two directions the operation is already two-level.

The decomposition is the first step of the universality chain, and the later steps consume it directly: a two-level operation on an adjacent pair is a multiply-controlled gate, relabelling one pair onto another is a Gray code, and removing controls is a recursion. The honest boundary is that the count is an upper bound on two-level factors, with no matching lower bound and no translation into a gate count, which is a separate open row.

Mathematically

IsTwoLevel is agreement with the identity outside a two-element index block, stated through IdOutside s for a general index set; twoLevelMat i j a b c d places a 2-by-2 block, composition of two such is 2-by-2 matrix multiplication (twoLevelMat_mul), and unitarity of the matrix is unitarity of the block. givensMat i j v is the Givens rotation in the (i, j) plane killing the j-component of v.

exists_clear_column: a product of two-level unitaries kills any prescribed set of components of a vector, one factor per component, with the pivot accumulating the norm of the cleared block. exists_twoLevel_prod is the decomposition, by induction on the support through exists_twoLevel_prod_of_idOutside. exists_twoLevel_prod_length is the Nielsen-Chuang count, at most d(d - 1)/2 factors, carried as Nat.choose (max s.card 2) 2 with Pascal's rule (m - 1) + choose (m - 1) 2 = choose m 2 and isTwoLevel_of_idOutside_card_le_two as the base case. No lower bound is proved, so the count is an upper bound and nothing here says it can't be beaten. How many elementary gates one two-level unitary costs is answered by the multiply-controlled layer, as ctrlGate_eq_twoLevelMat identifies a multiply-controlled gate with a two-level matrix on an adjacent pair and exists_multiCtrl_sandwich relabels an arbitrary pair to an adjacent one by a Gray code.

The name

Wallace Givens gave the plane rotations their name in a 1958 paper on reducing a matrix to triangular form, as a numerically stable way of annihilating one entry at a time, and they remain standard in numerical linear algebra. The application to quantum circuits is Nielsen and Chuang's textbook section 4.5, which turns the same elimination into the first half of a universality proof.

Reciprocally, quantum computing has sent work back the other way, as circuits built from Givens rotations are now a standard ansatz for simulating electrons, where preserving particle number is exactly the two-level structure.

Related entries

• Clifford plus TClifford plus T is the standard universal gate set, as the Clifford gates alone are classically simulable and adding the single eighth-turn phase gate makes every unitary reachable to any accuracy you ask for.
• Toffoli gateThe Toffoli gate flips its target only when both controls are set, which is enough to compute anything classically while remaining reversible, and its count is the currency in which the cost of a quantum algorithm is quoted.
• Pauli matricesThree small matrices carry the entire two-level world, and their refusal to commute is the uncertainty principle in its smallest packaging.
• Kronecker productTwo quantum systems become one by multiplying their descriptions rather than adding them, which is why quantum resources multiply where classical ones merely add.
• Hermitian operatorA single symmetry condition on an operator guarantees that every number it can produce in a measurement is real, and it delivers the whole machinery of outcomes and eigenstates at no extra cost.