Ground state preparation of random all-to-all Hamiltonians using ADAPT-VQE

This paper demonstrates that the TETRIS-ADAPT-VQE algorithm can achieve high-fidelity ground state preparation for random all-to-all Hamiltonians like the SK and SYK models, though it remains efficient only for the SK model while failing to scale efficiently for dense or moderately sparse SYK models.

The Gist

Imagine you are trying to find the most stable, relaxed position for a massive, chaotic crowd of people. In the world of quantum physics, this "crowd" is a group of particles, and their "relaxed position" is called the ground state. Finding this state is crucial for understanding how materials behave, how black holes work, and even how gravity connects to quantum mechanics.

However, some of these crowds are incredibly difficult to organize. They are "random" and "all-to-all," meaning every single particle is constantly interacting with every other particle, not just its neighbors. This creates a level of complexity that is like trying to untangle a knot where every strand is tied to every other strand.

This paper investigates whether we can use a new type of quantum computer algorithm, called TETRIS-ADAPT-VQE, to organize these chaotic crowds efficiently. Think of this algorithm as a smart, adaptive builder that constructs a specific "circuit" (a set of instructions) to guide the particles into their calmest state. The researchers tested this on three different types of chaotic crowds:

1. The Quantum SK Model: A crowd where everyone interacts with everyone else randomly.
2. The Dense SYK Model: A crowd where everyone interacts with everyone else, but the rules are slightly different (involving specific types of particles called Majorana fermions).
3. The Sparse SYK Model: A "thinned out" version of the Dense SYK model, where many of the interactions are removed to see if it becomes easier to manage.

The Results: A Tale of Two Crowds

The researchers found that the difficulty of organizing these crowds depends entirely on which crowd you are dealing with.

1. The SK Model: The Manageable Crowd
For the Quantum SK model, the algorithm worked beautifully. It was like building a house with a standard set of bricks. As the crowd got bigger (up to 18 people), the number of instructions needed to organize them grew in a predictable, manageable way (polynomial growth). The algorithm successfully found the perfect resting position with near-perfect accuracy (over 99.99% correct).

• The Takeaway: For this specific type of random interaction, quantum computers look very promising for solving the problem efficiently.

2. The SYK Models: The Impossible Knot
For both the "Dense" and "Sparse" SYK models, the story was very different. Even though the "Sparse" model had fewer interactions (like removing some of the tangled strings), the algorithm still struggled immensely.

• The Problem: As the crowd grew (up to 20 particles), the number of instructions required to organize them exploded exponentially. It's as if adding just one more person to the room required doubling the entire construction crew and the amount of building materials.
• The Surprise: The researchers expected that making the model "sparse" (removing interactions) would make it easier. However, they discovered that the entanglement (the invisible, complex connections between the particles) remained just as messy and "volume-heavy" as the dense version. The particles were still so deeply linked that removing a few rules didn't simplify the overall puzzle.
• The Takeaway: Even with a powerful quantum algorithm, preparing the ground state for these specific SYK models is currently too hard. The complexity grows too fast for the computer to handle as the system gets larger.

Why Does This Matter?

The paper concludes that while quantum computers might be great at solving the "SK" type of random problems, they hit a wall with the "SYK" type. The "Sparse" SYK model, which was hoped to be an easier version, turned out to be just as difficult because the fundamental nature of the particles' connections (their entanglement) didn't change just because there were fewer rules.

In short: The researchers built a very smart "organizer" (the algorithm). It worked perfectly for one kind of chaotic room but failed to scale up for the other two, proving that some quantum problems are inherently much harder to solve than others, regardless of how many connections you try to remove.

Technical Summary

Technical Summary: Ground State Preparation of Random All-to-All Hamiltonians using ADAPT-VQE

Problem Statement
The paper addresses the challenge of preparing ground states for random Hamiltonians with all-to-all interactions, specifically the quantum Sherrington-Kirkpatrick (SK) model and the Sachdev-Ye-Kitaev (SYK) model (in both dense and sparse variants). These systems are characterized by volume-law entanglement in their ground states, making them difficult to simulate using classical tensor network methods. While Neural Quantum States (NQS) have improved classical approximations, they struggle to reproduce the correct behavior of all volume-law states, particularly for the SYK model. Consequently, the authors investigate whether variational quantum algorithms can offer a quantum advantage in simulating these specific disordered systems, a question that remains open despite theoretical arguments suggesting that sufficiently sparse random Hamiltonians might be easy to prepare.

Methodology
The authors employ the TETRIS-ADAPT-VQE (Adaptive Derivative Assembled Problem-Tailored Variational Quantum Eigensolver) algorithm. This approach constructs compact, hardware-friendly quantum circuits by iteratively selecting operators from a predefined pool based on gradient information, avoiding the optimization issues associated with fixed ansätze.

Key methodological components include:

• Operator Pools: To respect the symmetries of the Hamiltonians and ensure efficient convergence, the authors construct symmetry-informed Pauli operator pools.
  • For the SK model, the pool includes operators $Z_i Y_j$ and $Y_i Z_j$ ($i < j$), derived from time-reversal and parity symmetries.
  • For the SYK models (dense and sparse), the pool includes $Z_i$, $X_i Y_j$, $Y_i X_j$, and $Z_i Z_j$ ($i < j$), respecting the $Z_2$ parity symmetry.
• Reference States: Simulations utilize an equal superposition of Néel states (for SK) or specific Néel states in the correct $Z_2$ parity sector (for SYK) as the initial reference state.
• Simulation Scope: The study performs noiseless classical simulations to evaluate scaling.
  • SK Model: Up to $L = 18$ sites (qubits).
  • SYK Models: Up to $N = 20$ Majorana fermions (corresponding to $n = 10$ qubits). The sparse SYK model uses a sparsification parameter $k_s = 9$.

Key Results
The performance of the algorithm varies significantly between the SK and SYK models:

1. Quantum SK Model:

   • The algorithm successfully constructs accurate ground states for up to $L=18$ qubits.
   • Fidelity: Achieves fidelities $\geq 99.9998\%$ across all tested instances.
   • Scaling: The preparation is efficient, with the two-qubit gate depth (CNOT count) and number of variational parameters scaling polynomially with system size.
   • Phase Dependence: The algorithm requires fewer iterations and parameters for $\Gamma = 3$ (paramagnetic phase) compared to $\Gamma = 1$ (near the spin-glass phase transition at $\Gamma = 1.5$), reflecting the changing complexity of the ground state.

2. Dense and Sparse SYK Models:

   • The algorithm achieves high fidelities ($\geq 99.3\%$) for up to $N=20$ Majorana fermions.
   • Scaling: Unlike the SK model, the two-qubit gate depth and number of parameters scale exponentially (or as a high-degree polynomial) with system size for both dense and sparse variants.
   • Sparsity Impact: While sparsification (reducing Hamiltonian terms from $O(N^4)$ to $O(N)$) significantly lowers the measurement cost for classical post-processing, it does not reduce the variational complexity required to prepare the ground state.
   • Entanglement Analysis: Both dense and sparse ($k_s=9$) SYK ground states exhibit volume-law entanglement entropy ($S_{EE} \propto N$) with nearly identical coefficients. This indicates that the difficulty in preparation is driven by the entanglement structure of the state rather than the number of Hamiltonian terms.

Significance and Claims
The paper claims that while TETRIS-ADAPT-VQE is an efficient method for preparing ground states of the quantum SK model (suggesting it is a suitable task for near-term quantum computers), it is not efficient for the dense or moderately sparse SYK models considered.

• Intrinsic Difficulty: The authors conclude that the exponential scaling observed for SYK models is likely intrinsic to the problem (due to volume-law entanglement) rather than an artifact of hyperparameter choices, as tested by varying reference states and operator pools.
• Limits of Sparsification: The work demonstrates that for $k_s = 9$, sparsification does not render the ground state preparation problem "easy" in the quantum sense, distinguishing these models from the "sufficiently sparse" Hamiltonians ($d=O(1)$) discussed in theoretical literature where preparation is argued to be easy.
• Open Questions: The authors note that it remains an open question whether ground-state preparation can be efficient for these models on quantum computers for less-sparse regimes ($k_s \gg 1$) or if alternative algorithms (e.g., AVQITE) might yield different results. They also found that ansatz transferability across different disorder instances does not work in practice for these systems.

In summary, the work provides a rigorous numerical benchmark showing that while variational quantum algorithms can handle certain all-to-all spin models efficiently, they currently face significant scaling barriers for fermionic models with volume-law entanglement like the SYK model, even when the Hamiltonian is sparsified.