Entropic property of randomized QAOA circuits

• URL: http://arxiv.org/abs/2308.01807v4
• Date: Tue, 28 Nov 2023 16:57:10 GMT
• Title: Entropic property of randomized QAOA circuits
• Abstract summary: Quantum approximate optimization algorithm (QAOA) aims to solve discrete optimization problems by sampling bitstrings using a parameterized quantum circuit. We provide analytical equations for probabilities and the numerical evidence that for unweighted Max-Cut problems on connected graphs such sampling always gives higher entropy of energy distribution. We also analyse the probability to obtain the global optima, which appears to be higher on average than for random sampling.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum approximate optimization algorithm (QAOA) aims to solve discrete optimization problems by sampling bitstrings using a parameterized quantum circuit. The circuit parameters (angles) are optimized in the way that minimizes the cost Hamiltonian expectation value. Recently, general statistical properties of QAOA output probability distributions have begun to be studied. In contrast to the conventional approach, we analyse QAOA circuits with random angles. We provide analytical equations for probabilities and the numerical evidence that for unweighted Max-Cut problems on connected graphs such sampling always gives higher entropy of energy distribution than uniform random sampling of bitstrings. We also analyse the probability to obtain the global optima, which appears to be higher on average than for random sampling.

Related papers

• Are Randomized Quantum Linear Systems Solvers Practical? [0.0]
  randomized quantum algorithms have been proposed in the context of quantum simulation and quantum linear algebra.<n>We provide explicit bounds on all relevant parameters that control the total error for a randomized quantum linear systems solver.<n>Our work serves as a bridge between theoretical algorithmic proposals and efficient hardware implementations.
  arXiv  Detail & Related papers  (2025-10-15T17:12:55Z)
• Biased Degenerate Ground-State Sampling of Small Ising Models with Converged QAOA [1.0878040851638]
  We numerically examine the fair sampling properties transverse field mixer QAOA, and Grover Mixer QAOA. Some problem instances clearly saturate the Shannon entropy of 0 with a maximally biased distribution that occurs when the learning converges to an approximation ratio of 1.
  arXiv  Detail & Related papers  (2024-11-08T02:54:28Z)
• Harmonic Path Integral Diffusion [0.4527270266697462]
  We present a novel approach for sampling from a continuous multivariate probability distribution, which may either be explicitly known (up to a normalization factor) or represented via empirical samples. Our method constructs a time-dependent bridge from a delta function centered at the origin of the state space at $t=0$, transforming it into the target distribution at $t=1$. We contrast these algorithms with other sampling methods, particularly simulated and path integral sampling, highlighting their advantages in terms of analytical control, accuracy, and computational efficiency.
  arXiv  Detail & Related papers  (2024-09-23T16:20:21Z)
• Performance Upper Bound of Grover-Mixer Quantum Alternating Operator Ansatz [3.5023108034606256]
  The Quantum Alternating Operator Ansatz (QAOA) represents a branch of quantum algorithms for solving optimization problems. A specific variant, the Grover-Mixer Quantum Alternating Operator Ansatz (GM-QAOA), ensures uniform amplitude across states that share equivalent objective values. We show that the GM-QAOA provides a quadratic enhancement in sampling probability and requires circuit depth that scales exponentially with problem size to maintain consistent performance.
  arXiv  Detail & Related papers  (2024-05-06T05:47:27Z)
• Parameter Setting in Quantum Approximate Optimization of Weighted Problems [10.396104620517171]
  In this work, we develop parameter settings for QAOA applied to a general class of weighted problems. First, we derive optimal parameters for QAOA with depth $p=1$ applied to the weighted MaxCut problem under different assumptions on the weights. Second, for $pgeq 1$ we prove that the QAOA energy landscape for weighted MaxCut approaches that for the unweighted case under a simple rescaling of parameters. Third, we propose a general rescaling scheme inspired by the analytical results for weighted MaxCut and demonstrate its effectiveness.
  arXiv  Detail & Related papers  (2023-05-24T14:37:33Z)
• Importance sampling for stochastic quantum simulations [68.8204255655161]
  We introduce the qDrift protocol, which builds random product formulas by sampling from the Hamiltonian according to the coefficients. We show that the simulation cost can be reduced while achieving the same accuracy, by considering the individual simulation cost during the sampling stage. Results are confirmed by numerical simulations performed on a lattice nuclear effective field theory.
  arXiv  Detail & Related papers  (2022-12-12T15:06:32Z)
• Problem-Size Independent Angles for a Grover-Driven Quantum Approximate Optimization Algorithm [0.0]
  We show that the calculation of the expectation of a problem Hamiltonian under a Grover-driven, QAOA-prepared state can be performed independently of system size. Such calculations can help deliver insights into the performance of and predictability of angles in QAOA in the limit of large problem sizes.
  arXiv  Detail & Related papers  (2022-08-22T17:18:25Z)
• Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems [98.34292831923335]
  Motivated by the problem of online correlation analysis, we propose the emphStochastic Scaled-Gradient Descent (SSD) algorithm. We bring these ideas together in an application to online correlation analysis, deriving for the first time an optimal one-time-scale algorithm with an explicit rate of local convergence to normality.
  arXiv  Detail & Related papers  (2021-12-29T18:46:52Z)
• A Stochastic Newton Algorithm for Distributed Convex Optimization [62.20732134991661]
  We analyze a Newton algorithm for homogeneous distributed convex optimization, where each machine can calculate gradients of the same population objective. We show that our method can reduce the number, and frequency, of required communication rounds compared to existing methods without hurting performance.
  arXiv  Detail & Related papers  (2021-10-07T17:51:10Z)
• Transferability of optimal QAOA parameters between random graphs [3.321726991033431]
  We show that convergence of the optimal QAOA parameters around specific values can be explained and predicted based on the local properties of the graphs. We demonstrate how optimized parameters calculated for a 6-node random graph can be successfully used without modification as nearly optimal parameters for a 64-node random graph.
  arXiv  Detail & Related papers  (2021-06-14T15:57:47Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  It is essential to theoretically guarantee that algorithms provide small objective residual with high probability. Existing methods for non-smooth convex optimization have complexity bounds with dependence on confidence level. We propose novel stepsize rules for two methods with gradient clipping.
  arXiv  Detail & Related papers  (2021-06-10T17:54:21Z)
• Revisiting the Sample Complexity of Sparse Spectrum Approximation of Gaussian Processes [60.479499225746295]
  We introduce a new scalable approximation for Gaussian processes with provable guarantees which hold simultaneously over its entire parameter space. Our approximation is obtained from an improved sample complexity analysis for sparse spectrum Gaussian processes (SSGPs)
  arXiv  Detail & Related papers  (2020-11-17T05:41:50Z)
• Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
  We consider the populationimation barycenter problem for random probability measures supported on a finite set of points and generated by an online stream of data. We employ the structure of the problem and obtain a convex-concave saddle-point reformulation of this problem. In the setting when the distribution of random probability measures is discrete, we propose an optimization algorithm and estimate its complexity.
  arXiv  Detail & Related papers  (2020-06-11T19:40:38Z)

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.