updated 2025-08-17
It is a long-standing goal to find problems with rigorous quantum advantage. In classical optimization problems, evidence is dubious; however, when the output is a quantum state, there is (intuitively) more hope.
Here we describe a few quantum Hamiltonians, along with associated algorithms and known hardness results.
Recall that we use Pauli matrices \(P \in \{I, X, Y, Z\}\), and \(P_i\) means the Pauli matrix \(P\) at site \(i\). There are also fermionic Hamiltonians, but I will ignore those here.
This is defined by a graph \(G(V,E)\), where
\[H = \frac{1}{2} \sum_{(i,j) \in E} I_i \otimes I_j - X_i \otimes X_j - Y_i \otimes Y_j - Z_i \otimes Z_j\]Alternatively, this can be written as \(H = \sum_{(i,j) \in E} 2 \vert \psi^{-} \rangle \langle \psi^{-} \vert\), where \(\vert \psi^{-} \rangle = \frac{1}{\sqrt{2}} (\vert 01\rangle - \vert 10\rangle)\) is the singlet state. Note that this Hamiltonian is rotation-invariant, and the minimum energy is zero.
This Hamiltonian can optionally be weighted with coefficients \(w_{ij}\).
I think this term is due to [King22]. This is defined also by a graph \(G(V,E)\), where
\[H = \frac{1}{2} \sum_{(i,j) \in E} I_i \otimes I_j + X_i \otimes X_j - Y_i \otimes Y_j + Z_i \otimes Z_j\]Alternatively, this can be written as \(H = \sum_{(i,j) \in E} \vert \phi^+\rangle \langle \phi^+\vert\), where \(\vert \phi^+\rangle = \frac{1}{\sqrt{2}}(\vert 00 \rangle + \vert 11 \rangle)\) is the EPR pair. Note that this Hamiltonian has a particularly simple optimal product state of \(\vert 0 \rangle^{\otimes n}\) with approximation ratio \(\frac{1}{2}\).
This Hamiltonian can also optionally be weighted with coefficients \(w_{ij}\).
This is a random family of Hamiltonians of the form
\[H = \frac{1}{2^n} \sum_{\vec{P} \in \{I, X, Y, Z\}^n} g_{\vec{P}} \vec{P}\]where an instance is drawn by choosing each \(g_{\vec{P}} \sim \mathcal{N}(0,1)\) i.i.d.
There is a variant of this model (let’s call it a Sparse Wigner Hamiltonian) with similar eigenvalue statistics, famously studied in [CDBBT23].
There are a few ways to describe a random family of quantum spin glasses:
Most algorithms have been studied for Quantum Max-Cut. A recent summary is given in Section 3 of [King22].
The classical algorithms:
All algorithms beyond this use some classical computation, then a variational circuit. As a result, the best quantum algorithms outperform known classical algorithms.
This is the state-of-the-art that I am aware of; but there is no claim anywhere that these are the best possible classical or quantum algorithms.
Some useful tools here are the Lasserre hierarchy (or Sum-of-Squares) and rounding techniques, rounding beyond product states, and analyzing simple variational circuits.
As far as I’m aware, the only model that has been studied in the average-case is for the Sparse Wigner GUE [CDBBT23]; since the eigenvalue distribution does not have a long tail, the naive “use phase estimation on a mixed state” provably reaches the optimal solution (whp). The eigenvalue distribution also holds for Wigner GUE, but it’s not possible to even describe this input model with a polynomial number of terms, so the latter does not have an efficient algorithm.
It’s possible to study algorithms for Quantum spin glasses and even Quantum Max-Cut on random regular graphs, but I haven’t seen this done before.
Deciding the ground state value of Quantum Max-Cut is QMA-hard (I can’t actually find a reference that exactly matches this, perhaps [CM13]? But it’s only with arbitrary weights.) It might actually be QMA\(_1\)-hard without weights, I’m not sure.
However, deciding the ground state value of EPR Hamiltonian (with arbitrary weights) is in StoqMA [King22]. In other words, this Hamiltonian is “sign-problem free”.
Note that for both Quantum Max-Cut and EPR Hamiltonian, product state solutions cannot have approximation ratio higher than \(0.5\); for example, consider a graph with one edge. But this does not imply a bound on all classical algorithms.
There is one attempt at proving hardness-of-approximation (in particular, by classical algorithms). Assuming a conjecture about Gaussian correlations, [HNPTW22] shows that approximating the ground state energy value of Quantum Max-Cut with approximation ratio higher than \(0.956\) is as hard as deciding the Unique Games problem (this is possibly NP-hard).
Proving quantum-hardness-of-approximation would require some quantum variant of a PCP theorem.
Note that the Hamiltonians above can be studied in an average-case setting if we randomize the choice of graph; say, from \(\mathbf{G}(n,p)\) or random \(d\)-regular graphs. In this case, we don’t know if the optimal value concentrates, or even the right order of magnitude of the optimal value.
Random families of Hamiltonians only have a sense of average-case hardness. For the Wigner GUE (and sparse variant by [CDBBT23]), the eigenvalue statistics are known to follow a semicircle law. As a result, the sparse variant is “quantumly easy”, although they show a quantum circuit lower bound(!) A classical hardness result is not known.
For Quantum spin glasses, [ES14] describes the eigenvalue statistics (which either have Gaussian tails or follow a semicircle law). In the Gaussian case, I don’t think the location of the optimal value is known. A natural question is if Quantum spin glasses have an optimal value related to a random family of Quantum Max-Cut, as is true in the classical setting (see [Panchenko14 notes], [DMS17], and spin-glass-reference).
There may be ways to extend recent average-case obstructions from classical spin glass theory to these quantum spin glasses. Notably, a property of the covariance matrices of nearly-optimal solutions (the Overlap Gap Property or (OGP)) obstructs certain algorithms from achieving the optimal solution in the average-case. See [Gamarnik21 survey], and the original paper [GS14] introducing the concept. The spin-glass-reference may also have some explainers. There are several kinds of OGPs (multi-, ensemble, branching, …) that have different obstruction strengths, and may obstruct different classes of algorithms. See also [AGK23] as viewing the OGP from the perspective of NLTS.
Some useful tools here include textbook random matrix theory ideas, like the trace power method and concentration bounds, as well as recent work in proving OGPs for spin glasses.
Inspired by conversations with many people, including Bobak Kiani, Joao Basso, Robbie King, Nathan Ju, James Sud, and Adrian She.
More to add? Email me at kmarw@uchicago.edu.