Quantum algorithm design has long operated on low-level circuits. A new mathematical framework makes it more efficient to build quantum algorithms from higher-level building blocks.
On September 14 and 15, quantum researchers gathered at QuSoft, in Amsterdam for a specialized workshop centred on a breakthrough in quantum algorithms design: the transducer. Co-organized by QuSoft senior researchers Stacey Jeffery and Freek Witteveen, the event brought theoretical computer scientists together to discuss the theoretical underpinnings of this framework, and how it can be used to develop new quantum algorithms.
From “Span Program” models to “Transducers”
For years, theoretical computer scientists working in quantum algorithms have made extensive use of a tool called span programs to understand both the power and limitations of quantum algorithms. Span programs convert complex decision problems into linear algebra puzzles, thus simplifying the problem of calculating an algorithm’s “query complexity”.
A quantum query is an operation where an algorithm interrogates an “oracle”: a special unitary transformation that accesses input parameter bits to modify a quantum state.* Counting how many queries an algorithm must make provides a query complexity value, which serves as a fundamental lower bound on the time needed to solve a problem.
While span programs proved an algorithm’s efficiency in the theoretical query complexity model, they suffered from a massive disadvantage: while query complexity is a lower bound on the time needed to solve a problem, in practice, the number of total steps needed may be much larger than this. A span program could prove a query-efficient algorithm existed, but it couldn’t tell scientists how many actual logic gates would be required to build it in practice.
To bridge this gap, Jeffery and her co-authors introduced the transducer in a paper titled “Taming Quantum Time Complexity”. Borrowed from classical computer science, a finite state transducer is a system that transitions between states according to set rules. Adapted for quantum logic, it acts as a system of modular algorithmic blocks that can be efficiently composed. Crucially, the transducer framework allows subroutines to plug directly into one another without triggering compounding error rates. By converting probabilistic algorithms into exact mathematical structures, researchers can trim unnecessary execution loops and calculate real execution time.
“Reducing time, in practice, also helps reduce space,” Witteveen explained.
Because quantum processors require constant, active error correction, longer execution times directly translate to higher spatial costs, requiring thousands of extra physical qubits just to keep the system stable during computation.
Proving the ultimate speed limit for ground-state energy estimation
The practical power of the transducer model was demonstrated through one of the most critical challenges in quantum physics: estimating the ground-state energy of a Hamiltonian, a core task for simulating molecules and which has applications in materials science (for example in drug discovery). Jeffery and Witteveen used the transducer model to design a streamlined algorithm that reduced the time required for ground-state energy estimation by a logarithmic factor. At the same time, QuSoft researcher Ronald de Wolf and his collaborator Rolando Somma published a key paper establishing the matching lower bound: the absolute mathematical speed limit for solving that exact problem. The new transducer-based algorithm hit de Wolf and Somma’s threshold precisely, proving Jeffery and Witteveen had achieved the fastest possible quantum algorithm for the task.
A funny anecdote about AI
The workshop featured talks and collaborative sessions aimed at making the transducer framework standard equipment for the next generation of quantum algorithms designers.
As a fun side note on how the community converged: despite its breakthrough potential, the original 2023 paper was initially relatively overlooked because its authors were not actively traveling to market it. Its recent surge in adoption was partly kickstarted by AI language models, which unexpectedly began recommending the paper to researchers asking about designing quantum algorithms and de-facto acting as accidental matchmakers!
Belovs, A., Jeffery, S., and Yolcu D., Taming Quantum Time Complexity. Quantum 8, 1444 (2024). https://doi.org/10.22331/q-2024-08-23-1444
