Quantum-Assisted Recursive Algorithm for Solving the Exact Cover Problem
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914035977420800 |
|---|---|
| author | Ni, Xiao-Hui Fan, Jia-Cheng Li, Ling-Xiao Huang, Zi-Wen Qin, Su-Juan Xu, Bing-Jie Wei-Huang Gao, Fei |
| author_facet | Ni, Xiao-Hui Fan, Jia-Cheng Li, Ling-Xiao Huang, Zi-Wen Qin, Su-Juan Xu, Bing-Jie Wei-Huang Gao, Fei |
| contents | The exact cover problem is an NP-complete problem with broad applications. Studies show that although applying the Quantum Approximate Optimization Algorithm (QAOA) to this problem can yield improved solution quality with deeper circuit depth, it can limit the algorithm's applicability on noisy intermediate-scale quantum devices. To improve solution quality at shallow depth, we propose a Quantum-Assisted Recursive Algorithm (QARA) for solving the exact cover problem. QARA addresses the problem by alternately applying classical and quantum pruning. Classical pruning is a repeatable pre-processing step to simplify the problem. When the classical pruning cannot promote the problem simplification, quantum pruning is invoked. During quantum pruning, QARA extracts information from the QAOA's output state to identify the subset with the strongest selection bias. This subset is then used to prune the problem based on our problem-tailored reduction rules. Furthermore, QARA incorporates a local verification and rollback mechanism to assistively judge the effectiveness of the quantum simplification. After quantum pruning, classical pruning is applied again to the reduced problem if the remaining subsets and element set are not null. This alternating process repeats until the original problem is fully resolved. In our numerical simulations, we evaluate the performance of QARA at one-layer depth on 140 instances with subset sizes ranging from 8 to 20. Numerical results show that the probability of QARA in finding an exact solution is approximately 60\% higher than that of both QAOA and Recursive QAOA, highlighting its efficiency. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_10811 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Quantum-Assisted Recursive Algorithm for Solving the Exact Cover Problem Ni, Xiao-Hui Fan, Jia-Cheng Li, Ling-Xiao Huang, Zi-Wen Qin, Su-Juan Xu, Bing-Jie Wei-Huang Gao, Fei Quantum Physics The exact cover problem is an NP-complete problem with broad applications. Studies show that although applying the Quantum Approximate Optimization Algorithm (QAOA) to this problem can yield improved solution quality with deeper circuit depth, it can limit the algorithm's applicability on noisy intermediate-scale quantum devices. To improve solution quality at shallow depth, we propose a Quantum-Assisted Recursive Algorithm (QARA) for solving the exact cover problem. QARA addresses the problem by alternately applying classical and quantum pruning. Classical pruning is a repeatable pre-processing step to simplify the problem. When the classical pruning cannot promote the problem simplification, quantum pruning is invoked. During quantum pruning, QARA extracts information from the QAOA's output state to identify the subset with the strongest selection bias. This subset is then used to prune the problem based on our problem-tailored reduction rules. Furthermore, QARA incorporates a local verification and rollback mechanism to assistively judge the effectiveness of the quantum simplification. After quantum pruning, classical pruning is applied again to the reduced problem if the remaining subsets and element set are not null. This alternating process repeats until the original problem is fully resolved. In our numerical simulations, we evaluate the performance of QARA at one-layer depth on 140 instances with subset sizes ranging from 8 to 20. Numerical results show that the probability of QARA in finding an exact solution is approximately 60\% higher than that of both QAOA and Recursive QAOA, highlighting its efficiency. |
| title | Quantum-Assisted Recursive Algorithm for Solving the Exact Cover Problem |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2509.10811 |