.png){kind=icon}
.png){kind=icon}
Return
A full-quantum algorithm for solving the exact cover problem via quantum gradient descent iteration
.png){kind=icon}
PRE
AI
DOI：10.1088/1555-6611/ae5047.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Combinatorial optimization problems are pervasive across various real-world industries, yet solving them remains classically intractable due to their nondeterministic polynomial (NP)-hard nature. This paper presents an iterative quantum algorithm based on full quantum gradient descent (QGD) to solve the exact cover problem, a fundamental NP-complete problem serving as a representative scenario of airline tail assignment. We formulate the practical optimization task into a set partitioning framework and subsequently map it onto the ground-state search of an Ising Hamiltonian. By employing a QGD-driven iterative mechanism, the proposed algorithm can evolve the initial state in a quantum register towards a high-fidelity approximation of the Ising ground state within only a few iterations. Numerical simulations validate the algorithm's effectiveness across various problem scales, encompassing both sparsely and nearly fully connected graph configurations. Results demonstrate that the algorithm achieves high precision with a relatively few number of iterative steps. Compared to existing approaches, this work bypasses complex classical optimization loops and requires significantly less pre-computation overhead, thereby offering a promising and scalable pathway for solving combinatorial optimization problems on future universal quantum computing platforms.
Keywords:
combinatorial optimization
full quantum gradient descent
tail assignment problem
exact cover
Journal
L
IF:
1.1
Papers:
61
Citations:
2.9K