Counting with the quantum alternating operator ansatz

• URL: http://arxiv.org/abs/2503.07720v1
• Date: Mon, 10 Mar 2025 18:00:02 GMT
• Title: Counting with the quantum alternating operator ansatz
• Authors: Julien Drapeau, Shreya Banerjee, Stefanos Kourtis,
• Abstract summary: We introduce a variational algorithm based on the quantum alternating operator ansatz (QAOA) for the approximate solution of computationally hard counting problems.<n>Our algorithm, dubbed VQCount, is based on the equivalence between random sampling and approximate counting and employs QAOA as a solution sampler.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce a variational algorithm based on the quantum alternating operator ansatz (QAOA) for the approximate solution of computationally hard counting problems. Our algorithm, dubbed VQCount, is based on the equivalence between random sampling and approximate counting and employs QAOA as a solution sampler. We first prove that VQCount improves upon previous work by reducing exponentially the number of samples needed to obtain an approximation within a multiplicative factor of the exact count. Using tensor network simulations, we then study the typical performance of VQCount with shallow circuits on synthetic instances of two #P-hard problems, positive #NAE3SAT and positive #1-in-3SAT. We employ the original quantum approximate optimization algorithm version of QAOA, as well as the Grover-mixer variant which guarantees a uniform solution probability distribution. We observe a tradeoff between QAOA success probability and sampling uniformity, which we exploit to achieve an exponential gain in efficiency over naive rejection sampling. Our results highlight the potential and limitations of variational algorithms for approximate counting.

Related papers

• Simple and Provable Scaling Laws for the Test-Time Compute of Large Language Models [70.07661254213181]
  We propose two principled algorithms for the test-time compute of large language models.<n>We prove theoretically that the failure probability of one algorithm decays to zero exponentially as its test-time compute grows.
  arXiv  Detail & Related papers  (2024-11-29T05:29:47Z)
• 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)
• Vanishing performance of the parity-encoded quantum approximate optimization algorithm applied to spin-glass models [0.0]
  parity mapping provides a geometrically local encoding of the Quantum Approximate Optimization Algorithm (QAOA) We show that for fixed number of parity-encoded QAOA layers, the performance or the output energy vanishes towards zero. Our results suggest that the parity-encoded QAOA does not have a promising scaling compared to the standard version of QAOA.
  arXiv  Detail & Related papers  (2023-11-03T18:00:00Z)
• Quantum-Based Feature Selection for Multi-classification Problem in Complex Systems with Edge Computing [15.894122816099133]
  A quantum-based feature selection algorithm for the multi-classification problem, namely, QReliefF, is proposed. Our algorithm is superior in finding the nearest neighbor, reducing the complexity from O(M) to O(sqrt(M)).
  arXiv  Detail & Related papers  (2023-10-01T03:57:13Z)
• Amplitude amplification-inspired QAOA: Improving the success probability for solving 3SAT [55.78588835407174]
  The amplitude amplification algorithm can be applied to unstructured search for satisfying variable assignments. The Quantum Approximate Optimization Algorithm (QAOA) is a promising candidate for solving 3SAT for Noisy Intermediate-Scale Quantum devices. We introduce amplitude amplification-inspired variants of QAOA to improve the success probability for 3SAT.
  arXiv  Detail & Related papers  (2023-03-02T11:52:39Z)
• 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)
• 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)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP) This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm. Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
  arXiv  Detail & Related papers  (2021-05-06T17:59:38Z)
• An optimal quantum sampling regression algorithm for variational eigensolving in the low qubit number regime [0.0]
  We introduce Quantum Sampling Regression (QSR), an alternative hybrid quantum-classical algorithm. We analyze some of its use cases based on time complexity in the low qubit number regime. We demonstrate the efficacy of our algorithm for a benchmark problem.
  arXiv  Detail & Related papers  (2020-12-04T00:01:15Z)
• 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)
• 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)
• Improving the Performance of Deep Quantum Optimization Algorithms with Continuous Gate Sets [47.00474212574662]
  Variational quantum algorithms are believed to be promising for solving computationally hard problems. In this paper, we experimentally investigate the circuit-depth-dependent performance of QAOA applied to exact-cover problem instances. Our results demonstrate that the use of continuous gate sets may be a key component in extending the impact of near-term quantum computers.
  arXiv  Detail & Related papers  (2020-05-11T17:20:51Z)

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.