Systematic study on the dependence of the warm-start quantum approximate optimization algorithm on approximate solutions

• URL: http://arxiv.org/abs/2209.02942v1
• Date: Wed, 7 Sep 2022 05:26:48 GMT
• Title: Systematic study on the dependence of the warm-start quantum approximate optimization algorithm on approximate solutions
• Authors: Ken N. Okada, Hirofumi Nishi, Taichi Kosugi, and Yu-ichiro Matsushita
• Abstract summary: We study how the accuracy of approximate solutions affect the performance of the warm-start QAOA (WS-QAOA) We find that WS-QAOA tends to outperform QAOA as approximate solutions become closer to the exact solutions in terms of the Hamming distance. We also solve MAX-CUT problems by WS-QAOA with approximate solutions obtained via QAOA, having a better result than QAOA especially when the circuit is relatively shallow.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum approximate optimization algorithm (QAOA) is a promising hybrid quantum-classical algorithm to solve combinatorial optimization problems in the era of noisy intermediate-scale quantum computers. Recently warm-start approaches have been proposed to improve the performance of QAOA, where approximate solutions are obtained by classical algorithms in advance and incorporated into the initial state and/or unitary ansatz. In this work, we study in detail how the accuracy of approximate solutions affect the performance of the warm-start QAOA (WS-QAOA). We numerically find that in typical MAX-CUT problems, WS-QAOA tends to outperform QAOA as approximate solutions become closer to the exact solutions in terms of the Hamming distance. We reveal that this could be quantitatively attributed to the initial state of the ansatz. We also solve MAX-CUT problems by WS-QAOA with approximate solutions obtained via QAOA, having a better result than QAOA especially when the circuit is relatively shallow. We believe that our study may deepen understanding of the performance of WS-QAOA and also provide a guide as to the necessary quality of approximate solutions.

Related papers

• Multiscale Quantum Approximate Optimization Algorithm [0.0]
  The quantum approximate optimization algorithm (QAOA) is one of the canonical algorithms designed to find approximate solutions to optimization problems. We propose a new version of QAOA that incorporates the capabilities of QAOA and the real-space renormalization group transformation.
  arXiv  Detail & Related papers  (2023-12-11T07:47:16Z)
• Evaluating the Practicality of Quantum Optimization Algorithms for Prototypical Industrial Applications [44.88678858860675]
  We investigate the application of the quantum approximate optimization algorithm (QAOA) and the quantum adiabatic algorithm (QAA) to the solution of a prototypical model in this field. We compare the performance of these two algorithms in terms of solution quality, using selected evaluation metrics.
  arXiv  Detail & Related papers  (2023-11-20T09:09:55Z)
• Probabilistic Sampling of Balanced K-Means using Adiabatic Quantum Computing [93.83016310295804]
  AQCs allow to implement problems of research interest, which has sparked the development of quantum representations for computer vision tasks. In this work, we explore the potential of using this information for probabilistic balanced k-means clustering. Instead of discarding non-optimal solutions, we propose to use them to compute calibrated posterior probabilities with little additional compute cost. This allows us to identify ambiguous solutions and data points, which we demonstrate on a D-Wave AQC on synthetic tasks and real visual data.
  arXiv  Detail & Related papers  (2023-10-18T17:59:45Z)
• A hybrid quantum-classical approach to warm-starting optimization [0.0]
  We compare the performance of standard QAOA with that of warm-start QAOA in the context of portfolio optimization. We show that the results can be reproduced or even surpassed by a purely classical preprocessing of the original problem followed by standard QAOA.
  arXiv  Detail & Related papers  (2023-09-25T08:53:54Z)
• A Review on Quantum Approximate Optimization Algorithm and its Variants [47.89542334125886]
  The Quantum Approximate Optimization Algorithm (QAOA) is a highly promising variational quantum algorithm that aims to solve intractable optimization problems. This comprehensive review offers an overview of the current state of QAOA, encompassing its performance analysis in diverse scenarios. We conduct a comparative study of selected QAOA extensions and variants, while exploring future prospects and directions for the algorithm.
  arXiv  Detail & Related papers  (2023-06-15T15:28:12Z)
• Mean-Field Approximate Optimization Algorithm [0.17812428873698405]
  Mean-field Approximate Optimization Algorithm (mean-field AOA) developed by replacing quantum evolution of QAOA with classical spin dynamics. We benchmark its performance against the QAOA on the Sherrington-Kirkpatrick (SK) model and the partition problem. Our algorithm can thus serve as a tool to delineate optimization problems that can be solved classically from those that cannot.
  arXiv  Detail & Related papers  (2023-03-01T08:47:06Z)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  Multi-Object Tracking (MOT) is most often approached in the tracking-by-detection paradigm, where object detections are associated through time. As these optimization problems are often NP-hard, they can only be solved exactly for small instances on current hardware. We show that our approach is competitive compared with state-of-the-art optimization-based approaches, even when using of-the-shelf integer programming solvers.
  arXiv  Detail & Related papers  (2022-02-17T18:59:20Z)
• Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
  We quantify scaling of the expected resource requirements by optimized circuits for hardware architectures with varying levels of connectivity. We show the number of measurements, and hence total time to synthesizing solution, grows exponentially in problem size and problem graph degree. These problems may be alleviated by increasing hardware connectivity or by recently proposed modifications to the QAOA that achieve higher performance with fewer circuit layers.
  arXiv  Detail & Related papers  (2022-01-06T21:02:30Z)
• Quantum Approximate Optimization Algorithm Based Maximum Likelihood Detection [80.28858481461418]
  Recent advances in quantum technologies pave the way for noisy intermediate-scale quantum (NISQ) devices. Recent advances in quantum technologies pave the way for noisy intermediate-scale quantum (NISQ) devices.
  arXiv  Detail & Related papers  (2021-07-11T10:56:24Z)
• Evaluation of QAOA based on the approximation ratio of individual samples [0.0]
  We simulate the performance of QAOA applied to the Max-Cut problem and compare it with some of the best classical alternatives. Because of the evolving QAOA computational complexity-theoretic guidance, we utilize a framework for the search for quantum advantage.
  arXiv  Detail & Related papers  (2020-06-08T18:00:18Z)
• Cross Entropy Hyperparameter Optimization for Constrained Problem Hamiltonians Applied to QAOA [68.11912614360878]
  Hybrid quantum-classical algorithms such as Quantum Approximate Optimization Algorithm (QAOA) are considered as one of the most encouraging approaches for taking advantage of near-term quantum computers in practical applications. Such algorithms are usually implemented in a variational form, combining a classical optimization method with a quantum machine to find good solutions to an optimization problem. In this study we apply a Cross-Entropy method to shape this landscape, which allows the classical parameter to find better parameters more easily and hence results in an improved performance.
  arXiv  Detail & Related papers  (2020-03-11T13:52:41Z)

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.