Grover Adaptive Search for the Higher-Order Formulation of Quadratic Assignment Problems
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911198964875264 |
|---|---|
| author | Mikuriya, Taku Fujiwara, Shintaro Yukiyoshi, Kein de Abreu, Giuseppe Thadeu Freitas Ishikawa, Naoki |
| author_facet | Mikuriya, Taku Fujiwara, Shintaro Yukiyoshi, Kein de Abreu, Giuseppe Thadeu Freitas Ishikawa, Naoki |
| contents | We demonstrate that the search space of the quadratic assignment problem (QAP), known as an NP-hard combinatorial optimization problem, can be reduced using Grover adaptive search (GAS) with permutation preparation operator (PPO). To that end, we first revise the traditional quadratic unconstrained binary optimization (QUBO) formulation of the QAP into a higher-order unconstrained binary optimization (HUBO) formulation, introducing a binary encoding method. Algebraic analyses in terms of the number of qubits, quantum gates, circuit depth, and query complexity are performed, which indicate that our proposed approach significantly reduces the search space size, improving convergence performance to the optimal solution compared to the conventional one. Furthermore, although the PPO for HUBO has a greater circuit depth than the PPO for QUBO, when the analysis is extended to the entire state preparation operator, both HUBO and QUBO exhibit comparable depths. Therefore, owing to its smaller number of variables, HUBO can be concluded to be more effective. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_12181 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Grover Adaptive Search for the Higher-Order Formulation of Quadratic Assignment Problems Mikuriya, Taku Fujiwara, Shintaro Yukiyoshi, Kein de Abreu, Giuseppe Thadeu Freitas Ishikawa, Naoki Quantum Physics We demonstrate that the search space of the quadratic assignment problem (QAP), known as an NP-hard combinatorial optimization problem, can be reduced using Grover adaptive search (GAS) with permutation preparation operator (PPO). To that end, we first revise the traditional quadratic unconstrained binary optimization (QUBO) formulation of the QAP into a higher-order unconstrained binary optimization (HUBO) formulation, introducing a binary encoding method. Algebraic analyses in terms of the number of qubits, quantum gates, circuit depth, and query complexity are performed, which indicate that our proposed approach significantly reduces the search space size, improving convergence performance to the optimal solution compared to the conventional one. Furthermore, although the PPO for HUBO has a greater circuit depth than the PPO for QUBO, when the analysis is extended to the entire state preparation operator, both HUBO and QUBO exhibit comparable depths. Therefore, owing to its smaller number of variables, HUBO can be concluded to be more effective. |
| title | Grover Adaptive Search for the Higher-Order Formulation of Quadratic Assignment Problems |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2410.12181 |