Computational complexity of three-dimensional Ising spin glass: Lessons from D-Wave annealer

• URL: http://arxiv.org/abs/2501.01107v3
• Date: Mon, 28 Jul 2025 22:05:15 GMT
• Title: Computational complexity of three-dimensional Ising spin glass: Lessons from D-Wave annealer
• Authors: Hao Zhang, Alex Kamenev,
• Abstract summary: Finding an exact ground state of a three-dimensional (3D) Ising spin glass is proven to be an NP-hard problem.<n>We report results of extensive experimentation with D-Wave 3D annealer with $Nle 5627$.<n>We found exact ground states for typical realizations of 3D spin glasses with the efficiency, which scales as $2/ beta$ with $betaapprox 103$.
• Score: 4.96596848660858
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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\le 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/ \beta}$ with $\beta\approx 10^3$. Based on statistical analysis of low-energy states, we argue that with an improvement of annealing protocols and device noise reduction, $\beta$ can be increased even further. This suggests that, for $N<\beta^3$, annealing devices provide most efficient way to find an exact ground state.

Related papers

• Ground States of the Mean-Field Spin Glass with 3-Spin Couplings [0.0]
  We use optimization methods to determine with low systematic error ground state configurations of the mean-field $p$-spin glass model with $p=3$. For the bond-diluted case, the energy density and its distribution appear to scale with $ln N/N$ and $1/N$ corrections, respectively. This would suggest that all $p$-spin models with $pgeq3$ exhibit the same ground-state corrections as in REM.
  arXiv  Detail & Related papers  (2025-01-22T20:34:39Z)
• Computing critical exponents in 3D Ising model via pattern recognition/deep learning approach [1.6317061277457001]
  We perform a supervised Deep Learning approach to train a neural network on specific conformations of spin states. We achieve a train/test accuracy of 0.92 and 0.6875, respectively. More work remains to be done to quantify the feasibility of computing critical exponents from this approach.
  arXiv  Detail & Related papers  (2024-11-04T20:57:24Z)
• Measuring quantum relative entropy with finite-size effect [53.64687146666141]
  We study the estimation of relative entropy $D(rho|sigma)$ when $sigma$ is known.<n>Our estimator attains the Cram'er-Rao type bound when the dimension $d$ is fixed.
  arXiv  Detail & Related papers  (2024-06-25T06:07:20Z)
• Bayesian Inference with Deep Weakly Nonlinear Networks [57.95116787699412]
  We show at a physics level of rigor that Bayesian inference with a fully connected neural network is solvable. We provide techniques to compute the model evidence and posterior to arbitrary order in $1/N$ and at arbitrary temperature.
  arXiv  Detail & Related papers  (2024-05-26T17:08:04Z)
• Scalable 3D Registration via Truncated Entry-wise Absolute Residuals [65.04922801371363]
  A $3$D registration approach can process more than ten million ($107$) point pairs with over $99%$ random outliers. We call our method TEAR, as it involves minimizing an outlier-robust loss that computes Truncated Entry-wise Absolute Residuals.
  arXiv  Detail & Related papers  (2024-04-01T04:43:39Z)
• Full quantum tomography of top quark decays [0.0]
  Quantum tomography in high-energy physics processes has usually been restricted to the spin degrees of freedom. We address the case of top quark decays $t to W b$, in which the orbital angular momentum ($L$) and the spins of $W$ and $b$ are intertwined into a 54-dimensional $LWb$ density operator. The entanglement between $L$ and the $W$ or $b$ spin is large and could be determined for decays of single top quarks produced at the Large Hadron Collider with Run 2 data.
  arXiv  Detail & Related papers  (2024-02-22T17:33:33Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Robust spectral $\pi$ pairing in the random-field Floquet quantum Ising model [44.84660857803376]
  We study level pairings in the many-body spectrum of the random-field Floquet quantum Ising model. The robustness of $pi$ pairings against longitudinal disorder may be useful for quantum information processing.
  arXiv  Detail & Related papers  (2024-01-09T20:37:48Z)
• Resummation-based Quantum Monte Carlo for Entanglement Entropy Computation [0.40964539027092917]
  We develop a new algorithm, dubbed ResumEE, to compute the entanglement entropy. Our ResumEE algorithm is efficient for precisely evaluating the entanglement entropy of SU($N$) spin models with continuous $N$.
  arXiv  Detail & Related papers  (2023-10-02T18:00:02Z)
• Isotope engineering for spin defects in van der Waals materials [3.76897330943914]
  We grow isotopically purified $mathrmh10mathrmB15mathrmN crystals in hexagonal boron nitride (hBN) Compared to $mathrmV_mathrmB-$ in hBN with the natural distribution of isotopes, we observe substantially narrower and less crowded $mathrmV_mathrmB-$ spin transitions. For quantum sensing, $mathrmB-$ centers in our $mathrmh10mathrmB15mathrm
  arXiv  Detail & Related papers  (2023-07-12T20:10:34Z)
• On the average-case complexity of learning output distributions of quantum circuits [55.37943886895049]
  We show that learning the output distributions of brickwork random quantum circuits is average-case hard in the statistical query model. This learning model is widely used as an abstract computational model for most generic learning algorithms.
  arXiv  Detail & Related papers  (2023-05-09T20:53:27Z)
• Fast Rates for Maximum Entropy Exploration [52.946307632704645]
  We address the challenge of exploration in reinforcement learning (RL) when the agent operates in an unknown environment with sparse or no rewards. We study the maximum entropy exploration problem two different types. For visitation entropy, we propose a game-theoretic algorithm that has $widetildemathcalO(H3S2A/varepsilon2)$ sample complexity. For the trajectory entropy, we propose a simple algorithm that has a sample of complexity of order $widetildemathcalO(mathrmpoly(S,
  arXiv  Detail & Related papers  (2023-03-14T16:51:14Z)
• Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials [93.59919600451487]
  "Statistical-computational gaps" occur in many statistical inference tasks. We consider a model for random order-3 decomposition where one component is slightly larger in norm than the rest. We show that tensor entries can accurately estimate the largest component when $ll n3/2$ but fail to do so when $rgg n3/2$.
  arXiv  Detail & Related papers  (2022-11-10T00:40:37Z)
• PDO-s3DCNNs: Partial Differential Operator Based Steerable 3D CNNs [69.85869748832127]
  In this work, we employ partial differential operators (PDOs) to model 3D filters, and derive general steerable 3D CNNs called PDO-s3DCNNs. We prove that the equivariant filters are subject to linear constraints, which can be solved efficiently under various conditions.
  arXiv  Detail & Related papers  (2022-08-07T13:37:29Z)
• A Law of Robustness beyond Isoperimetry [84.33752026418045]
  We prove a Lipschitzness lower bound $Omega(sqrtn/p)$ of robustness of interpolating neural network parameters on arbitrary distributions. We then show the potential benefit of overparametrization for smooth data when $n=mathrmpoly(d)$. We disprove the potential existence of an $O(1)$-Lipschitz robust interpolating function when $n=exp(omega(d))$.
  arXiv  Detail & Related papers  (2022-02-23T16:10:23Z)
• Robust Estimation for Random Graphs [47.07886511972046]
  We study the problem of robustly estimating the parameter $p$ of an ErdHos-R'enyi random graph on $n$ nodes. We give an inefficient algorithm with similar accuracy for all $gamma 1/2$, the information-theoretic limit.
  arXiv  Detail & Related papers  (2021-11-09T18:43:25Z)
• Quantum spin solver near saturation: QS$^3_{~}$ [0.0]
  We develop a program package named QS$3$ [textipakj'u:-'es-kj'u:b] based on the (thick-restart) Lanczos method for analyzing spin-1/2 XXZ-type quantum spin models. We show the benchmark results of QS$3$ for the low-energy excitation dispersion of the isotropic Heisenberg model on the $10times10times10$ cubic lattice.
  arXiv  Detail & Related papers  (2021-07-02T07:06:34Z)
• Fast Quantum Property Prediction via Deeper 2D and 3D Graph Networks [41.727588601578155]
  We design a deep graph neural network to predict quantum properties by directly learning from 2D molecular graphs. We also propose a 3D graph neural network to learn from low-coster sets.
  arXiv  Detail & Related papers  (2021-06-16T05:07:28Z)
• Renormalized q-dependent Spin Susceptibility by inverting the Random Phase Approximation: Implications for quantitative assessment of the role of spin fluctuations in 2D Ising superconductor NbSe$_{2}$ [0.0]
  We describe an alternative way to calculate the static $chi(mathbfq)$, which can be applied to most common DFT codes without additional programming. We find that the structure of spin fluctuations is more complicated, with the fluctuation spectrum sharply peaked at $mathbfqapprox (0.2,0)$.
  arXiv  Detail & Related papers  (2021-04-27T14:09:59Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  We show that extending the smoothing technique to defend against other attack models can be challenging. We present experimental results on CIFAR to validate our theory.
  arXiv  Detail & Related papers  (2020-02-08T22:02:14Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.