Counting with the quantum alternating operator ansatz

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 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.

14 pages, 11 figures; published version

References in corpus (18)

• SciPy 1.0--Fundamental Algorithms for Scientific Computing in Python
• Variational Quantum Algorithms
• Ising formulations of many NP problems
• Quantum Amplitude Amplification and Estimation
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Training variational quantum algorithms is NP-hard
• Quantum Supremacy and the Complexity of Random Circuit Sampling
• Hyper-optimized tensor network contraction
• Quantum annealing initialization of the quantum approximate optimization algorithm
• Quantum Approximate Counting, Simplified
• Grover Mixers for QAOA: Shifting Complexity from Mixer Design to State Preparation
• Exponentially-Biased Ground-State Sampling of Quantum Annealing Machines with Transverse-Field Driving Hamiltonians
• The Phase Diagram of 1-in-3 Satisfiability Problem
• Fast counting with tensor networks
• Fair Sampling Error Analysis on NISQ Devices
• Grover-QAOA for 3-SAT: Quadratic Speedup, Fair-Sampling, and Parameter Clustering
• Feeding the multitude: A polynomial-time algorithm to improve sampling
• Analytical results for the Quantum Alternating Operator Ansatz with Grover Mixer