A Statistical Approach to Analyzing the Quantum Alternating Operator Ansatz with Grover Mixer

• Guilherme Adamatti Bridi UFRJ
• Franklin de Lima Marquezino UFRJ

DOI: https://doi.org/10.5753/ctd.2025.8022

Resumo

The Quantum Alternating Operator Ansatz (QAOA) is a promising quantum heuristic to combinatorial optimization, designed for the Noisy Intermediate-Scale Quantum (NISQ) era. A key quantum operator of the algorithm is the mixing, which introduces quantum interference. This work investigates analytically the performance of QAOA with the Grover mixer, a mixing operator inspired by Grover’s algorithm. A critical feature of QAOA with Grover mixer is that it depends only on the probability distribution of the solutions, ignoring the structure of the problem. Due to this, it was conjectured that QAOA with this mixer is bounded to the quadratic speed-up of Grover’s algorithm over the classical brute force on the unstructured search problem. On the other hand, this feature allows the development of a statistical approach, which we explore in this work. For a variant of QAOA called Grover mixing QAOA (GM-QAOA), the analysis leads to an expression for the expectation value whose number of terms depends exponentially on the number of layers of the QAOA. In contrast, for Grover mixer Threshold QAOA (GM-Th-QAOA), a simpler variant that has an intimate relationship with Grover’s algorithm, we obtain a constant-time expression, which allows us to get bounds for different performance metrics, such as the statistical quantities of standard score and quantile. Subsequently, we generalized QAOA with the Grover mixer in a framework we called Grover-based QAOA. By using a contradiction argument with the optimality of Grover’s algorithm, we extend all the bounds of GM-Th-QAOA to the general context of Grover-based QAOA. As a result, we get the main contribution of this work: the proof of the aforementioned conjecture on the performance of QAOA with Grover mixer. We apply our bounds to the class of complete bipartite graphs on the Max-Cut problem, demonstrating that we cannot obtain a polynomial-time algorithm with Grover-based QAOA for these instances, showing that the performance limitation of the Grover mixer can be very severe. Our results suggest that achieving competitive performance with QAOA requires a mixing operator capable of leveraging the structure of combinatorial optimization problems.

Referências

Akshay, V., Philathong, H., Morales, M. E. S., and Biamonte, J. (2020). Reachability deficits in quantum approximate optimization. Physical review letters, 124(9):090504.

Bärtschi, A. and Eidenbenz, S. (2020). Grover mixers for qaoa: Shifting complexity from mixer design to state preparation. In 2020 IEEE International Conference on Quantum Computing and Engineering, pages 72–82. IEEE.

Benchasattabuse, N., Bärtschi, A., García-Pintos, L. P., Golden, J., Lemons, N., and Eidenbenz, S. (2023). Lower bounds on number of qaoa rounds required for guaranteed approximation ratios. arXiv preprint arXiv:2308.15442.

Bernhard, K. and Vygen, J. (2012). Combinatorial optimization: Theory and algorithms. Springer-Verlag, Berlim, 5 edition.

Blekos, K., Brand, D., Ceschini, A., Chou, C.-H., Li, R.-H., Pandya, K., and Summer, A. (2024). A review on quantum approximate optimization algorithm and its variants. Physics Reports, 1068:1–66.

Bridi, G. A. (2024). A statistical approach to analyzing the quantum alternating operator ansatz with grover mixer. Master’s thesis, Universidade Federal do Rio de Janeiro.

Bridi, G. A. and Marquezino, F. d. L. (2024). Analytical results for the quantum alternating operator ansatz with grover mixer. Physical Review A, 110(5):052409.

Cerezo, M., Arrasmith, A., Babbush, R., Benjamin, S. C., Endo, S., Fujii, K., McClean, J. R., Mitarai, K., Yuan, X., Cincio, L., et al. (2021). Variational quantum algorithms. Nature Reviews Physics, 3(9):625–644.

Cheng, B., Deng, X.-H., Gu, X., He, Y., Hu, G., Huang, P., Li, J., Lin, B.-C., Lu, D., Lu, Y., et al. (2023). Noisy intermediate-scale quantum computers. Frontiers of Physics, 18(2):21308.

Farhi, E., Goldstone, J., and Gutmann, S. (2014). A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028.

Golden, J., Bärtschi, A., O’Malley, D., and Eidenbenz, S. (2023a). Numerical evidence for exponential speed-up of qaoa over unstructured search for approximate constrained optimization. In 2023 IEEE International Conference on Quantum Computing and Engineering, volume 1, pages 496–505. IEEE.

Golden, J., Bärtschi, A., O’Malley, D., and Eidenbenz, S. (2023b). The quantum alternating operator ansatz for satisfiability problems. In 2023 IEEE International Conference on Quantum Computing and Engineering, volume 1, pages 307–312. IEEE.

Golden, J., Bärtschi, A., O’Malley, D., and Eidenbenz, S. (2021). Threshold-based quantum optimization. In 2021 IEEE International Conference on Quantum Computing and Engineering, pages 137–147. IEEE.

Grover, L. K. (1996). A fast quantum mechanical algorithm for database search. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 212–219.

Hadfield, S., Wang, Z., O’gorman, B., Rieffel, E. G., Venturelli, D., and Biswas, R. (2019). From the quantum approximate optimization algorithm to a quantum alternating operator ansatz. Algorithms, 12(2):34.

Hamann, A., Dunjko, V., and Wölk, S. (2021). Quantum-accessible reinforcement learning beyond strictly epochal environments. Quantum Machine Intelligence, 3:1–18.

Headley, D. (2023). Angles and devices for quantum approximate optimization. PhD thesis, Universität des Saarlandes.

Headley, D. and Wilhelm, F. K. (2023). Problem-size-independent angles for a grover-driven quantum approximate optimization algorithm. Physical Review A, 107(1):012412.

Marsh, S. and Wang, J. B. (2020). Combinatorial optimization via highly efficient quantum walks. Physical Review Research, 2(2):023302.

Portugal, R. (2018). Quantum walks and search algorithms. Springer, Cham, 2 edition.

Preskill, J. (2018). Quantum computing in the nisq era and beyond. Quantum, 2:79.

Shor, P. W. (1994). Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th annual symposium on foundations of computer science, pages 124–134. IEEE.

Zalka, C. (1999). Grover’s quantum searching algorithm is optimal. Physical Review A, 60(4):2746.