Quantum Annealing Algorithms for Estimating Ising Partition Functions

• URL: http://arxiv.org/abs/2504.21666v1
• Date: Wed, 30 Apr 2025 14:09:40 GMT
• Title: Quantum Annealing Algorithms for Estimating Ising Partition Functions
• Authors: Haowei Li, Zhiyuan Yao, Xingze Qiu,
• Abstract summary: Estimating partition functions of Ising spin glasses is crucial in statistical physics, optimization, and machine learning.<n>This work bridges quantum dynamics with computational complexity, offering a practical pathway to quantum advantage in spin glass thermodynamics.
• Score: 2.8311048083168657
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Estimating partition functions of Ising spin glasses is crucial in statistical physics, optimization, and machine learning, yet remains classically intractable due to its #P-hard complexity. While Jarzynski's equality offers a theoretical approach, it becomes unreliable at low temperatures due to rare divergent statistical fluctuations. Here, we present a protocol that overcomes this limitation by synergizing reverse quantum annealing with tailored nonequilibrium initial distributions. Our method can dramatically suppress the estimator variance, achieving saturation in the low-temperature regime. Numerical benchmarks on the Sherrington-Kirkpatrick spin glass and the 3-SAT problem demonstrate that our protocol reduces scaling exponents by over an order of magnitude (e.g., from ~8.5 to ~0.5), despite retaining exponential system-size dependences. Crucially, our protocol circumvents stringent adiabatic constraints, making it feasible for near-term quantum devices like superconducting qubits, trapped ions, and Rydberg atom arrays. This work bridges quantum dynamics with computational complexity, offering a practical pathway to quantum advantage in spin glass thermodynamics and beyond.

Related papers

• Qubit-efficient quantum combinatorial optimization solver [0.0]
  We develop a qubit-efficient algorithm that overcomes the limitation by mapping a candidate bit solution to an entangled wave function of fewer qubits. This approach could benefit near-term intermediate-scale and future fault-tolerant small-scale quantum devices.
  arXiv  Detail & Related papers  (2024-07-22T11:02:13Z)
• Adiabatic Bottlenecks in Quantum Annealing and Nonequilibrium Dynamics of Paramagnons [0.0]
  Correspondence between long-range interacting quantum spin glasses and optimization problems underpins the physical motivation for adiabatic quantum computing. In disordered (quantum) spin systems, the focus is on exact methods such as the replica trick that allow the calculation of system quantities in the limit of infinite system and ensemble size. Here, we apply the nonequilibrium Green-function formalism to the spin coherent-state path integral to obtain the statistical fluctuations and the collective-excitation spectrum.
  arXiv  Detail & Related papers  (2024-03-18T07:59:46Z)
• Near-Term Distributed Quantum Computation using Mean-Field Corrections and Auxiliary Qubits [77.04894470683776]
  We propose near-term distributed quantum computing that involve limited information transfer and conservative entanglement production. We build upon these concepts to produce an approximate circuit-cutting technique for the fragmented pre-training of variational quantum algorithms.
  arXiv  Detail & Related papers  (2023-09-11T18:00:00Z)
• Quantum Thermal State Preparation [39.91303506884272]
  We introduce simple continuous-time quantum Gibbs samplers for simulating quantum master equations. We construct the first provably accurate and efficient algorithm for preparing certain purified Gibbs states. Our algorithms' costs have a provable dependence on temperature, accuracy, and the mixing time.
  arXiv  Detail & Related papers  (2023-03-31T17:29:56Z)
• Universality of critical dynamics with finite entanglement [68.8204255655161]
  We study how low-energy dynamics of quantum systems near criticality are modified by finite entanglement. Our result establishes the precise role played by entanglement in time-dependent critical phenomena.
  arXiv  Detail & Related papers  (2023-01-23T19:23:54Z)
• Probing finite-temperature observables in quantum simulators of spin systems with short-time dynamics [62.997667081978825]
  We show how finite-temperature observables can be obtained with an algorithm motivated from the Jarzynski equality. We show that a finite temperature phase transition in the long-range transverse field Ising model can be characterized in trapped ion quantum simulators.
  arXiv  Detail & Related papers  (2022-06-03T18:00:02Z)
• Exponential precision by reaching a quantum critical point [0.0]
  We report a protocol that is capable of surpassing the quadratic scaling, and yields an exponential advantage. The exponential advantage stems from the breakdown of the adiabatic condition close to a critical point. Our findings unveil a novel quantum metrological protocol whose precision scaling goes beyond the paradigmatic Heisenberg limit.
  arXiv  Detail & Related papers  (2021-12-21T14:46:33Z)
• Mitigated barren plateaus in the time-nonlocal optimization of analog quantum-algorithm protocols [0.0]
  algorithmic classes such as variational quantum algorithms have been shown to suffer from barren plateaus. We present an approach to quantum algorithm optimization that is based on trainable Fourier coefficients of Hamiltonian system parameters.
  arXiv  Detail & Related papers  (2021-11-15T21:13:10Z)
• Robust Nonadiabatic Holonomic Quantum Gates on Decoherence-Protected Qubits [4.18804572788063]
  We propose a scheme for quantum manipulation by combining the geometric phase approach with the dynamical correction technique. Our scheme is implemented on the superconducting circuits, which also simplifies previous implementations.
  arXiv  Detail & Related papers  (2021-10-06T14:39:52Z)
• Enhanced nonlinear quantum metrology with weakly coupled solitons and particle losses [58.720142291102135]
  We offer an interferometric procedure for phase parameters estimation at the Heisenberg (up to 1/N) and super-Heisenberg scaling levels. The heart of our setup is the novel soliton Josephson Junction (SJJ) system providing the formation of the quantum probe. We illustrate that such states are close to the optimal ones even with moderate losses.
  arXiv  Detail & Related papers  (2021-08-07T09:29:23Z)
• Continuous-time dynamics and error scaling of noisy highly-entangling quantum circuits [58.720142291102135]
  We simulate a noisy quantum Fourier transform processor with up to 21 qubits. We take into account microscopic dissipative processes rather than relying on digital error models. We show that depending on the dissipative mechanisms at play, the choice of input state has a strong impact on the performance of the quantum algorithm.
  arXiv  Detail & Related papers  (2021-02-08T14:55:44Z)
• Assessment of weak-coupling approximations on a driven two-level system under dissipation [58.720142291102135]
  We study a driven qubit through the numerically exact and non-perturbative method known as the Liouville-von equation with dissipation. We propose a metric that may be used in experiments to map the regime of validity of the Lindblad equation in predicting the steady state of the driven qubit.
  arXiv  Detail & Related papers  (2020-11-11T22:45:57Z)

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.