Counting with the quantum alternating operator ansatz
Provides a variational quantum algorithm for approximate counting, a fundamental computational problem, with provable sample complexity improvements.
VQCount uses QAOA to approximate #P-hard counting problems, reducing the number of samples needed exponentially compared to prior work. On synthetic instances of #NAE3SAT and #1-in-3SAT, it achieves empirical efficiency gains over rejection sampling and Grover-based counting.
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.