Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

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

Published Mar 20, 2026• 0 citations
Publisher

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.

DOI
10.1109/aetcse69203.2026.11504007

Related papers

A full-quantum algorithm for solving the exact cover problem via quantum gradient descent iteration

Jingyu Huo, Ling Fan, Ru Zhang +1 more

Abstract 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.

Laser Physics•Mar 20, 2026•1 citation

Iterative quantum algorithm for combinatorial optimization based on quantum gradient descent

Xin Yi, Jingyu Huo, Yong‐Pan Gao +3 more

Combinatorial optimization has wide and high-value applications in many fields of science and industry, but solving general combinatorial optimization problems is non-deterministic polynomial time (NP) hard. Many such problems can be mapped onto the ground-state-search problems of the Ising model. Here, an iterative quantum algorithm based on quantum gradient descent to solve combinatorial optimization problems is introduced, where the initial state of a quantum register evolves over several iterations to a good approximation of the Ising-Hamiltonian ground state. We verified the effectiveness of the proposed algorithm in solving the MaxCut problem for different types of undirected graphs by numerical simulations, and analyzed the robustness of the algorithm to errors by simulating random error and Gaussian error. We compared the performance of the algorithm with the quantum approximate optimization algorithm, and the results indicate that the proposed algorithm has comparable convergence performance. We also verified the feasibility of the algorithm by conducting experiments on a real quantum computer through the quantum cloud platform. Our work provides a potential method for solving combinatorial optimization problems on future quantum devices without the use of complex classical optimization loops.

Results in Physics•Nov 20, 2023•17 citations

Quantum-Enhanced Gradient Descent (QGD)

Jincheng Zhang

Quantum-Enhanced Gradient Descent (QGD) presents a novel algorithmic approach to optimization, leveraging quantum computing to accelerate the gradient descent process. This paper explores the potential of quantum algorithms to significantly expedite convergence in machine learning and other optimization problems. We detail the core mechanism of QGD, outlining its integration of quantum parallelism and its impact on the traditional iterative nature of gradient descent. We provide a comprehensive discussion of the theoretical foundations, potential implementation challenges, and preliminary experimental results demonstrating the efficacy of QGD. The core claim is that QGD can provide a substantial speedup compared to classical gradient descent, particularly in scenarios involving complex landscapes and large datasets.

•Sep 3, 2026•0 citations

Quantum Gradient Descent – Beyond Classical Optimization

Jincheng Zhang

Quantum Gradient Descent (QGD) presents a novel approach to optimization, leveraging the inherent quantum properties of systems to achieve solutions beyond the limitations of classical methods. This paper explores the potential of QGD, focusing on the implementation of a "Quantum State Collapse" mechanism to dynamically shift and explore multiple solution spaces simultaneously. We detail the theoretical framework underpinning this approach, outlining the challenges and opportunities presented by this paradigm shift. The core claim is that QGD offers a fundamentally different path toward finding optimal solutions, potentially unlocking new capabilities in complex optimization problems across diverse fields.

•Sep 3, 2026•0 citations

Quantum-compatible Riemannian conjugate gradient for ground-state preparation

Andres Arcia-Lopez, Marek Gluza, Yudai Suzuki +1 more

Riemannian optimization provides a natural geometric framework for designing quantum algorithms for ground-state preparation, most notably through quantum imaginary-time evolution. However, existing geometry-aware approaches primarily employ steepest-descent updates, leaving more advanced methods from classical Riemannian optimization largely unexplored. In this work, we introduce quantum conjugate gradient descent (QCGD), a quantum-compatible implementation of Riemannian conjugate gradient that combines the steepest descent direction with information retained from previous search directions. In our numerical experiments, the proposed approach achieves faster convergence per iteration than the baseline double-bracket quantum imaginary-time evolution (DB-QITE) algorithm, and we quantify the associated circuit cost with gate counts produced by Qrisp. This improvement, however, comes at the cost of increased circuit depth for each update step, revealing a trade-off between convergence rate and implementation complexity. Nevertheless, since the circuit depth for those algorithms grows exponentially with the number of iterations, the proposed method may offer practical advantages, particularly in the early fault-tolerant regime.

quant-pharXiv:2610.21782•Oct 16, 2026•0 citations

Quantum Circuit Optimization through Iteratively Pre-Conditioned Gradient Descent

Dhruv Srinivasan, Kushal Chakrabarti, Nikhil Chopra +1 more

Gate-based quantum algorithms are typically implemented by circuits consisting of many single-qubit and multi-qubit gates operating on a quantum input state, followed by measurements of the output state. For certain quantum subroutines, such as initial state preparation and quantum Fourier transforms, explicit decompositions of the circuit in terms of single-qubit and two-qubit maximally entangling gates may exist. However, they often lead to large-depth circuits that are challenging for noisy intermediate-scale quantum (NISQ) hardware. Additionally, exact decompositions might only exist for some modular quantum circuits. Therefore, it is essential to find gate combinations that approximate these circuits to high fidelity with potentially low depth. Gradient-based optimization has been used to find such approximate decompositions. Still, these traditional optimizers often run into problems of slow convergence requiring many iterations, and performing poorly in the presence of noise, a factor that is especially relevant for NISQ hardware. Here we present iteratively preconditioned gradient descent (IPG) for optimizing quantum circuits and demonstrate performance speedups for state preparation and implementation of quantum algorithmic subroutines. IPG is a noise-resilient, higher-order algorithm that has shown promising gains in convergence speed for classical optimizations, converging locally at a linear rate for convex problems and superlinearly when the solution is unique. Specifically, we show an improvement in fidelity by a factor of 104for preparing a 4-qubit W state and a maximally entangled 5-qubit GHZ state with compared to other commonly used classical optimizers tuning the same ansatz. Such faster convergence with promise for noise-resilience could provide advantages for quantum algorithms on NISQ hardware, especially since the cost of running each iteration on a quantum computer is substantially higher than the classical optimizer step.

arXiv:2309.09957•IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 17, 2023•2 citations
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.
Abstract 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.
Combinatorial optimization has wide and high-value applications in many fields of science and industry, but solving general combinatorial optimization problems is non-deterministic polynomial time (NP) hard. Many such problems can be mapped onto the ground-state-search problems of the Ising model. Here, an iterative quantum algorithm based on quantum gradient descent to solve combinatorial optimization problems is introduced, where the initial state of a quantum register evolves over several iterations to a good approximation of the Ising-Hamiltonian ground state. We verified the effectiveness of the proposed algorithm in solving the MaxCut problem for different types of undirected graphs by numerical simulations, and analyzed the robustness of the algorithm to errors by simulating random error and Gaussian error. We compared the performance of the algorithm with the quantum approximate optimization algorithm, and the results indicate that the proposed algorithm has comparable convergence performance. We also verified the feasibility of the algorithm by conducting experiments on a real quantum computer through the quantum cloud platform. Our work provides a potential method for solving combinatorial optimization problems on future quantum devices without the use of complex classical optimization loops.
Quantum-Enhanced Gradient Descent (QGD) presents a novel algorithmic approach to optimization, leveraging quantum computing to accelerate the gradient descent process. This paper explores the potential of quantum algorithms to significantly expedite convergence in machine learning and other optimization problems. We detail the core mechanism of QGD, outlining its integration of quantum parallelism and its impact on the traditional iterative nature of gradient descent. We provide a comprehensive discussion of the theoretical foundations, potential implementation challenges, and preliminary experimental results demonstrating the efficacy of QGD. The core claim is that QGD can provide a substantial speedup compared to classical gradient descent, particularly in scenarios involving complex landscapes and large datasets.
Quantum Gradient Descent (QGD) presents a novel approach to optimization, leveraging the inherent quantum properties of systems to achieve solutions beyond the limitations of classical methods. This paper explores the potential of QGD, focusing on the implementation of a "Quantum State Collapse" mechanism to dynamically shift and explore multiple solution spaces simultaneously. We detail the theoretical framework underpinning this approach, outlining the challenges and opportunities presented by this paradigm shift. The core claim is that QGD offers a fundamentally different path toward finding optimal solutions, potentially unlocking new capabilities in complex optimization problems across diverse fields.
Riemannian optimization provides a natural geometric framework for designing quantum algorithms for ground-state preparation, most notably through quantum imaginary-time evolution. However, existing geometry-aware approaches primarily employ steepest-descent updates, leaving more advanced methods from classical Riemannian optimization largely unexplored. In this work, we introduce quantum conjugate gradient descent (QCGD), a quantum-compatible implementation of Riemannian conjugate gradient that combines the steepest descent direction with information retained from previous search directions. In our numerical experiments, the proposed approach achieves faster convergence per iteration than the baseline double-bracket quantum imaginary-time evolution (DB-QITE) algorithm, and we quantify the associated circuit cost with gate counts produced by Qrisp. This improvement, however, comes at the cost of increased circuit depth for each update step, revealing a trade-off between convergence rate and implementation complexity. Nevertheless, since the circuit depth for those algorithms grows exponentially with the number of iterations, the proposed method may offer practical advantages, particularly in the early fault-tolerant regime.
Gate-based quantum algorithms are typically implemented by circuits consisting of many single-qubit and multi-qubit gates operating on a quantum input state, followed by measurements of the output state. For certain quantum subroutines, such as initial state preparation and quantum Fourier transforms, explicit decompositions of the circuit in terms of single-qubit and two-qubit maximally entangling gates may exist. However, they often lead to large-depth circuits that are challenging for noisy intermediate-scale quantum (NISQ) hardware. Additionally, exact decompositions might only exist for some modular quantum circuits. Therefore, it is essential to find gate combinations that approximate these circuits to high fidelity with potentially low depth. Gradient-based optimization has been used to find such approximate decompositions. Still, these traditional optimizers often run into problems of slow convergence requiring many iterations, and performing poorly in the presence of noise, a factor that is especially relevant for NISQ hardware. Here we present iteratively preconditioned gradient descent (IPG) for optimizing quantum circuits and demonstrate performance speedups for state preparation and implementation of quantum algorithmic subroutines. IPG is a noise-resilient, higher-order algorithm that has shown promising gains in convergence speed for classical optimizations, converging locally at a linear rate for convex problems and superlinearly when the solution is unique. Specifically, we show an improvement in fidelity by a factor of 104for preparing a 4-qubit W state and a maximally entangled 5-qubit GHZ state with compared to other commonly used classical optimizers tuning the same ansatz. Such faster convergence with promise for noise-resilience could provide advantages for quantum algorithms on NISQ hardware, especially since the cost of running each iteration on a quantum computer is substantially higher than the classical optimizer step.