Gate Decomposition

Short Definition

Gate decomposition is the construction of a circuit over a declared gate alphabet whose action equals, or approximates to a declared tolerance, a target unitary transformation. The target may be given as a small dense matrix, a controlled or block-diagonal operator, a tensor product, a Pauli rotation, an isometry, or a structured algorithmic operation. Those inputs should not be treated as interchangeable: their structure determines both the appropriate synthesis method and the attainable cost.

A complete synthesis problem can be written schematically as

$$\mathsf{Synth} \bigl( U;\, \mathcal G,\, \Xi,\, d,\, \epsilon,\, \mathcal A,\, \mathbf c \bigr) \longrightarrow \bigl( C,\, \mathcal K \bigr).$$

Here $U$ is the target, $\mathcal G$ is the allowed gate alphabet, $\Xi$ collects semantic conventions and target capabilities, $d$ is the comparison metric, $\epsilon$ is the allowed synthesis error, $\mathcal A$ states the ancilla contract, and $\mathbf c$ states which costs matter. The output circuit $C$ is accompanied by a certificate $\mathcal K$ recording the decomposition, parameters, residual error, resources, and conventions used.

This page is the canonical home for unitary decomposition and gate synthesis algorithms: controlled constructions, multiplexors, one- and two-qubit canonical decompositions, recursive dense-unitary synthesis, structure-aware methods, finite-alphabet approximation, cost contracts, and verification. Universal Gate Sets owns universality and the Solovay–Kitaev theorem. Circuit Intermediate Representations owns representation and lowering contracts. Circuit Optimization owns circuit rewriting, cancellation, commutation, and abstract depth reduction. Later pages own qubit mapping and routing, calibration-aware choices, and pulse-level realization.

State the Synthesis Contract First

The phrase “decompose $U$” is incomplete until equality, context, and cost are fixed. If global phase is unobservable in the declared context, exact synthesis may require

$$V(C) = e^{i\phi}U$$

for some $\phi$. An approximate phase-insensitive requirement may use

$$d_{\sim}(U,V) = \min_{\phi\in\mathbb R} \left\| U-e^{i\phi}V \right\|_{\mathrm{op}} \leq \epsilon.$$

If the synthesized block will later be controlled or placed on one branch of an interferometer, the same phase can become relative. The contract may then require literal matrix equality or an explicitly propagated phase correction.

The gate alphabet also needs more than names. For every gate, fix:

• matrix and tensor-product conventions;
• parameter ranges, periodicities, and angle units;
• whether inverses are primitive or synthesized;
• whether arbitrary rotations are exact or only symbolic;
• which controls, measurements, resets, and ancillas are permitted;
• whether qubit permutations are physical operations or bookkeeping;
• which gates are native, logical, virtual, or merely accepted by software.

The cost is usually a vector rather than one count:

$$\begin{aligned} \mathbf c(C) = \bigl(& N_{2q},\, D_{2q},\, N_T,\, D_T, \\ & N_{1q},\, N_{\mathrm{anc}},\, \tau,\, \epsilon_{\mathrm{synth}} \bigr). \end{aligned}$$

The entries can represent two-qubit count and depth, $T$ count and depth, one-qubit count, ancillas, duration, and synthesis error. A fault-tolerant compiler may rank $T$ states above Clifford gates; a present-day device may rank calibrated entanglers and duration above one-qubit gates. Reporting only “gate count” hides this choice.

Three tasks should remain distinct:

Task	Input	Principal output
decomposition	one operation or structured map	an exact or approximate circuit over a lower-level alphabet
circuit optimization	an existing circuit	a behavior-preserving circuit with improved cost
mapping and routing	a circuit plus target graph	placed operations satisfying connectivity

A production compiler can interleave them, but a claim about one does not establish the others.

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

Generic dense synthesis is a fallback, not the first move. Preserve tensor, control, diagonal, Pauli, Clifford, and isometric structure until bounded-size or recursively decomposable blocks are exposed; only then choose continuous or finite-alphabet gate sequences and verify the declared equivalence.

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).$$

Single-Qubit Gates owns the rotation conventions, Euler derivation, phase distinctions, and Bloch-sphere interpretation. At the decomposition layer, four implementation facts matter:

1. Euler angles are not unique, especially when $\sin\gamma=0$.
2. Branch choices should vary continuously when parameters are swept.
3. A symbolic $R_z(\theta)$ may become a frame update, a pulse, or a finite-alphabet approximation.
4. Neighboring one-qubit factors should remain visible to a later optimization pass instead of being prematurely rounded or expanded.

The middle angle can be chosen in a conventional interval such as $0\leq\gamma\leq\pi$, with endpoint singularities handled explicitly. A numerically stable implementation should use matrix entries or a quaternion representation with a documented branch policy, then reconstruct the matrix and report the residual. Extracting angles and trusting them without reconstruction is not verification.

For a native continuous alphabet, Euler decomposition can be exact at the ideal matrix level. For a discrete fault-tolerant alphabet such as Clifford+$T$, generic angles require a second, approximate synthesis stage. Those are different claims even if both compiler passes are called “decomposition.”

Controlled Operations owns the projector/block semantics, branch-phase conventions, and access licensing for controlled and SELECT operations. This page begins from that fixed semantic target and owns constructive synthesis, topology, approximation, and compiled cost.

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.$$

Then, in matrix-product order,

$$\begin{aligned} C(V) = &(I\otimes A)\, \operatorname{CNOT}\, (I\otimes B) \\ &\times \operatorname{CNOT}\, (I\otimes C). \end{aligned}$$

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. Controlled gates are the $k=1$ case. 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.

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

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

where

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

with $k_j\in SU(2)$. Using Weyl symmetries, the nonlocal coordinates can be placed in a canonical chamber, for this convention,

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

The outer factors are local one-qubit gates. The coordinate triple records the nonlocal equivalence class. 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.

A practical KAK implementation usually:

1. removes a declared global phase to enter $SU(4)$;
2. changes to a magic or Bell basis;
3. extracts local invariants or eigenphases that determine a Weyl-chamber representative;
4. resolves permutation and sign symmetries consistently;
5. reconstructs the four local factors;
6. converts the nonlocal block into the chosen entangler sequence;
7. verifies the reconstructed matrix in the original basis.

Eigenvalue degeneracies occur on chamber boundaries. The decomposition remains valid there, but individual local factors may be nonunique and numerically discontinuous. Stable software clusters nearly degenerate eigenvalues, applies a deterministic gauge convention, and verifies the final product rather than demanding continuity from nonunique factors.

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. 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. A standard construction 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 a larger unitary is used internally, its action on the unspecified orthogonal subspace is a compiler choice, not part of the source semantics. That freedom can be used to reduce cost, but the certificate should say which subspace was required and which was unconstrained.

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$ 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 ladder 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 the algebraic decomposition contract.

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. 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. Multiqubit results require careful ancilla conditions; allowing one local ancilla enlarges the constructive characterization.

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),$$

subject to the algorithm’s stated arithmetic assumptions. 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.

Finite-alphabet methods include:

• exact algebraic reduction when the matrix lies in the generated ring;
• meet-in-the-middle or database search for small optimal words;
• number-theoretic approximation of axial rotations;
• phase-polynomial and parity-network synthesis for Clifford+$T$ structure;
• bounded-depth numerical search when exact optimality is not tractable.

The reported result must separate three errors:

$$\begin{gathered} \epsilon_{\mathrm{synth}} \not\equiv \epsilon_{\mathrm{physical}}, \\ \epsilon_{\mathrm{physical}} \not\equiv p_{\mathrm{logical}}. \end{gathered}$$

Synthesis error is coherent mismatch between ideal matrices or channels. Physical error is the noisy implementation of the chosen gates. Logical failure is the probability or channel error after fault-tolerant protection. They can interact, but they are not one interchangeable “fidelity.”

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,$$

minimizing total count under a saturated linear error budget gives

$$\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 optimizer may later cancel or combine approximated rotations. It must then recompute or conservatively update the residual; the original per-gate bounds do not automatically certify the rewritten circuit.

Choose a Cost Objective Without Hiding Tradeoffs

One scalarized synthesis objective is

$$\begin{aligned} \min_C\quad & w_2N_{2q}(C) +w_TN_T(C) +w_dD(C) \\ & +w_aN_{\mathrm{anc}}(C) +w_e\epsilon_{\mathrm{synth}}(C), \end{aligned}$$

subject to semantic equality or tolerance and target legality. The weights encode an architecture and workload policy. They are not universal constants.

Whenever practical, report a Pareto set rather than one unexplained weighted winner. Two decompositions can exchange:

• entangler count for one-qubit count;
• depth for ancillas;
• $T$ count for measurement and feedforward;
• exactness for a smaller approximation error budget;
• generic portability for a target-specific native interaction;
• compilation time for circuit quality.

Routing, parallel scheduling, and pulse calibration can reverse an alphabet-level ranking. A decomposition certificate should therefore retain several cost components for later passes instead of collapsing them too early.

Verification and Certificates

For an exact small-block decomposition, multiply the synthesized gate matrices in the declared tensor and time order. Let

$$R = U^\dagger V(C).$$

If global phase is allowed, $R$ should be proportional to the identity. When $\operatorname{Tr}R\neq0$, a useful phase estimate is

$$\phi_* = \arg\operatorname{Tr}R.$$

The compiler must still evaluate its declared residual, for example

$$r_{\mathrm{op}} = \left\| R-e^{i\phi_*}I \right\|_{\mathrm{op}},$$

and should not substitute average process fidelity for a worst-case metric without saying so. Near a poor approximation where the trace is small, direct phase minimization is more reliable than this estimate.

For large structured circuits, use layered evidence:

1. prove or symbolically check each decomposition identity;
2. verify small instances by full matrices;
3. test structural invariants such as unitarity, support, phase polynomial, or KAK coordinates;
4. use randomized state tests as diagnostics, not proofs;
5. perform translation validation on the actual emitted circuit;
6. retain source maps and pass provenance.

A useful certificate $\mathcal K$ records:

Field	Minimum content
target	exact symbolic object, matrix hash, or structured specification
equivalence	literal, global-phase, subspace, channel, or approximate
alphabet	gate definitions, parameter and tensor conventions, profile version
ancillas	number, initial state, restoration and measurement contract
synthesis	algorithm, implementation version, tolerances, random seed if used
residual	metric, numerical precision, measured value, acceptance threshold
resources	gate counts by class, depth model, ancillas, compilation time
target assumptions	native family, directionality, connectivity assumptions, calibration epoch if consumed

Random input states can miss a phase error, an incorrect action on a small subspace, or a convention mismatch. Passing a few simulations is useful debugging evidence, not a general equivalence proof.

Common Mistakes

• Treating a generic $n$-qubit unitary as though it had a polynomial-size circuit.
• Materializing a dense matrix for an operation already described by a short structured circuit.
• Saying “three entanglers suffice” without naming CNOT, local-gate freedom, exactness, and the two-qubit scope.
• Dropping a one-qubit global phase before adding a control.
• Comparing CNOT count, CZ count, $T$ count, and pulse count as though they were the same resource.
• Confusing exact continuous-angle decomposition with finite-alphabet exact synthesis.
• Applying a generic Solovay–Kitaev bound where a number-theoretic or structure-specific compiler is available.
• Completing an isometry or state-preparation task to an arbitrary dense unitary and paying for irrelevant columns.
• Ignoring clean-versus-dirty ancilla restoration.
• Assuming a matrix residual also certifies target connectivity, timing, or noisy implementation.
• Running optimization after synthesis without updating the error and provenance certificate.
• Using random-state tests as the sole correctness criterion.

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. Audit a Pauli-string implementation

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. Design a synthesis certificate

List the information needed to support the claim: “This circuit implements the given two-qubit unitary to error below $10^{-10}$.”

Solution

The certificate should identify the target matrix or hash and its basis order; the gate matrices, parameter units, tensor order, and multiplication convention; whether global phase is allowed; the comparison metric; numerical precision; the measured residual and threshold; the KAK and one-qubit decomposition conventions; the exact output circuit; ancilla assumptions; algorithm and implementation versions; gate counts and depth model; and any target profile used.

It should also record whether $10^{-10}$ is matrix synthesis error, not a physical error rate or logical failure probability. A matrix reconstruction or translation-validation record is stronger evidence than a few random-state tests.

Research Status

Euler, controlled-unitary, Cartan/KAK, cosine–sine, and Quantum Shannon decompositions are established results. The exponential size of a generic dense-unitary circuit is an information-theoretic feature, not a temporary compiler limitation.

Active work concerns better synthesis for structured operations, restricted native entanglers, topology and ancilla constraints, arithmetic gate sets, measurement-assisted constructions, approximate block replacement, and joint objectives spanning compilation time, circuit resources, and physical error. Claims of “optimal decomposition” are therefore meaningful only for the exact alphabet, equivalence, ancilla, topology, and cost model proved.

Further Connections

• Circuit Intermediate Representations defines how target operations, gate alphabets, tolerances, profiles, and synthesis certificates are represented.
• Quantum Software Stack places decomposition between logical intent, later optimization and routing, controller execution, and reproducible evidence.
• Circuit Optimization takes synthesized circuits through verified cancellation, commutation, structured algebra, window resynthesis, and depth reduction.
• Resource Estimation Tools propagates decomposition choices, synthesis precision, gate counts, depth, and ancilla liveness into fault-tolerant and physical scenarios.
• Qubit Mapping and Routing turns decomposed interactions into a connectivity-legal circuit while preserving a time-dependent program-to-physical map.
• Error-Aware Compilation compares legal exact or approximate gate words under a declared, uncertainty-aware physical risk model.
• Pulse-Level Control binds chosen target operations to calibrated waveform families, frames, sample grids, schedules, and executable evidence.
• Universal Gate Sets owns exact and approximate universality, Clifford+$T$, Solovay–Kitaev scaling, and the circuit-level error-budget bound.
• Single-Qubit Gates owns rotation conventions and Euler synthesis; Multi-Qubit Gates owns controlled, exchange, SWAP, Toffoli, and parity-measurement gate families.
• Circuit Model fixes register order, dynamic-circuit semantics, and resource conventions.
• Quantum Gates Formula Card and Quantum Gates Reference Table provide compact matrices and convention checks.
• Surface Code explains why a logical gate can lower to code deformations, lattice surgery, or state injection rather than one physical gate word.
• Error Estimates develops truncation, conditioning, residual, and precision concepts needed for numerical synthesis validation.

References

1. A. Barenco et al., “Elementary gates for quantum computation,” Physical Review A 52, 3457–3467 (1995), doi:10.1103/PhysRevA.52.3457.
2. 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.
3. 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.
4. 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.
5. 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.
6. 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.
7. 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.
8. 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.
9. 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.
10. 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.
11. 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.
12. B. Giles and P. Selinger, “Exact synthesis of multiqubit Clifford+$T$ circuits,” Physical Review A 87, 032332 (2013), doi:10.1103/PhysRevA.87.032332.
13. 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.
14. P. Selinger, “Efficient Clifford+$T$ approximation of single-qubit operators,” Quantum Information and Computation 15, 159–180 (2015), arXiv:1212.6253.
15. C. M. Dawson and M. A. Nielsen, “The Solovay–Kitaev algorithm,” Quantum Information and Computation 6, 81–95 (2006), arXiv:quant-ph/0505030.
16. 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.
17. M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, 10th anniversary ed., Cambridge University Press (2010), doi:10.1017/CBO9780511976667.