ICRC is the premier venue for novel computing approaches, including algorithms and languages, system software, system and network architectures, new devices and circuits and applications of new materials and physics.

In the award-winning paper, titled ​“Optimized Quantum Program Execution Ordering to Mitigate Errors in Simulations of Quantum Systems,” the researchers present a novel strategy for simulating the time evolution of a physical system at a quantum mechanical level of detail. Such molecular simulations, called Hamiltonian simulations, are important in physics and chemistry applications such as designing better pharmaceuticals or fertilizers.

Hamiltonian simulation requires algorithms that implement the evolution of a quantum state efficiently – that is, using elementary operations, or gates, to perform a computation task. But the memory requirements of general Hamiltonians grow exponentially with respect to system size, making the problem infeasible on classical computers.

The problem has long attracted attention. Almost four decades ago, Richard Feynman suggested a quantum computer as a possible solution; and since then numerous strategies have been proposed for compiling quantum programs, also known as quantum circuits, for Hamiltonian simulations.

“Most of the proposals, however, have focused on maximizing either the accuracy or the gate cancellation,” said Teague Tomesh, a Ph.D. candidate at Princeton University and lead author of the paper presented at ICRC21. ​“Our work instead focuses on both.”

To maximize accuracy, the researchers group together mutually commuting terms in the Hamiltonian matrix characterizing the quantum mechanical system. For terms that do not commute, the researchers employed a truncation technique known as Trotterization, which breaks the continuous time evolution into many small time steps. The terms then can be directly implemented as a quantum circuit.

“This approach helps reduce algorithmic errors, but we also lose something” said Martin Suchara, a computational scientist in Argonne’s Mathematics and Computer Science Division. ​“In particular, the depth of the final quantum circuit increases, which means more physical errors, as well as greater runtime.”

Reducing errors in quantum computing is extremely important. Current quantum computers are prone to errors; indeed, they are often referred to as noisy intermediate-scale quantum, or NISQ, systems. To address this issue, the researchers introduced a new strategy for Hamiltonian simulation, called max-commute-tsp. The strategy involves choosing a term ordering to produce quantum circuits with fewer gates. For this, they used as a model the well-known traveling salesperson problem, which finds the shortest possible path that visits all terms.

“We view this work as an application-compiler codesign strategy. That is, we use our application-level knowledge to guide program order at the compiler level, before the application is compiled down into a quantum circuit,” Suchara said. ​“This enables us to select terms that simultaneously mitigate both physical and algorithmic errors and thus improve the overall performance of Hamiltonian simulations on quantum computers.”

To test their strategy, the team performed noiseless and noisy simulations as well as experiments on trapped ion quantum computers. For the noiseless tests, the new max-commute-tsp technique was compared with popular lexicographic and magnitude ordering strategies. In all cases max-commute-tsp produced accurate Hamiltonian circuits using fewer entangling gates. Lexicographic ordering cancels many gates, mitigating physical errors, but it has poor accuracy at small time values. The magnitude ordering approach can produce highly accurate Hamiltonian simulation circuits, but the new strategy was able to cancel 39% more gates (see Fig. 1). For the noisy simulations and hardware executions, the researchers compared ideal output vs. noisy output. Again the max-commute-tsp strategy produced circuits with better accuracy than that of the other two orderings. The experiments demonstrated the importance of both gate cancellation and simulation accuracy for overall performance.

The researchers would next like to explore other regimes besides molecular systems. Of particular interest are combinatorial problems involving the widely used quantum approximation optimization algorithm, or QAOA.

“We expect that our strategy will significantly outperform the less flexible magnitude and lexicographic approaches, reducing Trotter errors while keeping the circuits short,” Suchara said. ​“Success with QAOA would significantly expand the realm of tractable problems in quantum computing.”

Information about the paper:

In addition to Tomesh and Suchara, the full team of researchers includes Kaiwen Gui, a Ph.D. student advised by Suchara; Pranav Gokhale, the Chain Reaction Innovations program winner at Argonne and founder of the quantum computing startup Super.tech; Yunong Shi, a graduate student at the University of Chicago and former W.J. Cody Fellow at Argonne in summer 2017; Margaret Martonosi, Hugh Trumbull Adams ​’35 Professor of Computer Science at Princeton; and Frederic T. Chong, a joint appointee with Argonne.

The award-winning paper will appear in the Proceedings of the IEEE International Conference on Rebooting Computing (ICRC 2021).