arXiv:2610.03595
The exact LCU sampling overhead of collective diagonal unitaries: resonances and a continued-fraction dichotomy
Zhihui Wang, Sujit Roy, Manil Maskey, Rahul Ramachandran
Abstract
The minimal sampling overhead of the quadratic collective phase $e^{-iγK^2}$ over one layer of single-qubit rotations is decided by the continued fraction of $γ/π$. Here $K$ is a collective observable with spectrum $\{0,\dots,n\}$, such as the permutation-symmetric Hamming weight. This gate is the cardinality-penalty layer of constrained optimization, the one-axis-twisting gate of spin squeezing and the Kerr phase of a bosonic mode. Instead of compiling it to two-qubit gates, we sample it as an LCU over such layers at overhead $Γ$. Our results give an optimality theory for this overhead. Ancilla-free sampling reproduces the target's outcome probabilities up to the minimal $Γ$, and no smaller factor works for every input; for permutation-symmetric $K$, independent per-qubit angles or one layer of arbitrary single-qubit gates give no further reduction. Rational angles $πp/q$ in lowest terms cost exactly $q$ once $n\ge2q-2$, attained uniquely by a uniform $q$-point sampler; the cost is $Θ(n)$ if and only if $γ/π$ is badly approximable, and bounded in $n$ if and only if it is rational. A second result shows what the symmetry buys: without it, the squaring phase of Fourier arithmetic on $m$ qubits costs at least $2^{0.557m-O(1)}$ over single-qubit gates, beyond the $2^{m/2}$ of every cut bound, by a new certificate-lifting argument. For constructions known only through upper bounds, it gives the optimum: the Fourier-based LCU of Carrera Vazquez, Egger and Woerner is, at fixed $n$, optimal up to a constant at typical angles and beaten by $(n+1)/q$ at rational ones with an $n$-independent sampler; the Kerr decomposition of Upreti, Quesada and Chabaud is the unique optimum over phase shifters at rational parameters without photon-number cutoff; and it identifies the rational couplings where one-axis twisting admits optimal cat decompositions.
AI Summary
The paper studies the minimum LCU overhead $\Gamma=(\sum_j|c_j|)^2$ for representing $e^{-i\gamma K^2}$ using collective rotations $e^{i\theta K}$, where $K$ has spectrum $\{0,\ldots,n\}$. This covers Hamming-weight penalties, one-axis twisting and truncated Kerr evolution. The cost is the optimal factor in a worst-case ancilla-free probability-domination guarantee, not an exact reproduction of the output distribution; unbiased quasiprobability estimation incurs shot overhead $\Gamma^2$. The LCU norm is formulated as a Fourier-moment interpolation problem for complex measures, with trigonometric-polynomial dual certificates. At $\gamma/\pi=p/q$ in lowest terms, a uniform $q$-angle sampler has overhead $q$ and is uniquely optimal for $n\ge2q-2$, proved using chirp Fourier flatness and a Fejér-windowed certificate. Detuning bounds and continued fractions establish $\Gamma=\Theta(n)$ exactly for badly approximable irrational angles, while bounded cost as $n\to\infty$ occurs exactly at rational angles. For symmetric diagonal targets, independent angles and arbitrary product unitaries cannot reduce the cost, using Grace–Walsh–Szegő coincidence and diagonal pinching. Without permutation symmetry, the binary-register squaring phase has product-unitary cost at least $2^{0.557m-O(1)}$, exceeding every single-bipartition bound, and at most $2^{m-2}$. The lower bound uses recursive certificate lifting. Limitations include the one-layer resource model, exact rather than approximate decompositions, an unresolved rational optimality threshold, and a conjectural all-angle detuning formula proved only near sufficiently low-denominator rationals. The register exponent near $0.844$ is numerical extrapolation; broader ancilla-assisted constructions and Gaussian resources for Kerr gates remain unresolved.
Error found: Theorem B's uniqueness claim fails at q = 1, n = 0, where every probability measure has the required sole moment and optimal total variation 1.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- v2: concise rewrite, 28 pages, 2 figures