General theory of temporary escape
On this page · Permalink · Source line 1
8.1 Nested gate models and distortion invariants
On this page · Permalink · Source line 2
8.1.1 Why a separate theory is needed
On this page · Permalink · Source line 10
A target transformation often belongs to a visibly structured class even when the machine used to realize it is capable of much more. A lower-triangular linear transformation may be synthesized by an unrestricted CNOT network. A diagonal unitary may be realized by a non-diagonal Clifford+\(T\) circuit. A charge-preserving unitary may be compiled by gates that temporarily visit other charge sectors. A Gaussian target may be realized by a circuit that briefly uses a non-Gaussian primitive. These situations share a question that is not answered by ordinary exact synthesis:
How much does it cost to require the entire path of a computation to retain the structure possessed by its endpoint?
The distinction is path dependent. It is not determined only by membership of the final target in a subgroup, a subcategory, or a model class.
8.1.2 Exact gate models
On this page · Permalink · Source line 24
Definition 8.1: Gate model
An exact gate model is a tuple
where \(\mathcal X\) is a set of states or morphisms, \(\mathcal S\) is a specified family of elementary generators, \(c:\mathcal S\to{\mathbb R}_{\ge0}\) is a cost function, and \(\circ\) is the composition law. A word
has cost
For a target \(U\in\mathcal X\), the exact synthesis cost is
The value is \(+\infty\) when the target has no realization.
The composition law may be group multiplication, composition of permutations, composition of quantum channels, tensor-network contraction, or composition in a dagger symmetric monoidal category. The additive cost may count all gates, only entangling gates, only non-Clifford gates, weighted error, or a vector of several resources. Depth fits this additive model by taking admissible parallel layers as generators, rather than charging one unit to each individual gate.
Definition 8.2: Nested realization pair
A nested realization pair consists of restricted and ambient models
with a common target class \(\mathcal T\) of finite ambient cost and the same cost on common generators. For \(U\in\mathcal T\), define
The additive defect is
When both costs are finite, \(\Delta(U)\) is a metric or optimization defect. If \({\ell_{\mathrm{res}}}(U)=+\infty\) and \({\ell_{\mathrm{amb}}}(U)<+\infty\), it is an existence defect. This convention unifies finite gate savings with the failure of a restricted realization category.
Proposition 8.3: Monotonicity
For every target in the common domain,
Consequently \(\Delta(U)\ge0\) whenever both models use the same nonnegative cost on their common generators.
Proof
Every restricted word is also an ambient word.
8.1.3 Cost models are part of the theorem
On this page · Permalink · Source line 77
A gate-set comparison is incomplete until the cost convention is fixed. The same pair of groups can display a defect under entangling count and no defect under total primitive count. A SWAP gate may be primitive, may cost three CNOTs, or may be implemented by physical motion. A local Clifford may be free in a fault-tolerant resource estimate and nonfree in a pulse-level model.
Definition 8.4: Resource vector
Let
be the resource vector of a gate. The achievable resource region of a target is
Its nondominated points form the Pareto boundary.
For a weight vector \(\lambda\in{\mathbb R}_{\ge0}^r\), scalarization gives
The scalar defect \(\Delta^\lambda(U)\) can vary with \(\lambda\) even when the target and gate alphabets are fixed.
Principle 8.5: Model specificity
Every claimed shortcut must state the target class, elementary gate alphabet, ancilla convention, exact or approximate synthesis criterion, and cost vector. Changing any one of these may remove, create, or reverse a defect.
8.1.4 Ancilla and restoration conventions
On this page · Permalink · Source line 115
Temporary workspace is meaningful only after its restoration rule is specified.
Definition 8.6: Ancilla conventions
An ancilla is
clean if it begins in a specified state and must return to that state,
borrowed or dirty if its initial state is arbitrary but must be restored,
consumable if restoration is not required,
catalytic if it is restored while enabling a cheaper realization of the target.
The present theory focuses on restoration. If an auxiliary resource may be discarded, the comparison becomes a different channel or isometry synthesis problem.
8.1.5 Worst-case and threshold functions
On this page · Permalink · Source line 128
For a size parameter \(n\), let \(\mathcal T_n\) denote the target family.
Definition 8.7: Extremal distortion
Define
and, when \(0<{\ell_{\mathrm{amb}}}(U)<\infty\),
The first defective size is
We set a threshold to \(+\infty\) when its defining set is empty.
Several threshold notions should not be conflated:
where \(\ell_{\le q}\) permits at most \(q\) ambient-only gates. A model may have an early metric threshold and a later existence threshold, or no threshold at all.
8.1.6 Equivalence, orbits, and classification
On this page · Permalink · Source line 155
A finite census should be quotiented by transformations preserving both gate models and the cost. Depending on the problem, these may include wire permutations, local Clifford conjugation, isotopy, simultaneous row and column relabeling, or graph automorphisms.
Definition 8.8: Cost-preserving equivalence
Targets \(U\) and \(V\) are equivalent if an automorphism \(\varphi\) of the ambient realization system satisfies
and preserves the gate costs.
Under this equivalence, both lengths and the defect are orbit invariants. A useful threshold theorem should classify minimal defective orbits, not merely list raw matrices.
8.1.7 Approximate synthesis and border defects
On this page · Permalink · Source line 171
For continuous gate models, exact word length can differ from the minimum length achievable as a limit.
Definition 8.9: Border cost
Let \(\overline{\mathcal W}_{L}\) be the topological or Zariski closure of targets realizable with cost at most \(L\). The border cost is
The border defect is
This is the circuit analogue of the distinction between tensor rank and border rank. An exact defect can disappear under degeneration, persist, or become larger after approximation changes the relevant cost geometry.
8.1.8 Metric and existence defects in one category
On this page · Permalink · Source line 187
Let \(\mathcal C_{\mathrm{res}}\subseteq\mathcal C_{\mathrm{amb}}\) be categories with weighted generating morphisms. For a morphism \(f\) in the restricted target class, the same definition
includes group-word metrics, adaptive quantum channels, tensor-network realizations, and orthogonality designs. This categorical form is essential when the ambient model permits measurement, branching, postselection, or entangled objects that do not lie in a common group.
Scope boundary
The abstract definition does not prove that a defect exists. It provides a common language in which a finite search, a symbolic identity, and a lower-bound certificate can be compared without changing the meaning of the target or the cost.
8.1.9 A standard theorem package
On this page · Permalink · Source line 198
A mature gate-set distortion result should contain as many of the following components as the model allows:
a precisely defined nested gate pair and cost vector,
a smallest defective target or a no-defect theorem below a threshold,
an explicit ambient word,
a restricted lower-bound certificate,
classification modulo cost-preserving equivalence,
a reusable catalytic normal form,
direct-sum, recursive, or tensor amplification,
generic-rigidity or sparsity results,
a certificate-producing implementation,
a clear account of which statements are symbolic, computed, or conjectural.
The remainder of the monograph follows this package.