An Entropy-Governed Speedup for Quantum Algorithms on Local Hamiltonians

• URL: http://arxiv.org/abs/2605.18241v1
• Date: Mon, 18 May 2026 11:36:43 GMT
• Title: An Entropy-Governed Speedup for Quantum Algorithms on Local Hamiltonians
• Abstract summary: Low-energy estimation and state preparation for general $k$-local Hamiltonians are fundamental challenges in quantum complexity theory.<n>We present an even faster quantum algorithm that outputs a quantum state with energy bounded by the minimum energy over all depth-$d$ states.
• Score: 1.0323063834827415
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Low-energy estimation and state preparation for general $k$-local Hamiltonians are fundamental challenges in quantum complexity theory. For constant relative accuracy, Buhrman et al. (PRL 2025) recently broke the natural Grover bound $O(2^{n/2})$, where $n$ denotes the number of qubits, for both problems. In this paper, for any sufficiently small parameter $d\ge 0$, we present an even faster quantum algorithm that outputs a quantum state with energy bounded by the minimum energy over all depth-$d$ states (i.e., states obtained by applying a depth-$d$ circuit to the all-zero state), together with an estimate of this energy. For the class of Hamiltonians with depth-$d$ ground states, our algorithm furthermore achieves exactly the same energy guarantees as Buhrman et al. Our results also provide insight into the distinction between strongly entangled states and those admitting efficient classical descriptions.

Related papers

• Rounding Almost Commuting Hamiltonians [40.02212661155582]
  Commuting Hamiltonians lie at the boundary between classical constraint satisfaction and quantum many-body physics.<n>We show how to efficiently approximate any almost commuting $2$-local qubit Hamiltonian by a commuting one.
  arXiv  Detail & Related papers  (2026-05-25T17:53:36Z)
• 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)
• Fast quantum computation with all-to-all Hamiltonians [1.7763840710724852]
  All-to-all interactions arise naturally in many areas of theoretical physics.<n>We show that all-to-all Hamiltonians can process information on much shorter timescales.
  arXiv  Detail & Related papers  (2025-09-29T18:02:00Z)
• Shallow quantum circuit for generating O(1)-entangled approximate state designs [6.161617062225404]
  We find a new ensemble of quantum states that serve as an $epsilon$-approximate state $t$-design while possessing extremely low entanglement, magic, and coherence.<n>These resources can reach their theoretical lower bounds, $Omega(log (t/epsilon))$, which are also proven in this work.<n>A class of quantum circuits proposed in our work offers reduced cost for classical simulation of random quantum states.
  arXiv  Detail & Related papers  (2025-07-23T18:56:19Z)
• Optimizing random local Hamiltonians by dissipation [44.99833362998488]
  We prove that a simplified quantum Gibbs sampling algorithm achieves a $Omega(frac1k)$-fraction approximation of the optimum. Our results suggest that finding low-energy states for sparsified (quasi)local spin and fermionic models is quantumly easy but classically nontrivial.
  arXiv  Detail & Related papers  (2024-11-04T20:21:16Z)
• Monogamy of Entanglement Bounds and Improved Approximation Algorithms for Qudit Hamiltonians [37.96754147111215]
  We prove new monogamy of entanglement bounds for two-local qudit Hamiltonians of rank-one projectors without one-local terms.<n>In particular, we certify the ground state energy in terms of the maximum matching of the underlying interaction graph via low-degree sum-of-squares.
  arXiv  Detail & Related papers  (2024-10-21T00:10:51Z)
• Beating the natural Grover bound for low-energy estimation and state preparation [0.23034630097498876]
  Estimating ground state energies of many-body Hamiltonians is a central task in many areas of quantum physics.<n>We give quantum algorithms which, given any $k$-body Hamiltonian $H$, compute an estimate for the ground state energy.
  arXiv  Detail & Related papers  (2024-07-03T12:47:06Z)
• Measuring the Loschmidt amplitude for finite-energy properties of the Fermi-Hubbard model on an ion-trap quantum computer [27.84599956781646]
  We study the operation of a quantum-classical time-series algorithm on a present-day quantum computer. Specifically, we measure the Loschmidt amplitude for the Fermi-Hubbard model on a $16$-site ladder geometry (32 orbitals) on the Quantinuum H2-1 trapped-ion device. We numerically analyze the influence of noise on the full operation of the quantum-classical algorithm by measuring expectation values of local observables at finite energies.
  arXiv  Detail & Related papers  (2023-09-19T11:59:36Z)
• Sparse random Hamiltonians are quantumly easy [105.6788971265845]
  A candidate application for quantum computers is to simulate the low-temperature properties of quantum systems. This paper shows that, for most random Hamiltonians, the maximally mixed state is a sufficiently good trial state. Phase estimation efficiently prepares states with energy arbitrarily close to the ground energy.
  arXiv  Detail & Related papers  (2023-02-07T10:57:36Z)
• Asymptotically Optimal Circuit Depth for Quantum State Preparation and General Unitary Synthesis [24.555887999356646]
  The problem is of fundamental importance in quantum algorithm design, Hamiltonian simulation and quantum machine learning, yet its circuit depth and size complexity remain open when ancillary qubits are available. In this paper, we study efficient constructions of quantum circuits with $m$ ancillary qubits that can prepare $psi_vrangle$ in depth. Our circuits are deterministic, prepare the state and carry out the unitary precisely, utilize the ancillary qubits tightly and the depths are optimal in a wide range of parameter regime.
  arXiv  Detail & Related papers  (2021-08-13T09:47:11Z)
• Nearly-frustration-free ground state preparation [0.0]
  Solving for quantum ground states is important for understanding the properties of quantum many-body systems. Recent work has presented a nearly optimal scheme that prepares ground states on a quantum computer for completely generic Hamiltonians.
  arXiv  Detail & Related papers  (2021-08-06T18:00:04Z)
• Quantum-inspired search method for low-energy states of classical Ising Hamiltonians [0.0]
  We develop a quantum-inspired numerical procedure for searching low-energy states of a classical Hamiltonian composed of two-body fully-connected random Ising interactions. We consider 120 instances of the random coupling realizations for the random Ising Hamiltonian with $N$ up to 600 and search the 120 lowest-energy states for each instance.
  arXiv  Detail & Related papers  (2020-10-01T02:29:31Z)
• Hamiltonian operator approximation for energy measurement and ground state preparation [23.87373187143897]
  We show how to approximate the Hamiltonian operator as a sum of propagators using a differential representation. The proposed approach, named Hamiltonian operator approximation (HOA), is designed to benefit analog quantum simulators.
  arXiv  Detail & Related papers  (2020-09-07T18:11:00Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)

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.