{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,2]],"date-time":"2026-04-02T11:40:10Z","timestamp":1775130010033,"version":"3.50.1"},"reference-count":26,"publisher":"MDPI AG","issue":"6","license":[{"start":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T00:00:00Z","timestamp":1654819200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>The quantum approximate optimization algorithm\/quantum alternating operator ansatz (QAOA) is a heuristic to find approximate solutions of combinatorial optimization problems. Most of the literature is limited to quadratic problems without constraints. However, many practically relevant optimization problems do have (hard) constraints that need to be fulfilled. In this article, we present a framework for constructing mixing operators that restrict the evolution to a subspace of the full Hilbert space given by these constraints. We generalize the \u201cXY\u201d-mixer designed to preserve the subspace of \u201cone-hot\u201d states to the general case of subspaces given by a number of computational basis states. We expose the underlying mathematical structure which reveals more of how mixers work and how one can minimize their cost in terms of the number of CX gates, particularly when Trotterization is taken into account. Our analysis also leads to valid Trotterizations for an \u201cXY\u201d-mixer with fewer CX gates than is known to date. In view of practical implementations, we also describe algorithms for efficient decomposition into basis gates. Several examples of more general cases are presented and analyzed.<\/jats:p>","DOI":"10.3390\/a15060202","type":"journal-article","created":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T10:25:12Z","timestamp":1654856712000},"page":"202","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":41,"title":["Constraint Preserving Mixers for the Quantum Approximate Optimization Algorithm"],"prefix":"10.3390","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3558-503X","authenticated-orcid":false,"given":"Franz Georg","family":"Fuchs","sequence":"first","affiliation":[{"name":"SINTEF, Department of Mathematics and Cybernetics, 0373 Oslo, Norway"}]},{"given":"Kjetil Olsen","family":"Lye","sequence":"additional","affiliation":[{"name":"SINTEF, Department of Mathematics and Cybernetics, 0373 Oslo, Norway"}]},{"given":"Halvor","family":"M\u00f8ll Nilsen","sequence":"additional","affiliation":[{"name":"SINTEF, Department of Mathematics and Cybernetics, 0373 Oslo, Norway"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1646-2472","authenticated-orcid":false,"given":"Alexander Johannes","family":"Stasik","sequence":"additional","affiliation":[{"name":"SINTEF, Department of Mathematics and Cybernetics, 0373 Oslo, Norway"}]},{"given":"Giorgio","family":"Sartor","sequence":"additional","affiliation":[{"name":"SINTEF, Department of Mathematics and Cybernetics, 0373 Oslo, Norway"}]}],"member":"1968","published-online":{"date-parts":[[2022,6,10]]},"reference":[{"key":"ref_1","unstructured":"Farhi, E., Goldstone, J., and Gutmann, S. (2014). A quantum approximate optimization algorithm. arXiv."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Hadfield, S., Wang, Z., O\u2019Gorman, B., Rieffel, E.G., Venturelli, D., and Biswas, R. (2019). From the quantum approximate optimization algorithm to a quantum alternating operator ansatz. Algorithms, 12.","DOI":"10.3390\/a12020034"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"5","DOI":"10.3389\/fphy.2014.00005","article-title":"Ising formulations of many NP problems","volume":"2","author":"Lucas","year":"2014","journal-title":"Front. Phys."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Hatano, N., and Suzuki, M. (2005). Finding exponential product formulas of higher orders. Quantum Annealing and Other Optimization Methods, Springer.","DOI":"10.1007\/11526216_2"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"545","DOI":"10.1090\/S0002-9939-1959-0108732-6","article-title":"On the product of semi-groups of operators","volume":"10","author":"Trotter","year":"1959","journal-title":"Proc. Am. Math. Soc."},{"key":"ref_6","unstructured":"Kronsj\u00f6, L. (1987). Algorithms: Their Complexity and Efficiency, John Wiley & Sons, Inc."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"6903","DOI":"10.1038\/s41598-019-43176-9","article-title":"QAOA for Max-Cut requires hundreds of qubits for quantum speed-up","volume":"9","author":"Guerreschi","year":"2019","journal-title":"Sci. Rep."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"625","DOI":"10.1038\/s42254-021-00348-9","article-title":"Variational quantum algorithms","volume":"3","author":"Cerezo","year":"2021","journal-title":"Nat. Rev. Phys."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"030503","DOI":"10.1088\/2058-9565\/aab822","article-title":"Quantum optimization using variational algorithms on near-term quantum devices","volume":"3","author":"Moll","year":"2018","journal-title":"Quantum Sci. Technol."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"120502","DOI":"10.1103\/PhysRevLett.127.120502","article-title":"Training variational quantum algorithms is NP-hard\u2014Even for logarithmically many qubits and free fermionic systems","volume":"127","author":"Bittel","year":"2021","journal-title":"Phys. Rev. Lett."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1038\/s41467-021-27045-6","article-title":"Noise-induced barren plateaus in variational quantum algorithms","volume":"12","author":"Wang","year":"2021","journal-title":"Nat. Commun."},{"key":"ref_12","unstructured":"Zhang, H.K., Zhu, C., Liu, G., and Wang, X. (2022). Fundamental limitations on optimization in variational quantum algorithms. arXiv."},{"key":"ref_13","unstructured":"Zhu, L., Tang, H.L., Barron, G.S., Mayhall, N.J., Barnes, E., and Economou, S.E. (2020). An adaptive quantum approximate optimization algorithm for solving combinatorial problems on a quantum computer. arXiv."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Bravyi, S., Kliesch, A., Koenig, R., and Tang, E. (2019). Obstacles to state preparation and variational optimization from symmetry protection. arXiv.","DOI":"10.1103\/PhysRevLett.125.260505"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Egger, D.J., Marecek, J., and Woerner, S. (2020). Warm-starting quantum optimization. arXiv.","DOI":"10.22331\/q-2021-06-17-479"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"034009","DOI":"10.1103\/PhysRevApplied.14.034009","article-title":"Applying the Quantum Approximate Optimization Algorithm to the Tail-Assignment Problem","volume":"14","author":"Svensson","year":"2020","journal-title":"Phys. Rev. Appl."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s42979-020-00437-z","article-title":"Efficient Encoding of the Weighted MAX k-CUT on a Quantum Computer Using QAOA","volume":"2","author":"Fuchs","year":"2021","journal-title":"SN Comput. Sci."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Hadfield, S., Wang, Z., Rieffel, E.G., O\u2019Gorman, B., Venturelli, D., and Biswas, R. (2017, January 12\u201317). Quantum approximate optimization with hard and soft constraints. Proceedings of the Second International Workshop on Post Moores Era Supercomputing, Denver, CO, USA.","DOI":"10.1145\/3149526.3149530"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"012320","DOI":"10.1103\/PhysRevA.101.012320","article-title":"XY mixers: Analytical and numerical results for the quantum alternating operator ansatz","volume":"101","author":"Wang","year":"2020","journal-title":"Phys. Rev. A"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1016\/0003-4916(61)90115-4","article-title":"Two soluble models of an antiferromagnetic chain","volume":"16","author":"Lieb","year":"1961","journal-title":"Ann. Phys."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Cook, J., Eidenbenz, S., and B\u00e4rtschi, A. (2020, January 12\u201316). The quantum alternating operator ansatz on maximum k-vertex cover. Proceedings of the 2020 IEEE International Conference on Quantum Computing and Engineering (QCE), Broomfield, CO, USA.","DOI":"10.1109\/QCE49297.2020.00021"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"062312","DOI":"10.1103\/PhysRevA.93.062312","article-title":"Driver Hamiltonians for constrained optimization in quantum annealing","volume":"93","author":"Hen","year":"2016","journal-title":"Phys. Rev. A"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"034007","DOI":"10.1103\/PhysRevApplied.5.034007","article-title":"Quantum annealing for constrained optimization","volume":"5","author":"Hen","year":"2016","journal-title":"Phys. Rev. Appl."},{"key":"ref_24","unstructured":"Sakurai, J.J. (1967). Advanced Quantum Mechanics, Pearson."},{"key":"ref_25","unstructured":"Gokhale, P., Angiuli, O., Ding, Y., Gui, K., Tomesh, T., Suchara, M., Martonosi, M., and Chong, F.T. (2019). Minimizing state preparations in variational quantum eigensolver by partitioning into commuting families. arXiv."},{"key":"ref_26","unstructured":"Gui, K., Tomesh, T., Gokhale, P., Shi, Y., Chong, F.T., Martonosi, M., and Suchara, M. (2020). Term grouping and travelling salesperson for digital quantum simulation. arXiv."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/6\/202\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T23:27:46Z","timestamp":1760138866000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/6\/202"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,10]]},"references-count":26,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2022,6]]}},"alternative-id":["a15060202"],"URL":"https:\/\/doi.org\/10.3390\/a15060202","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,6,10]]}}}