Energy-Based Models of Quantum Computation

In the classical Ising model, spins s_i ∈ {−1, +1} minimize

The couplings J_ij encode compatibility or frustration, while the fields h_i bias individual spins. A low-energy spin configuration can therefore represent a good solution to a combinatorial problem.

From spin glasses to optimization

This connection was made sharp by Barahona: finding a ground state of an Ising spin glass is NP-hard in two dimensions when magnetic fields are allowed [1]. Without fields, the planar problem is solvable in polynomial time; adding fields changes the complexity class.

The Sherrington–Kirkpatrick model supplied a complementary physical picture: a mean-field Ising spin glass with random, competing couplings and a thermodynamic spin-glass transition [2]. This was not a computational-complexity transition; simulated annealing later supplied the algorithmic link [3].

Ground-state spin logic then showed that Boolean functions—and hence switching circuits—can be embedded in Ising ground spaces [12]. Energy minima can thus represent optimization problems and computations, not only physical configurations.

The quantum Local Hamiltonian problem

For a quantum system, the energy function is replaced by a Hamiltonian H. The Local Hamiltonian problem asks, given thresholds a < b separated by at least an inverse polynomial, whether its ground-state energy obeys

This is a promise problem: inputs lying between a and b are excluded. Kitaev’s history-state construction encoded the accepting evolution of a quantum verification circuit into the low-energy sector of a local Hamiltonian. Circuit acceptance could therefore be reformulated as a ground-energy decision problem. The resulting Local Hamiltonian problem is QMA-complete, where QMA is the quantum analogue of NP [4][5].

This statement should be kept distinct from a claim that every output bit is literally an energy eigenvalue. Rather, an efficiently specified quantum verification problem is reduced to the question of whether a Hamiltonian has sufficiently low ground energy. QMA-completeness persists for two-local interactions and even under a two-dimensional square-lattice restriction [5][6].

Adiabatic computation

Farhi, Goldstone, Gutmann, and Sipser gave the optimization picture its quantum dynamical form. One starts from the easily prepared ground state of H_init and evolves slowly toward H_final, whose ground state encodes the answer [7]. The adiabatic theorem motivates this procedure: if the path is traversed slowly relative to the relevant spectral gap, the state remains close to the instantaneous ground state. The gap is essential—an exponentially small minimum gap can require an exponentially long runtime.

Aharonov and collaborators proved that adiabatic quantum computation is polynomially equivalent to the standard circuit model [8]. Their result establishes universality of the computational model; it is not a proof that an arbitrary optimization instance can be solved efficiently.

Realizable universal Hamiltonians

Biamonte and Love identified restricted two-body menus that remain universal: local X and Z fields with either ZZ and XX, or ZX-type, couplings. These models are QMA-complete; a tunable XX term turns the transverse-field Ising model into a universal model [9].

The transverse-field Ising model is stoquastic, with non-positive off-diagonal elements in a suitable basis. Bravyi and Hastings showed that its ground-energy problem on degree-three graphs is StoqMA-complete, rather than known to be QMA-complete [10]. The Biamonte–Love couplers therefore cross a meaningful boundary.

Energy-based models in machine learning

Energy-based machine learning uses the same language for a different goal. A Boltzmann machine assigns a probability distribution

and learning changes the parameters θ so that observed data occupy low-energy, high-probability regions. Quantum machine learning likewise uses Ising and Boltzmann-type models as trainable probability landscapes, rather than QMA decision problems [11].

Variational computation: a quantum–classical feedback loop

Variational computation shares this feedback architecture: a classical procedure changes parameters in response to information supplied by a quantum system. For an observable written as H = ∑_α h_αP_α, a variational routine prepares |ψ(θ)⟩ and estimates

The quantum device estimates the individual terms P_α; a classical outer loop aggregates those estimates and updates θ. This makes variational computation relevant to machine learning as a trainable quantum–classical architecture, without making every variational algorithm a machine-learning algorithm [13].

QAOA is a particular variational ansatz: it alternates a cost Hamiltonian with a noncommuting mixer Hamiltonian, originally to seek low-cost solutions [15]. Universal variational quantum computation constructs objective functions whose minima prepare the outputs of arbitrary quantum circuits, establishing a universal model of computation [14]. Separately, specified QAOA sequences have been shown to be gate-set universal under explicit conditions on their interactions and symmetries [16].

The possible separation from classical energy-based models lies here. Given a classical spin configuration, its energy is directly evaluated by summing the displayed terms. For a sufficiently general quantum Hamiltonian and a highly entangled circuit state, no efficient classical method is known for faithfully evaluating the corresponding expectation-value landscape at scale. The working hypothesis—not a general theorem—is that this task will require exponential classical resources in the general case. Brute-force state-vector simulation uses 2ⁿ amplitudes, but that is not an unconditional lower bound: many structured Hamiltonians, states, and shallow circuits remain classically tractable. QMA-completeness of the Local Hamiltonian problem is strong evidence of a complexity barrier [4][5]; it does not prove that every quantum expectation-value calculation is exponentially hard.