A lower bound result about the approximability of the energy function of Ising spin glasses in the quantum context is determined. The ground-state problem for the three-dimensional Ising spin glasses represented on two-level grids such that the vertical interactions are at most (where n is the number of spins set on the grid), is considered. We prove that, unless , there is a constant such that every quantum approximate polynomial-time algorithm finds a solution with absolute error greater than , with high probability, infinitely often.
We study the magnetization of the ground states of Ising spin glasses as a function of the magnetic field. The grids are two-dimensional with Gaussian bond distribution. Finding a ground state in this case is a difficult combinatorial problem. We present a method that guarantees finding a true ground state. Although it is unlikely that one can have an algorithm with a polynomial bound for the running time, in all cases we tried, our method found a solution in a reasonable amount of time. We used this to obtain estimations of the critical exponents.
We present a polynomial time algorithm for the construction of the Gibbs distribution of configurations in the Ising model, on a quantum computer. The algorithm is designed so that each run provides one configuration with exactly the correct quantum probability, namely, the corresponding thermodynamic weight. The partition function is thus approximated in the most efficient way. The algorithm does not suffer from critical slowing down, unlike its classical counterparts. Moreover, the algorithm can be applied in any dimension, to any of the frustrated Ising models, diluted Ising models, and spin glasses. In particular, we show that under certain plausible assumptions concerning the scaling of the number of low-lying metastable states, the ground state of any dimensional short-range spin glass can be found in poly(N_T) steps, N_T being the number of spins (N) in the system plus the number of bonds between them (N_B). Since the problem of finding the ground state of a spin glass in 3D is known to be NP-complete, we thus provide evidence that possibly P=NP on a quantum computer.
A central question in quantum information theory is the circuit complexity of states arising from standard many-body models. We study this question for quantum
p-spin glasses, random Hamiltonians whose interactions act on
p-tuples of qubits through Pauli strings. Anschuetz, Gamarnik, and Kiani (arXiv:2404.07231) showed that the optimum energy is separated from the best energy achievable by product states. This leaves open whether shallow circuits can close the gap, since even depth-one circuits can generate entanglement.
We show that the entanglement needed to close the product-state gap cannot be generated at shallow depth. When the average interaction degree grows with
n, we prove that, for all sufficiently large fixed
p, any circuit preparing an
n-qubit state whose normalized energy is within a fixed positive constant of the optimum must have depth
Ωp(logn). In the bounded-average-degree regime, we prove a fixed-depth obstruction: for every fixed
D, a sufficiently large degree prefactor rules out depth-
D preparation of near-ground states. Both results hold uniformly over circuits with an arbitrary number of ancilla qubits.
Our results give an obstruction in the spirit of the No Low-Energy Trivial States problem of Freedman and Hastings (arXiv:1301.1363), but for random quantum spin glasses rather than code-based Hamiltonians such as those of Anshu, Breuckmann, and Nirkhe (arXiv:2206.13228), whose ground states admit polynomial-size preparation circuits. This setting opens a probabilistic route to NLTS-like questions: we recast state-preparation lower bounds for random quantum Hamiltonians as uniform control of Gaussian processes indexed by shallow circuits.
We describe a classical approximation algorithm for evaluating the ground state energy of the classical Ising Hamiltonian with linear terms on an arbitrary planar graph. The running time of the algorithm grows linearly with the number of spins and exponentially with
1/ϵ, where
ϵ is the worst-case relative error. This result contrasts the well known fact that exact computation of the ground state energy for the two-dimensional Ising spin glass model is NP-hard. We also present a classical approximation algorithm for the quantum Local Hamiltonian Problem or Quantum Ising Spin Glass problem on a planar graph {\em with bounded degree} which is known to be a QMA-complete problem. Using a different technique we find a classical approximation algorithm for the quantum Ising spin glass problem on the simplest planar graph with unbounded degree, the star graph.
Finding an exact ground state of a three-dimensional (3D) Ising spin glass is proven to be an NP-hard problem (i.e., at least as hard as any problem in the nondeterministic polynomial-time (NP) class). Given validity of the exponential time hypothesis, its computational complexity was proven to be no less than 2 N 2 / 3 , where N is the total number of spins. Here, we report results of extensive experimentation with D-Wave 3D annealer with N ≤ 5627 . We found exact ground states (in a probabilistic sense) for typical realizations of 3D spin glasses with the efficiency, which scales as 2 N / β with β ≈ 10 3 . Based on statistical analysis of low-energy states, we argue that with an improvement of annealing protocols and device noise reduction, β can be increased even further. This suggests that, for N < β 3 , annealing devices provide most efficient way to find an exact ground state.
Large numbers of ground states of three-dimensional (3D) Edwards-Anderson Ising spin glasses are calculated for sizes up to
103 using a combination of a genetic algorithm and cluster-exact approximation. A detailed analysis shows that true ground states are obtained. The ground-state stiffness (or domain wall) energy \ensuremath{\Delta} is calculated. A $|\ensuremath{\Delta}|\ensuremath{\sim}{L}^{{\ensuremath{\Theta}}_{S}}$ behavior with ${\ensuremath{\Theta}}_{S}=0.19(2)$ is found that strongly indicates that the 3D model has an equilibrium spin-glass-paramagnet transition for nonzero
Tc.