Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2010.00180 · Journal of the Physical Society of Japan

Quantum-inspired Search Method for Low-energy States of Classical Ising Hamiltonians

Hiroshi Ueda, Yuichi Otsuka, Seiji Yunoki

Published Mar 17, 2022• 0 citations
arXivHTMLPDF

Abstract

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 and a random local longitudinal magnetic field. In this method, we introduce infinitesimal quantum interactions that do not commute with the original Ising Hamiltonian, and repeatedly generate and truncate direct product states, inspired by the Krylov subspace method, to obtain the low-energy states of the original classical Ising Hamiltonian. The computational cost is controlled by the form of infinitesimal quantum interactions (e.g., one-body or two-body interactions) and the numbers of infinitesimal interaction terms introduced, different initial states considered, and low-energy states kept during the iteration. For a demonstrate of the method, here we introduce as the infinitesimal quantum interactions pair products of Pauli $X$ operators acting on different sites and on-site Pauli $X$ operators into the random Ising Hamiltonian, in which the numerical cost is $O(N^3)$ per iteration with the system size $N$. 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. We find that the time-to-solution by the quantum-inspired method proposed here, with parallelization in terms of the different initial states, for searching the ground state of the random Ising Hamiltonian scales approximately as $N^5$ for $N$ up to 600. We also examine the basic physical properties such as the ensemble-averaged ground-state and first-excited energies and the ensemble-averaged number of states in the low-energy region of the random Ising Hamiltonian.

DOI
10.7566/jpsj.91.044005

Related papers

Beyond ground states: Physics-inspired optimization of excited states of classical Hamiltonians

Erik Altelarrea-Ferré, Júlia Barberà-Rodríguez, David Jansen +1 more

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 fully connected Ising models with random interactions and on the shortest vector problem (SVP). The latter is a fundamental lattice problem underlying the security of many post-quantum cryptographic schemes, and its solution can be mapped to the first excited state of an Ising Hamiltonian. For the fully connected Ising models, we show that, on the tested instances, ExcLQA outperforms both a matrix-product-state-based method and simulated annealing. Notably, even when only a lower bound on the ground-state energy is provided, rather than the exact ground-state information required by these competing methods, ExcLQA still achieves superior performance. For the SVP, ExcLQA finds exact solutions for instances up to rank 46, and outperforms the Metropolis-Hastings algorithm in terms of solved ratio, number of shots, and approximation factor on the tested instances.

arXiv:2507.12394•Physical Review Applied•May 20, 2026•0 citations

Beating the Natural Grover Bound for Low-Energy Estimation and State Preparation

Harry Buhrman, Sevag Gharibian, Zeph A. Landau +3 more

Estimating ground state energies of many-body Hamiltonians is a central task in many areas of quantum physics. In this Letter, we give quantum algorithms which, given any k-body Hamiltonian H, compute an estimate for the ground state energy and prepare a quantum state achieving said energy, respectively. Specifically, for any ϵ>0, our algorithms return, with high probability, an estimate of the ground state energy of H within additive error ϵM, or a quantum state with the corresponding energy. Here, M is the total strength of all interaction terms, which in general is extensive in the system size. Our approach makes no assumptions about the geometry or spatial locality of interaction terms of the input Hamiltonian and thus handles even long-range or all-to-all interactions, such as in quantum chemistry, where lattice-based techniques break down. In this fully general setting, the run-time of our algorithms scales as 2^{cn/2} for c<1, yielding the first quantum algorithms for low-energy estimation breaking a standard square root Grover speedup for unstructured search. The core of our approach is remarkably simple, and relies on showing that an extensive fraction of the interactions can be neglected with a controlled error. What this ultimately implies is that even arbitrary k-local Hamiltonians have structure in their low energy space, in the form of an exponential-dimensional low energy subspace.

arXiv:2407.03073•Physical Review Letters•May 28, 2025•3 citations

Calculation of generating function in many-body systems with quantum computers: technical challenges and use in hybrid quantum-classical methods

Edgar Andres Ruiz Guzman, Denis Lacroix A

The generating function of a Hamiltonian $H$ is defined as $F(t)=\langle e^{-itH}\rangle$, where $t$ is the time and where the expectation value is taken on a given initial quantum state. This function gives access to the different moments of the Hamiltonian $\langle H^{K}\rangle$ at various orders $K$. The real and imaginary parts of $F(t)$ can be respectively evaluated on quantum computers using one extra ancillary qubit with a set of measurement for each value of the time $t$. The low cost in terms of qubits renders it very attractive in the near term period where the number of qubits is limited. Assuming that the generating function can be precisely computed using quantum devices, we show how the information content of this function can be used a posteriori on classical computers to solve quantum many-body problems. Several methods of classical post-processing are illustrated with the aim to predict approximate ground or excited state energies and/or approximate long-time evolutions. This post-processing can be achieved using methods based on the Krylov space and/or on the $t$-expansion approach that is closely related to the imaginary time evolution. Hybrid quantum-classical calculations are illustrated in many-body interacting systems using the pairing and Fermi-Hubbard models.

arXiv:2104.08181•Apr 16, 2021•2 citations

Data and code for "Energy-selective quantum search with Ising Hamiltonian phase oracles"

Andrey Zhukov, Andrey Zhukov, Andrey Lebedev +1 more

This archive contains the numerical data and scripts used to generate the figures for the paper “Energy-selective quantum search with Ising Hamiltonian phase oracles”. The main numerical dataset is used for the scaling analysis of the correlation-induced resonance displacement φ₀ in the zero-field random Ising ensemble. The simulations use dimensionless units with σ_J = 1 and the Hamiltonian H(s) = 2 sum_{i<j} J_ij s_i s_j, where the couplings are independent Gaussian random variables, J_ij ~ N(0, 1), and h_i = 0. For each random Ising instance, the archive stores the truncated characteristic-function coefficients g_m = 2^{-n} Tr exp(-i m T H), m = 0, ..., 15. These coefficients are used to extract the local displacement φ₀ from the zero of the imaginary part of the response function C(φ) = 2 sum_{m=0}^{15} g_m (-1)^m exp(i m φ) - 1. The quantity plotted in the paper is the disorder-averaged second moment <φ₀²> and the scaled combination n⁶<φ₀²>. The Monte Carlo average is over independent disorder realizations only. For each realization, the trace over spin configurations is evaluated deterministically. The data cover even system sizes n = 18, 20, 22, ..., 36. For the largest systems, the computation splits the spins into two equal halves, performs GPU block contractions, and uses the zero-field spin-flip symmetry H(s)=H(-s) to reduce the sum by a factor of two. Archive contents - scripts/01_generate_phi0_coefficients.py Generates the characteristic-function coefficient files g_m for the random Ising ensemble. - scripts/02_analyze_phi0_scaling.py Computes φ₀, bootstrap confidence intervals, the finite-n covariance-sum comparison, and the scaling plots. - scripts/03_make_gaussian_amplification.py Generates the Gaussian amplification figure used as Fig. 1 in the paper. - data/phi0_coefficients/ Directory for the NumPy .npz files containing the characteristic-function coefficients. The production files have names of the form Nq_<n>_K_<K>.npz. The .npz files are saved without pickle objects. They can be read with standard NumPy using np.load. Typical usage To regenerate the Gaussian amplification figure: python scripts/03_make_gaussian_amplification.py --output-dir output/fig1_gaussian To analyze the φ₀ scaling data: python scripts/02_analyze_phi0_scaling.py \ --data-dir data/phi0_coefficients \ --output-dir output/phi0_scaling To run a short test calculation of the characteristic-function coefficients: python scripts/01_generate_phi0_coefficients.py \ --smoke-test \ --output-dir output/smoke_test_coefficients To regenerate the full production dataset on a CUDA-capable GPU: python scripts/01_generate_phi0_coefficients.py \ --production \ --output-dir data/phi0_coefficients The production calculations were performed using CuPy on an NVIDIA GPU. The analysis and plotting scripts use NumPy, pandas, and Matplotlib.

•May 25, 2026•0 citations

Krylov diagonalization of large many-body Hamiltonians on a quantum processor

Nobuyuki Yoshioka, Mirko Amico, William Kirby +16 more

The estimation of low energies of many-body systems is a cornerstone of the computational quantum sciences. Variational quantum algorithms can be used to prepare ground states on pre-fault-tolerant quantum processors, but their lack of convergence guarantees and impractical number of cost function estimations prevent systematic scaling of experiments to large systems. Alternatives to variational approaches are needed for large-scale experiments on pre-fault-tolerant devices. Here, we use a superconducting quantum processor to compute eigenenergies of quantum many-body systems on two-dimensional lattices of up to 56 sites, using the Krylov quantum diagonalization algorithm, an analog of the well-known classical diagonalization technique. We construct subspaces of the many-body Hilbert space using Trotterized unitary evolutions executed on the quantum processor, and classically diagonalize many-body interacting Hamiltonians within those subspaces. These experiments demonstrate exponential convergence towards an estimate of the ground state energy, and show that quantum diagonalization algorithms are poised to complement their classical counterparts at the foundation of computational methods for quantum systems. The estimation of low energies of many-body systems is a cornerstone of the computational quantum sciences. This paper demonstrates on a superconducting quantum processor that the Krylov quantum diagonalization algorithm is poised to complement its classical counterparts at the foundation of computational methods for quantum systems.

arXiv:2407.14431•Nature Communications•Jun 24, 2025•29 citations

Predicting ground state, excited states and long-time evolution of many-body systems from short-time evolution on a quantum computer

Edgar Andres Ruiz Guzman, Denis Lacroix A

The generating function of a Hamiltonian $H$ is defined as $F(t)=\langle e^{-itH}\rangle$, where $t$ is the time and where the expectation value is taken on a given initial quantum state. This function gives access to the different moments of the Hamiltonian $\langle H^{K}\rangle$ at various orders $K$. With the constraint of minimizing the quantum resources needed on near-term quantum computers, we show that the evaluation of the generating function can be made with only one extra ancillary qubit. Due to the limited stability of actual quantum devices, the function $F(t)$ can a priori be estimated on a restricted time interval limiting automatically the orders of the moments that could be computed. Despite of this current limitation and even with a small number of moments, a post-processing on classical computers can be used to predict approximate ground or excited state energies and/or approximate long-time evolutions. This post-processing can be achieved using methods based on the Krylov space and/or on the $t$-expansion approach that is based on imaginary time evolution. Hybrid quantum-classical calculations are illustrated in many-body interacting systems using the pairing and Fermi-Hubbard models. Possible extensions using symmetry breaking and restoration as well as a multi-reference framework are discussed.

•Apr 16, 2021•2 citations
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 and a random local longitudinal magnetic field. In this method, we introduce infinitesimal quantum interactions that do not commute with the original Ising Hamiltonian, and repeatedly generate and truncate direct product states, inspired by the Krylov subspace method, to obtain the low-energy states of the original classical Ising Hamiltonian. The computational cost is controlled by the form of infinitesimal quantum interactions (e.g., one-body or two-body interactions) and the numbers of infinitesimal interaction terms introduced, different initial states considered, and low-energy states kept during the iteration. For a demonstrate of the method, here we introduce as the infinitesimal quantum interactions pair products of Pauli XXX operators acting on different sites and on-site Pauli XXX operators into the random Ising Hamiltonian, in which the numerical cost is O(N3)O(N^3)O(N3) per iteration with the system size NNN. We consider 120 instances of the random coupling realizations for the random Ising Hamiltonian with NNN up to 600 and search the 120 lowest-energy states for each instance. We find that the time-to-solution by the quantum-inspired method proposed here, with parallelization in terms of the different initial states, for searching the ground state of the random Ising Hamiltonian scales approximately as N5N^5N5 for NNN up to 600. We also examine the basic physical properties such as the ensemble-averaged ground-state and first-excited energies and the ensemble-averaged number of states in the low-energy region of the random Ising Hamiltonian.
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 fully connected Ising models with random interactions and on the shortest vector problem (SVP). The latter is a fundamental lattice problem underlying the security of many post-quantum cryptographic schemes, and its solution can be mapped to the first excited state of an Ising Hamiltonian. For the fully connected Ising models, we show that, on the tested instances, ExcLQA outperforms both a matrix-product-state-based method and simulated annealing. Notably, even when only a lower bound on the ground-state energy is provided, rather than the exact ground-state information required by these competing methods, ExcLQA still achieves superior performance. For the SVP, ExcLQA finds exact solutions for instances up to rank 46, and outperforms the Metropolis-Hastings algorithm in terms of solved ratio, number of shots, and approximation factor on the tested instances.
Estimating ground state energies of many-body Hamiltonians is a central task in many areas of quantum physics. In this Letter, we give quantum algorithms which, given any k-body Hamiltonian H, compute an estimate for the ground state energy and prepare a quantum state achieving said energy, respectively. Specifically, for any ϵ>0, our algorithms return, with high probability, an estimate of the ground state energy of H within additive error ϵM, or a quantum state with the corresponding energy. Here, M is the total strength of all interaction terms, which in general is extensive in the system size. Our approach makes no assumptions about the geometry or spatial locality of interaction terms of the input Hamiltonian and thus handles even long-range or all-to-all interactions, such as in quantum chemistry, where lattice-based techniques break down. In this fully general setting, the run-time of our algorithms scales as 2^{cn/2} for c<1, yielding the first quantum algorithms for low-energy estimation breaking a standard square root Grover speedup for unstructured search. The core of our approach is remarkably simple, and relies on showing that an extensive fraction of the interactions can be neglected with a controlled error. What this ultimately implies is that even arbitrary k-local Hamiltonians have structure in their low energy space, in the form of an exponential-dimensional low energy subspace.
The generating function of a Hamiltonian HHH is defined as F(t)=⟨e−itH⟩F(t)=\langle e^{-itH}\rangleF(t)=⟨e−itH⟩, where ttt is the time and where the expectation value is taken on a given initial quantum state. This function gives access to the different moments of the Hamiltonian ⟨HK⟩\langle H^{K}\rangle⟨HK⟩ at various orders KKK. The real and imaginary parts of F(t)F(t)F(t) can be respectively evaluated on quantum computers using one extra ancillary qubit with a set of measurement for each value of the time ttt. The low cost in terms of qubits renders it very attractive in the near term period where the number of qubits is limited. Assuming that the generating function can be precisely computed using quantum devices, we show how the information content of this function can be used a posteriori on classical computers to solve quantum many-body problems. Several methods of classical post-processing are illustrated with the aim to predict approximate ground or excited state energies and/or approximate long-time evolutions. This post-processing can be achieved using methods based on the Krylov space and/or on the ttt-expansion approach that is closely related to the imaginary time evolution. Hybrid quantum-classical calculations are illustrated in many-body interacting systems using the pairing and Fermi-Hubbard models.
This archive contains the numerical data and scripts used to generate the figures for the paper “Energy-selective quantum search with Ising Hamiltonian phase oracles”. The main numerical dataset is used for the scaling analysis of the correlation-induced resonance displacement φ₀ in the zero-field random Ising ensemble. The simulations use dimensionless units with σ_J = 1 and the Hamiltonian H(s) = 2 sum_{i<j} J_ij s_i s_j, where the couplings are independent Gaussian random variables, J_ij ~ N(0, 1), and h_i = 0. For each random Ising instance, the archive stores the truncated characteristic-function coefficients g_m = 2^{-n} Tr exp(-i m T H), m = 0, ..., 15. These coefficients are used to extract the local displacement φ₀ from the zero of the imaginary part of the response function C(φ) = 2 sum_{m=0}^{15} g_m (-1)^m exp(i m φ) - 1. The quantity plotted in the paper is the disorder-averaged second moment <φ₀²> and the scaled combination n⁶<φ₀²>. The Monte Carlo average is over independent disorder realizations only. For each realization, the trace over spin configurations is evaluated deterministically. The data cover even system sizes n = 18, 20, 22, ..., 36. For the largest systems, the computation splits the spins into two equal halves, performs GPU block contractions, and uses the zero-field spin-flip symmetry H(s)=H(-s) to reduce the sum by a factor of two. Archive contents - scripts/01_generate_phi0_coefficients.py Generates the characteristic-function coefficient files g_m for the random Ising ensemble. - scripts/02_analyze_phi0_scaling.py Computes φ₀, bootstrap confidence intervals, the finite-n covariance-sum comparison, and the scaling plots. - scripts/03_make_gaussian_amplification.py Generates the Gaussian amplification figure used as Fig. 1 in the paper. - data/phi0_coefficients/ Directory for the NumPy .npz files containing the characteristic-function coefficients. The production files have names of the form Nq_<n>_K_<K>.npz. The .npz files are saved without pickle objects. They can be read with standard NumPy using np.load. Typical usage To regenerate the Gaussian amplification figure: python scripts/03_make_gaussian_amplification.py --output-dir output/fig1_gaussian To analyze the φ₀ scaling data: python scripts/02_analyze_phi0_scaling.py \ --data-dir data/phi0_coefficients \ --output-dir output/phi0_scaling To run a short test calculation of the characteristic-function coefficients: python scripts/01_generate_phi0_coefficients.py \ --smoke-test \ --output-dir output/smoke_test_coefficients To regenerate the full production dataset on a CUDA-capable GPU: python scripts/01_generate_phi0_coefficients.py \ --production \ --output-dir data/phi0_coefficients The production calculations were performed using CuPy on an NVIDIA GPU. The analysis and plotting scripts use NumPy, pandas, and Matplotlib.
The estimation of low energies of many-body systems is a cornerstone of the computational quantum sciences. Variational quantum algorithms can be used to prepare ground states on pre-fault-tolerant quantum processors, but their lack of convergence guarantees and impractical number of cost function estimations prevent systematic scaling of experiments to large systems. Alternatives to variational approaches are needed for large-scale experiments on pre-fault-tolerant devices. Here, we use a superconducting quantum processor to compute eigenenergies of quantum many-body systems on two-dimensional lattices of up to 56 sites, using the Krylov quantum diagonalization algorithm, an analog of the well-known classical diagonalization technique. We construct subspaces of the many-body Hilbert space using Trotterized unitary evolutions executed on the quantum processor, and classically diagonalize many-body interacting Hamiltonians within those subspaces. These experiments demonstrate exponential convergence towards an estimate of the ground state energy, and show that quantum diagonalization algorithms are poised to complement their classical counterparts at the foundation of computational methods for quantum systems. The estimation of low energies of many-body systems is a cornerstone of the computational quantum sciences. This paper demonstrates on a superconducting quantum processor that the Krylov quantum diagonalization algorithm is poised to complement its classical counterparts at the foundation of computational methods for quantum systems.
The generating function of a Hamiltonian HHH is defined as F(t)=⟨e−itH⟩F(t)=\langle e^{-itH}\rangleF(t)=⟨e−itH⟩, where ttt is the time and where the expectation value is taken on a given initial quantum state. This function gives access to the different moments of the Hamiltonian ⟨HK⟩\langle H^{K}\rangle⟨HK⟩ at various orders KKK. With the constraint of minimizing the quantum resources needed on near-term quantum computers, we show that the evaluation of the generating function can be made with only one extra ancillary qubit. Due to the limited stability of actual quantum devices, the function F(t)F(t)F(t) can a priori be estimated on a restricted time interval limiting automatically the orders of the moments that could be computed. Despite of this current limitation and even with a small number of moments, a post-processing on classical computers can be used to predict approximate ground or excited state energies and/or approximate long-time evolutions. This post-processing can be achieved using methods based on the Krylov space and/or on the ttt-expansion approach that is based on imaginary time evolution. Hybrid quantum-classical calculations are illustrated in many-body interacting systems using the pairing and Fermi-Hubbard models. Possible extensions using symmetry breaking and restoration as well as a multi-reference framework are discussed.