Trotter error compensation with polylogarithmic precision and nested-commutator scaling without ancillas

• URL: http://arxiv.org/abs/2607.11856v1
• Date: Mon, 13 Jul 2026 17:42:25 GMT
• Title: Trotter error compensation with polylogarithmic precision and nested-commutator scaling without ancillas
• Abstract summary: We develop a high-order nested-commutator algorithm that preserves the main advantages of product formulas.<n>The resulting time dependence matches that of a product formula of order $2K+1$.
• Score: 23.101202672272027
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Product formulas are among the most practical approaches to Hamiltonian simulation, requiring no ancillary qubits and exhibiting error bounds governed by nested commutators rather than only by Hamiltonian norms. Their circuit size, however, scales polynomially with the inverse precision. We develop a high-order nested-commutator compensation (HNCC) algorithm that preserves the main advantages of product formulas while achieving polylogarithmic precision dependence in the circuit size and the standard $\mathcal{O}(\varepsilon^{-2})$ sampling cost. HNCC uses a truncated Baker--Campbell--Hausdorff expansion to represent high-order Trotter errors by products of nested commutators and compensates these errors at the superoperator level through randomly sampled Pauli-rotation channels, avoiding Hadamard tests and ancillary qubits. For a fixed $K$-th order product formula applied to a $k$-local Hamiltonian on $N$ qubits with $Γ$ Pauli terms and local interaction strength $g_0$, HNCC estimates $\operatorname{tr}[Oe^{-\mathrm{i} tH}ρe^{\mathrm{i} tH}]$ to additive precision $\varepsilon\|O\|$ using $\mathcal{O}(\varepsilon^{-2})$ repetitions and a maximum gate count per circuit of $\mathcal{O}(N^{\frac{2}{2K+1}} (k g_0 t \log(1/\varepsilon))^{1+\frac{1}{2K+1}} k(Γ+\log(1/\varepsilon)))$. The resulting time dependence matches that of a product formula of order $2K+1$. Finite-size resource estimates for the periodic Heisenberg chain indicate that HNCC achieves the lowest CNOT and $T$-gate counts per circuit among the product-formula-based methods considered.

Related papers

• Optimal T-Count for Block Encodings of Fermionic and Spin Hamiltonians [4.914113120082008]
  We study the cost of constructing block encodings of structured fermionic and spin Hamiltonians in a unitary Clifford$+T$ model.<n>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 $mina,n+2s$ ancillas.
  arXiv  Detail & Related papers  (2026-09-10T07:01:08Z)
• A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
  We study tradeoff between solution quality and stability when elements arrive over time.<n>Our algorithm has a future implementation for rational oracle$ with $O(varepsilon-1)$ recourse and separate the existence of universal-price certificates from their efficient algorithms.
  arXiv  Detail & Related papers  (2026-09-09T10:13:43Z)
• Practical Estimation of Trotter Error for Hamiltonian Simulation [0.2538121404112091]
  Trotter product formulas are a leading approach for Hamiltonian simulation on quantum computers.<n>We develop new theoretical results, algorithms, and software tools that advance the state-of-the-art in Trottercal error estimation.
  arXiv  Detail & Related papers  (2026-06-29T18:00:06Z)
• Robust Structure Learning of $k$-local Lindbladians [6.257768263476564]
  We present an efficient protocol for learning an unknown $k$-local Lindblad generator on $n$ qubits.<n>For fixed $k$ and bounded weighted interaction strength, the protocol estimates all Hamiltonian and dissipative Pauli-GKSL coefficients to entrywise accuracy.<n>We extend the guarantees to model misspecifications and prove sample-complexity lower bounds.
  arXiv  Detail & Related papers  (2026-06-22T17:38:41Z)
• Optimal Bounds, Barriers, and Extensions for Non-Hermitian Bivariate Quantum Signal Processing [0.0]
  We find the anti-Hermitian query complexity $d_I = (betaI T + log/varepsilon)/loglog (1/varepsilon)$ to be tight, established via Chebyshev coefficient, modified Bessel functions, and Lambert$W$ inversion.<n>A constant-access-operator construction achieves intrinsic barrier $e-2T$ on a restricted domain, though extension to the full bitorus remains open.
  arXiv  Detail & Related papers  (2026-05-12T19:03:36Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  We establish new exponential in dimension lower bounds for the Maximum Halfspace Discrepancy problem.<n>Both are fundamental problems in computational geometry and machine learning in their exact and approximate forms.
  arXiv  Detail & Related papers  (2026-03-19T15:53:41Z)
• Entanglement-Dependent Error Bounds for Hamiltonian Simulation [0.0]
  We prove that the first-order Trotter error scales as $mathcalO(t2 S_textmax operatornamepolylog(n)/r)$ rather than the worst-case $mathcalO(t2 n/r)$.<n>These results have immediate applications to quantum chemistry, condensed matter simulation, and resource estimation for fault-tolerant quantum computing.
  arXiv  Detail & Related papers  (2026-01-31T06:34:37Z)
• On the commutator scaling in Hamiltonian simulation with multi-product formulas [0.0]
  We show an alternative commutator-scaling error of MPF and derive its size-efficient cost properly inheriting the advantage in Trotterization.<n>We prove that Hamiltonian simulation by MPF certainly achieves the cost whose system-size dependence is as large as Trotterization.
  arXiv  Detail & Related papers  (2025-07-09T05:25:06Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  Recent studies show that a reproducing kernel Hilbert space (RKHS) is not a suitable space to model functions by neural networks. In this paper, we study a suitable function space for over- parameterized two-layer neural networks with bounded norms.
  arXiv  Detail & Related papers  (2024-04-29T15:04:07Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  Under nonlinear measurements, most prior results are non-uniform, i.e., they hold with high probability for a fixed $mathbfx*$ rather than for all $mathbfx*$ simultaneously. Our framework accommodates GCS with 1-bit/uniformly quantized observations and single index models as canonical examples. We also develop a concentration inequality that produces tighter bounds for product processes whose index sets have low metric entropy.
  arXiv  Detail & Related papers  (2023-09-25T17:54:19Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  We study a function of the form $mathbfxmapstosigma(mathbfwcdotmathbfx)$ for monotone activations. The goal of the learner is to output a hypothesis vector $mathbfw$ that $F(mathbbw)=C, epsilon$ with high probability.
  arXiv  Detail & Related papers  (2022-06-17T17:55:43Z)
• Random quantum circuits transform local noise into global white noise [118.18170052022323]
  We study the distribution over measurement outcomes of noisy random quantum circuits in the low-fidelity regime. For local noise that is sufficiently weak and unital, correlations (measured by the linear cross-entropy benchmark) between the output distribution $p_textnoisy$ of a generic noisy circuit instance shrink exponentially. If the noise is incoherent, the output distribution approaches the uniform distribution $p_textunif$ at precisely the same rate.
  arXiv  Detail & Related papers  (2021-11-29T19:26:28Z)
• Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
  We show that HSDMPG can attain an $mathcalObig (1/sttnbig)$ which is at the order of excess error on a learning model. For loss factors, we prove that HSDMPG can attain an $mathcalObig (1/sttnbig)$ which is at the order of excess error on a learning model.
  arXiv  Detail & Related papers  (2020-09-18T02:18:44Z)
• Linear Time Sinkhorn Divergences using Positive Features [51.50788603386766]
  Solving optimal transport with an entropic regularization requires computing a $ntimes n$ kernel matrix that is repeatedly applied to a vector. We propose to use instead ground costs of the form $c(x,y)=-logdotpvarphi(x)varphi(y)$ where $varphi$ is a map from the ground space onto the positive orthant $RRr_+$, with $rll n$.
  arXiv  Detail & Related papers  (2020-06-12T10:21:40Z)

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

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.