Planted-Solution Pauli Hamiltonians as a Quantum Benchmarking Primitive

This paper introduces a framework for constructing Pauli Hamiltonians with exactly known ground-state energies by embedding planted block-product states, serving as a versatile quantum benchmarking primitive that inherits classical hardness properties and supports optional Clifford conjugation.

The Gist

Imagine you are trying to test a new, super-smart robot designed to solve the hardest puzzles in the universe. The problem is: How do you know if the robot is actually right?

If the puzzle is easy, you can solve it yourself on a piece of paper to check the answer. But if the puzzle is so hard that even the world's fastest supercomputers can't solve it, you have no way to verify if the robot is telling the truth or just making things up. This is the "verification gap" that scientists face when testing quantum computers.

This paper introduces a clever solution: The "Planted" Puzzle.

The Core Idea: Hiding a Treasure Map

Think of the researchers as puzzle makers who want to create a "hard-looking" puzzle that actually has a known solution.

1. The "Planted" Solution: First, they secretly decide on the correct answer. Let's call this the "Treasure." They build a specific, simple state (like a row of coins all showing "Heads") and decide, "This is the winner."
2. Building the Trap: Next, they build a massive, complex machine (a Hamiltonian) around this treasure. They do this by stacking many small, local rules on top of each other.
   • Analogy: Imagine you have a room full of people. You tell each small group of three people, "Make sure your three coins match the secret pattern I gave you."
   • Because the groups overlap (Person A is in Group 1 and Group 2), the rules get tangled. The final machine looks like a chaotic, jumbled mess of instructions.
3. The Scramble: To make it even harder, they apply a "Clifford Scramble." This is like taking the whole room, spinning it around, and shuffling the people so that the original groups are no longer obvious.
   • The Magic Trick: Even though the room looks completely chaotic and the groups are hidden, the "Treasure" (the ground state) is still there, and it still wins. The rules haven't changed the prize; they've just hidden the map.

Why This is Special

Usually, if a puzzle looks this messy and complex, no one knows the answer. If you ask a quantum computer to solve it, you have no way to check if it got it right.

But with this method, the researchers know the answer beforehand because they planted it. However, the answer is not visible in the messy instructions they give to the computer.

• For the Computer: It sees a giant, confusing wall of math (a "Pauli Hamiltonian") with no obvious patterns. It has to work hard to find the lowest energy state.
• For the Researchers: They hold the "Certification Key." They know exactly what the answer should be, so they can grade the computer's performance.

The "Hardness" Spectrum

The paper explains that they can tune how hard the puzzle is:

• Easy Mode: They can make the rules simple and the groups small.
• Hard Mode: They can make the rules overlap more and scramble the instructions deeper.
• The "Classical" Connection: They can even turn these quantum puzzles into classic logic puzzles (like Sudoku or SAT problems) just by changing the rules slightly. This means if a puzzle is known to be hard for classical computers, they can "plant" that same difficulty into their quantum version.

Testing the Robot

The researchers used this method to create thousands of these "Planted" puzzles. They looked at how the "energy gap" (the difference between the best answer and the second-best answer) behaved as the puzzles got bigger.

• They found that as the puzzles got larger, the gap between the best and second-best answers got smaller and smaller (exponentially).
• This makes the puzzle harder to solve because the computer has to be extremely precise to find the true winner among many nearly-winner options.

The Bottom Line

This paper doesn't claim to have solved the hardest problems in physics. Instead, it provides a controlled testing ground.

Think of it like a driving test for self-driving cars.

• Old way: You drive the car in a random storm. If it crashes, you don't know if it was the storm or the car's bad software.
• This paper's way: You build a specific, tricky obstacle course where you know the perfect path exists. You hide the path so the car has to figure it out, but you keep the map in your pocket to grade the car.

They have also released the software and the "answer keys" to the public, so other scientists can use these planted puzzles to test their own quantum algorithms fairly and reliably.

Technical Summary

Technical Summary: Planted-Solution Pauli Hamiltonians as a Quantum Benchmarking Primitive

Problem Statement
The ability to benchmark quantum devices and algorithms designed for ground-state energy estimation is hindered by a fundamental verification gap. For problems where classical verification is intractable (the regime intended for quantum advantage), there is no trusted reference solution to validate results. Conversely, standard solvable quantum models (e.g., free-fermion or commuting projector systems) are often too simple to stress-test algorithms intended for generic, interacting many-body systems. The challenge is to construct benchmark instances that are:

1. Efficiently verifiable: Exact ground-state energies are known by construction.
2. Non-trivial: They lack visible algebraic or structural features that allow solvers to bypass the intended difficulty.
3. Scalable: They can be generated systematically for varying system sizes and complexities.

Methodology
The authors propose a framework for constructing Planted-Solution Pauli Hamiltonians. The construction pipeline involves four main stages:

1. Partitioning and Planting: A system of $n$ qubits is partitioned into disjoint blocks $\{A_1, \dots, A_M\}$. For each block, a normalized state $|\psi_{A_i}\rangle$ is drawn Haar-randomly. These define a global product ground state $|\Psi^\star\rangle = \bigotimes_i |\psi_{A_i}\rangle$.
2. Local Clause Construction: Random subsets of blocks $S_k$ are selected to define overlapping support regions $\Lambda_k$. For each region, a local Hamiltonian $H^{(k)}$ is constructed such that the restriction of the planted state, $|\psi_{\Lambda_k}\rangle$, is its ground state. The excited states of $H^{(k)}$ are chosen generically (e.g., via a random orthonormal basis completion).
3. Assembly: The full Hamiltonian is formed as a weighted sum of these local clauses: $H = \sum_k \alpha_k H^{(k)}$. Because each local term acts on a bounded number of qubits ($O(1)$), the total Hamiltonian can be expanded exactly into a polynomial-size linear combination of Pauli strings.
4. Obfuscation (Optional): To further hide the planted structure, a global Clifford circuit $U$ of bounded depth is applied: $H' = U H U^\dagger$. Since Clifford unitaries map Pauli strings to Pauli strings, $H'$ retains a compact Pauli representation. The ground state becomes the stabilizer state $U|\Psi^\star\rangle$, which is typically highly entangled but remains efficiently classically describable.

Key Contributions

• A New Benchmark Primitive: The paper introduces a family of Hamiltonians where the ground-state energy is known a priori by design, yet the model is presented solely as a dense, non-commuting sum of Pauli operators with no manifest block structure.
• Bridging Classical and Quantum Hardness: The framework subsumes classical planted constraint-satisfaction problems (CSPs) as a diagonal special case. By embedding classical planted $k$-SAT instances into the diagonal subclass, the construction allows for the direct inheritance of classical hardness properties. Non-diagonal choices allow for a continuous interpolation toward genuinely quantum benchmarks.
• Multiple Planted Solutions: The authors extend the framework to support multiple, mutually orthogonal global ground states. This creates an optimization landscape with competing global attractors that are locally indistinguishable but globally incompatible, challenging solvers that rely on local gradients or initialization.
• Open-Source Implementation: The authors provide open-source software, certification keys, and example instances to ensure reproducibility and allow independent verification of results across different platforms and algorithms.

Results and Characterization
The authors performed numerical characterization on single-planted instances with random clause eigenbases:

• Degeneracy: At low clause counts ($K$), a fraction of instances exhibit numerically degenerate ground states. This fraction decreases as $K$ and system size $n$ increase.
• Spectral Gap Scaling:
  • The unnormalized spectral gap grows approximately linearly with the number of clauses $K$.
  • The intensively normalized gap ($\Delta_1/K$) increases with clause density ($K/n$).
  • Crucially, at a fixed clause density, the intensive gap decreases approximately exponentially with system size $n$. The "half-life" of the gap (the number of qubits required to halve the gap) increases with clause density, ranging from $\approx 1.9$ qubits at $K=10$ to $\approx 3.3$ qubits at $K=26$.
• Nature of Hardness: The authors explicitly state that these spectral features (such as gap closing) are reported as properties of the ensemble. They do not claim that these features constitute a proof of algorithmic hardness or that recovering the block structure is computationally intractable. The difficulty is empirical and intended to stress-test solvers.

Significance and Claims
The paper positions this framework as a controlled and tunable benchmarking environment. Its primary significance lies in providing a rigorous source of reference instances where:

• The ground-state energy is known exactly, enabling objective evaluation of algorithm accuracy and convergence.
• The planted structure is not manifest in the input representation, preventing solvers from exploiting trivial symmetries.
• The difficulty can be tuned via parameters such as block size, constraint density, and scrambling depth.

The authors emphasize that the framework does not claim to solve the QMA-hardness problem or assert that structure recovery is theoretically hard. Instead, it offers a practical tool for assessing the reliability and scaling behavior of quantum simulation methods in the absence of classical verification, filling the gap between trivial solvable models and intractable generic systems. Future work suggested includes extending the framework to dynamical benchmarks by identifying subclasses where time-dependent quantities can be efficiently evaluated classically in a hidden representation.