A novel quantum-inspired approximate dynamic programming algorithm (ADP) is proposed for solving unit commitment (UC) problems.The quantum computing theory is applied to tackle some new issues rising from ADP.In details, the unit states in UC problems are expressed by the quantum superposition.Then, the collapsing principle of quantum measurement is applied to solve the Bellman equation of ADP speedily.Based on the quantum rotation gate, the pre-decision states of the ADP are generated by quantum amplitude amplification technology.In the proposal algorithm, the quantum computation balances between state space exploration and exploitation automatically.Test cases of UC are performed to verify the feasibility of the proposal approximate algorithm for the range of 10 to 100 units with 24-hour with ramp rate constraints.The experimental results show that the quantum-inspired ADP algorithm can find the better sub-optimal solutions of large scale UC problems within a reasonable time.A novel quantum-inspired approximate dynamic programming algorithm (ADP) is proposed for solving unit commitment (UC) problems.The quantum computing theory is applied to tackle some new issues rising from ADP.In details, the unit states in UC problems are expressed by the quantum superposition.Then, the collapsing principle of quantum measurement is applied to solve the Bellman equation of ADP speedily.Based on the quantum rotation gate, the pre-decision states of the ADP are generated by quantum amplitude amplification technology.In the proposal algorithm, the quantum computation balances between state space exploration and exploitation automatically.Test cases of UC are performed to verify the feasibility of the proposal approximate algorithm for the range of 10 to 100 units with 24-hour with ramp rate constraints.The experimental results show that the quantum-inspired ADP algorithm can find the better sub-optimal solutions of large scale UC problems within a reasonable time.

International Conference on Materials Engineering, Manufacturing Technology and Control (ICMEMTC)Jan 1, 20160 citations

Quantum Algorithms for Discrete Optimization

Sergio Boixo, Rolando D. Somma

Jan 1, 20150 citations

QGENE: A Quantum Dynamic Programming Model for Pairwise Sequence Alignment

Shyam Sundar, Hari Priya Narahari, Sadanand Venkataraman +4 more

We propose QGENE, a quantum-enhanced framework for approximate string matching used to perform local DNA sequence alignment. QGENE is a dynamic programming model with recursive functions that emulates the Smith Waterman pairwise sequence alignment. QGENE facilitates overlapped computation of both the forward scan and traceback steps in the Smith-Waterman algorithm using quantum circuits within the Qiskit platform. The model integrates Quantum Fourier Transform (QFT)-based arithmetic operations and Grover's algorithm for score comparison. QGENE's traceback logic processes antidiagonals in the alignment matrix, while supporting precise nucleotide matching and efficient traceback operations. The results are comparatively evaluated with a Quadratic Unconstrained Binary Optimization (QUBO) model mapped to an Ising Hamiltonian, enabling advanced quantum optimization algorithms such as the Quantum Approximate Optimization Algorithm (QAOA).We propose QGENE, a quantum-enhanced framework for approximate string matching used to perform local DNA sequence alignment. QGENE is a dynamic programming model with recursive functions that emulates the Smith Waterman pairwise sequence alignment. QGENE facilitates overlapped computation of both the forward scan and traceback steps in the Smith-Waterman algorithm using quantum circuits within the Qiskit platform. The model integrates Quantum Fourier Transform (QFT)-based arithmetic operations and Grover's algorithm for score comparison. QGENE's traceback logic processes antidiagonals in the alignment matrix, while supporting precise nucleotide matching and efficient traceback operations. The results are comparatively evaluated with a Quadratic Unconstrained Binary Optimization (QUBO) model mapped to an Ising Hamiltonian, enabling advanced quantum optimization algorithms such as the Quantum Approximate Optimization Algorithm (QAOA).

IEEE International Conference on Quantum Computing and Engineering (QCE)Aug 30, 20250 citations

Hybrid Quantum-Classical Dynamic Programming Algorithm

Chih-Chieh Chen, Kodai Shiba, Masaru Sogabe +2 more

Advances in intelligent systems and computingJan 1, 20211 citation

Quantum Algorithms for Solving Dynamic Programming Problems

Pooya Ronagh

We present a general quantum algorithm for solving finite-horizon dynamic programming problems. Up to polylogarithmic factors, our algorithm provides a quadratic quantum advantage in terms of the number of states of a given dynamic programming problem. This speedup comes at the expense of the appearance of other polynomial factors representative of the number of actions of the dynamic programming problem, the maximum value of the instantaneous reward, and the time horizon of the problem. Our algorithm can be applied to combinatorial optimization problems solved classically using dynamic programming techniques. As one application, we show that the travelling salesperson problem can be solved in $O^*(\lceil c \rceil^4 \sqrt{2^n})$ on a quantum computer, where $n$ is the number of vertices of the underlying graph and $\lceil c \rceil$ is its maximum edge-weight. As another example, we show that the minimum set-cover problem can be solved in $O(\sqrt{2^n} \operatorname{poly}(m, n))$ , where $m$ is the number of sets used to cover a universe of size $n$ . Finally, we prove lower bounds for the query complexity of quantum algorithms and classical randomized algorithms for solving dynamic programming problems, and show that no greater-than-quadratic speedup in either the number of states or number of actions can be achieved for solving dynamic programming problems using quantum algorithms.We present a general quantum algorithm for solving finite-horizon dynamic programming problems. Up to polylogarithmic factors, our algorithm provides a quadratic quantum advantage in terms of the number of states of a given dynamic programming problem. This speedup comes at the expense of the appearance of other polynomial factors representative of the number of actions of the dynamic programming problem, the maximum value of the instantaneous reward, and the time horizon of the problem. Our algorithm can be applied to combinatorial optimization problems solved classically using dynamic programming techniques. As one application, we show that the travelling salesperson problem can be solved in $O^*(\lceil c \rceil^4 \sqrt{2^n})$ on a quantum computer, where $n$ is the number of vertices of the underlying graph and $\lceil c \rceil$ is its maximum edge-weight. As another example, we show that the minimum set-cover problem can be solved in $O(\sqrt{2^n} \operatorname{poly}(m, n))$, where $m$ is the number of sets used to cover a universe of size $n$. Finally, we prove lower bounds for the query complexity of quantum algorithms and classical randomized algorithms for solving dynamic programming problems, and show that no greater-than-quadratic speedup in either the number of states or number of actions can be achieved for solving dynamic programming problems using quantum algorithms.

Jun 5, 201913 citations

QUANTUM ALGORITHM FOR LINEAR PROGRAMMING PROBLEMS

Pramod S. Joag, Dhananjay P. Mehendale

Bulletin of the American Physical SocietyMar 15, 20161 citation

O^*(\lceil c \rceil^4 \sqrt{2^n})

on a quantum computer, where

n

is the number of vertices of the underlying graph and

\lceil c \rceil

is its maximum edge-weight. As another example, we show that the minimum set-cover problem can be solved in

O(\sqrt{2^n} \operatorname{poly}(m, n))

, where

m

is the number of sets used to cover a universe of size

n

. Finally, we prove lower bounds for the query complexity of quantum algorithms and classical randomized algorithms for solving dynamic programming problems, and show that no greater-than-quadratic speedup in either the number of states or number of actions can be achieved for solving dynamic programming problems using quantum algorithms.