Mapping the Hunt for Quantum Advantage
By Konstantinos Meichanetzidis
When will quantum computers outperform classical ones?
This question has hovered over the field for decades, shaping billion-dollar investments and driving scientific debate.
The question has more meaning in context, as the answer depends on the problem at hand. We already have estimates of the quantum computing resources needed for Shor’s algorithm, which has a superpolynomial advantage for integer factoring over the best-known classical methods, threatening cryptographic protocols. Quantum simulation allows one to glean insights into exotic materials and chemical processes that classical machines struggle to capture, especially when strong correlations are present. But even within these examples, estimates change surprisingly often, carving years off expected timelines. And outside these famous cases, the map to quantum advantage is surprisingly hazy.
Researchers at Quantinuum have taken a fresh step toward drawing this map. In a new theoretical framework, Harry Buhrman, Niklas Galke, and Konstantinos Meichanetzidis introduce the concept of “queasy instances” (quantum easy) – problem instances that are comparatively easy for quantum computers but appear difficult for classical ones.
From Problem Classes to Problem Instances
Traditionally, computer scientists classify problems according to their worst-case difficulty. Consider the problem of Boolean satisfiability, or SAT, where one is given a set of variables (each can be assigned a 0 or a 1) and a set of constraints and must decide whether there exists a variable assignment that satisfies all the constraints. SAT is a canonical NP-complete problem, and so in the worst case, both classical and quantum algorithms are expected to perform badly, which means that the runtime scales exponentially with the number of variables. On the other hand, factoring is believed to be easier for quantum computers than for classical ones. But real-world computing doesn’t deal only in worst cases. Some instances of SAT are trivial; others are nightmares. The same is true for optimization problems in finance, chemistry, or logistics. What if quantum computers have an advantage not across all instances, but only for specific “pockets” of hard instances? This could be very valuable, but worst-case analysis is oblivious to this and declares that there is no quantum advantage.
To make that idea precise, the researchers turned to a tool from theoretical computer science: Kolmogorov complexity. This is a way of measuring how “regular” a string of bits is, based on the length of the shortest program that generates it. A simple string like 0000000000 can be described by a tiny program (“print ten zeros”), while the description of a program that generates a random string exhibiting no pattern is as long as the string itself. From there, the notion of instance complexity was developed: instead of asking “how hard is it to describe this string?”, we ask “how hard is it to solve this particular problem instance (represented by a string)?” For a given SAT formula, for example, its polynomial-time instance complexity is the size of the smallest program that runs in polynomial time and decides whether the formula is satisfiable. This smallest program must be consistently answering all other instances, and it is also allowed to declare “I don’t know”.
In their new work, the team extends this idea into the quantum realm by defining polynomial-time quantum instance complexity as the size of the shortest quantum program that solves a given instance and runs on polynomial time. This makes it possible to directly compare quantum and classical effort, in terms of program description length, on the very same problem instance. If the quantum description is significantly shorter than the classical one, that problem instance is one the researchers call “queasy”: quantum-easy and classically hard. These queasy instances are the precise places where quantum computers offer a provable advantage – and one that may be overlooked under a worst-case analysis.
Why “Queasy”?
The playful name captures the imbalance between classical and quantum effort. A queasy instance is one that makes classical algorithms struggle, i.e. their shortest descriptions of efficient programs that decide them are long and unwieldy, while a quantum computer can handle the same instance with a much simpler, faster, and shorter program. In other words, these instances make classical computers “queasy,” while quantum ones solve them efficiently and finding them quantum-easy. The key point of these definitions lies in demonstrating that they yield reasonable results for well-known optimisation problems.
By carefully analysing a mapping from the problem of integer factoring to SAT (which is possible because factoring is inside NP and SAT is NP-complete) the researchers prove that there exist infinitely many queasy SAT instances. SAT is one of the most central and well-studied problems in computer science that finds numerous applications in the real-world. The significant realisation that this theoretical framework highlights is that SAT is not expected to yield a blanket quantum advantage, but within it lie islands of queasiness – special cases where quantum algorithms decisively win.
Algorithmic Utility
Finding a queasy instance is exciting in itself, but there is more to this story. Surprisingly, within the new framework it is demonstrated that when a quantum algorithm solves a queasy instance, it does much more than solve that single case. Because the program that solves it is so compact, the same program can provably solve an exponentially large set of other instances, as well. Interestingly, the size of this set depends exponentially on the queasiness of the instance!
Think of it like discovering a special shortcut through a maze. Once you’ve found the trick, it doesn’t just solve that one path, but reveals a pattern that helps you solve many other similarly built mazes, too (even if not optimally). This property is called algorithmic utility, and it means that queasy instances are not isolated curiosities. Each one can open a doorway to a whole corridor with other doors, behind which quantum advantage might lie.
A North Star for the Field
Queasy instances are more than a mathematical curiosity; this is a new framework that provides a language for quantum advantage. Even though the quantities defined in the paper are theoretical, involving Turing machines and viewing programs as abstract bitstrings, they can be approximated in practice by taking an experimental and engineering approach. This work serves as a foundation for pursuing quantum advantage by targeting problem instances and proving that in principle this can be a fruitful endeavour.
The researchers see a parallel with the rise of machine learning. The idea of neural networks existed for decades along with small scale analogue and digital implementations, but only when GPUs enabled large-scale trial and error did they explode into practical use. Quantum computing, they suggest, is on the cusp of its own heuristic era. “Quristics” will be prominent in finding queasy instances, which have the right structure so that classical methods struggle but quantum algorithms can exploit, to eventually arrive at solutions to typical real-world problems. After all, quantum computing is well-suited for small-data big-compute problems, and our framework employs the concepts to quantify that; instance complexity captures both their size and the amount of compute required to solve them.
Most importantly, queasy instances shift the conversation. Instead of asking the broad question of when quantum computers will surpass classical ones, we can now rigorously ask where they do. The queasy framework provides a language and a compass for navigating the rugged and jagged computational landscape, pointing researchers, engineers, and industries toward quantum advantage.
About Quantinuum
Quantinuum, the world’s largest integrated quantum company, pioneers powerful quantum computers and advanced software solutions. Quantinuum’s technology drives breakthroughs in materials discovery, cybersecurity, and next-gen quantum AI. With over 500 employees, including 370+ scientists and engineers, Quantinuum leads the quantum computing revolution across continents.
Quantinuum is pleased to announce that applications are now open for the Quantinuum SG Grand Challenge 2026, a global innovation challenge designed to bring together researchers, developers, scientists and innovators to explore practical applications of quantum computing.
Organized by Quantinuum and supported by Singapore's National Quantum Office and Aqora, the three-month program aims to foster collaboration across academia, industry and the quantum developer community while supporting the continued growth of Singapore's quantum ecosystem.
A Platform for Quantum Computing Innovation
Participants will work in teams to develop solutions across a range of challenge areas, including chemistry and molecular simulation, optimization, AI for quantum systems, quantum error correction, condensed matter and materials science, and open innovation. Throughout the program, participants will have access to mentoring, technical enablement and Quantinuum quantum computing resources.
Singapore Grand Finale
Selected finalist teams will be invited to present their work at the Grand Finale hosted in Singapore before representatives from academia, and industry. The event will celebrate innovative applications of quantum computing while providing an opportunity for participants to engage with Singapore's growing quantum community.
Join the Challenge
The Quantinuum SG Grand Challenge welcomes participants from around the world. Whether you are an experienced quantum researcher or beginning your quantum computing journey, the program offers an opportunity to collaborate, learn and contribute to the development of practical quantum applications.
Applications are now open. Spaces are limited and subject to review and approval.
- Researchers from Quantinuum, Caltech, the University of Chicago, and Harvard created a rare topologically ordered state of matter on Quantinuum's System Model H2 and used it to perform protected universal quantum gates with non-Abelian anyons.
- The work explores an alternative approach to fault tolerance by using topological properties to protect quantum information. This could reduce the need for magic state distillation, which can (in some circumstances) be resource-intensive.
- Quantinuum continues to show leadership in fault tolerance, with successful demonstrations spanning world record error rates to exotic approaches like topological computing
Quantum computing is all about putting the exotic properties of physics to work. Qubits can exist in two states at once, like the famous cat that is both alive and dead. Qubits can also be entangled, where the state of one will instantaneously affect the state of another - even when they have no way to “talk” to each other. Qubits can even be teleported, moving a quantum state from one place to another without physically moving it through space.
These features give quantum computing its power. But the ‘spooky’ nature of quantum computing doesn’t stop there: our quantum computers are potent enough to make exotic states of matter out of our qubits, and to perform calculations that would warp the mind of more traditional thinkers.
A new approach
In a recent paper published in Nature, researchers at Quantinuum teamed up with Caltech, the University of Chicago, and Harvard to create a rare ‘topologically ordered’ state of matter from our qubits.
When the qubits become ‘topologically ordered’, they become more than individual particles, now ‘related’ to each other in a specific way. This is like how hydrogen and oxygen act as individual gas particles alone, but you can put them together in a certain way so that they become water, a liquid, and an entirely different creature.
When the qubits become topologically ordered, the quantum information that they carried individually gets spread out over the whole system, which acts as a sort of protection from noise. This is like how a net makes a stronger barrier than a bunch of un-knotted ropes.
Once the researchers had topologically ordered qubits, they used the exotic particles that resulted (called non-Abelian anyons) to compute, performing error-protected gates and measurements.
To perform gates, the researchers 'braided' the anyons, which is like changing the shape of the “net”. This is something like the children’s game ‘cats cradle’. Through a sequence of changes to the “net”, the quantum computer can perform full calculations, one day helping scientists to understand the secrets hidden in the world around us.
Why go to such trouble? Well, for the love of discovery of course - but the team had an additional, specific motivation. One of the biggest challenges in building practical quantum computers is protecting them from errors while still being able to perform every operation needed for computation (this is referred to as universality).
This work takes a fresh approach to this challenge. Unlike traditional quantum error correction, the special properties of topological matter enable a universal set of fault tolerant gates without relying on expensive magic state distillation.
Why this matters
Quantum error correction is essential for large-scale quantum computing. While it protects fragile quantum information from noise by turning delicate physical qubits into robust logical qubits, it also introduces a significant constraint: not every quantum gate can be performed directly on logical qubits.
For decades, the standard solution has been to supplement error-corrected operations with magic states. These specially prepared quantum resources enable universal computation but can come at a steep cost - in many estimates of future fault-tolerant quantum computers, magic state preparation dominates both the physical qubit count and the runtime of useful algorithms.
Reducing this overhead has therefore become an important goal in quantum computing. This new approach may significantly reduce the cost by enabling the ‘topological preparation’ of magic states, eliding expensive protocols like distillation. If universal computation can be performed without large-scale magic state distillation, quantum computers could require significantly fewer physical qubits and spend much less time generating computational resources before running useful algorithms.
We will never stop exploring
While there is still considerable work ahead to understand the practical implementation and scalability of these ideas, this result expands the landscape of what's possible in quantum fault tolerance.
Of course, this impressive demonstration describes just one approach we are taking to fault tolerance at scale. We will continue to push forward with topological computing alongside more traditional approaches to quantum error correction, as well as exploring everything we can imagine in between. We are looking at a number of ways to reduce the resource cost of magic states in particular, and are making strides in multiple dimensions. With machines that are both flexible and accurate enough to do it all, who can resist?
- Quantinuum continues its progress toward fault-tolerant quantum computing, with a series of peer-reviewed breakthroughs in fault-tolerant operations.
- Our progress is not only scientific; it is commercial. By improving logical-qubit reliability and encoding efficiency, Quantinuum is reducing the resource overhead required to scale its quantum computers toward commercially useful workloads.
- These results were achieved on commercial Quantinuum hardware, reinforcing that our architecture is not just setting new standards, but building a practical foundation for customers, partners, and researchers preparing for the fault-tolerant era.
Fault-tolerant quantum computing is the threshold the industry must cross before quantum computers can solve the hardest, highest-value problems with confidence. To be commercially useful at scale, the question is not simply who can build more qubits. It is who can build reliable, efficient, scalable systems that reduce technical risk and accelerate the path to commercial usefulness.
Quantinuum is progressing on that path.
Last year, in partnership with Microsoft, we published a breakthrough in logical computing, demonstrating logical qubits that outperformed their physical counterparts by a factor of 800. We are proud to announce that this work is now being published in Nature, one of the most highly regarded scientific journals in the world.
This work highlights our leading fidelities, as shown in Table 1:
Since then, we’ve accelerated our efforts to reach large-scale fault tolerance and advanced what we believe to be the core building blocks of fault-tolerant quantum computing, from logical-qubit teleportation and multiple error-correction breakthroughs to one of the first meaningful computations using logical qubits. Importantly, these results were achieved on commercial Quantinuum hardware, demonstrating not just scientific progress, but a practical and efficient path toward scalable, customer-ready fault tolerance.
A Recap of Our Recent Technical Progress
Since the work with Microsoft, we achieved a milestone years ahead of schedule, demonstrating high-fidelity teleportation of a logical qubit, which was published in Science, one of the world’s most prestigious journals. Later, we beat our own record in this crucial fault tolerance milestone, thanks to continued improvements to our System Model H2’s fidelity.
Then, a series of results demonstrating more error-correcting milestones (and codes):
- Better than physical results in a high-rate non-local code,
- First-ever demonstration of a single-shot error correcting code (which significantly reduces resource requirements) in 4 dimensions
- Extending qubit lifetimes by 10x with a concatenated code
- Observed fault-tolerance thresholds with concatenated codes
- High fidelity magic states and a fully fault tolerant universal gate set in two different papers
Recently, we topped ourselves yet again by performing one of the first meaningful computations with logical qubits – exploring key questions in materials and magnetism, using logical qubits with better error rates than their physical counterparts. This result also includes a leading “encoding rate” squeezing 48 logical qubits out of just 98 physical qubits, emphasizing how our architecture helps to support large scale fault tolerance without enormous resource costs.
It is worth noting that all these results were achieved on our commercial hardware, not on one-off laboratory test-stands – reflecting the performance that we are able to deliver to our customers.
We also did crucial theoretical work, exploring new options for error correction that can reduce resource requirements, time to solution, and shorten the timeline to large scale fault tolerance.
Commercial Implications and the Road Ahead
We believe the commercial implication is clear: Quantinuum is reducing the uncertainty around the path to fault-tolerant quantum computing. Our architecture, hardware fidelity, full-stack control, and error-correction progress are converging into a practical roadmap for systems that can support valuable scientific and commercial workloads.
For those evaluating when quantum computing will become strategically relevant, we believe the signal is also increasingly clear: the fault-tolerant era is no longer a distant concept. It is becoming an engineering reality, and Quantinuum is leading the way.