International Conference on Advanced Electronic Materials, Computers and Software Engineering (AEMCSE)
A Universal Quantum Gradient Descent Framework for Exact Cover Problems
Jingyu Huo, Ru Zhang, Cong Cao
Abstract
Combinatorial optimization problems are foundational in computational science, yet their NP-complete nature renders them classically intractable as problem scales increase. Many such problems can be successfully mapped onto the ground-state search of an Ising Hamiltonian. In this work, we propose a full-quantum iterative algorithm based on the quantum gradient descent (QGD) framework, implemented via the linear combination of unitaries, to solve the standard exact cover problem. By reformulating discrete logical constraints into a quadratic unconstrained binary optimization model, the algorithm evolves an initial uniform superposition state directly within the Hilbert space toward the ground-state subspace. Numerical simulations on instances ranging from different qubits demonstrate that the algorithm achieves high-fidelity convergence with a logarithmic scaling of iteration depth relative to solution precision. Notably, our results reveal that the QGD framework effectively preserves the symmetry of the solution space, allowing for the simultaneous identification of the entire set of optimal results in the presence of ground-state degeneracy. By bypassing complex classical-quantum optimization loops and the associated barren plateau problem, this work provides a robust and scalable full-quantum pathway for resolving high-dimensional logic constraints on future universal quantum computing platforms.