Source-linked AI summary
Improved classical optimization of fermionic Hamiltonians beyond Gaussian states
Ojas Parekh
TL;DR
Approximating extremal eigenvalues of quartic fermionic Hamiltonians is difficult because inverse-polynomial additive precision is QMA-hard. The paper gives a randomized polynomial-time classical algorithm combining Gaussian and sparse Fock-basis candidates, with an Ω(1/√n) general approximation guarantee. Its eigenvalue bound connects the optimum to Gaussian energy and the normalized Frobenius norm.
Problem
Inverse-polynomial additive approximation of extremal eigenvalues of quartic fermionic Hamiltonians is QMA-hard, motivating efficient coarser approximations.
Source: §1 · p. 1Method
A bound relating λmax(H) to Gaussian energy and the normalized Frobenius norm guides an algorithm that compares Gaussian and sparse Fock-basis candidates.
Source: §1.1 · p. 3Results
The randomized polynomial-time classical algorithm improves the general guarantee to Ω(1/√n) and outputs a Gaussian state or a superposition of at most t + 1 Fock basis states.
Source: §1 · p. 1, §1.1 · p. 2Takeaways & Limitations
For this general quartic-Hamiltonian setting, the guarantee can be achieved with either a fermionic Gaussian state or a polynomially sparse Fock-basis state.
Source: §1.1 · p. 2Unless otherwise stated, the results concern homogeneous quartic Hamiltonians on n ≥ 2 modes.
Source: §2 · p. 6
Abstract
from arXiv · showhide
We give a polynomial-time randomized classical algorithm that approximates the largest eigenvalue $\lambda_{\max}$ of a traceless quartic fermionic Hamiltonian $H$ on $n$ modes. The algorithm achieves energy at least $\lambda_{\max}/O(\sqrt n)$ and outputs either a fermionic Gaussian state or a polynomially sparse state in the Fock basis. This is achieved through a new upper bound on $\lambda_{\max}$ in terms of the maximum energy of a Gaussian state and $\sqrt{2^{-n}\operatorname{Tr}(H^2)}$.
1 Introduction
Extremal eigenvalue optimization for quartic fermionic Hamiltonians is computationally hard at inverse-polynomial precision, motivating coarser efficient approximations. The paper improves the general classical guarantee to Ω(1/√n) using Gaussian and non-Gaussian candidate states and a bound relating the optimum to Gaussian energy and the normalized Frobenius norm.
1.2 Related work
- Earlier work gave an Ω(1/(n log n)) classical guarantee for quadratic and quartic terms, while Gaussian states alone attain only Θ(1/√n) on quartic SYK.The paper identifies its Ω(1/√n) general guarantee as an improvement for general quartic Hamiltonians; related work also gives constant-factor Gaussian approximations under sparsity or interaction assumptions.Source: §1 · p. 1, §1.2 · pp. 3–4
1.1 Problem and main result
- The randomized polynomial-time classical algorithm achieves an Ω(1/√n) approximation and returns either a Gaussian state or a superposition of at most t + 1 Fock basis states.The guarantee holds with probability at least 2/3, and the output energy is efficiently computable classically.Source: §1 · p. 1, §1.1 · p. 2
- The eigenvalue bound relates λmax(H) to the Gaussian optimum and normalized Frobenius norm, yielding the two-case strategy for obtaining an Ω(1/√n) approximation.When Gaussian energy is large relative to λmax(H), the best Gaussian state approximates well; otherwise √nσ is large and an Ω(σ)-energy state suffices.Source: §1.1 · pp. 2–3
- The algorithm compares a Gaussian candidate with a sparse Fock-basis candidate, addressing whether Gaussian energy is large or the normalized Frobenius norm supplies the needed scale.The Gaussian candidate approximates the Gaussian optimum within Ω(1/log n); the other candidate is produced by a simple classical algorithm.Source: §1.1 · p. 3
1.3 Technical overview
- A Gaussian mixture approximates state quartic moment matrices, and a specialized conversion from operator to Frobenius norm introduces a Θ(√n) factor that drives the approximation guarantee.For quartic Hamiltonians, a signed sum-of-squares representation motivates Gaussian variance bounds; a suitable Gaussian mixture removes the dependence of the chosen Gaussian on H.Source: §1.3 · pp. 4–5
- The overview first shows that some Gaussian state earns 1/3 the maximum energy, then improves the guarantee to 1/2 using a stronger bound in Corollary 3.4.Source: §1.3 · p. 4
2 Preliminaries
The preliminaries establish the Majorana-operator notation and moment-matrix framework used to represent quartic Hamiltonians, then summarize how Gaussian states encode moments and energies.
2 Preliminaries
- The analysis assumes homogeneous quartic Hamiltonians on n ≥2 modes and uses normalized trace, operator-norm, and positive-semidefinite-order notation.The trace Tr is unnormalized, while τ = 2^-n Tr_H.Source: §2 · pp. 5–6
2.1 Majorana monomials
- Majorana monomials form an orthonormal operator basis for the normalized-trace inner product, and a homogeneous quartic operator’s square has only degrees zero, four, and eight.Its degree-zero component is τ[R^2]I.Source: §2.1 · p. 6
2.2 Moment and coefficient matrices
- Moment matrices encode identity and quartic moments, while coefficient matrices represent quartic Hamiltonians through the trace inner product.The paper’s analysis uses these objects to approximate a state’s quartic moment matrix by that of a Gaussian mixture.Source: §2.2 · pp. 6–7
2.3 Gaussian states
- Wick’s theorem computes Gaussian-state moments from the covariance matrix, enabling polynomial-time computation of the quartic moments and energies used here.The paper also states that Gaussian states can be represented by their quadratic moments.Source: §2.3 · p. 8
3 Approximating the moment matrix of a state
The section shows that a state’s quartic moment matrix can be approximated by that of a Gaussian mixture. A coefficient-matrix-dependent argument and finite-dimensional convexity establish the approximation, with a stronger consequence for positive-semidefinite coefficient matrices.
3 Approximating the moment matrix of a state
- A state’s moment matrix can be approximated in operator norm by that of a mixture of Gaussian states.The section first obtains a Gaussian approximation dependent on a coefficient matrix, then removes that dependence by taking a mixture.Source: §3 · pp. 10–13
- For every density matrix and real symmetric coefficient matrix, the paper derives a Gaussian moment-matrix approximation bound that depends on that coefficient matrix.The proof starts from a Gaussian maximizing overlap with a top eigenstate of the coefficient-matrix Hamiltonian.Source: §3 · p. 12
- Convexity and strict separation remove the dependence on the coefficient matrix, yielding a Gaussian mixture whose moment matrix is within operator norm 2 of the target.The mixture is expressed using finitely many pure Gaussian states.Source: §3 · pp. 12–13
- For positive-semidefinite coefficient matrices, the section’s results imply that a Gaussian state earns a constant fraction of the maximum energy.Source: §3 · p. 13
4 Bounding the maximum eigenvalue
The section develops an operator-norm bound for homogeneous quartic operators and a sharper conversion between moment-matrix norms for physical states. These ingredients yield the paper’s eigenvalue bound.
4 Bounding the maximum eigenvalue
- For homogeneous quartic R, Lemma 4.1 relates R^2 to its coefficient matrix, and the proof bounds R^2 using conjugation by Majorana operators.The identity from Lemma 4.1 is also used to prove Lemma 1.3.Source: §4 · pp. 13–14
- For homogeneous quartic R with τ[R²] = 1 and ∥CR∥op ≤ 1/√n, the Gaussian-state comparison bounds the largest eigenvalue of HA by 25.The comparison first gives λmax(HA) ≤G(HA) + 2 Tr[A]; here Tr[A] = 6 and ∥A∥op ≤1/n.Source: §4 · p. 15
- Special properties of physical-state moment matrices improve the conversion from operator norm to Frobenius norm over more generic relationships.This norm conversion supplies an ingredient for the eigenvalue bound.Source: §4 · pp. 15–16
- The section proves an eigenvalue bound by combining an approximation of the top-state moment matrix by a Gaussian mixture with a Cauchy–Schwarz argument.The Gaussian mixture has moment matrix within Frobenius norm 5√n of the top state’s moment matrix.Source: §4 · pp. 13, 16
5 Constructing a good candidate state
The section constructs a sparse candidate by applying a shifted Hamiltonian to random Fock basis states and accepting one whose normalized energy exceeds a threshold. A cubic trace bound makes polynomially many trials sufficient.
5 Constructing a good candidate state
- Applying 16σI + H to a uniformly random Fock basis state and testing the normalized result yields a candidate with energy greater than σ/16 when accepted.The algorithm uses the test to reject zero vectors as well.Source: §5 · pp. 16–17
- A cubic trace bound implies that O(t^3/2) independent trials suffice to find an accepted state with high probability.The stated trial count is N = ⌈32b/15⌉, with the rejection probability bounded using the acceptance probability p ≥ 15/(16b).Source: §5 · pp. 16–17
- For n ≥ 2, the randomized polynomial-time algorithm returns a state description satisfying the lemma’s guarantee with probability at least 5/6.The supplied lemma statement does not specify the omitted guarantee expression.Source: §5 · p. 17
- The resulting state is proportional to (16σI + H)|y⟩ for some basis string y and is supported on at most t + 1 Fock basis strings.Its energy is efficiently computable classically, and the running time is polynomial in n and the input length.Source: §5 · p. 17
6 Establishing the approximation guarantee
The section combines an eigenvalue bound, a sparse-state construction, and a Gaussian-state approximation algorithm. It returns the higher-energy candidate, with success probability at least 2/3.
6 Establishing the approximation guarantee
- The proof combines the eigenvalue bound, the sparse-state result, and the Gaussian-state approximation algorithm.It runs the Gaussian approximation algorithm twice independently and keeps the better Gaussian candidate.Source: §6 · p. 18
- The randomized polynomial-time algorithm returns either a fermionic Gaussian state or a superposition of at most t + 1 Fock basis states, with probability at least 2/3.The output energy is efficiently computable classically, and the running time is polynomial in n and the input length.Source: §6 · p. 18
- The algorithm returns the higher-energy candidate, or the Gaussian state if the sparse-state algorithm reports failure.On the joint success event, the cited proof combines the two candidate guarantees; both candidate descriptions and energies are computable in polynomial time.Source: §6 · p. 18
7 Discussion
The discussion identifies an Ω(1/√n) approximation for homogeneous quartic Hamiltonians using Gaussian states supplemented by a norm-based approximation. It leaves open whether Gaussian states alone can achieve this approximation and whether broader techniques can improve the results.
7 Discussion
- Supplementing Gaussian states with an approximation based on the normalized Frobenius norm σ yields an Ω(1/√n) approximation for homogeneous quartic fermionic Hamiltonians.The discussion asks whether this approximation is possible using only Gaussian states and whether it is possible in polynomial time.Source: §7 · p. 18
- The discussion asks whether the moment-matrix bound has broader applications and whether SDP hierarchies and sums-of-squares bounds could improve the results.The results do not rely on SDP hierarchies but make critical use of moment and coefficient matrices.Source: §7 · p. 18
AI methodology
The methodology account describes extensive use of GPT-6 Astra in developing the work’s research directions, bounds, algorithm, and proofs. The author reports sustained exchanges and contributions to reformulating and simplifying the proofs.
AI methodology
- GPT developed additive bounds of the form (1.5) and an Ω(1/n^3/4)-approximation algorithm, which the author and GPT improved to Ω(1/√n).The improved result retained the same type of additive bound, while the proof techniques changed substantially.Source: AI methodology · p. 19
- The author contributed to reformulating and simplifying the proofs, including suggesting a simpler optimization formulation for the variational argument in Lemma 3.1.The results and proofs reached their present form through exchanges over approximately a month.Source: AI methodology · p. 19