Improved constant factors for qubitized Hamiltonian simulation

• URL: http://arxiv.org/abs/2608.02734v1
• Date: Mon, 03 Aug 2026 18:00:03 GMT
• Title: Improved constant factors for qubitized Hamiltonian simulation
• Abstract summary: Quantum signal processing serves as theally optimal technique for Hamiltonian simulation on a quantum computer.<n>There is a gap between state-of-the-art bounds and the optimal constant multiplicative factor, which is approximately equal to 1.<n>Our improvement resides in a careful treatment of the Bessel tail in the Jacobi-Anger series using Kapteyn's and Watson's inequalities.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantum signal processing (QSP) serves as the asymptotically optimal technique for Hamiltonian simulation on a quantum computer. By approximating the time evolution operator via the Jacobi-Anger expansion, the Hamiltonian simulation problem reduces to a problem in polynomial approximation theory: find a sufficient degree-$d$ polynomial series to approximate $e^{-iτx}$ on $[-1,1]$ within error $ε$. While $d\in\tilde{\mathcal{O}}(τ)$ is known to be asymptotically optimal, there exists a gap between state-of-the-art bounds and the optimal constant multiplicative factor, which is approximately equal to 1. Here, we close this gap almost entirely, to the point where possible future improvements will not be of practical significance. Our improvement resides in a careful treatment of the Bessel tail in the Jacobi-Anger series using Kapteyn's and Watson's inequalities, thereby reducing the overhead estimates for all Hamiltonian simulation tasks on quantum computers by a factor of $\approx e/2$.

Related papers

• Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise [49.730496294398726]
  We develop a novel quantum mean estimator for heavy-tailed random variables.<n>We derive stronger lower bounds for tail index>4/3$, showing that a nontrivial dependence on a dimension is unavoidable.<n>For a convex objective function, we propose a quantum projected gradient descent method.
  arXiv  Detail & Related papers  (2026-07-28T09:29:37Z)
• Optimal Lower Bounds for Hamiltonian Simulation [42.227880669333835]
  For Hamiltonian $H = sum_j h_j$, we proveally tight lower bounds on the gate and query complexities of simulating time evolution on a quantum computer.<n>Our hold for arbitrary term norms $|h_j|$, time $t$, and trace-distance error $$.
  arXiv  Detail & Related papers  (2026-07-22T07:41:32Z)
• DQC1-completeness of normalized trace estimation for functions of log-local Hamiltonians [20.990700912031773]
  We study the computational complexity of estimating the normalized trace $2-nTr[f(A)]$ for a log-local Hamiltonian $A$ acting on $n$ qubits.<n>This problem arises naturally in the DQC1 model, yet its complexity is only understood for a limited class of functions $f(x)$.<n>We show that if $f(x)$ is a continuous function with approximate degree $(rm poly(n))$, then estimating $2-nTr[f(A)]$ up to constant additive error is
  arXiv  Detail & Related papers  (2026-04-02T01:15:12Z)
• 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)
• Hamiltonian Decoded Quantum Interferometry [69.7049555871155]
  We introduce Hamiltonian Decoded Quantum Interferometry (HDQI)<n>HDQI utilizes coherent measurements and the symplectic representation of the Pauli group to reduce Gibbs sampling and Hamiltonian Bellians.<n>We show that HDQI efficiently prepares Gibbs states at arbitrary temperatures for a class of physically motivated commuting Hamiltonians.
  arXiv  Detail & Related papers  (2025-10-09T08:06:15Z)
• Sublinear Time Quantum Sensitivity Sampling [57.356528942341534]
  We present a unified framework for quantum sensitivity sampling, extending the advantages of quantum computing to a broad class of classical approximation problems.<n>Our framework provides a streamlined approach for constructing coresets and offers significant runtime improvements in applications such as clustering, regression, and low-rank approximation.
  arXiv  Detail & Related papers  (2025-09-20T20:18:49Z)
• Quantum algorithms based on quantum trajectories [0.4870012761464388]
  We show that the additive complexity of $O(T + log(1/epsilon))$ is reachable for the simulation of a large class of Lindbladian.<n>In this work we show that the additive complexity of $O(T + log(1/epsilon))$ is reachable for the simulation of a large class of Lindbladian by constructing a novel quantum algorithm based on quantum trajectories.
  arXiv  Detail & Related papers  (2025-09-12T17:27:25Z)
• Computable entanglement cost under positive partial transpose operations [4.642647756403864]
  We consider the problem of computing the entanglement cost of preparing noisy quantum states under quantum operations.<n>To our knowledge, this is the first time that an entanglement measure is shown to be efficiently computable despite no closed-form formula being available.
  arXiv  Detail & Related papers  (2024-05-15T18:00:01Z)
• Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
  We study the problem of estimating frequency response functions of systems of coupled, classical harmonic oscillators using a quantum computer.<n>Our proposed quantum algorithm operates in the standard $s-sparse, oracle-based query access model.<n>We show that a simple adaptation of our algorithm solves the random glued-trees problem in time.
  arXiv  Detail & Related papers  (2024-05-14T15:28:37Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Quantum Algorithm for Solving the Advection Equation using Hamiltonian Simulation [0.0]
  One-dimensional advection can be simulated directly since the central finite difference operator for first-order derivatives is anti-Hermitian. A single copy of the initial quantum state is required and the circuit depth grows linearly with the required number of time steps.
  arXiv  Detail & Related papers  (2023-12-15T13:39:27Z)
• A quantum-classical performance separation in nonconvex optimization [7.427989325451079]
  We prove that the recently proposed Quantum Hamiltonian (QHD) algorithm is able to solve any $d$dimensional queries from this family. On the other side, a comprehensive empirical study suggests that representative state-of-the-art classical algorithms/solvers would require a superpolynomial time to solve such queries.
  arXiv  Detail & Related papers  (2023-11-01T19:51:00Z)
• A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
  In this paper we consider finding an approximate second-order stationary point (SOSP) that minimizes a twice different subject general non conic optimization. In particular, we propose a Newton-CG based-augmentedconjugate method for finding an approximate SOSP.
  arXiv  Detail & Related papers  (2023-01-10T20:43:29Z)
• Quantum algorithm for time-dependent Hamiltonian simulation by permutation expansion [6.338178373376447]
  We present a quantum algorithm for the dynamical simulation of time-dependent Hamiltonians. We demonstrate that the cost of the algorithm is independent of the Hamiltonian's frequencies.
  arXiv  Detail & Related papers  (2021-03-29T05:02:02Z)

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.