Connection between single-layer Quantum Approximate Optimization Algorithm interferometry and thermal distributions sampling

• URL: http://arxiv.org/abs/2310.09172v1
• Date: Fri, 13 Oct 2023 15:06:58 GMT
• Title: Connection between single-layer Quantum Approximate Optimization Algorithm interferometry and thermal distributions sampling
• Authors: Pablo D\'iez-Valle, Diego Porras, and Juan Jos\'e Garc\'ia-Ripoll
• Abstract summary: We extend the theoretical derivation of the amplitudes of the eigenstates, and the Boltzmann distributions generated by single-layer QAOA. We also review the implications that this behavior has from both a practical and fundamental perspective.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Quantum Approximate Optimization Algorithm (QAOA) is an algorithm originally proposed to find approximate solutions to Combinatorial Optimization problems on quantum computers. However, the algorithm has also attracted interest for sampling purposes since it was theoretically demonstrated under reasonable complexity assumptions that one layer of the algorithm already engineers a probability distribution beyond what can be simulated by classical computers. In this regard, a recent study has shown as well that, in universal Ising models, this global probability distribution resembles pure but thermal-like distributions at a temperature that depends on internal correlations of the spin model. In this work, through an interferometric interpretation of the algorithm, we extend the theoretical derivation of the amplitudes of the eigenstates, and the Boltzmann distributions generated by single-layer QAOA. We also review the implications that this behavior has from both a practical and fundamental perspective.

Related papers

• Harmonic Path Integral Diffusion [0.4527270266697462]
  We present a novel approach for sampling from a continuous multivariate probability distribution. Our method constructs a time-dependent bridge from a delta function centered at the origin of the state space.
  arXiv  Detail & Related papers  (2024-09-23T16:20:21Z)
• Distributed Markov Chain Monte Carlo Sampling based on the Alternating Direction Method of Multipliers [143.6249073384419]
  In this paper, we propose a distributed sampling scheme based on the alternating direction method of multipliers. We provide both theoretical guarantees of our algorithm's convergence and experimental evidence of its superiority to the state-of-the-art. In simulation, we deploy our algorithm on linear and logistic regression tasks and illustrate its fast convergence compared to existing gradient-based methods.
  arXiv  Detail & Related papers  (2024-01-29T02:08:40Z)
• Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms [64.10576998630981]
  We show the first tight characterization of the optimal Hessian-dependent sample complexity. A Hessian-independent algorithm universally achieves the optimal sample complexities for all Hessian instances. The optimal sample complexities achieved by our algorithm remain valid for heavy-tailed noise distributions.
  arXiv  Detail & Related papers  (2023-06-21T17:03:22Z)
• Algorithmic Cluster Expansions for Quantum Problems [0.0]
  We establish a general framework for developing approximation algorithms for a class of counting problems. We apply our framework to approximating probability amplitudes of a class of quantum circuits close to the identity. We show that our algorithmic condition is almost optimal for expectation values and optimal for thermal expectation values in the sense of zero freeness.
  arXiv  Detail & Related papers  (2023-06-15T09:11:48Z)
• 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)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  Efficient computation of the optimal transport distance between two distributions serves as an algorithm that empowers various applications. This paper develops a scalable first-order optimization-based method that computes optimal transport to within $varepsilon$ additive accuracy.
  arXiv  Detail & Related papers  (2023-01-30T15:46:39Z)
• Quantization-Based Optimization: Alternative Stochastic Approximation of Global Optimization [0.0]
  We propose a global optimization algorithm based on quantizing the energy level of an objective function in an NP-hard problem. Numerical experiments show that the proposed algorithm outperforms conventional learning methods in solving NP-hard optimization problems.
  arXiv  Detail & Related papers  (2022-11-08T03:01:45Z)
• Stochastic Approximation with Decision-Dependent Distributions: Asymptotic Normality and Optimality [8.771678221101368]
  We analyze an approximation for decision-dependent problems, wherein the data distribution used by the algorithm evolves along the iterate sequence. We show that under mild assumptions, the deviation between the iterate of the algorithm and its solution isally normal. We also show that the performance of the algorithm with averaging is locally minimax optimal.
  arXiv  Detail & Related papers  (2022-07-09T01:44:17Z)
• Amortized Implicit Differentiation for Stochastic Bilevel Optimization [53.12363770169761]
  We study a class of algorithms for solving bilevel optimization problems in both deterministic and deterministic settings. We exploit a warm-start strategy to amortize the estimation of the exact gradient. By using this framework, our analysis shows these algorithms to match the computational complexity of methods that have access to an unbiased estimate of the gradient.
  arXiv  Detail & Related papers  (2021-11-29T15:10:09Z)
• Active Model Estimation in Markov Decision Processes [108.46146218973189]
  We study the problem of efficient exploration in order to learn an accurate model of an environment, modeled as a Markov decision process (MDP) We show that our Markov-based algorithm outperforms both our original algorithm and the maximum entropy algorithm in the small sample regime.
  arXiv  Detail & Related papers  (2020-03-06T16:17:24Z)

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.