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.
Progressing your organization along the five levels of quantum maturity
Quantum computing has moved from a bet on the future to a race already underway. Early adopters are locking in strategic partnerships, building proprietary IP, and positioning themselves years ahead of competitors who are still watching from the sidelines. For executives, the question isn't whether to engage with quantum computing. It's how far along that journey your organization actually is, and what it takes to move forward.
That's a harder question to answer than it sounds. Quantum maturity isn't a single milestone you either hit or miss. It's a progression, built across talent, technology access, workflow integration, partnerships, and value realization, and most organizations aren't entirely sure where they currently stand and what to do next.
Our new paper, A Roadmap for Quantum Maturity, is built to answer exactly that.
A Framework for Where You Stand, and Where to Go Next
Drawing on extensive client experience, the paper lays out five distinct levels of quantum maturity, from early awareness through full transformation, along with the leadership actions that move an organization from one level to the next.
- Awareness — early conversations, but no clear ownership or use cases yet
- Exploration — exploring partnerships and prioritizing use cases with limited budget
- Experimentation — quantum roadmap established and guiding dedicated teams, funding, and partners to execute pilot use case projects
- Integration — quantum computing applications are being embedded into business unit workflows, and the quantum roadmap is integrated with broader digital technology strategy, including AI, HPC, and data
- Transformation — quantum capabilities are embedded in core products and decision-making, with differentiated, proprietary advantage
Most industry leaders today sit at the exploration or experimentation stages, with clear ambitions to reach transformation within the next several years. The paper breaks down what separates organizations that progress from those that stall out at proof-of-concept.
The Advantage Is Built, Not Bought
One of the paper's central takeaways is one many executives underestimate: investing in quantum technology alone isn't enough. Organizations that advance fastest pair that investment with a deliberate strategy, building quantum literacy across leadership and technical teams, honestly assessing capability gaps, focusing on a small number of high-impact use cases tied to real business metrics, and defining a clear roadmap that connects research to business advantage.
How Quantinuum Can Help
Achieving quantum maturity is a journey, not a single step, and most organizations don't need to make that journey alone. Quantinuum's consulting services are built to support every stage of it, from advisory and use-case identification, to capability building, technology access, and the co-development of scalable quantum solutions.
Whether your organization is just starting to build awareness or already scaling toward transformation, our team can help you identify exactly where you stand today, and what it takes to move to the next level.
- SoftBank Corp. and Quantinuum articulated a roadmap connecting quantum algorithms, hardware evolution, and commercial applications, helping organizations understand when quantum computing can address real-world challenges.
- The analysis demonstrates that quantum value will emerge in stages, with early opportunities in data analysis and longer-term breakthroughs in scientific computing as fault-tolerant systems mature.
- The work provides a practical planning framework for enterprises preparing to integrate quantum computing alongside AI and classical high-performance computing infrastructure in quantum-AI data centers.
Quantum computing is increasingly moving from exploratory discussion to structured enterprise planning. As organizations begin to assess where and when quantum technologies may deliver real business impact, a new class of work is emerging: integrated roadmaps that connect algorithmic feasibility, hardware development, and commercial opportunity.
A recent white paper from SoftBank Corp. and Quantinuum represents one of the most comprehensive examples of this approach to date. Rather than treating quantum computing as a distant, abstract capability, the study constructs a detailed, quantitative framework for understanding how real-world use cases evolve as hardware matures—and what this means for enterprise strategy.
A Comprehensive Roadmap
The SoftBank–Quantinuum white paper is broad in scope. It attempts to answer a fundamental question:
Which real-world problems can benefit from quantum computation, at what scale, with what accuracy requirements, and under what hardware conditions?
To address this, the study adopts a structured methodology that connects:
- Algorithmic resource estimates (logical qubits, circuit depth, gate counts)
- Explicit error correction assumptions and overhead models
- Hardware roadmaps across multiple generations
- Timelines for when specific classes of problems may become feasible
Two representative domains anchor the analysis:
- Quantum chemistry, particularly excited-state dynamics and photochemical processes
- Topological data analysis (TDA), including graph-based structure and anomaly detection
These domains were selected because they combine industrial relevance with computational structures that scale poorly on classical systems but map naturally onto quantum approaches.
Quantum chemistry is closely tied to materials science, energy systems, and the development of sustainable technologies. TDA, by contrast, offers tools for understanding complex data structures in networks, finance, and large-scale systems—where identifying structure and anomalies is increasingly critical.
Together, they illustrate how quantum computing may create value across both deep scientific domains and high-impact data applications.
An important caveat is that the resulting roadmap assumes a widely-studied but inefficient error correcting code. As more error correcting codes come online, the resources required to run algorithms will shrink. That means that the timelines detailed in this work can be thought of as “worst case” scenarios, which adds to the value by setting out a clear limit.
A distinguishing feature of the work is its emphasis on implementation over abstraction. Rather than relying solely on theoretical models, the study explicitly constructs quantum circuits and executes them on Quantinuum’s Helios and H2 system.
Parallel Paths to Value
A notable insight from the study is that quantum value creation will not follow a single linear path.
Instead, two complementary regimes are expected to emerge:
- In quantum chemistry, the focus is on fault-tolerant, logical-qubit-based computation, where error correction is essential for scaling toward meaningful scientific and industrial outcomes.
- In TDA, value can emerge earlier, where partial quantum advantage may already support useful computational tasks without full error correction.
This dual-track structure is important: it shows that quantum computing is not a single “threshold technology,” but a spectrum of capabilities that unlock value at different stages of maturity.
The Vision for Quantum Industrialization
The framework ultimately supports a broader strategic vision: the evolution of Quantum AI Data Centers—hybrid infrastructures where quantum processors operate alongside AI and classical HPC systems.
For enterprises, the implication is clear: quantum computing readiness is no longer about speculation. It is about structured preparation, disciplined modeling, and early engagement with the full stack of capabilities that will define the next generation of computational infrastructure.
Every year, The IEEE International Conference on Quantum Computing and Engineering – or IEEE Quantum Week – brings together engineers, scientists, researchers, students, and others to learn about advancements in quantum computing. This year’s conference, from September 13th - 18th in Toronto, Canada, will focus on translating research into real-world impact through the convergence of generative AI, distributed quantum systems, and quantum software engineering.
Throughout IEEE Quantum Week, our quantum experts will be on-site to share insights on upgrades to our hardware, enhancements to our software stack, our path to error correction, and more.
Meet our team at Booth #501 and join the below sessions to discover how Quantinuum is forging the path to fault-tolerant quantum computing with our integrated full-stack.
Keynote with Quantinuum's CEO, Dr. Rajeeb Hazra
September 14th
5:00 – 6:30pm | 800 Hall G
Quantum computing has passed the point where error correction is theoretical. What comes next depends on systems that hold logical performance steady and do real work at scale. On September 14th, join Quantinuum’s CEO Dr. Rajeeb Hazra for his keynote session on “Logically Speaking: The Next Era of Error Correction” where he will explore what the next era of quantum computing requires: shared definitions of logical performance, and benchmarks built on real workloads.
Speaking Sessions
September 13th
11:00 – 11:12am | Location: 601A/B
Workshop: QGenAI: Synergies between Quantum Computing and Generative Artificial Intelligence
Finding Compatible Datasets for Quantum Generative Modeling
Presenting Author: Chen-Yu Liu
September 14th
1:00 – 1:20pm | Location: 701B
Workshop: Q3-Control: Integrated Systems for Quantum Computing, Sensing, and Networking
Cryo-ASICs for Scalable Control
Speaker: Dr. Patty Lee
September 15th
2:30 – 3:30pm | Exhibit Hall (informal event)
Workshop: Q3-Control: Integrated Systems for Quantum Computing, Sensing, and Networking
The Quantum Spectrum
Speaker: Dr. Patty Lee
3:00 – 4:30pm | Location: 801A
Where Quantum-HPC Integration Actually Stands in 2026
Panelist: Neal Erickson
3:00 – 4:30pm | Location: 718A
From Research to Commercialization: Defining the Quantum Workforce for the Next Five Years
Panelist: Kortny Rolston-Duce
September 16th
10:00 – 11:30am | Location: 801B
Who Will Turn Quantum Computing into Value? Specialists, Domain Experts, and the Workforce Gap
Panelist: Enrico Rinaldi
September 17th
10:00 – 11:30am | Location: 701B
International Workshop on Quantum Computing for Power Systems: From Optimization Algorithms to Grid-Scale Applications | Session 1
Organizer: Kortny Rolston-Duce
10:00 – 11:30am | Location: 714A
openQSE: Co-Designing the Quantum-HPC Software Stack from Applications to Control Systems | Session 1
Speaker: Neal Erickson
10:00 – 11:30am
The Impact of Qubit Connectivity on Quantum Advantage in Noisy IQP Circuits
Presenting Author: Leonardo Placidi
10:15 – 11:00 am | Location: 601A/B
Workshop: AI for Circuit Synthesis, Optimization, and Discovery
Automated near-term quantum algorithm discovery
Speaker: Konstantinos Meichanetzidis
11:00 – 11:15am | Location: 601A/B
Workshop: AI for Circuit Synthesis, Optimization, and Discovery
Fast Stabilizer State Preparation via AI-Optimized Graph Decimation
Presenting Author: Jasmine Brewer
1:00 – 1:15pm | Location: 601A/B
Workshop: AI for Circuit Synthesis, Optimization, and Discovery
Reinforcement Learning for Adaptive Composition of Quantum Circuit Optimisation Passes
Speaker: Gabriel Matos
1:00 – 1:20am | 718B
Quantum Software 2.6: current challenges and headways in quantum software | Session 1
Quantum compilation and hybrid compilation
Speaker: Ross Duncan
1:00 – 2:30pm | Location: 714A
openQSE: Co-Designing the Quantum-HPC Software Stack from Applications to Control Systems | Session 2
Speaker: Phillipp Seitz
1:45 – 2:00pm | Location: 601A/B
Workshop: AI for Circuit Synthesis, Optimization, and Discovery
Graph-Theoretic Quantum Circuit Optimization with the ZX-Calculus and Gumbel AlphaZero
Speaker: Alexander Koziell-Pipe
2:00 – 2:15pm | Location: 601A/B
Workshop: AI for Circuit Synthesis, Optimization, and Discovery
Reusable Equivariant Neural Compilers for Matrix-Group Quantum Circuit Synthesis
Speaker: Richie Yeung
3:30 - 4:00pm | Location: 715B
Workshop: 4th Workshop on Quantum Computing for Natural Sciences: Technology and Applications
Quantum Algorithms
Speaker: Setso Metodi
September 18th
10:00 – 11:30am | Location: 801B
Scalable QPU architectures
Panelist: Setso Metodi