Compressed space quantum approximate optimization algorithm for constrained combinatorial optimization
| Autor: | Shirai, Tatsuhiko, Togawa, Nozomu |
|---|---|
| Rok vydání: | 2024 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | Combinatorial optimization is a promising area for achieving quantum speedup. Quantum approximate optimization algorithm (QAOA) is designed to search for low-energy states of the Ising model, which correspond to near-optimal solutions of combinatorial optimization problems (COPs). However, effectively dealing with constraints of COPs remains a significant challenge. Existing methods, such as tailoring mixing operators, are typically limited to specific constraint types, like one-hot constraints. To address these limitations, we introduce a method for engineering a compressed space that represents the feasible solution space with fewer qubits than the original. Our approach includes a scalable technique for determining the unitary transformation between the compressed and original spaces on gate-based quantum computers. We then propose compressed space QAOA, which seeks near-optimal solutions within this reduced space, while utilizing the Ising model formulated in the original Hilbert space. Experimental results on a quantum simulator demonstrate the effectiveness of our method in solving various constrained COPs. Comment: 11 pages, 7 figures |
| Databáze: | arXiv |
| Externí odkaz: |
|