Out of the Loop: Structural Approximation of Optimisation Landscapes and non-Iterative Quantum Optimisation
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908642000764928 |
|---|---|
| author | Krüger, Tom Mauerer, Wolfgang |
| author_facet | Krüger, Tom Mauerer, Wolfgang |
| contents | The Quantum Approximate Optimisation Algorithm (QAOA) is a widely studied quantum-classical iterative heuristic for combinatorial optimisation. While QAOA targets problems in complexity class NP, the classical optimisation procedure required in every iteration is itself known to be \NP-hard. Still, advantage over classical approaches is suspected for certain scenarios, but nature and origin of its computational power are not yet satisfactorily understood.
By introducing means of efficiently and accurately approximating the QAOA optimisation landscape from solution space structures, we derive a new algorithmic variant of unit-depth QAOA for two-level Hamiltonians (including all problems in NP): Instead of performing an iterative quantum-classical computation for each input instance, our non-iterative method is based on a quantum circuit that is instance-independent, but problem-specific. It matches or outperforms unit-depth QAOA for key combinatorial problems, despite reduced computational effort.
Our approach is based on proving a long-standing conjecture regarding instance-independent structures in QAOA. By ensuring generality, we link existing empirical observations on QAOA parameter clustering to established approaches in theoretical computer science, and provide a sound foundation for understanding the link between structural properties of solution spaces and quantum optimisation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_06493 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Out of the Loop: Structural Approximation of Optimisation Landscapes and non-Iterative Quantum Optimisation Krüger, Tom Mauerer, Wolfgang Quantum Physics The Quantum Approximate Optimisation Algorithm (QAOA) is a widely studied quantum-classical iterative heuristic for combinatorial optimisation. While QAOA targets problems in complexity class NP, the classical optimisation procedure required in every iteration is itself known to be \NP-hard. Still, advantage over classical approaches is suspected for certain scenarios, but nature and origin of its computational power are not yet satisfactorily understood. By introducing means of efficiently and accurately approximating the QAOA optimisation landscape from solution space structures, we derive a new algorithmic variant of unit-depth QAOA for two-level Hamiltonians (including all problems in NP): Instead of performing an iterative quantum-classical computation for each input instance, our non-iterative method is based on a quantum circuit that is instance-independent, but problem-specific. It matches or outperforms unit-depth QAOA for key combinatorial problems, despite reduced computational effort. Our approach is based on proving a long-standing conjecture regarding instance-independent structures in QAOA. By ensuring generality, we link existing empirical observations on QAOA parameter clustering to established approaches in theoretical computer science, and provide a sound foundation for understanding the link between structural properties of solution spaces and quantum optimisation. |
| title | Out of the Loop: Structural Approximation of Optimisation Landscapes and non-Iterative Quantum Optimisation |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2408.06493 |