Performance of quantum annealing for 2-SAT problems with multiple satisfying assignments
- URL: http://arxiv.org/abs/2502.01423v3
- Date: Wed, 12 Feb 2025 16:27:14 GMT
- Title: Performance of quantum annealing for 2-SAT problems with multiple satisfying assignments
- Authors: Vrinda Mehta, Hans De Raedt, Kristel Michielsen, Fengping Jin,
- Abstract summary: We study the scaling and sampling performance of numerical simulation of quantum annealing as well as that of the physical quantum annealers offered by D-Wave.
The sampling behavior can be explained by theory and the scaling behavior of the time to solution depends on the scaling behavior of the minimum energy gap.
The corresponding results from the D-Wave quantum annealers do not fit to this ideal picture, but suggest that the scaling of the time to solution from the quantum annealers matches those calculated from the equilibrium probability distribution.
- Score: 0.3749861135832073
- License:
- Abstract: Using a specially constructed set of hard 2-SAT problems with four satisfying assignments, we study the scaling and sampling performance of numerical simulation of quantum annealing as well as that of the physical quantum annealers offered by D-Wave. To this end, we use both the standard quantum annealing and reverse annealing protocols in both our simulations and on the D-Wave quantum annealer. In the case of ideal quantum annealing the sampling behavior can be explained by perturbation theory and the scaling behavior of the time to solution depends on the scaling behavior of the minimum energy gap between the ground state and the first excited state of the annealing Hamiltonian. The corresponding results from the D-Wave quantum annealers do not fit to this ideal picture, but suggest that the scaling of the time to solution from the quantum annealers matches those calculated from the equilibrium probability distribution.
Related papers
- Thermalization and Criticality on an Analog-Digital Quantum Simulator [133.58336306417294]
We present a quantum simulator comprising 69 superconducting qubits which supports both universal quantum gates and high-fidelity analog evolution.
We observe signatures of the classical Kosterlitz-Thouless phase transition, as well as strong deviations from Kibble-Zurek scaling predictions.
We digitally prepare the system in pairwise-entangled dimer states and image the transport of energy and vorticity during thermalization.
arXiv Detail & Related papers (2024-05-27T17:40:39Z) - On Quantum Annealing Without a Physical Quantum Annealer [0.0]
We propose and evaluate a hybrid quantum classical: Quantum Accelerated Simulated Annealing (QASA)
Our simulation results show QASA performing comparably to SA but for a reduced amount of steps.
arXiv Detail & Related papers (2023-07-19T00:37:34Z) - Robust Extraction of Thermal Observables from State Sampling and
Real-Time Dynamics on Quantum Computers [49.1574468325115]
We introduce a technique that imposes constraints on the density of states, most notably its non-negativity, and show that this way, we can reliably extract Boltzmann weights from noisy time series.
Our work enables the implementation of the time-series algorithm on present-day quantum computers to study finite temperature properties of many-body quantum systems.
arXiv Detail & Related papers (2023-05-30T18:00:05Z) - Anti-crossings occurrence as exponentially closing gaps in Quantum
Annealing [0.0]
We use a perturbative expansion to derive a condition for the occurrence of an avoided level crossing during the annealing process.
We show that no exponentially small gaps arise for regular bipartite graphs, implying that QA can efficiently solve MaxCut in that case.
arXiv Detail & Related papers (2023-04-25T14:42:20Z) - Adaptive variational quantum minimally entangled typical thermal states
for finite temperature simulations [0.0]
We describe and benchmark a quantum computing version of the minimally entangled typical thermal states (METTS) algorithm.
The algorithm, which we name AVQMETTS, dynamically generates compact and problem-specific quantum circuits.
arXiv Detail & Related papers (2023-01-06T16:40:06Z) - Quantum emulation of the transient dynamics in the multistate
Landau-Zener model [50.591267188664666]
We study the transient dynamics in the multistate Landau-Zener model as a function of the Landau-Zener velocity.
Our experiments pave the way for more complex simulations with qubits coupled to an engineered bosonic mode spectrum.
arXiv Detail & Related papers (2022-11-26T15:04:11Z) - 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) - Implementation of a two-stroke quantum heat engine with a collisional
model [50.591267188664666]
We put forth a quantum simulation of a stroboscopic two-stroke thermal engine in the IBMQ processor.
The system consists of a quantum spin chain connected to two baths at their boundaries, prepared at different temperatures using the variational quantum thermalizer algorithm.
arXiv Detail & Related papers (2022-03-25T16:55:08Z) - The quantum annealing gap and quench dynamics in the exact cover problem [0.0]
Annealing explores equilibrium phases of a Hamiltonian with slowly changing parameters.
Quenches are sudden changes of the Hamiltonian, producing a non-equilibrium situation.
arXiv Detail & Related papers (2021-06-15T12:43:23Z) - Quantum Statistical Complexity Measure as a Signalling of Correlation
Transitions [55.41644538483948]
We introduce a quantum version for the statistical complexity measure, in the context of quantum information theory, and use it as a signalling function of quantum order-disorder transitions.
We apply our measure to two exactly solvable Hamiltonian models, namely: the $1D$-Quantum Ising Model and the Heisenberg XXZ spin-$1/2$ chain.
We also compute this measure for one-qubit and two-qubit reduced states for the considered models, and analyse its behaviour across its quantum phase transitions for finite system sizes as well as in the thermodynamic limit by using Bethe ansatz.
arXiv Detail & Related papers (2020-02-05T00:45:21Z)
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.