Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

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

quant-phSubmitted Oct 2, 2026• Announced Oct 5, 2026• 0 citations
v1 · Oct 2, 2026v2 · Oct 5, 2026
arXivHTMLPDF

Abstract

We consider the cost of implementing the quadratic collective phase $e^{-iγK^2}$, with $K$ a collective observable of evenly spaced spectrum, such as the permutation-symmetric Hamming weight. This gate is the cardinality-penalty layer of constrained quantum optimization, the one-axis-twisting gate of spin squeezing and the Kerr phase of a bosonic mode. Instead of two-qubit gates, it can be sampled as a linear combination of single-qubit rotation layers (an LCU) at an overhead $Γ$. We determine the minimal overhead. Ancilla-free sampling of the layers reproduces the target's outcome probabilities up to this factor, and no smaller factor works for every input; when $K$ is permutation symmetric, arbitrary single-qubit gates do no better. The minimal overhead's growth with the register size $n$ is set by the continued fraction of $γ/π$: rational angles $πp/q$ in lowest terms cost exactly $Γ=q$ for every $n\ge2q-2$; the cost is $Θ(n)$ if and only if $γ/π$ is badly approximable; and a master formula, proved two-sided near low-denominator rationals, reads it off the nearest one. Without the symmetry the cost over single-qubit gates can be exponential: for the binary-weighted $K=\sum_j2^jx_j$ the squaring phase of Fourier arithmetic on $m$ qubits costs at least $2^{0.557m-O(1)}$, beyond the $2^{m/2}$ ceiling of every cut bound, by a new certificate-lifting argument. The Fourier-based LCU of Carrera Vazquez, Egger and Woerner (2026), which guarantees $Γ\le n+1$, is optimal up to a constant factor at typical angles at fixed $n$; at rational angles the unique optimizer is the fractional-revival decomposition of Kerr optics, a recipe independent of $n$. In bosonic simulation, the Kerr-gate phase-shifter decomposition of Upreti, Quesada and Chabaud (2026) is the unique optimum over phase shifters, and a finite-cost one exists only at rational $γ/π$.

Comments
55 pages, 2 figures

Related papers

Efficient Fourier-Based Linear Combination of Unitaries and Applications in Quantum Optimization

Almudena Carrera Vazquez, Daniel J. Egger, Stefan Woerner

We investigate ancilla-free linear combination of unitaries (LCU) as a framework for approximating complex quantum circuits. This is particularly effective for quantum optimization algorithms, where candidate solutions can be evaluated classically and the task is to sample high-quality bitstrings rather than reproduce the full output distribution. We show that Fourier-based LCU constructions efficiently decompose broad classes of diagonal and non-diagonal unitaries, replacing highly connected qubit interactions with single-qubit gate layers or significantly simpler structures at the cost of a polynomial sampling overhead. Applied to algorithms such as QAOA, this yields efficient, hardware-friendly decompositions of, for instance, cardinality-constraint penalties and the fully connected XY-mixer, while maintaining rigorous performance guarantees compared to fully coherent implementations. Furthermore, we establish a formal connection between Fourier-based quantum penalties and Lagrangian relaxation, offering a unified perspective on constraint handling. We validate our approach using exact statevector simulations of 12-qubit circuits and large-scale experiments on 106 superconducting qubits. Our results illustrate how approximate sampling via an LCU systematically trades circuit complexity for sampling overhead, extending the practical reach of near-term quantum optimization.

quant-pharXiv:2605.18985•May 20, 2026•2 citations

Multi-qubit controlled gate synthesis without T-count overhead in the small-error limit

Soichiro Yamazaki, Seiseki Akibue, Kaoru Sano

We study the Clifford+T synthesis of quantum multiplexers $U=\bigoplus_{i=1}^{2^n}U_i$: an $n$-qubit control register selects which single-qubit gate $U_i\in\mathrm{SU}(2)$ acts on the target qubit. For each block $U_i$, consider the minimum even T-count needed to approximate it within diamond distance $\varepsilon$ without ancillae, and let $m$ be the largest of these costs. For an arbitrary multiplexer $U$, we construct an approximation of $U$ within the same distance using at most $m+O(\sqrt{2^n(m+1)})$ $T$ gates. With one control qubit, the cost is $m+O(1)$ and no ancillae are required. We also prove a lower bound that allows the Clifford+T circuit to use any number of clean ancillae initialized to zero and returned exactly to zero. For fixed $n$ and independent Haar-random blocks, the minimum T-count among these circuits lies between $(3-δ)\log_2(1/\varepsilon)$ and $(3+δ)\log_2(1/\varepsilon)$ for every fixed $δ>0$, except with probability $O(\varepsilon^{c_{n,δ}})$ as $\varepsilon\rightarrow0$. The optimal leading coefficient is therefore the same as for a single Haar-random $\mathrm{SU}(2)$ gate. In the lower-bound proof, unitarity forces pairs of off-diagonal blocks describing transitions in opposite directions to satisfy cancellation relations with residuals of order $\varepsilon^2$. We combine these relations with the arithmetic of Clifford+T circuits to bound the Haar measure of targets compatible with each pair of off-diagonal blocks. As an application, we obtain ancilla-free approximations of Haar-random $\mathrm{SU}(4)$ gates within diamond distance $\varepsilon$, using at most $(9+δ)\log_2(1/\varepsilon)$ $T$ gates for every fixed $δ>0$, except with probability $O(\varepsilon^{c_δ})$ with $c_δ>0$.

quant-pharXiv:2603.14202•Mar 17, 2026•1 citation

Optimal T-Count for Block Encodings of Fermionic and Spin Hamiltonians

Jiaxin Ma, Kevin J. Joven, Yuan Liu

We determine the non-Clifford $T$-gate cost of constructing block encodings of structured fermionic and spin Hamiltonians in a unitary Clifford$+T$ model, when arbitrarily many clean ancillas and unrestricted block-encoding subnormalization are allowed, but without mid-circuit measurements or classical feed-forward. Our main technical tool is an ancilla-compression theorem: any block encoding of an $n$-qubit operator with $a$ clean ancillas and at most $s$ $T$ gates can be compressed to use at most $\min\{a,n+2s\}$ ancillas, without increasing the absolute error or $T$-count. For general second-quantized Hamiltonians with bounded one- and two-body coefficients, at operator-norm block-encoding error $ε$, a volume-covering argument combined with circuit counting gives the worst-case lower bound $Ω(n^2\sqrt{\log(n^4/ε)})$, matching the existing upper bound at fixed precision. For the bond-dependent Kitaev honeycomb family on $n$ spins, we obtain independent lower bounds $Ω(n)$ from stabilizer nullity and $Ω(\log(1/ε))$ from one-qubit state preparation, established using different Hamiltonian instances. Together with an explicit LCU construction, they give the tight worst-case scaling $Θ(n+\log(1/ε))$. As an application, we evaluate the $T$-count of a Hamiltonian simulation circuit based on quantum singular value transformation, with each block-encoding query compiled separately. When phase synthesis and controlled queries add at most constant-factor overhead, the simulation $T$-count scales as the query count times the optimal $T$-count per query.

quant-pharXiv:2609.11153•Sep 11, 2026•1 citation

Hardware-Friendly Estimation of LCU-Based Expectation Values via Quantum-to-Classical Workload Shifting

Hari Hara Suthan Chittoor, Thirumalai Manimaran

Estimating the expectation value of an observable $O$ for a quantum state evolved under a general, possibly non-unitary, operator $A$ is a fundamental task in quantum simulation, chemistry, and variational algorithms. Existing linear-combination-of-unitaries (LCU) approaches implement $A$ on hardware, requiring ancilla qubits, controlled unitaries and, in randomized variants, fresh circuit executions for every Monte Carlo sample. These costs are prohibitive on NISQ and early fault-tolerant devices. We propose HERMES (Hardware-Efficient Reusable Measurements for Estimating LCU-based expectation valueS), which moves the processing of $A$ entirely to the classical domain. Expanding $A$ and $O$ in the Pauli basis and sampling pairs of Pauli terms classically, HERMES rewrites $μ= \mathrm{Tr}(OAρA^{\dagger})/\mathrm{Tr}(AρA^{\dagger})$ as a ratio of weighted sums of Pauli expectation values on the unmodified state $ρ$, with no ancillas, controlled unitaries, or quantum implementation of $A$. A two-level measurement reduction scheme (Pauli deduplication and commuting-group partitioning) bounds the number of distinct measurement settings independently of the sample count, unlike randomized LCU methods whose circuit executions grow linearly with it. On ground-state energy estimation of $\mathrm{H}_2$ and $\mathrm{LiH}$ via imaginary-time evolution, HERMES matches or beats Pauli single-ancilla LCU baseline using shallow circuits with no two-qubit gates beyond state preparation under qubit-wise commuting grouping. It is also more robust to noise and completes a noisy $\mathrm{LiH}$ simulation infeasible for the baseline, at the cost of classical overhead growing with the number of Pauli terms in $A$.

quant-pharXiv:2610.32841•Oct 26, 2026•0 citations

Approximate synthesis of general single-qubit unitaries over the Clifford+$\sqrt{T}$ gate set

Mathias Weiden, Jae Won Kim, Justin Kalloor +2 more

For the standard Clifford+$T$ gate set, deterministic, ancilla-free synthesis now attains the minimal $T$-count for general single-qubit unitaries (Morisaki et al., arXiv:2510.05816). The $\sqrt{T}$ gate rotates by half the angle of $T$, generating a finer lattice of implementable operations. Access to this magic state is expected to lower the cost of deterministic and ancilla-free synthesis of general single-qubit unitaries (Kliuchnikov et al., arXiv:2203.10064), but no direct Clifford+$\sqrt{T}$ algorithm existed for this case. We provide one by extending the integer lattice-point enumeration method of Morisaki et al. We adopt a resource state cost model based on the magic-state catalysis approach of Gidney and Fowler (arXiv:1812.01238). On Haar-random targets synthesized to precisions ranging from $\varepsilon=10^{-3}$ to $10^{-8}$, the cost of Clifford+$\sqrt{T}$ circuits scales as $2.4\log_2(1/\varepsilon)$ compared to $3.0\log_2(1/\varepsilon)$ for $T$-count-optimal Clifford+$T$ circuits. Once a one-time catalyst state is amortized, the Clifford+$\sqrt{T}$ circuits are never costlier than their Clifford+$T$ counterparts.

quant-pharXiv:2609.16659•Sep 16, 2026•0 citations

Optimal Two-Qubit Gate-Cutting Cost and Measures of Nonlocality

Michael Hart

Circuit cutting enables quantum computations to be decomposed into smaller subcircuits at the cost of additional sampling overhead. Gate-cutting provides one such approach by replacing nonlocal gates with quasiprobability decompositions of local operations. Starting from the known optimal two-qubit gate-cutting formula, we derive complete sharp lower and upper envelopes relating the quasiprobability extent $γ$ to five established descriptors: entangling power, gate typicality, operator entanglement, Schmidt strength, and maximum product-input concurrence. We recast $γ$ as a Rényi-$1/2$ functional of the operator-Schmidt spectrum and show how the physical constraints on two-qubit spectra sharpen generic entropy bounds and select a small set of recurring extremal Cartan families. None of the five descriptors generically determines $γ$ alone, but each imposes exact constraints, revealing how substantially the optimal gate-cutting cost can vary between gates with similar nonlocal characteristics.

quant-pharXiv:2609.30141•Sep 25, 2026•0 citations
We consider the cost of implementing the quadratic collective phase e−iγK2e^{-iγK^2}e−iγK2, with KKK a collective observable of evenly spaced spectrum, such as the permutation-symmetric Hamming weight. This gate is the cardinality-penalty layer of constrained quantum optimization, the one-axis-twisting gate of spin squeezing and the Kerr phase of a bosonic mode. Instead of two-qubit gates, it can be sampled as a linear combination of single-qubit rotation layers (an LCU) at an overhead ΓΓΓ. We determine the minimal overhead. Ancilla-free sampling of the layers reproduces the target's outcome probabilities up to this factor, and no smaller factor works for every input; when KKK is permutation symmetric, arbitrary single-qubit gates do no better. The minimal overhead's growth with the register size nnn is set by the continued fraction of γ/πγ/πγ/π: rational angles πp/qπp/qπp/q in lowest terms cost exactly Γ=qΓ=qΓ=q for every n≥2q−2n\ge2q-2n≥2q−2; the cost is Θ(n)Θ(n)Θ(n) if and only if γ/πγ/πγ/π is badly approximable; and a master formula, proved two-sided near low-denominator rationals, reads it off the nearest one. Without the symmetry the cost over single-qubit gates can be exponential: for the binary-weighted K=∑j2jxjK=\sum_j2^jx_jK=∑j​2jxj​ the squaring phase of Fourier arithmetic on mmm qubits costs at least 20.557m−O(1)2^{0.557m-O(1)}20.557m−O(1), beyond the 2m/22^{m/2}2m/2 ceiling of every cut bound, by a new certificate-lifting argument. The Fourier-based LCU of Carrera Vazquez, Egger and Woerner (2026), which guarantees Γ≤n+1Γ\le n+1Γ≤n+1, is optimal up to a constant factor at typical angles at fixed nnn; at rational angles the unique optimizer is the fractional-revival decomposition of Kerr optics, a recipe independent of nnn. In bosonic simulation, the Kerr-gate phase-shifter decomposition of Upreti, Quesada and Chabaud (2026) is the unique optimum over phase shifters, and a finite-cost one exists only at rational γ/πγ/πγ/π.
We investigate ancilla-free linear combination of unitaries (LCU) as a framework for approximating complex quantum circuits. This is particularly effective for quantum optimization algorithms, where candidate solutions can be evaluated classically and the task is to sample high-quality bitstrings rather than reproduce the full output distribution. We show that Fourier-based LCU constructions efficiently decompose broad classes of diagonal and non-diagonal unitaries, replacing highly connected qubit interactions with single-qubit gate layers or significantly simpler structures at the cost of a polynomial sampling overhead. Applied to algorithms such as QAOA, this yields efficient, hardware-friendly decompositions of, for instance, cardinality-constraint penalties and the fully connected XY-mixer, while maintaining rigorous performance guarantees compared to fully coherent implementations. Furthermore, we establish a formal connection between Fourier-based quantum penalties and Lagrangian relaxation, offering a unified perspective on constraint handling. We validate our approach using exact statevector simulations of 12-qubit circuits and large-scale experiments on 106 superconducting qubits. Our results illustrate how approximate sampling via an LCU systematically trades circuit complexity for sampling overhead, extending the practical reach of near-term quantum optimization.
We study the Clifford+T synthesis of quantum multiplexers U=⨁i=12nUiU=\bigoplus_{i=1}^{2^n}U_iU=⨁i=12n​Ui​: an nnn-qubit control register selects which single-qubit gate Ui∈SU(2)U_i\in\mathrm{SU}(2)Ui​∈SU(2) acts on the target qubit. For each block UiU_iUi​, consider the minimum even T-count needed to approximate it within diamond distance ε\varepsilonε without ancillae, and let mmm be the largest of these costs. For an arbitrary multiplexer UUU, we construct an approximation of UUU within the same distance using at most m+O(2n(m+1))m+O(\sqrt{2^n(m+1)})m+O(2n(m+1)​) TTT gates. With one control qubit, the cost is m+O(1)m+O(1)m+O(1) and no ancillae are required. We also prove a lower bound that allows the Clifford+T circuit to use any number of clean ancillae initialized to zero and returned exactly to zero. For fixed nnn and independent Haar-random blocks, the minimum T-count among these circuits lies between (3−δ)log⁡2(1/ε)(3-δ)\log_2(1/\varepsilon)(3−δ)log2​(1/ε) and (3+δ)log⁡2(1/ε)(3+δ)\log_2(1/\varepsilon)(3+δ)log2​(1/ε) for every fixed δ>0δ>0δ>0, except with probability O(εcn,δ)O(\varepsilon^{c_{n,δ}})O(εcn,δ​) as ε→0\varepsilon\rightarrow0ε→0. The optimal leading coefficient is therefore the same as for a single Haar-random SU(2)\mathrm{SU}(2)SU(2) gate. In the lower-bound proof, unitarity forces pairs of off-diagonal blocks describing transitions in opposite directions to satisfy cancellation relations with residuals of order ε2\varepsilon^2ε2. We combine these relations with the arithmetic of Clifford+T circuits to bound the Haar measure of targets compatible with each pair of off-diagonal blocks. As an application, we obtain ancilla-free approximations of Haar-random SU(4)\mathrm{SU}(4)SU(4) gates within diamond distance ε\varepsilonε, using at most (9+δ)log⁡2(1/ε)(9+δ)\log_2(1/\varepsilon)(9+δ)log2​(1/ε) TTT gates for every fixed δ>0δ>0δ>0, except with probability O(εcδ)O(\varepsilon^{c_δ})O(εcδ​) with cδ>0c_δ>0cδ​>0.
We determine the non-Clifford TTT-gate cost of constructing block encodings of structured fermionic and spin Hamiltonians in a unitary Clifford+T+T+T model, when arbitrarily many clean ancillas and unrestricted block-encoding subnormalization are allowed, but without mid-circuit measurements or classical feed-forward. Our main technical tool is an ancilla-compression theorem: any block encoding of an nnn-qubit operator with aaa clean ancillas and at most sss TTT gates can be compressed to use at most min⁡{a,n+2s}\min\{a,n+2s\}min{a,n+2s} ancillas, without increasing the absolute error or TTT-count. For general second-quantized Hamiltonians with bounded one- and two-body coefficients, at operator-norm block-encoding error εεε, a volume-covering argument combined with circuit counting gives the worst-case lower bound Ω(n2log⁡(n4/ε))Ω(n^2\sqrt{\log(n^4/ε)})Ω(n2log(n4/ε)​), matching the existing upper bound at fixed precision. For the bond-dependent Kitaev honeycomb family on nnn spins, we obtain independent lower bounds Ω(n)Ω(n)Ω(n) from stabilizer nullity and Ω(log⁡(1/ε))Ω(\log(1/ε))Ω(log(1/ε)) from one-qubit state preparation, established using different Hamiltonian instances. Together with an explicit LCU construction, they give the tight worst-case scaling Θ(n+log⁡(1/ε))Θ(n+\log(1/ε))Θ(n+log(1/ε)). As an application, we evaluate the TTT-count of a Hamiltonian simulation circuit based on quantum singular value transformation, with each block-encoding query compiled separately. When phase synthesis and controlled queries add at most constant-factor overhead, the simulation TTT-count scales as the query count times the optimal TTT-count per query.
Estimating the expectation value of an observable OOO for a quantum state evolved under a general, possibly non-unitary, operator AAA is a fundamental task in quantum simulation, chemistry, and variational algorithms. Existing linear-combination-of-unitaries (LCU) approaches implement AAA on hardware, requiring ancilla qubits, controlled unitaries and, in randomized variants, fresh circuit executions for every Monte Carlo sample. These costs are prohibitive on NISQ and early fault-tolerant devices. We propose HERMES (Hardware-Efficient Reusable Measurements for Estimating LCU-based expectation valueS), which moves the processing of AAA entirely to the classical domain. Expanding AAA and OOO in the Pauli basis and sampling pairs of Pauli terms classically, HERMES rewrites μ=Tr(OAρA†)/Tr(AρA†)μ= \mathrm{Tr}(OAρA^{\dagger})/\mathrm{Tr}(AρA^{\dagger})μ=Tr(OAρA†)/Tr(AρA†) as a ratio of weighted sums of Pauli expectation values on the unmodified state ρρρ, with no ancillas, controlled unitaries, or quantum implementation of AAA. A two-level measurement reduction scheme (Pauli deduplication and commuting-group partitioning) bounds the number of distinct measurement settings independently of the sample count, unlike randomized LCU methods whose circuit executions grow linearly with it. On ground-state energy estimation of H2\mathrm{H}_2H2​ and LiH\mathrm{LiH}LiH via imaginary-time evolution, HERMES matches or beats Pauli single-ancilla LCU baseline using shallow circuits with no two-qubit gates beyond state preparation under qubit-wise commuting grouping. It is also more robust to noise and completes a noisy LiH\mathrm{LiH}LiH simulation infeasible for the baseline, at the cost of classical overhead growing with the number of Pauli terms in AAA.
Approximate synthesis of general single-qubit unitaries over the Clifford+T\sqrt{T}T​ gate set
For the standard Clifford+TTT gate set, deterministic, ancilla-free synthesis now attains the minimal TTT-count for general single-qubit unitaries (Morisaki et al., arXiv:2510.05816). The T\sqrt{T}T​ gate rotates by half the angle of TTT, generating a finer lattice of implementable operations. Access to this magic state is expected to lower the cost of deterministic and ancilla-free synthesis of general single-qubit unitaries (Kliuchnikov et al., arXiv:2203.10064), but no direct Clifford+T\sqrt{T}T​ algorithm existed for this case. We provide one by extending the integer lattice-point enumeration method of Morisaki et al. We adopt a resource state cost model based on the magic-state catalysis approach of Gidney and Fowler (arXiv:1812.01238). On Haar-random targets synthesized to precisions ranging from ε=10−3\varepsilon=10^{-3}ε=10−3 to 10−810^{-8}10−8, the cost of Clifford+T\sqrt{T}T​ circuits scales as 2.4log⁡2(1/ε)2.4\log_2(1/\varepsilon)2.4log2​(1/ε) compared to 3.0log⁡2(1/ε)3.0\log_2(1/\varepsilon)3.0log2​(1/ε) for TTT-count-optimal Clifford+TTT circuits. Once a one-time catalyst state is amortized, the Clifford+T\sqrt{T}T​ circuits are never costlier than their Clifford+TTT counterparts.
Circuit cutting enables quantum computations to be decomposed into smaller subcircuits at the cost of additional sampling overhead. Gate-cutting provides one such approach by replacing nonlocal gates with quasiprobability decompositions of local operations. Starting from the known optimal two-qubit gate-cutting formula, we derive complete sharp lower and upper envelopes relating the quasiprobability extent γγγ to five established descriptors: entangling power, gate typicality, operator entanglement, Schmidt strength, and maximum product-input concurrence. We recast γγγ as a Rényi-1/21/21/2 functional of the operator-Schmidt spectrum and show how the physical constraints on two-qubit spectra sharpen generic entropy bounds and select a small set of recurring extremal Cartan families. None of the five descriptors generically determines γγγ alone, but each imposes exact constraints, revealing how substantially the optimal gate-cutting cost can vary between gates with similar nonlocal characteristics.