Related papers: An Exactness Barrier for ZX-Calculus Optimization of Synthesized Clifford+T Circuits

An Exactness Barrier for ZX-Calculus Optimization of Synthesized Clifford+T Circuits

URL: http://arxiv.org/abs/2608.22801v1
Date: Mon, 24 Aug 2026 04:53:20 GMT
Title: An Exactness Barrier for ZX-Calculus Optimization of Synthesized Clifford+T Circuits
Abstract summary: Gate and circuit optimization are usually studied separately.<n>We show both behaviours follow from a single bound.<n>This explains and predicts the size of the near-null optimization pipeline.
Score: 3.825239835665478
License: http://creativecommons.org/licenses/by-nc-nd/4.0/
Abstract: Gate synthesis and circuit optimization are usually studied separately, and evidence on their interaction is contradictory: ZX-calculus rewriting removes a stable fraction of Solovay-Kitaev circuits, yet almost nothing from number-theoretically synthesized circuits. We show both behaviours follow from a single bound. For any optimizer that preserves the implemented element exactly--including all sound ZX rewriting with extraction--the achievable T-count is bounded below by the denominator exponent of the synthesized ring element. This exactness barrier is computable per instance and separates exact post-processing from approximation-aware resynthesis by a certified factor reaching 101x at recursion depth five. The two behaviours are then the barrier operating at different distances from the floor. For Solovay-Kitaev circuits we prove that the local ZX simplification layer (spider fusion and identity removal) computes exactly the free-product normal form of Z_2 * Z_8, giving exact per-instance compression and, under a calibrated ergodicity hypothesis, a depth-independent limit law confirmed on two independently constructed nets. For number-theoretically synthesized circuits the floor is already saturated: on single-qubit words automated ZX simplification attains it exactly, via a closed-form formula for minimal T-count in terms of phase linkage through the Z-axis normalizer. At two qubits and beyond the same valuation yields unconditional rigidity certificates, which on the quantum-Shannon-decomposition plus gridsynth pipeline certify 99.4-99.9% of the synthesized T-count as incompressible, with rigidity strengthening as accuracy tightens. This explains, and predicts the size of, the near-null optimization recently reported for that pipeline.

Related papers

Near-optimal synthesis of non-Gaussian phase gates via qubit-oscillator Rabi control [10.877976778339495]
We develop an efficient qubit-oscillator Rabi synthesis scheme for phase gates.<n>We show that a degree-(R) phase gate can be approximated by an analytically constructed Rabi sequence with total time.
arXiv Detail & Related papers (2026-09-08T17:53:18Z)
Encoding Compact U(1) Gauge Fields in Bosonic Modes with GKP Stabilization [0.0]
We bridge the gap between bosonic quantum hardware and compact lattice gauge theories.<n>A one-to-one encoding becomes exact in the limit of infinite squeezing.<n>A one-plaquette example reproduces the exact compact-rotor dynamics.
arXiv Detail & Related papers (2026-08-31T18:01:02Z)
New Methods and Frameworks for Quantum State Preparation in Modern Quantum Systems [0.0]
It derives two syntheses built on the Digital Signal-induced Heap Transform (DsiHT): the QsiHT Fast Path Real Synthesis and the QsiHT Fast Path Complex Synthesis.<n>Both are benchmarked against ten configurations spanning the UCR, isometry, multiplexor, Schmidt/SVD, QSD, and heap-transform families.
arXiv Detail & Related papers (2026-08-10T17:32:27Z)
Maximal Classicalization of Finite-Group Quantum Reference-Frame Noise [0.0]
A finite quantum reference token with group-valued misalignment induces a random-unitary channel.<n>We prove that the following conditions are equivalent for a unitary representation U of a finite group G.
arXiv Detail & Related papers (2026-07-14T17:07:57Z)
Exponential-Family Tensor Completion via Nonconvex Dual Total-Variation Regularization [33.64818873746132]
We present a rigorous theoretical analysis of TV regularization for tensor completion under exponential-family noise.<n>We propose a family of dual-TV (DTV) regularizers based on the transformed L1 function, which simultaneously capture sparsity and low-rank structures in the gradient tensor.
arXiv Detail & Related papers (2026-06-29T22:32:19Z)
Recursively Trained Diffusion Models: Limiting Collapse Distribution and Spectral Characterization [27.894241484593735]
Recursive training of generative models can lead to model collapse, a compounding drift away from the true data distribution.<n>We show that even with perfect score estimation and exact sampling, the early stopping of the reverse diffusion drives a progressive drift away from the data distribution.<n>We prove our idealized characterization is robust, with mode-dependent contraction rates that contract high-order errors faster than low-order ones.
arXiv Detail & Related papers (2026-06-11T18:06:26Z)
Transformers Provably Learn to Internalize Chain-of-Thought [65.41010769606844]
Implicit Chain-of-Thought (ICoT) trains models to internalize intermediate steps within their hidden states.<n>Log-ICoT removes thinking tokens one at a time, reducing the number of stages from linear in $k$ to logarithmic.<n>Experiments on multi-layer transformers confirm the theory and visualize how reasoning is progressively absorbed into deeper layers.
arXiv Detail & Related papers (2026-05-27T15:17:06Z)
VORT: Adaptive Power-Law Memory for NLP Transformers [0.913755431537592]
We introduce a memory architecture in which each ingested token is assigned a learnable fractional order _iin[,1]<n>Because the fractional weighted sum is non-Markovian, we approximate it through a sum-of-exponentials (SOE) decomposition computed by Gauss--Laguerre quadrature.<n>Retrieval is keyed and associative via a linear-attention accumulator with an exact O(KSd_d_v) -per-step recurrence.
arXiv Detail & Related papers (2026-05-09T14:20:17Z)
Fault-Tolerant Resource Comparison of Qudit and Qubit Encodings for Diagonal Quadratic Operators [36.94429692322632]
Finite local Hilbert-space truncations arise naturally in quantum simulations of lattice field theories and motivate qudit encodings.<n>We compare the non-Clifford cost of implementing diagonal evolutions, exemplified by $U=e-it_x2$ in a uniform field-amplitude discretization of a real scalar field, using either one logical $d$-level qudit or $n_b=eil log drceil$ logical qubits.
arXiv Detail & Related papers (2026-04-29T15:25:08Z)
Bridging wire and gate cutting with ZX-calculus [45.200826131319815]
We show how decompositions of ideal, global unitaries can be obtained diagrammatically using ZX-calculus expanding.<n>We obtain improved decompositions for multi-qubit controlled-Z (MCZ) gates with $1$-norm equal to $3$ for any number of qubits and any partition.
arXiv Detail & Related papers (2025-03-14T15:20:47Z)
High-Precision Multi-Qubit Clifford+T Synthesis by Unitary Diagonalization [0.8341988468339112]
Resource-efficient and high-precision approximate synthesis of quantum circuits expressed in the Clifford+T gate set is vital for Fault-Tolerant quantum computing.<n>We leverage search-based methods to first approximately diagonalize a unitary, then perform the inversion analytically.<n>Our approach improves both the implementation precision and run time of synthesis algorithms by orders of magnitude when evaluated on unitaries from real quantum algorithms.
arXiv Detail & Related papers (2024-08-31T12:10:32Z)
On the Constant Depth Implementation of Pauli Exponentials [49.48516314472825]
We decompose $Zotimes n$ exponentials of arbitrary length into circuits of constant depth using $mathcalO(n)$ ancillae and two-body XX and ZZ interactions.<n>We prove the correctness of our approach, after introducing novel rewrite rules for circuits which benefit from qubit recycling.
arXiv Detail & Related papers (2024-08-15T17:09:08Z)

This list is automatically generated from the titles and abstracts of the papers in this site.