Gate Decomposition

Gate decomposition expresses a desired transformation as a sequence of gates available in a chosen alphabet. The main idea is to preserve useful structure: a parity rotation can need only a few entanglers even when its full matrix is large. A generic many-qubit unitary, in contrast, usually requires exponentially many gates. This page develops constructive synthesis and its approximation limits; circuit optimization explains how to simplify an already constructed circuit.

Required background. Circuit representations explain inputs, outputs and allowed operations; universal gate sets distinguish exact from approximate synthesis. Use the matrix and rotation conventions in single-qubit gates and multi-qubit gates.

Gate synthesis and the meaning of equality

Write $V$ for the matrix of the synthesized circuit and $U$ for its target. For an isolated unitary, $V=e^{i\phi}U$ has the same physical action. A useful approximation measure is therefore

d_{\sim}(U,V)=\min_\phi\|U-e^{i\phi}V\|_{\mathrm{op}}.

The operator norm bounds the largest state-vector error over normalized inputs. The same global phase can become relative if this block is later coherently controlled. In that setting, match the phase or supply its correction; controlled operations explains why.

Fix the available gates, their angle units, allowed ancillas and connectivity before counting resources. Three CNOTs, three native entanglers and three logical $T$ gates are different costs. Likewise, an exact symbolic rotation does not imply a noiseless physical implementation. Keep synthesis error, implementation noise and fault-tolerant logical failure distinct.

Preserve Structure Before Expanding a Matrix

A generic $n$ -qubit matrix has $4^n$ complex entries before constraints are used. Materializing it can destroy precisely the structure that made the original operation efficient. The first synthesis decision is therefore not which matrix factorization to call. It is whether the target has a better description.

Recognized structure	Preferred first reduction	Why it matters
tensor product	synthesize factors independently	avoids artificial entanglers
controlled or block diagonal	controlled-unitary or multiplexor construction	retains shared substructure
diagonal	phase polynomial or diagonal synthesis	avoids generic off-diagonal work
Pauli exponential	basis change, parity computation, one rotation	cost scales with support
Clifford operation	symplectic or tableau synthesis	preserves efficient discrete structure
state preparation or isometry	synthesize only required columns	avoids completing a full arbitrary unitary
sparse permutation	reversible-logic synthesis	exploits combinatorial action
dense one- or two-qubit block	Euler or Cartan/KAK decomposition	closed-form bounded-size synthesis
dense multiqubit unitary	cosine–sine or Quantum Shannon decomposition	asymptotically appropriate generic fallback

Structure recognition must itself be reliable. A matrix that is numerically close to diagonal is not exactly diagonal, and treating it as such spends an approximation budget. Likewise, inferring a tensor product from rounded entries requires a residual and a threshold. Exact symbolic predicates and numerical near-structure tests should be separate compiler modes.

One-Qubit Leaves

Every $U\in U(2)$ admits an Euler form

U = e^{i\alpha} R_z(\beta) R_y(\gamma) R_z(\delta).

The Euler construction derives these angles. A common choice is $0\leq\gamma\leq\pi$ . At its endpoints, some angles become redundant: choose a convenient representative and reconstruct the matrix to check it. Smooth targets need not admit a globally continuous choice of Euler angles. A jump in a coordinate is not necessarily a jump in the implemented gate.

Leave symbolic angles available for later fusion. A native continuous alphabet can implement the Euler factors exactly at the ideal-matrix level; a finite alphabet such as Clifford+ $T$ usually needs an approximation stage.

Controlled Unitaries

Let

C(V) = |0\rangle\langle0|\otimes I + |1\rangle\langle1|\otimes V

be a one-control operation. For every $V\in SU(2)$ , one can choose one-qubit gates $A$ , $B$ , and $C$ satisfying

ABC=I, \qquad AXBXC=V.

For $V=R_z(\beta)R_y(\gamma)R_z(\delta)$ , a constructive choice is

\begin{aligned} A&=R_z(\beta)R_y(\gamma/2),\\ B&=R_y(-\gamma/2)R_z[-(\beta+\delta)/2],\\ C&=R_z[(\delta-\beta)/2]. \end{aligned}

The adjacent $y$ rotations cancel in $ABC$ . In $AXBXC$ , conjugation by $X$ reverses both rotation axes in $B$ , producing the desired Euler angles. This is the controlled-unitary construction of Barenco and colleagues.

Then, in matrix-product order,

C(V) = (I\otimes A)\, \operatorname{CNOT}\, (I\otimes B) \times \operatorname{CNOT}\, (I\otimes C).

On the control- $0$ block the two $X$ actions are absent and the target sees $ABC=I$ . On the control- $1$ block it sees $AXBXC=V$ . If $U=e^{i\delta}V\in U(2)$ , the missing phase is a phase gate $P(\delta)=\operatorname{diag}(1,e^{i\delta})$ on the control. It cannot be discarded as a global phase of the full controlled operation.

Worked example: controlled z rotation

Take

\begin{aligned} A&=R_z(\theta/2), \\ B&=R_z(-\theta/2), \\ C&=I. \end{aligned}

Because $XR_z(\lambda)X=R_z(-\lambda)$ ,

AXBXC = R_z(\theta), \qquad ABC=I.

Thus a controlled $R_z(\theta)$ uses two CNOTs and two nontrivial target rotations in this exact continuous-angle construction. A later optimizer may merge either rotation with neighboring local gates. A target with a native controlled-phase family may use a different and cheaper decomposition.

Multiplexors and Uniformly Controlled Gates

A multiplexed one-qubit operation has the block form

\mathcal M = \sum_{j=0}^{2^k-1} |j\rangle\langle j| \otimes U_j = \bigoplus_{j=0}^{2^k-1}U_j,

where $k$ control qubits select one of $2^k$ target operations. An ordinary controlled gate is the special case $k=1$ , $U_0=I$ . Uniformly controlled rotations restrict all $U_j$ to rotations about one axis with branch-dependent angles.

Gray-code constructions order control patterns so that only one control bit changes between adjacent branches. This turns a direct exponential collection of separately controlled gates into a regular network of one-qubit rotations and CNOTs. The size still grows exponentially with the number of independent branches, as it must for generic independent $U_j$ , but common structure and a residual diagonal factor can reduce constants.

For example, to select $R_z(\theta_0)$ or $R_z(\theta_1)$ using one control, set $a=(\theta_0+\theta_1)/2$ and $b=(\theta_0-\theta_1)/2$ . Apply to the target, in time order, $R_z(a)$ , CNOT, $R_z(b)$ , CNOT. The two control branches see respectively $R_z(a+b)$ and $R_z(a-b)$ , so they recover the specified angles. This small example explains how sums and differences of branch angles become ordinary gates.

Multiplexors are the bridge between block matrix factorizations and circuits. They are central to cosine–sine and Quantum Shannon decompositions, state preparation, and uniformly controlled rotation networks.

Two-Qubit Cartan Decomposition

Every $U\in U(4)$ can be written in a Cartan, or KAK, form

U = e^{i\phi} (k_1\otimes k_2) \times A_{\mathrm{nl}}(\mathbf c) \times (k_3\otimes k_4),

where

A_{\mathrm{nl}}(\mathbf c) = \exp\!\bigl[ -i\bigl( c_1X\otimes X + c_2Y\otimes Y + c_3Z\otimes Z \bigr) \bigr].

Here $k_j\in SU(2)$ . The three Pauli products commute, so the nonlocal factor can also be written as three commuting exponentials. Using local symmetries and global phase, coordinates can be chosen in the region

\frac{\pi}{4} \geq c_1 \geq c_2 \geq |c_3|.

Boundary points can still represent the same class; one may choose $c_3\geq0$ when $c_1=\pi/4$ to remove this remaining duplication. The coordinates describe local equivalence, not the amount of entanglement generated on every input. SWAP, for example, is nonlocal but preserves product states. Representative points include:

Gate class	Canonical coordinates $(c_1,c_2,c_3)$
local gate	$(0,0,0)$
CNOT or CZ	$(\pi/4,0,0)$
iSWAP	$(\pi/4,\pi/4,0)$
SWAP	$(\pi/4,\pi/4,\pi/4)$

Signs and chamber labels vary across references because authors choose different Pauli, exponential, magic-basis, and tensor-order conventions. A compiler should attach the convention to the coordinates rather than treating the triple as self-describing.

With arbitrary one-qubit gates and CNOT as the entangler, three CNOTs are necessary and sufficient for a generic two-qubit unitary. Special chamber subsets need zero, one, or two. This is a worst-case exact statement for that alphabet, not a claim that three of an arbitrary native entangler always suffice at the same local cost.

KAK algorithms extract these coordinates in a magic or Bell basis and recover the surrounding local factors. Degenerate eigenvalues at chamber boundaries make some factors nonunique. Check the reconstructed matrix in the original basis rather than demanding smoothness of every intermediate factor. Zhang and colleagues develop the geometry; Vidal–Dawson and Vatan–Williams give three-CNOT constructions.

Native Entanglers and Local Equivalence

KAK coordinates separate two questions:

Which nonlocal operation is needed?
Which local basis changes surround it?

For example,

\operatorname{CNOT}_{1\to2} = (I\otimes H)\, \operatorname{CZ}\, (I\otimes H).

CNOT and CZ therefore have the same canonical nonlocal coordinates. A CZ-native target pays one entangler plus local basis changes rather than a three-CNOT generic construction.

For a parameterized native entangler $E(\lambda)$ , synthesis becomes a reachability problem in the Weyl chamber: choose parameters and interleaved local gates so that the composed canonical point reaches the target class. The shortest word depends on the native family, allowed parameter range, directionality, and whether inverse interactions are available. Calibration quality and crosstalk can change which exact word is preferable, but those device-state choices belong to error-aware compilation rather than the algebraic KAK theorem.

Dense Multiqubit Unitaries

The special efficiency of one- and two-qubit synthesis does not continue for a generic $n$ -qubit unitary. The Lie group $SU(2^n)$ has

\dim SU(2^n) = 4^n-1

real parameters. Without ancillary qubits or measurements, a circuit over arbitrary one-qubit gates and $m$ CNOTs can carry at most $3n+4m$ independent continuous parameters after redundant local degrees of freedom are removed. Therefore a generic exact circuit needs at least

m \geq \left\lceil \frac{ 4^n-3n-1 }{4} \right\rceil

CNOTs. For $n=2$ this gives three; for $n=3$ it gives fourteen. The parameter count does not prove that the lower bound is achievable at every $n$ , but it does establish exponential worst-case scaling.

Two classical matrix factorizations organize generic constructions.

QR and two-level elimination

QR-style synthesis uses Givens rotations to eliminate matrix entries. Each Givens rotation is a two-level unitary: it acts nontrivially only on the span of two computational basis states. That two-level action is then implemented with controlled one-qubit gates and basis-state permutations.

This route is constructive and conceptually direct, but naively translating every eliminated entry can produce large multi-controlled networks. Gray-code ordering, ancillas, and shared-control simplifications improve the circuit.

Cosine–sine decomposition

Partition a $2^n\times2^n$ unitary into equal blocks. A cosine–sine decomposition has the form

U = \begin{pmatrix} A_0&0\\ 0&A_1 \end{pmatrix} \begin{pmatrix} C&-S\\ S&C \end{pmatrix} \begin{pmatrix} B_0&0\\ 0&B_1 \end{pmatrix},

where $A_j$ and $B_j$ are unitaries of half the dimension, while $C$ and $S$ are real diagonal matrices satisfying

C^2+S^2=I.

The middle factor is a uniformly controlled $y$ rotation. The outer block-diagonal factors become multiplexors and are decomposed recursively. Quantum Shannon decomposition reorganizes this recursion to reduce CNOT counts. The construction of Shende, Bullock and Markov has leading CNOT count

N_{\mathrm{CNOT}} \sim \frac{23}{48}\,4^n,

while the parameter lower bound has leading coefficient $1/4$ . Both are $\Theta(4^n)$ : generic dense synthesis is exponentially large and cannot be made polynomial merely by choosing a clever universal alphabet.

The classical input is already exponential. A dense unitary contains $4^n$ complex entries, and stable factorization requires exponential memory and arithmetic. These generic algorithms are appropriate for small blocks, compiler validation, or genuinely unstructured targets. They are not a scalable way to compile an algorithm whose efficient structure was discarded.

Isometries and State Preparation

An isometry $W:\mathbb C^{2^m}\to\mathbb C^{2^n}$ with $m\leq n$ obeys

W^\dagger W=I_{2^m}.

Only $2^m$ orthonormal columns are prescribed. Completing them arbitrarily to a $2^n\times2^n$ unitary and then invoking generic unitary synthesis solves a larger problem than necessary.

State preparation is the case $m=0$ : only the image of $|0^n\rangle$ is fixed. A normalized pure state has $2^{n+1}-2$ real parameters after normalization and global phase, exponentially fewer than the $4^n-1$ parameters of a generic special unitary. Isometry-specific constructions exploit this gap and can also expose ancilla tradeoffs.

If an isometry is implemented by adding $n-m$ qubits in $|0\rangle$ , only that input subspace is prescribed. The remaining columns can be chosen to reduce cost. This freedom does not permit losing relative phases between specified columns: an isometry must act correctly on their superpositions.

Worked Decomposition: A Pauli-String Rotation

Let

P = \bigotimes_{j=1}^{n}P_j, \qquad P_j\in\{I,X,Y,Z\},

and let $w\geq1$ be the number of nonidentity factors. The target is

U_P(\theta) = \exp\!\left( -\frac{i\theta}{2}P \right).

Choose a local basis change $B=\bigotimes_jB_j$ such that

BPB^\dagger = \bigotimes_{j\in S}Z_j.

One valid choice on the support is $B_j=H$ for $P_j=X$ , $B_j=HS^\dagger$ for $P_j=Y$ , and $B_j=I$ for $P_j=Z$ .

Select one support qubit $t$ as a parity target. Let $L$ be a ladder of CNOTs from every other support qubit into $t$ . Conjugation gives

L^\dagger Z_tL = \bigotimes_{j\in S}Z_j.

Functional calculus then yields the circuit identity

\begin{aligned} U_P(\theta) = B^\dagger L^\dagger R_{z,t}(\theta) L B. \end{aligned}

With all-to-all interactions, the complete compute–uncompute sequence uses $2(w-1)$ CNOTs: $w-1$ to compute parity and $w-1$ to uncompute it. Connectivity can require routing; several adjacent Pauli rotations can share or cancel parity work; and a target with native Pauli interactions may avoid the ladder. Those are later optimization and mapping decisions. The identity above is exact for the stated rotation convention.

For a basis string, the target stores the parity of all support bits. Its $Z$ eigenvalue is $+1$ for even parity and $-1$ for odd parity. Applying the rotation therefore multiplies these two sectors by $e^{-i\theta/2}$ and $e^{i\theta/2}$ . Uncomputing restores the original bits while retaining that relative phase.

Three-qubit parity is computed into the bottom wire, rotated, and uncomputed — Read the circuit from left to right. For $P=Z_1Z_2Z_3$ , four CNOTs compute and erase the parity while $R_z(\theta)$ supplies its phase. The dashed division marks the moment when the bottom bit is $x_1\oplus x_2\oplus x_3$ ; all three bits return to their initial values at the output.

If $w=0$ , then $P=I$ and $U_P=e^{-i\theta/2}I$ is a global phase. No parity target exists. Discard the phase only in a phase-insensitive setting; after adding a control it becomes a phase gate on that control.

Ancillas are unnecessary for this construction. If an ancilla-assisted variant is used, a clean ancilla must return to $|0\rangle$ , while a dirty ancilla must return to its unknown input state, including its correlations with any external reference. Leaving residual entanglement is not deallocation.

Exact and Approximate Finite-Alphabet Synthesis

A continuous alphabet containing arbitrary rotations has uncountably many parameter values. A finite alphabet has only countably many finite words, so a generic continuous target cannot be synthesized exactly. The compiler must first ask whether the target belongs to the exactly synthesizable subgroup.

For the one-qubit Clifford+ $T$ alphabet, exact synthesis is characterized by matrix entries in

\mathbb Z \left[ \frac{1}{\sqrt2},i \right]

under the standard phase convention. Efficient exact algorithms can produce optimal or tightly controlled $T$ counts for this algebraic domain. For multiple qubits, Giles and Selinger prove that the same ring condition is necessary and sufficient when at most one ancillary qubit initialized and restored to $|0\rangle$ is allowed. Without that ancilla, further determinant restrictions can matter.

A generic $R_z(\theta)$ does not satisfy that ring condition and must be approximated. Number-theoretic Clifford+ $T$ synthesis for one-qubit $z$ rotations achieves, in the typical ancilla-free case,

N_T = 3\log_2\frac1\epsilon + O\!\left( \log\log\frac1\epsilon \right).

This is a typical-case scaling, not a uniform guarantee for every angle and tolerance. Ross and Selinger give exact optimality with a factoring oracle, and near-optimality under a stated number-theoretic hypothesis without one; their worst cases have a leading coefficient four rather than three. This is much closer to the logarithmic information-theoretic lower scaling than a generic Solovay–Kitaev construction. The Universal Gate Sets page states the Solovay–Kitaev assumptions and explains why the theorem is a general fallback rather than an optimal compiler for every structured alphabet.

Allocate Approximation Error

Suppose a structural decomposition exposes $r$ rotations and rotation $j$ is approximated to operator-norm error $\epsilon_j$ . The telescoping bound derived on Universal Gate Sets gives the sufficient condition

\sum_{j=1}^{r}\epsilon_j \leq \epsilon_{\mathrm{synth}}.

Equal allocation is simple but not always cost optimal. If the synthesis model for rotation $j$ is

N_j \approx a_j\log\frac1{\epsilon_j} +b_j,

for $a_j>0$ , minimizing the continuous cost under a saturated linear budget gives the interior solution

\epsilon_j = \epsilon_{\mathrm{synth}} \frac{a_j}{ \sum_{k=1}^{r}a_k }.

The formula follows from a Lagrange multiplier and says that a rotation whose precision is more expensive receives a larger share of the allowed error. Integer gate counts, shared subcircuits, error cancellation, and physical noise make real allocation discrete and target dependent, but the calculation is a useful baseline.

An exact rewrite of the synthesized circuit preserves its matrix and hence the existing error bound. An additional approximate rewrite spends more of the tolerance. If phase is ignored, the rewrite must preserve equality in the same phase-insensitive setting. Bounds remain valid after exact cancellation even when their per-gate decomposition is no longer visible.

Checking a synthesized circuit

For a small circuit, multiply its matrices in the stated time and tensor order and form $R=U^\dagger V$ . Exact agreement up to phase means that $R$ is a scalar multiple of the identity. If $\operatorname{Tr}R\ne0$ , the angle

\phi_F=\arg\operatorname{Tr}R

minimizes the Frobenius residual $\|R-e^{i\phi}I\|_F$ . It need not minimize the operator norm, even when $R$ is very close to $I$ . For a worst-case tolerance, evaluate that norm at the chosen phase to obtain an upper bound, or minimize it directly. For unitary $R$ with eigenvalues $e^{i\lambda_j}$ ,

\|R-e^{i\phi}I\|_{\mathrm{op}} =\max_j|e^{i\lambda_j}-e^{i\phi}|.

Thus the problem is to cover the eigenvalues on the unit circle with the smallest chord radius about a phase point. A small average infidelity cannot replace this worst-case check. Floating-point multiplication supplies a numerical residual; a rigorous tolerance also needs control of rounding.

Large circuits need algebraic identities, compact invariants or a suitable equivalence checker. Testing random states can reveal mistakes but cannot establish the action on every input. Check the allowed ancilla subspace and output ordering as well as the gate product. Connectivity and physical noise are separate questions, developed in routing and error-aware compilation.

Exercises

1. Verify the controlled rotation construction

For

\begin{aligned} A&=R_z(\theta/2), \\ B&=R_z(-\theta/2), \\ C&=I, \end{aligned}

verify the control- $0$ and control- $1$ blocks of the two-CNOT construction.

Solution

On control $0$ , both CNOTs act trivially on the target, so the target product in matrix order is

ABC = R_z(\theta/2)R_z(-\theta/2) = I.

On control $1$ , each CNOT contributes $X$ . Using $XR_z(\lambda)X=R_z(-\lambda)$ ,

\begin{aligned} AXBX &= R_z(\theta/2) X R_z(-\theta/2) X \\ &= R_z(\theta/2) R_z(\theta/2) \\ &= R_z(\theta). \end{aligned}

The full operation is therefore $C(R_z(\theta))$ .

2. Derive a two-qubit ZZ rotation

Show that

e^{-i\theta Z_1Z_2/2} = \operatorname{CNOT}_{1\to2} R_{z,2}(\theta) \operatorname{CNOT}_{1\to2}.

Solution

CNOT is self-adjoint and conjugates the target Pauli as

\operatorname{CNOT}_{1\to2} Z_2 \operatorname{CNOT}_{1\to2} = Z_1Z_2.

For any unitary $W$ and operator $A$ ,

W e^A W^\dagger = e^{WAW^\dagger}.

Since $R_{z,2}(\theta)=e^{-i\theta Z_2/2}$ , conjugating it by CNOT gives the claimed identity. The construction uses two CNOTs and one $z$ rotation before any neighboring-gate optimization.

3. Apply the parameter lower bound

Evaluate the CNOT parameter-count lower bound for generic unitaries on two, three, and four qubits.

Solution

Use

m_{\min} \geq \left\lceil \frac{4^n-3n-1}{4} \right\rceil.

Therefore

\begin{array}{c|c} n&\text{lower bound}\\ \hline 2&3\\ 3&14\\ 4&61 \end{array}

For $n=4$ , $(256-12-1)/4=60.75$ . These are generic lower bounds from continuous parameter counting, not constructive gate counts for every unitary.

4. Use local equivalence

Prove that CNOT and CZ need the same number of entanglers on a target where arbitrary one-qubit gates are free and CZ is native.

Solution

Hadamard exchanges $X$ and $Z$ , so

\operatorname{CNOT}_{1\to2} = (I\otimes H) \operatorname{CZ} (I\otimes H).

Thus each CNOT can be replaced by one CZ and two local Hadamards, and the inverse replacement is identical. The gates lie in the same KAK local equivalence class $(\pi/4,0,0)$ . They have equal entangler count under the stated model, though duration or one-qubit cost can differ on real hardware.

5. Find the phase that becomes observable

Let $V=e^{i\gamma}U$ . Compare $C(V)$ and $C(U)$ and show that their difference is not generally a global phase on the joint system.

Solution

The controlled operations are

\begin{aligned} C(V) &= |0\rangle\langle0|\otimes I + e^{i\gamma} |1\rangle\langle1|\otimes U, \\ C(U) &= |0\rangle\langle0|\otimes I + |1\rangle\langle1|\otimes U. \end{aligned}

Only the control- $1$ block acquires the phase. Indeed,

C(V) = \bigl(P(\gamma)\otimes I\bigr)C(U).

This is a relative phase between control branches unless $e^{i\gamma}=1$ . A phase-insensitive isolated-gate certificate therefore cannot be reused unchanged after adding a control.

6. Allocate an unequal error budget

Three rotations have asymptotic costs

N_j = a_j\log\frac1{\epsilon_j}, \qquad (a_1,a_2,a_3)=(1,2,3).

Minimize their continuous total cost subject to $\epsilon_1+\epsilon_2+\epsilon_3=\epsilon$ .

Solution

Introduce a multiplier $\lambda$ :

\mathcal L = \sum_j a_j\log\frac1{\epsilon_j} + \lambda \left( \sum_j\epsilon_j-\epsilon \right).

Stationarity gives

-\frac{a_j}{\epsilon_j} +\lambda = 0,

so $\epsilon_j=a_j/\lambda$ . Summing the errors gives $\lambda=6/\epsilon$ and therefore

(\epsilon_1,\epsilon_2,\epsilon_3) = \left( \frac{\epsilon}{6}, \frac{\epsilon}{3}, \frac{\epsilon}{2} \right).

The most precision-expensive rotation receives the largest allowed error. Integer word lengths can shift the discrete optimum.

7. Count state-preparation parameters

Why can state preparation require asymptotically fewer parameters than a generic unitary? Count the real degrees of freedom in both cases.

Solution

A complex state vector in dimension $2^n$ has $2^{n+1}$ real components. Normalization removes one degree of freedom and global phase removes another, leaving

2^{n+1}-2.

A generic element of $SU(2^n)$ has

4^n-1

real parameters. State preparation fixes one output ray rather than every column of a unitary, so completing the remaining columns and synthesizing them solves an exponentially larger problem than the source contract requires.

8. Construct a Pauli-string rotation

A compiler synthesizes $e^{-i\theta X_1Y_2Z_4/2}$ using qubit $4$ as the parity target. Give valid local basis changes and the all-to-all CNOT count before optimization.

Solution

Choose

B_1=H, \qquad B_2=HS^\dagger, \qquad B_4=I.

These map $X_1Y_2Z_4$ to $Z_1Z_2Z_4$ by conjugation. Compute parity into qubit $4$ with CNOTs $1\to4$ and $2\to4$ , apply $R_{z,4}(\theta)$ , undo the two CNOTs in reverse order, and undo the basis changes. The support weight is $w=3$ , so the decomposition uses

2(w-1)=4

CNOTs before cancellation, routing, or native-interaction substitution.

9. Compare average and worst-case phase alignment

Let $R=\operatorname{diag}(1,1,1,e^{i\eta})$ with $0<\eta<\pi$ . Find the operator-norm minimizing phase and compare it with $\phi_F$ when $\eta$ is small.

Solution

The distinct eigenvalues lie at the ends of an arc of length $\eta<\pi$ . Its midpoint balances their chord distances, so

\phi_{\mathrm{op}}=\eta/2, \qquad r_{\mathrm{op}}=2\sin(\eta/4).

In contrast, $\phi_F=\arg(3+e^{i\eta})\approx\eta/4$ . The three repeated eigenvalues pull the Frobenius optimum toward zero; multiplicity does not change the maximum distance. Its operator residual is approximately $3\eta/4$ , compared with $\eta/2$ at the optimum. The distinction persists arbitrarily near the identity.

References

A. Barenco et al., “Elementary gates for quantum computation,” Physical Review A 52, 3457–3467 (1995), doi:10.1103/PhysRevA.52.3457.
V. Bergholm, J. J. Vartiainen, M. Möttönen, and M. M. Salomaa, “Quantum circuits with uniformly controlled one-qubit gates,” Physical Review A 71, 052330 (2005), doi:10.1103/PhysRevA.71.052330.
M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, 10th anniversary ed., Cambridge University Press (2010), doi:10.1017/CBO9780511976667.
G. Vidal and C. M. Dawson, “A universal quantum circuit for two-qubit transformations with three CNOT gates,” Physical Review A 69, 010301(R) (2004), doi:10.1103/PhysRevA.69.010301.
N. Khaneja and S. J. Glaser, “Cartan decomposition of $SU(2^n)$ and control of spin systems,” Chemical Physics 267, 11–23 (2001), doi:10.1016/S0301-0104(01)00318-4.
R. Iten, R. Colbeck, I. Kukuljan, J. Home, and M. Christandl, “Quantum circuits for isometries,” Physical Review A 93, 032318 (2016), doi:10.1103/PhysRevA.93.032318.
V. Kliuchnikov, D. Maslov, and M. Mosca, “Fast and efficient exact synthesis of single-qubit unitaries generated by Clifford and $T$ gates,” Quantum Information and Computation 13, 607–630 (2013), arXiv:1206.5236.
S. S. Bullock and I. L. Markov, “Asymptotically optimal circuits for arbitrary $n$ -qubit diagonal computations,” Quantum Information and Computation 4, 27–47 (2004), arXiv:quant-ph/0303039.
M. Möttönen, J. J. Vartiainen, V. Bergholm, and M. M. Salomaa, “Quantum circuits for general multiqubit gates,” Physical Review Letters 93, 130502 (2004), doi:10.1103/PhysRevLett.93.130502.
C. M. Dawson and M. A. Nielsen, “The Solovay–Kitaev algorithm,” Quantum Information and Computation 6, 81–95 (2006), arXiv:quant-ph/0505030.
B. Giles and P. Selinger, “Exact synthesis of multiqubit Clifford+ $T$ circuits,” Physical Review A 87, 032332 (2013), doi:10.1103/PhysRevA.87.032332.
N. J. Ross and P. Selinger, “Optimal ancilla-free Clifford+ $T$ approximation of $z$ -rotations,” Quantum Information and Computation 16, 901–953 (2016), arXiv:1403.2975.
P. Selinger, “Efficient Clifford+ $T$ approximation of single-qubit operators,” Quantum Information and Computation 15, 159–180 (2015), arXiv:1212.6253.
V. V. Shende, I. L. Markov, and S. S. Bullock, “Minimal universal two-qubit controlled-NOT-based circuits,” Physical Review A 69, 062321 (2004), doi:10.1103/PhysRevA.69.062321.
V. V. Shende, S. S. Bullock, and I. L. Markov, “Synthesis of quantum-logic circuits,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 25, 1000–1010 (2006), doi:10.1109/TCAD.2005.855930.
F. Vatan and C. Williams, “Optimal quantum circuits for general two-qubit gates,” Physical Review A 69, 032315 (2004), doi:10.1103/PhysRevA.69.032315.
J. Zhang, J. Vala, S. Sastry, and K. B. Whaley, “Geometric theory of nonlocal two-qubit operations,” Physical Review A 67, 042313 (2003), doi:10.1103/PhysRevA.67.042313.