Hardware-Optimal Quantum Algorithms

Quantum computing remains a research endeavor, explained the Physics Nobel Laureate Frank Wilczek earlier this year, contextualizing the widespread industry aspirations to enter markets. The highly error-prone quantum computations will likely require quantum error correction algorithms to make them practical. However, many such algorithms fail to account for hardware-specific error models. In this interview, ISTA PhD student Stefanie Muroya talks about her work enabling hardware-optimal quantum algorithms, now published in PNAS.

Quantum computing uses qubits instead of classical bits. Unlike classical bits, they are not only comprised of 0 or 1 but can exist in superposition due to quantum phenomena. Theoretically, this means that quantum computers can simultaneously explore many computational paths, rendering them far superior for solving specific problems compared to the most advanced classical supercomputers. Potentially. In practice, though, the fragility of quantum states makes quantum computations prone to errors. That´s where error correction comes in. However, quantum algorithms are typically designed independently of hardware and use simplified models. This often leads to suboptimal performance on real quantum hardware.

Together with ISTA professors Thomas Henzinger and Krishnendu Chatterjee, PhD student Stefanie Muroya has developed a method to integrate a given hardware specification into the automatic creation of an optimal algorithm. The approach leads to provable performance guarantees. While Muroya’s findings could help advance future quantum computers, the field still faces multiple challenges.

We often think of future quantum computers as super-powerful machines that could outperform classical computers. So, why does quantum computing rely on quantum error correction algorithms?

We need quantum error correction because of how sensitive quantum systems are to environmental disturbances. Fortunately, theory tells us that quantum error correction will enable fault-tolerant quantum computing if quantum algorithms achieve a sufficiently low error rate. Therefore, we must focus on developing better quantum hardware and synthesizing quantum algorithms that optimally exploit the hardware’s capabilities.

What types of errors are we talking about, and what role do the hardware specifications play?

If we consider that a qubit is a linear combination of the two classical states 0 and 1 with complex coefficients, typical examples of errors include bit flips and phase flips. Bit flips change the coefficients of the classical states 0 and 1, whereas phase flips change the sign of the coefficient of the classical state 1. In addition, a qubit can suddenly reset to the state 0, or we might have measurement errors that return a wrong value. Any of these errors can affect instructions sent to a quantum computer. Given an instruction, hardware specifications can tell us the probability of specific errors happening. Robust hardware will need a very low probability of error.

How “wrong” can quantum error correction algorithms be, and what strategy did you develop to calculate their accuracy?

In theory, quantum error correction algorithms are correct. In practice, however, they may not behave as expected. Existing error correction and mitigation strategies may make unrealistic assumptions, such as assuming that certain operations can be performed without error. They may also fail to fully account for models of the hardware-specific noise, which formalize the many factors that can affect the accuracy of the calculations. By considering published hardware specifications, we can synthesize optimal sub-procedures for specific hardware and provide a formal accuracy guarantee. This gives the algorithms that use these sub-procedures the potential to increase their effectiveness when executed on imperfect quantum hardware. Thus, our work bridges a gap between theoretical algorithm design and practical implementation.

How exactly does your method allow you to create an optimal algorithm for any given hardware specifications?

We use a stochastic mathematical model called Partially Observable Markov Decision Processes (POMDPs). In a Markov Decision Process model, an agent moves across states by repeatedly choosing an action and then probabilistically ending in another state. If the agent does not possess full information about the current state, this yields a POMDP, a partially observable Markov Decision Process. In our case, states consist of a quantum and a classical component, and our information is partial because we cannot directly observe the quantum component. We can choose an instruction—for instance, make a decision—by looking at the classical component. Then, the probability of ending in a different state is induced by the given hardware specification. Our method allows us to find a strategy that reaches a given target state with the highest possible probability. Such a strategy corresponds to a hardware-optimal quantum algorithm for a given hardware specification.

How did you test your approach? Can your method advance hardware development?

While many hardware-agnostic algorithms exist, our work shows that different hardware specifications have different optimal algorithms. We tested our method with hardware specifications from Qiskit, which apply to hardware from IBM. However, apart from existing quantum hardware, our work also applies to future hardware. Since it pinpoints the deficiencies of quantum hardware, yes, hardware developers can use it to tune their technology.

Beyond quantum hardware, does your work have any implications for topological quantum computation?

When developed, topological quantum computers are expected to be very robust. They are less prone to perturbations due to how they encode information. But, errors can still occur, and they may also benefit from our approach.

How do you envision the future of quantum computation?

In the future, I envision quantum computers being integrated with classical computers to solve problems cooperatively. Also, I am sure that as research continues, we will be able to find more applications in which quantum computers can outperform classical ones. However, I think an initial goal would be to build robust quantum computers that can effectively suppress errors through quantum error correction and mitigation. This will help quantum computing become practical. With my research, I hope to contribute toward achieving practical quantum computing and gain a deeper understanding of quantum algorithms and how hardware errors affect them.

Let’s suppose you now have a super-powerful and practical quantum computer, and you could press a button to answer a burning question. What would it be?

I would probably use it for a quantum simulation aiding drug discovery for some disease. Or a simulation that helps us understand the relationship between quantum mechanics and general relativity.

Publication:

Stefanie Muroya, Krishnendu Chatterjee, and Thomas A. Henzinger. 2025. Hardware-Optimal Quantum Algorithms. PNAS. DOI: 10.1073/pnas.2419273122