Dynamic programming lends speed to some quantum algorithms
The group of CQT Fellow Nelly Ng shows quantum dynamic programming can solve quantum recursions efficiently
(From left) Co-authors Marek Gluza, Nelly Ng and Jeongrak Son and collaborator Ryuji Takagi (not pictured) designed a method that compresses circuit depth by expanding circuit width for computing quantum recursions.
Like saving your progress in a game saves you time when you next want to play, memory can help speed up a quantum computation. That’s the finding of CQT Fellow Nelly Ng and her coauthors, who have proposed a technique that uses memory to compute problems known as quantum recursions more efficiently.
Called quantum dynamic programming (QDP), the team’s new technique could exponentially speed up recursion computations compared to other methods at the cost of needing more qubits. The researchers published their work in Physical Review Letters on 7 May 2025.
Nelly holds a co-appointment as Nanyang Assistant Professor at Nanyang Technological University, Singapore (NTU Singapore). Her co-authors are NTU PhD student Jeongrak Son, NTU Research Fellow Marek Gluza and collaborator Ryuji Takagi who is based at the University of Tokyo, Japan.
Calling on memory
Recursions are a structure that appear in algorithms for ground state preparation, among others. Grover’s famous search algorithm can also be written as a quantum recursion.
A classic example of a recursion is the Fibonacci sequence, where each number in the sequence is the sum of the two numbers preceding it, giving 0, 1, 1, 2, 3, 5, 8, 13 and so on. Likewise, a quantum recursion is a sequence of quantum states that depend on the earlier states.
Current approaches to solve quantum recursions use brute force computation, or unfolding, which is akin to calculating the nth number in Fibonacci’s sequence by starting from zero at each step. The time it takes grows exponentially with n.
With memory, those time demands can be scaled back by reducing recomputation. For example, you might compute the seventh number of the Fibonacci sequence (8) by retrieving the previous two digits from memory (5 and 3) and adding them, instead of calculating each digit again.
The extra challenge in quantum computing is how to retrieve the full information of a quantum state stored in memory. This is because any measurement made on a state changes the state. Solving a quantum recursion takes more tricks.
Existing approaches to solve a quantum recursion either (i) make many measurements on many copies of the quantum memory to retrieve the information, a technique known as quantum tomography; or (ii) use unfolding, recomputing the whole sequence each time. Both are time consuming and demand either many copies of the state, meaning a wide circuit, or many operations, known as a deep circuit.
This is where QDP comes in. “To solve this problem, we have come up with a third way that compresses the depth of the circuit and expands the width,” says Jeongrak, who is also first author of the paper.
Similar to tomography, the researchers start with many copies of the initial quantum state. Different to tomography, they don’t measure these states, instead using them as a memory that stores both the state and instructions for how the state should evolve to the next step of the recursion. “The essential step of using memory is storing the information of what interaction is going on in the evolution, as that influences the computation,” says Marek.
For example, if 128 copies of the initial state are prepared, the researchers can compute the recursion such that the number of copies of the state reduces by half at each step, using two copies to get one copy of the next state.
While the circuit is still wide, the method ultimately uses fewer copies of the state than tomography, and it is shallow, using fewer rounds of operations than unfolding.
Systematic tradeoffs
The researchers see their method as an additional tool to choose from depending on the hardware constraints. For example, QDP suits a quantum processor with many qubits but a short coherence time, while unfolding could suit a processor having fewer qubits but a long coherence time, and the best solution might use the two approaches together.
Nelly says, “The beautiful thing about our work is not only that we can trade exponential circuit depth with width, but it is a systematic tradeoff.” That gives the researchers control to tailor the mix of tools they use to the needs of the hardware.
Next, the team is looking to optimise the tradeoff by finding information theoretic bounds and to collaborate with experimentalists to test QDP on current hardware.
