# Counting with the quantum alternating operator ansatz

arXiv: https://arxiv.org/abs/2503.07720 · HTML: https://mlsanity.com/paper/2503.07720/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Mar 2025.

## Built on by (most cited first, 1 of 1)

- [Degeneracy Counting Quantum Algorithm using Decoherence](https://mlsanity.com/paper/2608.14941/) (2026)

## Abstract (arXiv)

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 an arbitrary small 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 empirical efficiency gain over both naive rejection sampling and Grover-based quantum counting. Our results highlight the potential and limitations of variational algorithms for approximate counting.