LX-mixers for QAOA: Optimal mixers restricted to subspaces and the stabilizer formalism
1SINTEF AS, Department of Mathematics and Cybernetics, Oslo, Norway
2Department of Mathematics, University of Oslo, Norway
| Published: | 2024-11-25, volume 8, page 1535 |
| Eprint: | arXiv:2306.17083v8 |
| Doi: | https://doi.org/10.22331/q-2024-11-25-1535 |
| Citation: | Quantum 8, 1535 (2024). |
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
We present a novel formalism to both understand and construct mixers that preserve a given subspace. The method connects and utilizes the stabilizer formalism that is used in error correcting codes. This can be useful in the setting when the quantum approximate optimization algorithm (QAOA), a popular meta-heuristic for solving combinatorial optimization problems, is applied in the setting where the constraints of the problem lead to a feasible subspace that is large but easy to specify. The proposed method gives a systematic way to construct mixers that are resource efficient in the number of controlled not gates and can be understood as a generalization of the well-known X and XY mixers and a relaxation of the Grover mixer: Given a basis of any subspace, a resource efficient mixer can be constructed that preserves the subspace. The numerical examples provided show a dramatic reduction of CX gates when compared to previous results. We call our approach logical X-Mixer or logical X QAOA ($\textbf{LX-QAOA}$), since it can be understood as dividing the subspace into code spaces of stabilizers S and consecutively applying logical rotational X gates associated with these code spaces. Overall, we hope that this new perspective can lead to further insight into the development of quantum algorithms.
Featured image: Schematic view of the proposed method to construct efficient mixers for the quantum alternating operator ansatz (QAOA) constrained to a subspace. The method can be understood as dividing the subspace into code spaces of stabilizers and consecutively applying logical rotational X gates associated with the code spaces.
Popular summary
► BibTeX data
► References
[1] Andreas Bärtschiand Stephan Eidenbenz ``Grover mixers for QAOA: Shifting complexity from mixer design to state preparation'' 2020 IEEE International Conference on Quantum Computing and Engineering (QCE) 72-82 (2020).
https://doi.org/10.1109/QCE49297.2020.00020
[2] Sebastian Brandhofer, Daniel Braun, Vanessa Dehn, Gerhard Hellstern, Matthias Hüls, Yanjun Ji, Ilia Polian, Amandeep Singh Bhatia, and Thomas Wellens, ``Benchmarking the performance of portfolio optimization with QAOA'' Quantum Information Processing 22, 1–27 (2023).
https://doi.org/10.1007/s11128-022-03766-5
[3] Sergey Bravyi, Alexander Kliesch, Robert Koenig, and Eugene Tang, ``Obstacles to Variational Quantum Optimization from Symmetry Protection'' Phys. Rev. Lett. 125, 260505 (2020).
https://doi.org/10.1103/PhysRevLett.125.260505
[4] Pablo Díez-Valle, Diego Porras, and Juan José García-Ripoll, ``Quantum Approximate Optimization Algorithm Pseudo-Boltzmann States'' Physical Review Letters 130, 050601 (2023).
https://doi.org/10.1103/PhysRevLett.130.050601
[5] Pablo Díez-Valle, Jorge Luis-Hita, Senaida Hernández-Santana, Fernando Martínez-García, Álvaro Díaz-Fernández, Eva Andrés, Juan José García-Ripoll, Escolástico Sánchez-Martínez, and Diego Porras, ``Multiobjective variational quantum optimization for constrained problems: an application to cash handling'' Quantum Science and Technology 8, 045009 (2023).
https://doi.org/10.1088/2058-9565/ace474
[6] Daniel J. Egger, Jakub Mareček, and Stefan Woerner, ``Warm-starting quantum optimization'' Quantum 5, 479 (2021).
https://doi.org/10.22331/q-2021-06-17-479
https://quantum-journal.org/papers/q-2021-06-17-479/
[7] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann, ``A quantum approximate optimization algorithm'' arXiv preprint arXiv:1411.4028 (2014).
https://doi.org/10.48550/arXiv.1411.4028
[8] Franz G Fuchs, Herman Øie Kolden, Niels Henrik Aase, and Giorgio Sartor, ``Efficient Encoding of the Weighted MAX k-CUT on a Quantum Computer Using QAOA'' SN Computer Science 2, 1–14 (2021).
https://doi.org/10.1007/s42979-020-00437-z
[9] Franz Georg Fuchs, Kjetil Olsen Lye, Halvor Møll Nilsen, Alexander Johannes Stasik, and Giorgio Sartor, ``Constraint Preserving Mixers for the Quantum Approximate Optimization Algorithm'' Algorithms 15, 202 (2022).
https://doi.org/10.3390/a15060202
[10] Stuart Hadfield, Zhihui Wang, Bryan O'Gorman, Eleanor G Rieffel, Davide Venturelli, and Rupak Biswas, ``From the quantum approximate optimization algorithm to a quantum alternating operator ansatz'' Algorithms 12, 34 (2019).
https://doi.org/10.3390/a12020034
[11] Stuart Hadfield, Zhihui Wang, Eleanor G Rieffel, Bryan O'Gorman, Davide Venturelli, and Rupak Biswas, ``Quantum approximate optimization with hard and soft constraints'' Proceedings of the Second International Workshop on Post Moores Era Supercomputing 15–21 (2017).
https://doi.org/10.1145/3149526.3149530
[12] Tianyi Hao, Ruslan Shaydulin, Marco Pistoia, and Jeffrey Larson, ``Exploiting In-Constraint Energy in Constrained Variational Quantum Optimization'' 2022 IEEE/ACM Third International Workshop on Quantum Computing Software (QCS) (2022).
https://doi.org/10.1109/qcs56647.2022.00017
[13] Naomichi Hatanoand Masuo Suzuki ``Finding exponential product formulas of higher orders'' Springer (2005).
https://doi.org/10.1007/11526216_2
[14] Dylan Herman, Ruslan Shaydulin, Yue Sun, Shouvanik Chakrabarti, Shaohan Hu, Pierre Minssen, Arthur Rattew, Romina Yalovetzky, and Marco Pistoia, ``Constrained optimization via quantum Zeno dynamics'' Communications Physics 6 (2023).
https://doi.org/10.1038/s42005-023-01331-9
[15] S. Marshand J. B. Wang ``Combinatorial optimization via highly efficient quantum walks'' Phys. Rev. Res. 2, 023302 (2020).
https://doi.org/10.1103/PhysRevResearch.2.023302
[16] Pradeep Niroula, Ruslan Shaydulin, Romina Yalovetzky, Pierre Minssen, Dylan Herman, Shaohan Hu, and Marco Pistoia, ``Constrained quantum optimization for extractive summarization on a trapped-ion quantum computer'' Scientific Reports 12 (2022).
https://doi.org/10.1038/s41598-022-20853-w
[17] Tatsuhiko Shiraiand Nozomu Togawa ``Postprocessing Variationally Scheduled Quantum Algorithm for Constrained Combinatorial Optimization Problems'' IEEE Transactions on Quantum Engineering 5, 1–14 (2024).
https://doi.org/10.1109/TQE.2024.3376721
[18] Jens Siewert ``On orthogonal bases in the Hilbert-Schmidt space of matrices'' Journal of Physics Communications 6, 055014 (2022).
https://doi.org/10.1088/2399-6528/ac6f43
[19] Daniel Stilck Françaand Raul Garcia-Patron ``Limitations of optimization algorithms on noisy quantum devices'' Nature Physics 17, 1221–1227 (2021).
https://doi.org/10.1038/s41567-021-01356-3
[20] Hale F Trotter ``On the product of semi-groups of operators'' Proceedings of the American Mathematical Society 10, 545–551 (1959).
https://doi.org/10.2307/2033649
[21] Pontus Vikstål, Mattias Grönkvist, Marika Svensson, Martin Andersson, Göran Johansson, and Giulia Ferrini, ``Applying the Quantum Approximate Optimization Algorithm to the Tail-Assignment Problem'' Phys. Rev. Applied 14, 034009 (2020).
https://doi.org/10.1103/PhysRevApplied.14.034009
[22] Zhihui Wang, Nicholas C. Rubin, Jason M. Dominy, and Eleanor G. Rieffel, ``XY mixers: Analytical and numerical results for the quantum alternating operator ansatz'' Physical Review A 101 (2020).
https://doi.org/10.1103/physreva.101.012320
[23] Linghua Zhu, Ho Lun Tang, George S. Barron, F. A. Calderon-Vargas, Nicholas J. Mayhall, Edwin Barnes, and Sophia E. Economou, ``Adaptive quantum approximate optimization algorithm for solving combinatorial problems on a quantum computer'' Phys. Rev. Res. 4, 033029 (2022).
https://doi.org/10.1103/PhysRevResearch.4.033029
Cited by
[1] Xiangdong Zheng, Jianan Min, Long Luo, Hongfang Yu, and Zonghang Li, "Power-Aware Orchestration for Geo-Distributed LLM Inference via Quantum Optimization", IEEE Transactions on Network Science and Engineering 13, 9969 (2026).
[2] Edric Matwiejew, Jonathan Wurtz, Jing Chen, Pascal Jahan Elahi, Tommaso Macri, and Ugo Varetto, "Continuous-time quantum-walk-based ansätze on neutral-atom hardware", Physical Review A 114 1, 012425 (2026).
[3] Alexey Bochkarev, Raoul Heese, Sven Jäger, Philine Schiewe, and Anita Schöbel, "Quantum computing for discrete optimization: A highlight of three technologies", European Journal of Operational Research 329 3, 747 (2026).
[4] Franz G. Fuchs, Ruben Pariente Bassa, and Frida Lien, "Encodings of the weighted MAX k-CUT problem on qubit systems", Frontiers in Quantum Science and Technology 4, 1636042 (2025).
[5] Manuel H. Muñoz-Arias, Stefanos Kourtis, and Alexandre Blais, "Low-depth Clifford circuits approximately solve MaxCut", Physical Review Research 6 2, 023294 (2024).
[6] Truman Yu Ng, Jin Ming Koh, and Dax Enshan Koh, "Analytical Expressions for the Quantum Approximate Optimization Algorithm and its Variants", arXiv:2411.09745, (2024).
[7] Alexey Bochkarev, Raoul Heese, Sven Jäger, Philine Schiewe, and Anita Schöbel, "Quantum Computing for Discrete Optimization: A Highlight of Three Technologies", arXiv:2409.01373, (2024).
[8] Franz G. Fuchs, Ruben P. Bassa, and Frida Lien, "Encodings of the weighted MAX k-CUT on qubit systems", arXiv:2411.08594, (2024).
The above citations are from Crossref's cited-by service (last updated successfully 2026-08-10 09:33:39) and SAO/NASA ADS (last updated successfully 2026-08-09 19:38:00). The list may be incomplete as not all publishers provide suitable and complete citation data.
Could not fetch ADS cited-by data during last attempt 2026-08-10 09:33:39: Cannot retrieve data from ADS due to rate limitations.
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.