Counting with the quantum alternating operator ansatz
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911593286074368 |
|---|---|
| author | Drapeau, Julien Banerjee, Shreya Kourtis, Stefanos |
| author_facet | Drapeau, Julien Banerjee, Shreya Kourtis, Stefanos |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_07720 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Counting with the quantum alternating operator ansatz Drapeau, Julien Banerjee, Shreya Kourtis, Stefanos Quantum Physics Statistical Mechanics Data Structures and Algorithms 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. |
| title | Counting with the quantum alternating operator ansatz |
| topic | Quantum Physics Statistical Mechanics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2503.07720 |