Improving Quantum Optimization Algorithms by Constraint Relaxation
Quantum optimization is a significant area of quantum computing research with anticipated near-term quantum advantages. Current quantum optimization algorithms, most of which are hybrid variational-Hamiltonian-based algorithms, struggle to present quantum devices due to noise and decoherence. Existi...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2024-09-01
|
| Series: | Applied Sciences |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2076-3417/14/18/8099 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850259165301178368 |
|---|---|
| author | Tomasz Pecyna Rafał Różycki |
| author_facet | Tomasz Pecyna Rafał Różycki |
| author_sort | Tomasz Pecyna |
| collection | DOAJ |
| description | Quantum optimization is a significant area of quantum computing research with anticipated near-term quantum advantages. Current quantum optimization algorithms, most of which are hybrid variational-Hamiltonian-based algorithms, struggle to present quantum devices due to noise and decoherence. Existing techniques attempt to mitigate these issues through employing different Hamiltonian encodings or Hamiltonian clause pruning, but they often rely on optimistic assumptions rather than a deep analysis of the problem structure. We demonstrate how to formulate the problem Hamiltonian for a quantum approximate optimization algorithm that satisfies all the requirements to correctly describe the considered tactical aircraft deconfliction problem, achieving higher probabilities for finding solutions compared to previous works. Our results indicate that constructing Hamiltonians from an unconventional, quantum-specific perspective with a high degree of entanglement results in a linear instead of exponential number of entanglement gates instead and superior performance compared to standard formulations. Specifically, we achieve a higher probability of finding feasible solutions: finding solutions in nine out of nine instances compared to standard Hamiltonian formulations and quadratic programming formulations known from quantum annealers, which only found solutions in seven out of nine instances. These findings suggest that there is substantial potential for further research in quantum Hamiltonian design and that gate-based approaches may offer superior optimization performance over quantum annealers in the future. |
| format | Article |
| id | doaj-art-6c517cd1c7d54459a529ed50e53c62cc |
| institution | OA Journals |
| issn | 2076-3417 |
| language | English |
| publishDate | 2024-09-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Applied Sciences |
| spelling | doaj-art-6c517cd1c7d54459a529ed50e53c62cc2025-08-20T01:55:57ZengMDPI AGApplied Sciences2076-34172024-09-011418809910.3390/app14188099Improving Quantum Optimization Algorithms by Constraint RelaxationTomasz Pecyna0Rafał Różycki1Poznan Supercomputing and Networking Center, IBCH PAS, 61-139 Poznan, PolandInstitute of Computing Science, Poznan University of Technology, 60-965 Poznan, PolandQuantum optimization is a significant area of quantum computing research with anticipated near-term quantum advantages. Current quantum optimization algorithms, most of which are hybrid variational-Hamiltonian-based algorithms, struggle to present quantum devices due to noise and decoherence. Existing techniques attempt to mitigate these issues through employing different Hamiltonian encodings or Hamiltonian clause pruning, but they often rely on optimistic assumptions rather than a deep analysis of the problem structure. We demonstrate how to formulate the problem Hamiltonian for a quantum approximate optimization algorithm that satisfies all the requirements to correctly describe the considered tactical aircraft deconfliction problem, achieving higher probabilities for finding solutions compared to previous works. Our results indicate that constructing Hamiltonians from an unconventional, quantum-specific perspective with a high degree of entanglement results in a linear instead of exponential number of entanglement gates instead and superior performance compared to standard formulations. Specifically, we achieve a higher probability of finding feasible solutions: finding solutions in nine out of nine instances compared to standard Hamiltonian formulations and quadratic programming formulations known from quantum annealers, which only found solutions in seven out of nine instances. These findings suggest that there is substantial potential for further research in quantum Hamiltonian design and that gate-based approaches may offer superior optimization performance over quantum annealers in the future.https://www.mdpi.com/2076-3417/14/18/8099quantum computingquantum optimizationquantum approximate optimization algorithmtactical aircraft deconfliction problemquadratic unconstrained binary optimizationHamiltonian |
| spellingShingle | Tomasz Pecyna Rafał Różycki Improving Quantum Optimization Algorithms by Constraint Relaxation Applied Sciences quantum computing quantum optimization quantum approximate optimization algorithm tactical aircraft deconfliction problem quadratic unconstrained binary optimization Hamiltonian |
| title | Improving Quantum Optimization Algorithms by Constraint Relaxation |
| title_full | Improving Quantum Optimization Algorithms by Constraint Relaxation |
| title_fullStr | Improving Quantum Optimization Algorithms by Constraint Relaxation |
| title_full_unstemmed | Improving Quantum Optimization Algorithms by Constraint Relaxation |
| title_short | Improving Quantum Optimization Algorithms by Constraint Relaxation |
| title_sort | improving quantum optimization algorithms by constraint relaxation |
| topic | quantum computing quantum optimization quantum approximate optimization algorithm tactical aircraft deconfliction problem quadratic unconstrained binary optimization Hamiltonian |
| url | https://www.mdpi.com/2076-3417/14/18/8099 |
| work_keys_str_mv | AT tomaszpecyna improvingquantumoptimizationalgorithmsbyconstraintrelaxation AT rafałrozycki improvingquantumoptimizationalgorithmsbyconstraintrelaxation |