Reverse quantum annealing assisted by forward annealing

• URL: http://arxiv.org/abs/2408.13603v1
• Date: Sat, 24 Aug 2024 15:13:24 GMT
• Title: Reverse quantum annealing assisted by forward annealing
• Abstract summary: We use a general method that improves the overall solution quality and quantity. A scaling analysis for the graph coloring problem shows that our method effectively extends the computational reach.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum annealers conventionally use forward annealing to generate heuristic solutions. Reverse annealing can potentially generate better solutions but necessitates an appropriate initial state. Ways to find such states are generally unknown or highly problem dependent, offer limited success, and severely restrict the scope of reverse annealing. We use a general method that improves the overall solution quality and quantity by feeding reverse annealing with low-quality solutions obtained from forward annealing. An experimental demonstration of solving the graph coloring problem using the D-Wave quantum annealers shows that our method is able to convert invalid solutions obtained from forward annealing to at least one valid solution obtained after assisted reverse annealing for $57\%$ of $459$ random Erd\H{o}s-R\'enyi graphs. Our method significantly outperforms random initial states, obtains more unique solutions on average, and widens the applicability of reverse annealing. Although the average number of valid solutions obtained drops exponentially with the problem size, a scaling analysis for the graph coloring problem shows that our method effectively extends the computational reach of conventional forward annealing using reverse annealing.

Related papers

• Extending the computational reach of Quantum Annealing using Reverse Annealing [0.0]
  We find that combining forward and reverse annealing consistently improves solution quality and efficiency across multiple problem classes.<n>We establish these results through a systematic experimental study on a D-Wave Advantage system.
  arXiv  Detail & Related papers  (2026-07-02T13:21:57Z)
• Apollo-MILP: An Alternating Prediction-Correction Neural Solving Framework for Mixed-Integer Linear Programming [57.24050601521162]
  We propose an Alternating prediction-correction neural solving framework (Apollo-MILP) In each iteration, Apollo-MILP conducts a prediction step for the unfixed variables, followed by a correction step to obtain an improved solution (called reference solution) through a trust-region search. Experiments on commonly used benchmarks demonstrate that our proposed Apollo-MILP significantly outperforms other ML-based approaches in terms of solution quality.
  arXiv  Detail & Related papers  (2025-03-03T03:19:49Z)
• Unraveling Reverse Annealing: A Study of D-Wave Quantum Annealers [0.3749861135832073]
  D-Wave quantum annealers offer reverse annealing as a feature allowing them to refine solutions to optimization problems. This paper investigates the influence of key parameters, such as annealing times and reversal distance, on the behavior of reverse annealing by studying models containing up to 1000 qubits. Our findings provide a deeper understanding that can better equip users to fully harness the potential of the D-Wave annealers.
  arXiv  Detail & Related papers  (2025-02-12T17:09:40Z)
• Improving Diffusion Inverse Problem Solving with Decoupled Noise Annealing [84.97865583302244]
  We propose a new method called Decoupled Annealing Posterior Sampling (DAPS) DAPS relies on a novel noise annealing process. We demonstrate that DAPS significantly improves sample quality and stability across multiple image restoration tasks.
  arXiv  Detail & Related papers  (2024-07-01T17:59:23Z)
• An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
  We analyse the ability of quantum D-Wave annealers to find the maximum clique on a graph, expressed as a QUBO problem. We propose a decomposition algorithm for the complementary maximum independent set problem, and a graph generation algorithm to control the number of nodes, the number of cliques, the density, the connectivity indices and the ratio of the solution size to the number of other nodes.
  arXiv  Detail & Related papers  (2024-06-11T04:40:05Z)
• Validation and benchmarking of quantum annealing technology [0.0]
  This thesis focuses on the problem of benchmarking and validating quantum annealers. We propose two algorithms for solving real-world problems and test how they perform on the current generation of quantum annealers.
  arXiv  Detail & Related papers  (2023-12-06T14:56:45Z)
• Initial State Encoding via Reverse Quantum Annealing and h-gain Features [1.8416014644193066]
  We explore two D-Wave features allowing one to encode an initial state into a quantum annealer. The h-gain feature allows one to put a time-dependent weighting scheme on linear ($h$) biases of the Hamiltonian. We evaluate the idea of iteratively applying RA and HG to a problem, with the goal of improving on an initial state that is not optimal.
  arXiv  Detail & Related papers  (2023-03-24T02:04:31Z)
• Physics-Informed Neural Network Method for Parabolic Differential Equations with Sharply Perturbed Initial Conditions [68.8204255655161]
  We develop a physics-informed neural network (PINN) model for parabolic problems with a sharply perturbed initial condition. Localized large gradients in the ADE solution make the (common in PINN) Latin hypercube sampling of the equation's residual highly inefficient. We propose criteria for weights in the loss function that produce a more accurate PINN solution than those obtained with the weights selected via other methods.
  arXiv  Detail & Related papers  (2022-08-18T05:00:24Z)
• Improving Diffusion Models for Inverse Problems using Manifold Constraints [55.91148172752894]
  We show that current solvers throw the sample path off the data manifold, and hence the error accumulates. To address this, we propose an additional correction term inspired by the manifold constraint. We show that our method is superior to the previous methods both theoretically and empirically.
  arXiv  Detail & Related papers  (2022-06-02T09:06:10Z)
• An application of the splitting-up method for the computation of a neural network representation for the solution for the filtering equations [68.8204255655161]
  Filtering equations play a central role in many real-life applications, including numerical weather prediction, finance and engineering. One of the classical approaches to approximate the solution of the filtering equations is to use a PDE inspired method, called the splitting-up method. We combine this method with a neural network representation to produce an approximation of the unnormalised conditional distribution of the signal process.
  arXiv  Detail & Related papers  (2022-01-10T11:01:36Z)
• Quantum annealing with twisted fields [0.0]
  We propose a method for suppressing the effects of decoherence and non-adiabatic transition. Our results can pave the way to a new approach for realizing practical quantum annealing.
  arXiv  Detail & Related papers  (2021-11-30T11:00:44Z)
• Quadratic Unconstrained Binary Optimisation via Quantum-Inspired Annealing [58.720142291102135]
  We present a classical algorithm to find approximate solutions to instances of quadratic unconstrained binary optimisation. We benchmark our approach for large scale problem instances with tuneable hardness and planted solutions.
  arXiv  Detail & Related papers  (2021-08-18T09:26:17Z)
• Advanced anneal paths for improved quantum annealing [0.0]
  We study how advanced features of the D-Wave annealer can help in improving the quality of the solutions returned by the annealer. The h-gain feature stands for time-dependent gain in Hamiltonian linear ($h$) biases and was originally developed to help study freezeout times and phase transitions in spin glasses. We test all techniques on a variety of input problems including the weighted Maximum Cut problem and the weighted Maximum Clique problem.
  arXiv  Detail & Related papers  (2020-09-10T17:15:48Z)
• Reverse Annealing for Nonnegative/Binary Matrix Factorization [0.0]
  It was recently shown that quantum annealing can be used as an effective, fast subroutine in certain types of matrix factorization algorithms. In this paper, we utilize reverse annealing instead of forward annealing in the quantum annealing subroutine for nonnegative/binary matrix factorization problems.
  arXiv  Detail & Related papers  (2020-07-10T18:40:02Z)
• Approximation Schemes for ReLU Regression [80.33702497406632]
  We consider the fundamental problem of ReLU regression. The goal is to output the best fitting ReLU with respect to square loss given to draws from some unknown distribution.
  arXiv  Detail & Related papers  (2020-05-26T16:26:17Z)

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.