Biased Degenerate Ground-State Sampling of Small Ising Models with Converged QAOA

• URL: http://arxiv.org/abs/2411.05294v1
• Date: Fri, 08 Nov 2024 02:54:28 GMT
• Title: Biased Degenerate Ground-State Sampling of Small Ising Models with Converged QAOA
• Abstract summary: 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.
• Score: 1.0878040851638
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Quantum Alternating Operator Ansatz, a generalization of the Quantum Approximate Optimization Algorithm (QAOA), is a quantum algorithm used for approximately solving combinatorial optimization problems. QAOA typically uses the Transverse field mixer as the driving Hamiltonian. One of the interesting properties of the Transverse-field driving Hamiltonian is that it results in non-uniform sampling of degenerate ground states of optimization problems. In this study we numerically examine the fair sampling properties transverse field mixer QAOA, and Grover Mixer QAOA (GM-QAOA) which provides theoretical guarantees of fair sampling of degenerate optimal solutions, up to large enough p such that the mean expectation value converges to an optimal approximation ratio of 1. This comparison is performed with high quality heuristically computed, but not necessarily optimal, QAOA angles which give strictly monotonically improving solution quality as p increases. These angles are computed using the Julia based numerical simulation software JuliQAOA. Fair sampling of degenerate ground-states is quantified using Shannon entropy of the ground-state amplitudes distribution. The fair sampling properties are reported on several quantum signature Hamiltonians from previous quantum annealing fair sampling studies. Small random fully connected spin glasses are shown which exhibit exponential suppression of some degenerate ground-states with transverse field mixer QAOA. The transverse field mixer QAOA simulations show that 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 while other problem instances never deviate from a maximum Shannon entropy (uniform distribution) at any p step.

Related papers

• Divide-and-Conquer Neural Network Surrogates for Quantum Sampling: Accelerating Markov Chain Monte Carlo in Large-Scale Constrained Optimization Problems [2.9436347471485558]
  One approach known as quantum-enhanced Markov chain Monte Carlo uses quantum samples as a proposal distribution to accelerate convergence to a target distribution.<n>We propose a divide-and-conquer neural network surrogate framework for quantum sampling to accelerate MCMC under fixed Hamming weight constraints.<n>Our method consistently accelerated mixing as the system size increased, with average improvements in the autocorrelation decay rate constant by speedup factors of about $20.3$ and $7.6$ over classical pair-flip methods.
  arXiv  Detail & Related papers  (2026-04-22T15:44:30Z)
• Unfair Sampling of Quantum Annealing in Weighted Graph Bipartitioning Problems [0.7519872646378835]
  We study how the penalty coefficient in the penalty method affects sampling fairness.<n>More than 70% of instances exhibit monotonically increasing sampling fairness as the penalty coefficient increases.<n>These results show that increasing the penalty coefficient improves sampling fairness, though at the cost of ground-state probability.
  arXiv  Detail & Related papers  (2026-04-13T13:28:49Z)
• Proximal-IMH: Proximal Posterior Proposals for Independent Metropolis-Hastings with Approximate Operators [4.887201041798969]
  We introduce Proximal-IMH, a scheme that corrects samples from the approximate posterior through an auxiliary optimization problem.<n>For idealized settings, we prove that the proximal correction tightens the match between approximate and exact posteriors, thereby improving acceptance rates and mixing.<n>The method applies to both linear and nonlinear input-output operators and is particularly suitable for inverse problems where exact posterior sampling is too expensive.
  arXiv  Detail & Related papers  (2026-02-24T22:58:50Z)
• Parallel simulation for sampling under isoperimetry and score-based diffusion models [56.39904484784127]
  As data size grows, reducing the iteration cost becomes an important goal. Inspired by the success of the parallel simulation of the initial value problem in scientific computation, we propose parallel Picard methods for sampling tasks. Our work highlights the potential advantages of simulation methods in scientific computation for dynamics-based sampling and diffusion models.
  arXiv  Detail & Related papers  (2024-12-10T11:50:46Z)
• Optimizing random local Hamiltonians by dissipation [44.99833362998488]
  We prove that a simplified quantum Gibbs sampling algorithm achieves a $Omega(frac1k)$-fraction approximation of the optimum. Our results suggest that finding low-energy states for sparsified (quasi)local spin and fermionic models is quantumly easy but classically nontrivial.
  arXiv  Detail & Related papers  (2024-11-04T20:21:16Z)
• Variational Tensor Network Simulation of Gaussian Boson Sampling and Beyond [0.0]
  We propose a classical simulation tool for general continuous variable sampling problems. We reformulate the sampling problem as that of finding the ground state of a simple few-body Hamiltonian. We validate our method by simulating Gaussian Boson Sampling, where we achieve results comparable to the state of the art.
  arXiv  Detail & Related papers  (2024-10-24T13:43:06Z)
• 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)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Symmetric Mean-field Langevin Dynamics for Distributional Minimax Problems [78.96969465641024]
  We extend mean-field Langevin dynamics to minimax optimization over probability distributions for the first time with symmetric and provably convergent updates. We also study time and particle discretization regimes and prove a new uniform-in-time propagation of chaos result.
  arXiv  Detail & Related papers  (2023-12-02T13:01:29Z)
• Entropic property of randomized QAOA circuits [0.0]
  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.
  arXiv  Detail & Related papers  (2023-08-03T15:13:23Z)
• PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash Equilibrium [58.26573117273626]
  We consider the non-AL equilibrium nonconptotic objective function in two-player zero-sum continuous games. Our novel insights into the particle-based algorithms for continuous distribution strategies are presented.
  arXiv  Detail & Related papers  (2023-03-02T05:08:15Z)
• 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)
• Sampling with Mollified Interaction Energy Descent [57.00583139477843]
  We present a new optimization-based method for sampling called mollified interaction energy descent (MIED) MIED minimizes a new class of energies on probability measures called mollified interaction energies (MIEs) We show experimentally that for unconstrained sampling problems our algorithm performs on par with existing particle-based algorithms like SVGD.
  arXiv  Detail & Related papers  (2022-10-24T16:54:18Z)
• Average-case Speedup for Product Formulas [69.68937033275746]
  Product formulas, or Trotterization, are the oldest and still remain an appealing method to simulate quantum systems. We prove that the Trotter error exhibits a qualitatively better scaling for the vast majority of input states. Our results open doors to the study of quantum algorithms in the average case.
  arXiv  Detail & Related papers  (2021-11-09T18:49:48Z)
• Efficient approximation of experimental Gaussian boson sampling [2.805766654291013]
  Two recent landmark experiments have performed Gaussian boson sampling (GBS) with a non-programmable linear interferometer and threshold detectors on up to 144 output modes. Here we give classical sampling algorithms with better total variation distance and Kullback-Leibler divergence than these experiments.
  arXiv  Detail & Related papers  (2021-09-23T17:47:06Z)
• Bosonic field digitization for quantum computers [62.997667081978825]
  We address the representation of lattice bosonic fields in a discretized field amplitude basis. We develop methods to predict error scaling and present efficient qubit implementation strategies.
  arXiv  Detail & Related papers  (2021-08-24T15:30:04Z)
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
  Asynchronous Q-learning aims to learn the optimal action-value function (or Q-function) of a Markov decision process (MDP) We show that the number of samples needed to yield an entrywise $varepsilon$-accurate estimate of the Q-function is at most on the order of $frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$ up to some logarithmic factor.
  arXiv  Detail & Related papers  (2020-06-04T17:51:00Z)

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.