Advanced anneal paths for improved quantum annealing

• URL: http://arxiv.org/abs/2009.05008v2
• Date: Fri, 23 Oct 2020 15:07:34 GMT
• Title: Advanced anneal paths for improved quantum annealing
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Advances in quantum annealing technology make it possible to obtain high quality approximate solutions of important NP-hard problems. With the newer generations of the D-Wave annealer, more advanced features are available which allow the user to have greater control of the anneal process. In this contribution, we study how such features can help in improving the quality of the solutions returned by the annealer. Specifically, we focus on two of these features: reverse annealing and h-gain. Reverse annealing (RA) was designed to allow refining a known solution by backward annealing from a classical state representing the solution to a mid-anneal point where a transverse field is present, followed by an ordinary forward anneal, which is hoped to improve on the previous solution. The h-gain (HG) 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. Here we apply HG to bias the quantum state in the beginning of the annealing process towards the known solution as in the RA case, but using a different apparatus. We also investigate a hybrid reverse annealing/h-gain schedule, which has a backward phase resembling an RA step and whose forward phase uses the HG idea. To optimize the parameters of the schedules, we employ a Bayesian optimization framework. We test all techniques on a variety of input problems including the weighted Maximum Cut problem and the weighted Maximum Clique problem. Our results show that each technique may dominate the others depending on the input instance, and that the HG technique is a viable alternative to RA for some problems.

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)
• Reverse quantum annealing assisted by forward annealing [0.0]
  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.
  arXiv  Detail & Related papers  (2024-08-24T15:13:24Z)
• 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)
• An Optimization-based Deep Equilibrium Model for Hyperspectral Image Deconvolution with Convergence Guarantees [71.57324258813675]
  We propose a novel methodology for addressing the hyperspectral image deconvolution problem. A new optimization problem is formulated, leveraging a learnable regularizer in the form of a neural network. The derived iterative solver is then expressed as a fixed-point calculation problem within the Deep Equilibrium framework.
  arXiv  Detail & Related papers  (2023-06-10T08:25:16Z)
• 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)
• Optimal Algorithms for the Inhomogeneous Spiked Wigner Model [89.1371983413931]
  We derive an approximate message-passing algorithm (AMP) for the inhomogeneous problem. We identify in particular the existence of a statistical-to-computational gap where known algorithms require a signal-to-noise ratio bigger than the information-theoretic threshold to perform better than random.
  arXiv  Detail & Related papers  (2023-02-13T19:57:17Z)
• Rethinking Initialization of the Sinkhorn Algorithm [36.72281550968301]
  We show that data-dependent initializers result in dramatic speed-ups, with no effect on differentiability as long as implicit differentiation is used. Ours rely on closed-forms for exact or approximate OT solutions known in the 1D, Gaussian or GMM settings.
  arXiv  Detail & Related papers  (2022-06-15T16:23:03Z)
• An Accelerated Variance-Reduced Conditional Gradient Sliding Algorithm for First-order and Zeroth-order Optimization [111.24899593052851]
  Conditional gradient algorithm (also known as the Frank-Wolfe algorithm) has recently regained popularity in the machine learning community. ARCS is the first zeroth-order conditional gradient sliding type algorithms solving convex problems in zeroth-order optimization. In first-order optimization, the convergence results of ARCS substantially outperform previous algorithms in terms of the number of gradient query oracle.
  arXiv  Detail & Related papers  (2021-09-18T07:08:11Z)
• 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)
• Genetic optimization of quantum annealing [0.0]
  We present a numerical approach based on genetic algorithms to improve the performance of quantum annealing. We also explore shortcuts to abaticity by computing a practically feasible $k$-local optimal driving operator.
  arXiv  Detail & Related papers  (2021-08-06T15:59:23Z)
• On Measuring and Controlling the Spectral Bias of the Deep Image Prior [63.88575598930554]
  The deep image prior has demonstrated the remarkable ability that untrained networks can address inverse imaging problems. It requires an oracle to determine when to stop the optimization as the performance degrades after reaching a peak. We study the deep image prior from a spectral bias perspective to address these problems.
  arXiv  Detail & Related papers  (2021-07-02T15:10:42Z)
• Inferring the Dynamics of the State Evolution During Quantum Annealing [0.0]
  We use advanced features of D-Wave 2000Q to indirectly infer information about the dynamics of the state evolution during the anneal process. We obtain approximate distributions of lowest-energy anneal solutions as the anneal time evolves.
  arXiv  Detail & Related papers  (2020-09-10T18:14:28Z)
• Quantum-optimal-control-inspired ansatz for variational quantum algorithms [105.54048699217668]
  A central component of variational quantum algorithms (VQA) is the state-preparation circuit, also known as ansatz or variational form. Here, we show that this approach is not always advantageous by introducing ans"atze that incorporate symmetry-breaking unitaries. This work constitutes a first step towards the development of a more general class of symmetry-breaking ans"atze with applications to physics and chemistry problems.
  arXiv  Detail & Related papers  (2020-08-03T18:00:05Z)
• 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.