Circuit Optimization

Circuit optimization rewrites a circuit to reduce a chosen cost while preserving the computation. Cancelling inverse gates is one example; adding ancillas to shorten the execution depth is another. A useful rewrite must preserve all outputs that later operations use, including classical measurement results and retained quantum states.

Required background. Circuit representations explain the operation and output definitions; gate decomposition constructs gate sequences; the circuit model fixes time order, subsystems and measurements.

Circuit rewrites and observable outputs

For a static unitary circuit on the same input and output wires, a common exact contract is

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

where a global phase is allowed only if the surrounding context makes it unobservable. If the block can later be controlled, used on one interferometer branch, or compared with a phase reference, literal equality or an explicitly propagated phase correction may be required.

Approximate optimization must name both metric and budget. One possible contract is

$$\min_{\phi\in\mathbb R} \left\| U(C')-e^{i\phi}U(C) \right\|_{\mathrm{op}} \leq \epsilon_{\mathrm{opt}}.$$

Near-equality is not an automatic license to delete a small rotation. It is a different compiler mode whose error must be composed with algorithmic, synthesis, numerical, and physical error budgets. Error Estimates develops the distinction between a residual, a bound, and a certified tolerance.

Unitary equality is insufficient for dynamic circuits. Measurements, resets, discarded systems, and classical branches define a channel or, when outcomes are retained, a quantum instrument. If $\mathcal I_y^C$ is the trace-nonincreasing map associated with output record $y$, exact instrument-level equivalence asks for

$$\begin{aligned} \mathcal I_y^{C'}(\rho) &= \mathcal I_y^C(\rho), \\ &\text{for all }\rho\text{ and retained }y. \end{aligned}$$

This requirement preserves both $p(y|\rho)=\operatorname{Tr}\mathcal I_y^C(\rho)$ and the conditional output state when the outcome has nonzero probability. The distribution and the unconditioned channel each contain less information than the instrument, but neither determines the other. Relabeling outcomes can change their probabilities without changing the summed channel. Conversely, applying $X$ after a $Z$ measurement changes the output state without changing the recorded probabilities. Exercise 9 develops both examples. Quantum Instruments is the canonical treatment of these distinctions.

Ancillas introduce another boundary. An exact clean-ancilla rewrite may need

$$U(C') \bigl( |\psi\rangle\otimes|0^a\rangle \bigr) = e^{i\phi} U(C) |\psi\rangle\otimes|0^a\rangle$$

for every data state $|\psi\rangle$, including restoration of all $a$ ancillas. It is sufficient to establish this vector identity on a basis with a common phase: linearity then extends it to every input and external reference. Matching only basis-output probabilities, or allowing a different untracked phase for each basis vector, is insufficient. Tracing out garbage also gives a weaker comparison when restored ancillas are required.

Gate count, depth and execution time

Choose the cost before comparing two circuits. An entangler count measures different work from a $T$ count or the longest chain of dependent operations. On a fault-tolerant device, reducing $T$ depth may require more qubits and Clifford operations. On a simulator, fusing gates can reduce runtime without improving a hardware circuit.

Keep several costs when they trade against each other. A candidate is Pareto dominated if another is no worse in every retained cost and better in at least one. A weighted sum or a stated priority order can choose among the remaining candidates. Neither choice makes the weights universal physical constants. Resource estimation connects these circuit costs to an architecture.

Expose the Dependency Structure

A textual gate list contains an arbitrary choice of order among operations that could run or move independently. For a static circuit or a finite unrolled execution, optimizers can construct a dependency directed acyclic graph

$$D_C = \bigl( V,\, E_q\cup E_c\cup E_t\cup E_f \bigr),$$

where vertices are operations and edges encode quantum-resource order, classical data flow, timing constraints, and semantic fences. A topological order respects these precedence edges, but an executable schedule also assigns start times and respects resource and result-readiness constraints. General adaptive loops are not one finite DAG.

Operations on disjoint subsystems commute. Operations sharing a subsystem may also commute, but this must follow from their semantics rather than their diagrammatic appearance. For unitary gates $A$ and $B$,

$$AB=BA \quad\Longleftrightarrow\quad [A,B]=0.$$

For Pauli strings, write a Pauli modulo phase as $P(\mathbf a,\mathbf b)$ with $X$ support $\mathbf a$ and $Z$ support $\mathbf b$. Then

$$\begin{aligned} P(\mathbf a,\mathbf b) P(\mathbf c,\mathbf d) &= (-1)^\omega P(\mathbf c,\mathbf d) P(\mathbf a,\mathbf b), \\ \omega &= \mathbf a\mathbin{\cdot}\mathbf d + \mathbf b\mathbin{\cdot}\mathbf c \pmod 2. \end{aligned}$$

The strings commute exactly when $\omega=0$. Their rotations then commute as well:

$$\begin{aligned} \omega=0 &\quad\Longrightarrow\quad R_P(\alpha)R_Q(\beta) \\ &= R_Q(\beta)R_P(\alpha). \end{aligned}$$

Gate-specific commutation rules are often cheaper to check. For $\operatorname{CNOT}_{c\to t}$,

$$\begin{aligned} \operatorname{CNOT}_{c\to t}R_{z,c}(\theta) &= R_{z,c}(\theta)\operatorname{CNOT}_{c\to t}, \\ \operatorname{CNOT}_{c\to t}R_{x,t}(\theta) &= R_{x,t}(\theta)\operatorname{CNOT}_{c\to t}. \end{aligned}$$

The analogous $R_{z,t}$ and $R_{x,c}$ moves are not generally valid. A rewrite engine should encode the positive rule and its side conditions, not infer a visual symmetry that the gate does not possess.

Barriers require a declared meaning. A semantic fence forbids movement because an external timing, calibration, or observation contract depends on the boundary. A display-only barrier may be ignored. Treating both spellings as the same object either blocks useful work or changes behavior.

Local Simplification and Canonicalization

The cheapest passes remove algebraic redundancy:

$$\begin{aligned} GG^\dagger &= I, \\ R_P(\alpha)R_P(\beta) &= R_P(\alpha+\beta), \\ R_P(0) &= I. \end{aligned}$$

This includes deleting identities, canceling adjacent self-inverse gates, fusing rotations about the same Pauli axis, normalizing angles, removing dead classical calculations, and canonicalizing equivalent gate spellings. A commutation pass can bring matching operations together before the local rule fires.

Angle normalization must respect the equivalence contract. With

$$R_P(\theta) = e^{-i\theta P/2},$$

one has

$$\begin{aligned} R_P(\theta+2\pi) &= -R_P(\theta), \\ R_P(\theta+4\pi) &= R_P(\theta). \end{aligned}$$

Reduction modulo $2\pi$ is valid up to global phase for an isolated unitary, but modulo $4\pi$ is needed for literal matrix equality. The sign can become a relative phase after adding a control. An angle reduction must therefore preserve the phase convention of the surrounding computation.

Local rules should also preserve parameter domains. The exact symbolic rule

$$R_z(a\theta+b)R_z(c\theta+d) = R_z\bigl((a+c)\theta+b+d\bigr)$$

holds for every allowed $\theta$. Replacing a rotation because its angle is small at one sampled parameter value is approximate specialization, not symbolic optimization.

Worked example: merge two parity rotations

Writing $C_{12}=\operatorname{CNOT}_{1\to2}$, the standard decomposition

$$\mathcal Z_{12}(\theta) = e^{-i\theta Z_1Z_2/2} = C_{12} R_{z,2}(\theta) C_{12}$$

can arise twice in succession. Expanding both blocks gives

$$\begin{aligned} \mathcal Z_{12}(\alpha) \mathcal Z_{12}(\beta) &= C_{12} R_z(\alpha) C_{12} {}\times C_{12} R_z(\beta) C_{12}\\ &= C_{12} R_z(\alpha+\beta) C_{12}\\ &= \mathcal Z_{12}(\alpha+\beta). \end{aligned}$$

The middle CNOTs cancel and the rotations fuse. The result reduces four entanglers to two, or to zero when $\alpha+\beta$ is an allowed identity angle. This example also shows why pass order matters: expanding structured operations can expose a cancellation, while expanding too early can hide larger algebraic structure.

Peepholes, Templates, and Superoptimization

A peephole optimizer selects a small subcircuit $W$, computes or recognizes its semantics, and replaces it by a cheaper equivalent $W'$. Exact matrix comparison is practical only for small wire counts, but a window can also be classified by a Clifford tableau, binary linear map, phase polynomial, or another compact invariant.

Template methods begin with an identity

$$T = G_0G_1\cdots G_{m-1} \simeq I.$$

If commutation and pattern matching identify a costly product $A$ from this template inside the circuit, the relation $AB\simeq I$ implies

$$A \simeq B^\dagger.$$

Replacing $A$ by $B^\dagger$ is profitable when the chosen cost of $B$ is smaller and every side condition is satisfied. Templates can reach beyond adjacent cancellation while remaining interpretable and fast.

Window resynthesis searches more broadly. It may enumerate circuits up to a size bound, use meet-in-the-middle tables, invoke a canonical synthesizer, or apply numerical optimization to a parameterized ansatz. Superoptimization extends this idea by generating equivalence classes or candidate identities and searching them under a cost model. Because exhaustive search grows rapidly, practical systems restrict width, gate count, parameter form, or search time.

Rewrite direction needs a termination policy. If every accepted exact rule strictly decreases a well-founded lexicographic score, repeated rewriting terminates, though possibly at a poor local minimum. Bidirectional rules such as commutation can loop. Equality-saturation systems avoid committing to one direction by storing many equivalent forms and performing cost extraction later, but their equivalence graph can itself grow beyond practical limits.

Exploit Algebraic Structure

Local matrices are not the only useful semantics. Different circuit fragments admit different compact descriptions.

Fragment	Compact semantics	Typical optimization
CNOT network	invertible binary matrix	block resynthesis and Gaussian-style elimination
CNOT plus diagonal phases	linear map plus phase polynomial	parity-term fusion and resynthesis
Clifford circuit	symplectic map and phase data	tableau reduction and Clifford resynthesis
Pauli rotations	labeled Pauli strings and angles	commuting sets, phase gadgets, shared parity networks
reversible classical circuit	basis-state permutation or Boolean map	templates and reversible-logic resynthesis
general bounded-width window	dense unitary or channel	exact or approximate peephole search
ZX diagram	typed open graph with rewrite semantics	graph simplification and circuit extraction

The optimizer should move into a representation whose equality test and rewrite rules match the fragment, then return with a checked extraction procedure. No one representation makes every optimization easy.

Linear reversible blocks

A CNOT-only circuit acts on computational-basis strings as

$$|x\rangle \longmapsto |Ax\rangle, \qquad A\in GL(n,\mathbb F_2).$$

Each CNOT is an elementary row operation over $\mathbb F_2$. An optimizer can accumulate a maximal block into $A$ and resynthesize the map rather than preserve an inefficient historical sequence. On unrestricted connectivity, the worst-case CNOT count can be made $\Theta(n^2/\log n)$, asymptotically improving ordinary one-row-at-a-time elimination. Connectivity-constrained synthesis belongs with mapping and routing; the algebraic target $A$ should be retained for that later pass.

Phase polynomials

Let

$$\Phi(\alpha) = \operatorname{diag}(1,e^{i\alpha}).$$

A circuit over CNOT and these phase gates acts as

$$C|x\rangle = e^{if(x)} |Ax\rangle,$$

where $A\in GL(n,\mathbb F_2)$ and

$$f(x) = \sum_{j=1}^{m} \alpha_j\ell_j(x) \pmod{2\pi}.$$

Each $\ell_j:\mathbb F_2^n\to\mathbb F_2$ is a parity function, embedded as $0$ or $1$ in the phase. A CNOT updates the live parity labels; a phase gate adds its angle to the label currently carried by its wire. Terms with the same $\ell_j$ can be combined, and a coefficient equal to zero modulo $2\pi$ disappears.

The pair $(A,f)$ specifies the action on every basis vector, including its phase, and therefore on every superposition. Comparing basis-output bit strings alone would miss $f$ entirely. Polynomial expressions for $f$ are not unique: equality means the same phase on every Boolean input, not the same list of terms.

This representation sees cancellations separated by long CNOT networks. It also distinguishes the final linear transformation $A$ from the phase function $f$, so either part can be resynthesized. Since

$$\Phi(\alpha) = e^{i\alpha/2}R_z(\alpha),$$

converting between phase-gate and $R_z$ conventions requires tracking global phase whenever the context is phase-sensitive.

For Clifford+$T$ circuits, coefficients are multiples of $\pi/4$. Odd coefficients represent non-Clifford phase terms, while even coefficients are Clifford phases. Reducing the number or layering of odd terms can lower $T$ count or $T$ depth. For important diagonal families, $T$-count reduction is related to decoding punctured Reed–Muller codes; more generally, common gate-count and depth optimization problems are NP-hard. Efficient heuristics and restricted exact algorithms are therefore central, not temporary substitutes for a known universal polynomial-time optimizer.

Clifford and Pauli structure

A Clifford circuit maps Paulis to Paulis under conjugation, so its action can be stored as a binary symplectic transformation plus phase data. Large Clifford windows can then be compared and resynthesized without constructing a $2^n\times2^n$ matrix. Stabilizer Formalism develops the tableau and symplectic representation.

Circuits dominated by Pauli rotations benefit from grouping commuting strings, combining identical rotations, and sharing parity-computation networks. A phase gadget represents a parity-dependent phase independently of one particular CNOT ladder. Keeping the gadget abstract allows a later extractor to trade entangler count against depth or connectivity.

ZX-calculus

The ZX-calculus translates circuits into open diagrams whose sound rewrite rules can expose nonlocal Clifford and phase structure. Graph transformations such as local complementation and pivoting can simplify a diagram before a new circuit is extracted. This can reveal cancellations hidden from fixed-width peepholes.

Three claims must remain separate:

• every applied graphical rewrite is sound in the declared fragment;
• the chosen rewrite strategy reaches a useful reduced diagram;
• circuit extraction succeeds and improves the selected circuit cost.

Soundness does not imply that a heuristic finds a global optimum, and a smaller diagram need not extract to a cheaper circuit under every gate alphabet. Completeness is also fragment-dependent. When comparing extracted circuits, retain the scalar convention and evaluate their cost again; deleting a diagram scalar can discard a relevant phase.

Depth Reduction and Scheduling

For a dependency graph with operation duration $d(v)$, an abstract critical path is

$$D(C) = \max_{\pi\in\operatorname{Paths}(D_C)} \sum_{v\in\pi}d(v).$$

Taking $d(v)=1$ gives layer depth; assigning gate-class durations gives a weighted depth. Without additional resource conflicts or edge delays, earliest-start scheduling attains this critical-path time. With shared resources it is a lower bound; any feasible schedule gives an upper bound on the optimum. A result-readiness delay must also be included on its dependency edge. An as-late-as-possible schedule, relative to a chosen finish time, reveals slack. Commutation can remove avoidable order edges, and resynthesis can change the graph itself.

Count and depth can move in opposite directions. Parallelizing parity computations may require more ancillas or CNOTs. Minimizing $T$ depth can leave $T$ count unchanged and increase Clifford work. A target-independent depth claim should therefore state:

• operation durations or the unit-layer convention;
• which operations conflict for resources;
• whether classical feedforward has zero or nonzero latency;
• whether connectivity and movement are included;
• whether ancillas may be introduced.

Physical placement, routing, crosstalk, calibrated durations, and controller timing can reverse an abstract schedule. Those refinements belong to their later canonical pages.

Pass Ordering and Fixed Points

Optimization passes generally do not commute:

$$\mathcal O_2\!\left(\mathcal O_1(C)\right) \neq \mathcal O_1\!\left(\mathcal O_2(C)\right).$$

Rotation fusion before finite-alphabet synthesis can approximate one angle instead of two. Decomposition can expose adjacent inverses. Local cleanup can make a larger resynthesis window recognizable. Routing can introduce SWAP or direction-correction gates that create new local cancellations. Conversely, premature decomposition can erase a high-level operation that a structure-aware pass would optimize better.

Alternate inexpensive cancellation with structural rewrites or bounded search when one exposes opportunities for another. Stop when no permitted rewrite improves the score, or when the search budget ends. Such a fixed point is a property of the chosen passes, not a proof that no cheaper circuit exists. Nam and colleagues give concrete examples of complementary passes; Hietala and colleagues show how transformations can be proved correct.

Parameterized and Approximate Circuits

Parameterized circuits require identities valid on the declared parameter domain. An optimizer may:

• combine affine angle expressions exactly;
• propagate known periodicities and constants;
• factor shared parameter expressions;
• use commutation conditions independent of parameter values;
• specialize only after parameters are bound.

Numerical sampling of several parameter values is not proof of a symbolic identity. Branch cuts in Euler angles, floating-point comparisons near multiples of $2\pi$, and assumptions such as $\theta\neq0$ should be explicit. For variational workloads, an approximate rewrite can also alter derivatives and the objective landscape even when sampled unitaries are close.

Approximate block replacement should return a residual in a composable metric. If unitary replacements satisfy

$$\left\| U_j-V_j \right\|_{\mathrm{op}} \leq \epsilon_j,$$

then a telescoping argument gives the conservative bound

$$\left\| U_m\cdots U_1 - V_m\cdots V_1 \right\|_{\mathrm{op}} \leq \sum_{j=1}^{m}\epsilon_j.$$

This bound may be loose, but it prevents an optimizer from spending the same global tolerance independently in every window. Gate Decomposition owns synthesis-error allocation and finite-alphabet approximation.

Measurements, Resets, and Classical Control

Dynamic operations break many unitary intuitions:

• measurement is not invertible, so it has no cancellation partner;
• reset discards input information and is not an inverse of preparation;
• moving a gate through measurement can change the measured observable;
• branch-local rewrites must preserve classical labels and branch conditions;
• dead-branch elimination needs a proof that the condition is unreachable;
• moving work across a feedback boundary can change latency and noise exposure.

Let $P_y=|y\rangle\langle y|$ be the projectors of a $Z$ measurement. Applying $X$ first and reporting $y$ has branch operator $P_yX$. The identity

$$P_yX=XP_{y\oplus1}$$

gives an exact rewrite: measure first, apply $X$ to the retained qubit, and return the complemented measurement bit. This preserves the entire instrument, including correlations with an external system. If the qubit is discarded, omit the final $X$ and complement only the bit. Leaving the qubit unchanged when it is retained generally fails. Classical feedforward must use the same complemented label consistently.

Checking a proposed rewrite

For static circuits on a small number of wires, form $M=U(C')^\dagger U(C)$. Agreement up to an allowed global phase requires $M=e^{i\phi}I$. If numerical residuals are used, evaluate the stated metric; gate decomposition explains why average and worst-case residuals differ.

Larger circuits can use Clifford tableaux, phase polynomials, decision diagrams, tensor contraction or proved graphical rules. A checker may return “unknown” because its method is inconclusive; that is different from finding a counterexample. Testing the particular output of an optimizer is often called translation validation. Proving a primitive rule is useful only when its side conditions also hold at the place where it is applied.

For dynamic programs compare outcome-resolved maps, or the specified subset of outputs. For ancilla-assisted changes include preparation, discard or restoration explicitly. Random-state tests are useful diagnostics, not an equivalence proof. Mathematical correctness of the ideal rewrite also does not imply equal physical noise: a shorter circuit can use a noisier native gate or expose a different idle interval. See error-aware compilation.

Exercises

1. Fuse rotations with the correct period

Simplify $R_z(\alpha)R_z(\beta)$ and state when an angle may be reduced modulo $2\pi$ rather than $4\pi$.

Solution

The generators are identical, so their exponentials commute and combine:

$$R_z(\alpha)R_z(\beta) = R_z(\alpha+\beta).$$

Because $R_z(\theta+2\pi)=-R_z(\theta)$, reduction modulo $2\pi$ preserves the operation only up to global phase. It is valid when the equivalence contract quotients global phase and the block cannot later be controlled or placed in a phase-sensitive context. Literal matrix equality uses period $4\pi$.

2. Test Pauli commutation

Determine whether $P=X_1Y_2Z_4$ commutes with $Q=Z_1Y_2X_3$, and decide whether their rotations may be reordered.

Solution

On qubit $1$, $X$ and $Z$ anticommute. On qubit $2$, the two $Y$ operators commute. On qubit $3$, $P$ is identity, and on qubit $4$, $Q$ is identity. There is one anticommuting overlap, so

$$PQ=-QP.$$

The strings do not commute, and generic rotations $R_P(\alpha)$ and $R_Q(\beta)$ cannot be reordered. Special angles can produce accidental identities, but they require a separate parameter-aware proof.

3. Optimize two ZZ gadgets

Starting from the decomposed circuit for $\mathcal Z_{12}(\alpha)\mathcal Z_{12}(-\alpha)$, count the CNOTs before and after local optimization.

Solution

Each gadget initially contains two CNOTs, so the concatenation has four. The two middle CNOTs cancel. The remaining rotations fuse:

$$R_z(\alpha)R_z(-\alpha)=I.$$

The two outer CNOTs then become adjacent and cancel. The optimized circuit is the identity with zero CNOTs. The result is exact, including global phase, because $\mathcal Z_{12}(\alpha)\mathcal Z_{12}(-\alpha)=I$.

4. Extract a phase polynomial

On basis input $(x_1,x_2)$, perform in temporal order $\Phi_2(\beta)$, $\operatorname{CNOT}_{1\to2}$, $\Phi_2(\alpha)$, and $\operatorname{CNOT}_{1\to2}$. Find $A$ and $f(x)$.

Solution

The first phase contributes $\beta x_2$. After the first CNOT, wire $2$ carries $x_1\oplus x_2$, so the second phase contributes $\alpha(x_1\oplus x_2)$. The final CNOT restores the input bits. Hence

$$\begin{aligned} A &= I, \\ f(x) &= \beta x_2 + \alpha(x_1\oplus x_2) \pmod{2\pi}. \end{aligned}$$

Any later phase term on the same parity $x_1\oplus x_2$ can be fused by adding its coefficient modulo $2\pi$.

5. Use an identity template

Suppose an exact template factors as $T=AB=I$. Prove the replacement $A\mapsto B^\dagger$ and give one condition beyond gate count that can make it undesirable.

Solution

From $AB=I$, right multiplication by $B^\dagger$ gives

$$A=B^\dagger.$$

The rewrite is therefore exact when the matched gates satisfy every template side condition. Even if $B^\dagger$ uses fewer gates, it may have greater critical-path depth, more expensive gate classes, unsupported inverse gates, additional ancillas, or worse connectivity. Acceptance must use the declared cost and legality contract.

6. Compute weighted depth

A dependency graph has edges $a\to c$, $b\to c$, $c\to d$, and $b\to e$. Durations are

$$\begin{aligned} d(a)&=2,\quad d(b)=3,\quad d(c)=4, \\ d(d)&=1,\quad d(e)=5. \end{aligned}$$

Find the critical-path depth.

Solution

The maximal path weights are

$$\begin{aligned} a\to c\to d &: 2+4+1=7, \\ b\to c\to d &: 3+4+1=8, \\ b\to e &: 3+5=8. \end{aligned}$$

Thus $D(C)=8$. There are two critical paths. Removing only one of them does not necessarily reduce total depth.

7. Explain a pass-order advantage

Two adjacent rotations $R_z(\alpha)$ and $R_z(\beta)$ must be approximated over a finite gate alphabet. Why can fusion before synthesis outperform synthesis before fusion?

Solution

Fusion gives one exact symbolic target,

$$R_z(\alpha+\beta),$$

which needs one approximation and one allocated error budget. Synthesizing the two rotations separately produces two gate words, may spend two error allocations, and can hide the exact angle relation from a later local pass. The later pass might still cancel parts of the words, but it is not guaranteed to recover a near-optimal approximation of the combined angle. This is why high-level algebraic optimization should normally precede irreversible finite-alphabet lowering.

8. Preserve a measurement rewrite

A circuit applies $X$, measures $Z$, and returns the classical result. Can the $X$ be moved after measurement while preserving the declared output?

Solution

Not without changing the classical processing. For input $\rho$, applying $X$ before $Z$ measurement exchanges the probabilities of outcomes $0$ and $1$. Measurement first gives the unexchanged label. An equivalent rewrite may measure first and then return the complemented classical bit $y'=y\oplus1$.

If the post-measurement qubit is retained, also apply $X$ after measurement. The equality $XP_{y\oplus1}=P_yX$ proves equality of the branch operators, so both the state and reported label agree for arbitrary inputs. If the qubit is discarded, its final $X$ can be omitted.

9. Separate a distribution from a channel

Compare three instruments, with $y=0,1$:

$$\begin{aligned} \mathcal I_y(\rho)&=P_y\rho P_y,\\ \mathcal J_y(\rho)&=XP_y\rho P_yX,\\ \mathcal K_y(\rho)&=P_{1-y}\rho P_{1-y}. \end{aligned}$$

Which pairs have the same outcome probabilities? Which have the same unconditioned channel? Give an input that distinguishes the others.

Solution

$\mathcal I$ and $\mathcal J$ have the same probabilities because unitary conjugation preserves trace. Their summed channels differ: on $|0\rangle$ they return $|0\rangle$ and $|1\rangle$, respectively. Meanwhile, $\sum_y\mathcal I_y=\sum_y\mathcal K_y$ by relabeling the sum, but their outcomes on $|0\rangle$ are deterministically $0$ and $1$. Thus neither a distribution nor an unconditioned channel alone fixes the other or the full instrument.

10. Small function error need not mean small gradient error

For $0<\epsilon\ll1$, compare $U(\theta)=I$ with $V(\theta)=R_z[\epsilon\sin(\theta/\epsilon^2)]$. Bound their operator-norm distance uniformly and compare their derivatives at $\theta=0$.

Solution

For $R_z(a)$, the eigenvalues give $\|R_z(a)-I\|_{\mathrm{op}}=2|\sin(a/4)|\leq|a|/2$. Here $|a|\leq\epsilon$, so the gate error is at most $\epsilon/2$ for every $\theta$. Nevertheless,

$$U'(0)=0, \qquad V'(0)=-\frac{iZ}{2\epsilon}.$$

The derivative error grows as $1/(2\epsilon)$. A synthesis tolerance on gate values alone does not control gradients in a variational algorithm.

References

• M. Amy, D. Maslov, and M. Mosca, “Polynomial-time $T$-depth optimization of Clifford+$T$ circuits via matroid partitioning,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 33, 1476–1489 (2014), doi:10.1109/TCAD.2014.2341953.
• J. van de Wetering and M. Amy, “Optimising quantum circuits is generally hard,” arXiv:2310.05958, version 3 (2024), arXiv:2310.05958.
• L. E. Heyfron and E. T. Campbell, “An efficient quantum compiler that reduces $T$ count,” Quantum Science and Technology 4, 015004 (2018), doi:10.1088/2058-9565/aad604.
• M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, 10th anniversary ed., Cambridge University Press (2010), doi:10.1017/CBO9780511976667.
• A. Cowtan, S. Dilkes, R. Duncan, W. Simmons, and S. Sivarajah, “Phase gadget synthesis for shallow circuits,” in Proceedings of QPL 2019, EPTCS 318, 213–228 (2020), doi:10.4204/EPTCS.318.13.
• R. Duncan, A. Kissinger, S. Perdrix, and J. van de Wetering, “Graph-theoretic simplification of quantum circuits with the ZX-calculus,” Quantum 4, 279 (2020), doi:10.22331/q-2020-06-04-279.
• K. Hietala, R. Rand, S.-H. Hung, X. Wu, and M. Hicks, “A verified optimizer for Quantum circuits,” Proceedings of the ACM on Programming Languages 5, POPL, Article 37 (2021), doi:10.1145/3434318.
• S. Yamashita and I. L. Markov, “Fast equivalence-checking for quantum circuits,” in Proceedings of NQCC 2010, 23–28 (2010), arXiv:0909.4119.
• D. Maslov, G. W. Dueck, D. M. Miller, and C. Negrevergne, “Quantum circuit simplification and level compaction,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 27, 436–444 (2008), doi:10.1109/TCAD.2007.911334.
• M. Amy and M. Mosca, “$T$-count optimization and Reed–Muller codes,” IEEE Transactions on Information Theory 65, 4771–4784 (2019), doi:10.1109/TIT.2019.2906374.
• Y. Nam, N. J. Ross, Y. Su, A. M. Childs, and D. Maslov, “Automated optimization of large quantum circuits with continuous parameters,” npj Quantum Information 4, 23 (2018), doi:10.1038/s41534-018-0072-4.
• K. N. Patel, I. L. Markov, and J. P. Hayes, “Efficient synthesis of linear reversible circuits,” Quantum Information and Computation 8, 282–294 (2008), arXiv:quant-ph/0302002.
• T. Peham, L. Burgholzer, and R. Wille, “Equivalence checking of quantum circuits with the ZX-calculus,” IEEE Journal on Emerging and Selected Topics in Circuits and Systems 12, 662–675 (2022), doi:10.1109/JETCAS.2022.3202204.
• A. Kissinger and J. van de Wetering, “Reducing $T$-count with the ZX-calculus,” Physical Review A 102, 022406 (2020), doi:10.1103/PhysRevA.102.022406.
• M. Xu et al., “Quartz: Superoptimization of quantum circuits,” in Proceedings of PLDI 2022, 625–640 (2022), doi:10.1145/3519939.3523433.