Building a useful quantum computer is not simply a matter of adding more qubits. The greater challenge is making these qubits reliable enough to perform long computations without errors overwhelming the result. Quantum error correction addresses this problem by encoding each logical qubit across many physical ones, but it comes at a cost: many of the operations required for a general-purpose or “universal” quantum computer become highly resource intensive once fault-tolerant error correction is introduced.

To address this resource challenge, researchers at the University of California, Davis, US have developed a classical simulation method that efficiently models the preparation of some of the most demanding quantum states. The method, which they describe in PRX Quantum, works even for large, high-fidelity protocols that were previously beyond reach.

Building a universal quantum computer

Logical operations in fault-tolerant (that is, error-corrected) quantum computing architectures fall into two broad categories. The first category is a set of operations known as Clifford gates that are relatively straightforward to implement and, importantly, can be simulated efficiently on a classical computer. By themselves, however, Clifford gates are not computationally universal. For that, you also need non-Clifford operations, which lie outside the set of classically-simulable gates and provide the missing ingredient for universal quantum computation.

To realize these non-Clifford operations in a fault-tolerant way, some qubits need to be in a special state known as a magic state. Preparing these magic states with sufficiently high fidelity is expected to dominate the cost of large-scale error-corrected quantum computers, so quantum computing theorists are searching intensively for more efficient preparation protocols. The problem is that this search contains a challenge of its own: how can we compare the efficiency of these approaches?

To assess a magic-state preparation protocol, we need to simulate it under realistic levels of error-inducing circuit-level noise. Yet the same non-Clifford operations that make magic states indispensable for quantum computation also make them difficult to simulate. Existing methods therefore become prohibitively expensive as protocols grow, limiting exact simulations to relatively small logical circuits.

Simplifying a difficult simulation

Rather than searching for a more efficient simulation algorithm directly, the UC Davis team of Samyak Surti, Lucas Daguerre and Isaac Kim first asked a more fundamental question: what mathematical structure do these protocols share?

Their framework for answering this question encompasses three broad classes of logical magic-state preparation protocols: code switching, magic state distillation, and Pauli-square-root Clifford (PSC) measurement-based protocols. In the first two classes, error propagation is relatively straightforward to analyse, but PSC protocols require a more sophisticated mathematical treatment. Rather than viewing these protocols simply as quantum circuits, Surti, Daguerre and Kim characterized their underlying algebraic structure, showing that Pauli errors (the fundamental types of qubit errors) propagate in a highly constrained and predictable way under sequential commutation. This commutation preserves the algebraic relationships between errors and logical operators, while anti-commuting operations exhibit predictable transformations rather than generating uncontrolled complexity.

These properties mean that commuting operations can be systematically reordered without changing the outcome, allowing much of the circuit’s complexity to be absorbed into its algebraic structure. Hence, rather than tracking an exponentially large quantum state, the simulator follows how a compact description of logical Pauli and Clifford errors evolves through the protocol.

The paper formalizes these ideas through a sequence of lemmas, propositions and theorems that establish the mathematical properties of PSC protocols. The result is a series of algorithms for simulating realistic, noisy, logical magic-state preparation protocols with a computational cost that scales polynomially with both the number of qubits and what is termed the stabilizer rank of the target magic state, which is a measure of its non-Clifford complexity. Since the standard single-qubit magic state has a stabilizer rank of only two, this complexity remains manageable even as the underlying error-correcting code grows, in marked contrast to state vector simulations that scale exponentially with qubit number. The team’s advance therefore makes large-scale logical simulations practical for the first time.

Accelerating fault-tolerant quantum computing

Although the new framework does not reduce the physical resources required to prepare logical magic states, it does change how those protocols can be analysed and designed. By exposing the algebraic structure underlying a broad class of logical magic-state preparation schemes, the UC Davis team transformed a computationally hard problem into one that admits efficient classical simulation. Researchers can therefore evaluate, compare and refine candidate preparation protocols under realistic circuit-level noise without resorting to exponentially expensive simulations or uncontrolled approximations.

Quantum error correction produces better ‘magic’ states

“The main motivation behind our work was to speed up the development of fault-tolerant quantum computer,” Kim tells Physics World. “I believe there is a large amount of uncertainty in how we will design and optimize magic state factories, which will likely remain as a bottleneck in the foreseeable future.”

As quantum computing progresses from proof-of-principle demonstrations to large-scale fault-tolerant architectures, the ability to characterize and benchmark logical operations efficiently will become increasingly important. This work offers more than just a faster simulator; instead, it provides a new theoretical foundation for designing one of the most resource-intensive building blocks of future quantum computers. “My hope is that this line of work can help us better design the fault-tolerant quantum computers we will be getting over the next few years,” Kim says.