Beyond Ground States: Physics-Inspired Optimization of Excited States of Classical Hamiltonians

• URL: http://arxiv.org/abs/2507.12394v1
• Date: Wed, 16 Jul 2025 16:40:49 GMT
• Title: Beyond Ground States: Physics-Inspired Optimization of Excited States of Classical Hamiltonians
• Authors: Erik Altelarrea-Ferré, Júlia Barberà-Rodríguez, David Jansen, Antonio Acín,
• Abstract summary: ExcLQA is a classical, physics-inspired algorithm that identifies excited states of classical Ising Hamiltonians.<n>We benchmark ExcLQA on the shortest vector problem (SVP), a fundamental lattice problem underlying the security of many postquantum cryptographic schemes.<n>Our results show that ExcLQA manages to solve SVP instances up to rank 46, and outperforms the Metropolis-Hastings algorithm in solved ratio, number of shots, and approximation factor.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce excited local quantum annealing (ExcLQA), a classical, physics-inspired algorithm that extends local quantum annealing (LQA) to identify excited states of classical Ising Hamiltonians. LQA simulates quantum annealing while constraining the quantum state to remain in a product state and uses a gradient-based approach to find approximate solutions to large-scale quadratic unconstrained binary optimization problems. ExcLQA extends this framework by adding a penalty term in the cost function to target excited states, with a single hyperparameter that can be tuned via binary search to set the desired penalization level. We benchmark ExcLQA on the shortest vector problem (SVP), a fundamental lattice problem underlying the security of many postquantum cryptographic schemes. Solving an SVP instance can be mapped to identifying the first excited state of a Hamiltonian, with approximate solutions located among nearby excited states. Our results show that ExcLQA manages to solve SVP instances up to rank 46, and outperforms the Metropolis-Hastings algorithm in solved ratio, number of shots, and approximation factor in the tested instances.

Related papers

• Learning Feasible Quantum States for Quadratic Constrained Binary Optimization Problems [41.23247424467223]
  We develop a variational approach that creates an equal superposition of quantum states that satisfy constraints in a QCBO.<n>The resulting equal superposition can be used as an initial state for quantum algorithms that solve QUBOs/QCBOs.
  arXiv  Detail & Related papers  (2025-08-04T16:44:53Z)
• An effcient variational quantum Korkin-Zolotarev algorithm for solving shortest vector problems [7.839882853089659]
  We propose a variational quantum Korkin-Zolotarev (VQKZ) algorithm, which significantly reduces the qubit requirement for solving the shortest vector problem (SVP)<n>By transforming the original SVP into a series of subproblems on projected sublattices, the proposed VQKZ algorithm enables near-term quantum devices to solve SVP instances with lattice dimensions 61.39% larger than those solvable by previous methods.
  arXiv  Detail & Related papers  (2025-05-13T09:32:21Z)
• Accelerating Quantum Reinforcement Learning with a Quantum Natural Policy Gradient Based Approach [36.05085942729295]
  This paper introduces a Quantum Natural Policy Gradient (QNPG) algorithm, which replaces the random sampling used in classicalNPG estimators with a deterministic gradient estimation approach.<n>The proposed QNPG algorithm achieves a sample complexity of $tildemathcalO(epsilon-1.5)$ for queries to the quantum oracle, significantly improving the classical lower bound of $tildemathcalO(epsilon-2)$ for queries to the Markov Decision Process (MDP)
  arXiv  Detail & Related papers  (2025-01-27T17:38:30Z)
• A Quantum Approximate Optimization Algorithm for Local Hamiltonian Problems [0.0]
  Local Hamiltonian Problems (LHPs) are important problems that are computationally-complete and physically relevant for many-body quantum systems.<n>We propose and analyze a quantum approximation which we call the Hamiltonian Quantum Approximate Optimization Algorithm (HamQAOA)<n>Our results indicate that the linear-depth HamQAOA can deterministically prepare exact ground states of 1-dimensional antiferromagnetic Heisenberg spin chains.
  arXiv  Detail & Related papers  (2024-12-12T12:22:08Z)
• Quantum Discrete Adiabatic Linear Solver based on Block Encoding and Eigenvalue Separator [5.138262101775231]
  The rise of quantum computing has spurred interest in quantum linear system problems.<n>The performance of the HHL algorithm is constrained by its dependence on the square of the condition number.<n>This work proposes a quantum discrete adiabatic linear solver based on block encoding and eigenvalue separation techniques.
  arXiv  Detail & Related papers  (2024-12-09T04:50:48Z)
• Benchmarking Variational Quantum Eigensolvers for Entanglement Detection in Many-Body Hamiltonian Ground States [37.69303106863453]
  Variational quantum algorithms (VQAs) have emerged in recent years as a promise to obtain quantum advantage. We use a specific class of VQA named variational quantum eigensolvers (VQEs) to benchmark them at entanglement witnessing and entangled ground state detection. Quantum circuits whose structure is inspired by the Hamiltonian interactions presented better results on cost function estimation than problem-agnostic circuits.
  arXiv  Detail & Related papers  (2024-07-05T12:06:40Z)
• Early Fault-Tolerant Quantum Algorithms in Practice: Application to Ground-State Energy Estimation [39.20075231137991]
  We investigate the feasibility of early fault-tolerant quantum algorithms focusing on ground-state energy estimation problems.<n> scaling these methods to larger system sizes reveals three key challenges: the smoothness of the CDF for large supports, the lack of tight lower bounds on the overlap with the true ground state, and the difficulty of preparing high-quality initial states.
  arXiv  Detail & Related papers  (2024-05-06T18:00:03Z)
• Sparse Quantum State Preparation for Strongly Correlated Systems [0.0]
  In principle, the encoding of the exponentially scaling many-electron wave function onto a linearly scaling qubit register offers a promising solution to overcome the limitations of traditional quantum chemistry methods. An essential requirement for ground state quantum algorithms to be practical is the initialisation of the qubits to a high-quality approximation of the sought-after ground state. Quantum State Preparation (QSP) allows the preparation of approximate eigenstates obtained from classical calculations, but it is frequently treated as an oracle in quantum information.
  arXiv  Detail & Related papers  (2023-11-06T18:53:50Z)
• Hybrid Quantum Classical Simulations [0.0]
  We report on two major hybrid applications of quantum computing, namely, the quantum approximate optimisation algorithm (QAOA) and the variational quantum eigensolver (VQE) Both are hybrid quantum classical algorithms as they require incremental communication between a classical central processing unit and a quantum processing unit to solve a problem.
  arXiv  Detail & Related papers  (2022-10-06T10:49:15Z)
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
  We analyze and optimize an improved quantum algorithm for topological data analysis. We show that super-quadratic quantum speedups are only possible when targeting a multiplicative error approximation. We argue that quantum circuits with tens of billions of Toffoli can solve seemingly classically intractable instances.
  arXiv  Detail & Related papers  (2022-09-27T17:56:15Z)
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays [39.76254807200083]
  We experimentally investigate quantum algorithms for solving the Maximum Independent Set problem. We find the problem hardness is controlled by the solution degeneracy and number of local minima. On the hardest graphs, we observe a superlinear quantum speedup in finding exact solutions.
  arXiv  Detail & Related papers  (2022-02-18T19:00:01Z)
• Quantum Approximate Optimization Algorithm Based Maximum Likelihood Detection [80.28858481461418]
  Recent advances in quantum technologies pave the way for noisy intermediate-scale quantum (NISQ) devices. Recent advances in quantum technologies pave the way for noisy intermediate-scale quantum (NISQ) devices.
  arXiv  Detail & Related papers  (2021-07-11T10:56:24Z)

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.