Reachability Deficits in Quantum Approximate Optimization of Graph Problems

• URL: http://arxiv.org/abs/2007.09148v2
• Date: Fri, 27 Aug 2021 11:56:24 GMT
• Title: Reachability Deficits in Quantum Approximate Optimization of Graph Problems
• Authors: V. Akshay and H. Philathong and I. Zacharov and J. Biamonte
• Abstract summary: We show that the emphdensity of problem constraints versus problem variables acts as a performance indicator. Motivated by Google's recent experimental realization of QAOA, we reanalysis the reported data reproduced in an ideal noiseless setting.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The quantum approximate optimization algorithm (QAOA) has become a cornerstone of contemporary quantum applications development. Here we show that the \emph{density} of problem constraints versus problem variables acts as a performance indicator. Density is found to correlate strongly with approximation inefficiency for fixed depth QAOA applied to random graph minimization problem instances. Further, the required depth for accurate QAOA solution to graph problem instances scales critically with density. Motivated by Google's recent experimental realization of QAOA, we preform a reanalysis of the reported data reproduced in an ideal noiseless setting. We found that the reported capabilities of instances addressed experimentally by Google, approach a rapid fall-off region in approximation quality experienced beyond intermediate-density. Our findings offer new insight into performance analysis of contemporary quantum optimization algorithms and contradict recent speculation regarding low-depth QAOA performance benefits.

Related papers

• Error Feedback under $(L_0,L_1)$-Smoothness: Normalization and Momentum [56.37522020675243]
  We provide the first proof of convergence for normalized error feedback algorithms across a wide range of machine learning problems. We show that due to their larger allowable stepsizes, our new normalized error feedback algorithms outperform their non-normalized counterparts on various tasks.
  arXiv  Detail & Related papers  (2024-10-22T10:19:27Z)
• Energy Landscapes for the Quantum Approximate Optimisation Algorithm [0.0]
  We use basin-hopping global methods to navigate the energy landscapes for QAOA ans"atze for various graphs. We find that the corresponding landscapes generally have a single funnel organisation, which makes it relatively straightforward to locate low-lying minima with good Max-Cut solution probabilities.
  arXiv  Detail & Related papers  (2024-01-09T19:17:01Z)
• 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)
• 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)
• Can Decentralized Stochastic Minimax Optimization Algorithms Converge Linearly for Finite-Sum Nonconvex-Nonconcave Problems? [56.62372517641597]
  Decentralized minimax optimization has been actively studied in the past few years due to its application in a wide range machine learning. This paper develops two novel decentralized minimax optimization algorithms for the non-strongly-nonconcave problem.
  arXiv  Detail & Related papers  (2023-04-24T02:19:39Z)
• 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)
• Quantifying the Impact of Precision Errors on Quantum Approximate Optimization Algorithms [0.24629531282150877]
  We show that errors in the analog implementation of QAOA circuits hinder its performance as an optimization algorithm. Despite this significant reduction, we show that it is possible to mitigate precision errors in QAOA via digitization of the variational parameters.
  arXiv  Detail & Related papers  (2021-09-09T18:00:03Z)
• Heavy-tailed Streaming Statistical Estimation [58.70341336199497]
  We consider the task of heavy-tailed statistical estimation given streaming $p$ samples. We design a clipped gradient descent and provide an improved analysis under a more nuanced condition on the noise of gradients.
  arXiv  Detail & Related papers  (2021-08-25T21:30:27Z)
• Empirical performance bounds for quantum approximate optimization [0.27998963147546135]
  Quantifying performance bounds provides insight into when QAOA may be viable for solving real-world applications. We find QAOA exceeds the Goemans-Williamson approximation ratio bound for most graphs. The resulting data set is presented as a benchmark for establishing empirical bounds on QAOA performance.
  arXiv  Detail & Related papers  (2021-02-12T23:12:09Z)
• Bridging Classical and Quantum with SDP initialized warm-starts for QAOA [4.76507354067301]
  We introduce a classical pre-processing step that initializes QAOA with a biased superposition of all possible cuts in the graph. We show that this variant of QAOA, called QAOA-Warm, is able to outperform standard QAOA on lower circuit depths with less training time.
  arXiv  Detail & Related papers  (2020-10-27T02:57:22Z)
• Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition [52.08417569774822]
  This paper focuses on methods for solving smooth non-concave min-max problems, which have received increasing attention due to deep learning (e.g., deep AUC)
  arXiv  Detail & Related papers  (2020-06-12T00:32: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.