Related papers: Optimal Lower Bounds for Hamiltonian Simulation

Optimal Lower Bounds for Hamiltonian Simulation

URL: http://arxiv.org/abs/2607.19852v1
Date: Wed, 22 Jul 2026 07:41:32 GMT
Title: Optimal Lower Bounds for Hamiltonian Simulation
Abstract summary: 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 $$.
Score: 42.227880669333835
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: For Hamiltonian $H = \sum_j h_j$, we prove asymptotically tight lower bounds on the gate and query complexities of simulating time evolution on a quantum computer. Our bounds hold for arbitrary term norms $\|h_j\|$, time $t$, and trace-distance error $ε$. The matching upper bound (known as composite qDRIFT) consists of high-order Trotterization of the large terms and a randomized first-order Trotterization of the small terms. Unlike prior work that chooses worst-case $\|h_j\|$ to encode the computation of parity or other Boolean functions in time evolution, our proof is elementary and based on a local, bounded-degree classical Hamiltonian. Our work suggests that for many physical systems (e.g., power-law interactions), gate count must scale polynomially in $1/ε$, contrary to the complexity suggested by counting coherent oracle queries such as those in the block-encoding model.

Related papers

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)
Optimal quantum simulation of linear non-unitary dynamics [0.31439717339537293]
We present a quantum algorithm for simulating the time evolution generated by any bounded, time-dependent operator $-A$.<n>Our method generalizes the recent Linear-Combination-of-Hamiltonian-Simulation (LCHS) framework.
arXiv Detail & Related papers (2025-08-26T17:58:27Z)
Computational Complexity of Non-Hermitian Quantum Systems [0.0]
conditional time evolutions arise when a quantum system is monitored and one postselects on a measurement record.<n>We establish an approximate equivalence between post-selection and arbitrary non-Hermitian Hamiltonians.<n>Non-Hermitian physics neither guarantees a quantum advantage nor precludes efficient classical simulation.
arXiv Detail & Related papers (2025-06-03T22:35:28Z)
Quantum singular value transformation without block encodings: Near-optimal complexity with minimal ancilla [18.660349597156266]
We develop new algorithms for Quantum Singular Value Transformation (QSVT), a unifying framework that encapsulates most known quantum algorithms.<n>Our results establish a new framework for quantum algorithms, significantly reducing hardware overhead while maintaining near-optimal performance.
arXiv Detail & Related papers (2025-04-03T08:24:15Z)
Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
arXiv Detail & Related papers (2024-08-14T19:04:13Z)
Composite QDrift-Product Formulas for Quantum and Classical Simulations in Real and Imaginary Time [0.18374319565577155]
Recent work has shown that it can be advantageous to implement a composite channel that partitions the Hamiltonian $H$ for a given simulation problem into subsets. We show that this approach holds in imaginary time, making it a candidate classical algorithm for quantum Monte-Carlo calculations. We provide exact numerical simulations of algorithmic cost by counting the number of gates of the form $e-iH_j t$ and $e-H_j beta$ to meet a certain error tolerance.
arXiv Detail & Related papers (2023-06-28T21:31:26Z)
On the complexity of implementing Trotter steps [2.1369834525800138]
We develop methods to perform faster Trotter steps with complexity sublinear in number of terms. We also realize faster Trotter steps when certain blocks of Hamiltonian coefficients have low rank. Our result suggests the use of Hamiltonian structural properties as both necessary and sufficient to implement Trotter synthesis steps with lower gate complexity.
arXiv Detail & Related papers (2022-11-16T19:00:01Z)
Average-case Speedup for Product Formulas [69.68937033275746]
Product formulas, or Trotterization, are the oldest and still remain an appealing method to simulate quantum systems. We prove that the Trotter error exhibits a qualitatively better scaling for the vast majority of input states. Our results open doors to the study of quantum algorithms in the average case.
arXiv Detail & Related papers (2021-11-09T18:49:48Z)
Hamiltonian simulation with random inputs [74.82351543483588]
Theory of average-case performance of Hamiltonian simulation with random initial states. Numerical evidence suggests that this theory accurately characterizes the average error for concrete models.
arXiv Detail & Related papers (2021-11-08T19:08:42Z)

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