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

Optimal ground state approximations for sparse Hamiltonians

Daniel Hothem, Ojas Parekh, Kevin Thompson

Published Mar 1, 2023• 0 citations
Publisher
DOI
10.2172/2431619

Related papers

Efficient Quantum Algorithms for Simulating Sparse Hamiltonians

Dominic William Berry, Graeme Ahokas, Richard Cleve +1 more

arXiv:quant-ph/0508139•Communications in Mathematical Physics•Dec 13, 2006•814 citations

Optimizing sparse fermionic Hamiltonians

Yaroslav Herasymenko, Maarten Stroeks, Jonas Helsen +1 more

We consider the problem of approximating the ground state energy of a fermionic Hamiltonian using a Gaussian state. In sharp contrast to the dense case [1, 2], we prove that strictly q -local sparse fermionic Hamiltonians have a constant Gaussian approximation ratio; the result holds for any connectivity and interaction strengths. Sparsity means that each fermion participates in a bounded number of interactions, and strictly q -local means that each term involves exactly q fermionic (Majorana) operators. We extend our proof to give a constant Gaussian approximation ratio for sparse fermionic Hamiltonians with both quartic and quadratic terms. With additional work, we also prove a constant Gaussian approximation ratio for the so-called sparse SYK model with strictly 4 -local interactions (sparse SYK- 4 model). In each setting we show that the Gaussian state can be efficiently determined. Finally, we prove that the O(n−1/2) Gaussian approximation ratio for the normal (dense) SYK- 4 model extends to SYK- q for even q>4 , with an approximation ratio of O(n1/2–q/4) . Our results identify non-sparseness as the prime reason that the SYK- 4 model can fail to have a constant approximation ratio [1, 2].

arXiv:2211.16518•Quantum•Aug 10, 2023•25 citations

Improved bounds on many-body hamiltonians

Jean-Louis Basdevant, André Martin, J. M. Richard

Nuclear Physics B•Oct 1, 1990•45 citations

Optimal Solution of Max-Cut Problem Using Quantum Adiabatic Approximation

WANG Fumin, NI Ming, ZHOU Ming, WU Yongzheng

When using classical approximation algorithm to solve the max-cut problem,the time complexity increases with the complexity of graph.In order to improve the solution efficiency,this paper uses quantum adiabatic approximation algorithm to solve the ground state for Hamiltonian of max-cut problem,and the ground state value is the optimal solution.The time complexity is independent of the number of vertices and edges of graph using quantum adiabatic approximation algorithm,and the max-cut problem can be calculated within finite steps.The computing process is based on the ProjectQ software developed.By establishing the evolutionary path from initial Hamiltonian to max-cut problem Hamiltonian,the change of the expected value is analyzed to determine whether the algorithm can find the optimal solution of max-cut problem or not.Numerical analysis results show that,this algorithm can effectively improve the efficiency of solving the max-cut problem,the accuracy of solution is 0.999 9 for 3-vertex undirected graph and 6-vertex undirected sparse graph,and the results for the 6-vertex undirected complete graph is 0.969 6.

•Jan 1, 2020•0 citations

Optimizing Sparse SYK

Matthew Ding, Robbie King, Bobak T. Kiani +1 more

Finding the ground state of strongly-interacting fermionic systems is often the prerequisite for fully understanding both quantum chemistry and condensed matter systems. The Sachdev–Ye–Kitaev (SYK) model is a representative example of such a system; it is particularly interesting not only due to the existence of efficient quantum algorithms preparing approximations to the ground state such as Hastings–O'Donnell (STOC 2022), but also known no-go results for many classical ansatzes in preparing low-energy states. However, this quantum-classical separation is known to not persist when the SYK model is sufficiently sparsified, i.e., when terms in the model are discarded with probability 1 − p , where p = Θ ( 1 / n 3 ) and n is the system size. This raises the question of how robust the quantum and classical complexities of the SYK model are to sparsification.In this work we initiate the study of the sparse SYK model where p ∈ [ Θ ( 1 / n 3 ) , 1 ] and show there indeed exists a certain robustness of sparsification. We prove that with high probability, Gaussian states achieve only a Θ ( 1 / n ) -factor approximation to the true ground state energy of sparse SYK for all p ≥ Ω ( log ⁡ n / n 2 ) , and that Gaussian states cannot achieve constant-factor approximations unless p ≤ O ( log 2 ⁡ n / n 3 ) . Additionally, we prove that the quantum algorithm of Hastings–O'Donnell still achieves a constant-factor approximation to the ground state energy when p ≥ Ω ( log ⁡ n / n ) . Combined, these show a provable separation between classical algorithms outputting Gaussian states and efficient quantum algorithms for the goal of finding approximate sparse SYK ground states whenever p ≥ Ω ( log ⁡ n / n ) , extending the analogous p = 1 result of Hastings–O'Donnell.

arXiv:2506.09037•Quantum•Mar 16, 2026•4 citations

Simulating Sparse Hamiltonians with Star Decompositions

Andrew M. Childs, Robin Kothari

arXiv:1003.3683•Lecture notes in computer science•Jan 1, 2011•92 citations
We consider the problem of approximating the ground state energy of a fermionic Hamiltonian using a Gaussian state. In sharp contrast to the dense case [1, 2], we prove that strictly q -local sparse fermionic Hamiltonians have a constant Gaussian approximation ratio; the result holds for any connectivity and interaction strengths. Sparsity means that each fermion participates in a bounded number of interactions, and strictly q -local means that each term involves exactly q fermionic (Majorana) operators. We extend our proof to give a constant Gaussian approximation ratio for sparse fermionic Hamiltonians with both quartic and quadratic terms. With additional work, we also prove a constant Gaussian approximation ratio for the so-called sparse SYK model with strictly 4 -local interactions (sparse SYK- 4 model). In each setting we show that the Gaussian state can be efficiently determined. Finally, we prove that the O(n−1/2) Gaussian approximation ratio for the normal (dense) SYK- 4 model extends to SYK- q for even q>4 , with an approximation ratio of O(n1/2–q/4) . Our results identify non-sparseness as the prime reason that the SYK- 4 model can fail to have a constant approximation ratio [1, 2].
When using classical approximation algorithm to solve the max-cut problem,the time complexity increases with the complexity of graph.In order to improve the solution efficiency,this paper uses quantum adiabatic approximation algorithm to solve the ground state for Hamiltonian of max-cut problem,and the ground state value is the optimal solution.The time complexity is independent of the number of vertices and edges of graph using quantum adiabatic approximation algorithm,and the max-cut problem can be calculated within finite steps.The computing process is based on the ProjectQ software developed.By establishing the evolutionary path from initial Hamiltonian to max-cut problem Hamiltonian,the change of the expected value is analyzed to determine whether the algorithm can find the optimal solution of max-cut problem or not.Numerical analysis results show that,this algorithm can effectively improve the efficiency of solving the max-cut problem,the accuracy of solution is 0.999 9 for 3-vertex undirected graph and 6-vertex undirected sparse graph,and the results for the 6-vertex undirected complete graph is 0.969 6.
Finding the ground state of strongly-interacting fermionic systems is often the prerequisite for fully understanding both quantum chemistry and condensed matter systems. The Sachdev–Ye–Kitaev (SYK) model is a representative example of such a system; it is particularly interesting not only due to the existence of efficient quantum algorithms preparing approximations to the ground state such as Hastings–O'Donnell (STOC 2022), but also known no-go results for many classical ansatzes in preparing low-energy states. However, this quantum-classical separation is known to not persist when the SYK model is sufficiently sparsified, i.e., when terms in the model are discarded with probability 1 − p , where p = Θ ( 1 / n 3 ) and n is the system size. This raises the question of how robust the quantum and classical complexities of the SYK model are to sparsification.In this work we initiate the study of the sparse SYK model where p ∈ [ Θ ( 1 / n 3 ) , 1 ] and show there indeed exists a certain robustness of sparsification. We prove that with high probability, Gaussian states achieve only a Θ ( 1 / n ) -factor approximation to the true ground state energy of sparse SYK for all p ≥ Ω ( log ⁡ n / n 2 ) , and that Gaussian states cannot achieve constant-factor approximations unless p ≤ O ( log 2 ⁡ n / n 3 ) . Additionally, we prove that the quantum algorithm of Hastings–O'Donnell still achieves a constant-factor approximation to the ground state energy when p ≥ Ω ( log ⁡ n / n ) . Combined, these show a provable separation between classical algorithms outputting Gaussian states and efficient quantum algorithms for the goal of finding approximate sparse SYK ground states whenever p ≥ Ω ( log ⁡ n / n ) , extending the analogous p = 1 result of Hastings–O'Donnell.