Constraint Preserving Mixers for the Quantum Approximate Optimization Algorithm
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...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2022-06-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/15/6/202 |
| _version_ | 1797490808726749184 |
|---|---|
| author | Franz Georg Fuchs Kjetil Olsen Lye Halvor Møll Nilsen Alexander Johannes Stasik Giorgio Sartor |
| author_facet | Franz Georg Fuchs Kjetil Olsen Lye Halvor Møll Nilsen Alexander Johannes Stasik Giorgio Sartor |
| author_sort | Franz Georg Fuchs |
| collection | DOAJ |
| description | 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 “XY”-mixer designed to preserve the subspace of “one-hot” 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 “XY”-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. |
| first_indexed | 2024-03-10T00:38:22Z |
| format | Article |
| id | doaj.art-708bab37f67745baabdfed5fcec5e5d7 |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-03-10T00:38:22Z |
| publishDate | 2022-06-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-708bab37f67745baabdfed5fcec5e5d72023-11-23T15:13:14ZengMDPI AGAlgorithms1999-48932022-06-0115620210.3390/a15060202Constraint Preserving Mixers for the Quantum Approximate Optimization AlgorithmFranz Georg Fuchs0Kjetil Olsen Lye1Halvor Møll Nilsen2Alexander Johannes Stasik3Giorgio Sartor4SINTEF, Department of Mathematics and Cybernetics, 0373 Oslo, NorwaySINTEF, Department of Mathematics and Cybernetics, 0373 Oslo, NorwaySINTEF, Department of Mathematics and Cybernetics, 0373 Oslo, NorwaySINTEF, Department of Mathematics and Cybernetics, 0373 Oslo, NorwaySINTEF, Department of Mathematics and Cybernetics, 0373 Oslo, NorwayThe 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 “XY”-mixer designed to preserve the subspace of “one-hot” 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 “XY”-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.https://www.mdpi.com/1999-4893/15/6/202quantum algorithms |
| spellingShingle | Franz Georg Fuchs Kjetil Olsen Lye Halvor Møll Nilsen Alexander Johannes Stasik Giorgio Sartor Constraint Preserving Mixers for the Quantum Approximate Optimization Algorithm Algorithms quantum algorithms |
| title | Constraint Preserving Mixers for the Quantum Approximate Optimization Algorithm |
| title_full | Constraint Preserving Mixers for the Quantum Approximate Optimization Algorithm |
| title_fullStr | Constraint Preserving Mixers for the Quantum Approximate Optimization Algorithm |
| title_full_unstemmed | Constraint Preserving Mixers for the Quantum Approximate Optimization Algorithm |
| title_short | Constraint Preserving Mixers for the Quantum Approximate Optimization Algorithm |
| title_sort | constraint preserving mixers for the quantum approximate optimization algorithm |
| topic | quantum algorithms |
| url | https://www.mdpi.com/1999-4893/15/6/202 |
| work_keys_str_mv | AT franzgeorgfuchs constraintpreservingmixersforthequantumapproximateoptimizationalgorithm AT kjetilolsenlye constraintpreservingmixersforthequantumapproximateoptimizationalgorithm AT halvormøllnilsen constraintpreservingmixersforthequantumapproximateoptimizationalgorithm AT alexanderjohannesstasik constraintpreservingmixersforthequantumapproximateoptimizationalgorithm AT giorgiosartor constraintpreservingmixersforthequantumapproximateoptimizationalgorithm |