˰

Mapping the Hunt for Quantum Advantage

October 23, 2025

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 ˰ 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 “qܱ𲹲”: 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. ‾ܰپ” 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 ˰

˰, the world’s largest integrated quantum company, pioneers powerful quantum computers and advanced software solutions. ˰’s technology drives breakthroughs in materials discovery, cybersecurity, and next-gen quantum AI. With over 500 employees, including 370+ scientists and engineers, ˰ leads the quantum computing revolution across continents. 

Blog
|
technical
July 29, 2026
Scaling the Signal: What a Larger QFT Says About Quantum Progress
  • Mitsui & Co. and Mitsubishi Electric demonstrated one of the world’s largest approximate Quantum Fourier Transforms (QFT) on ˰ ˰, scaling from prior records to 98 physical qubits.
  • The collaboration also implemented a logical QFT using a QEC (Quantum Error Correction) code with up to 12 logical qubits.
  • The work highlights ˰’s accuracy and flexible architecture.

While there is ongoing debate around the pace of quantum computing’s development, a more grounded way to assess progress is through concrete demonstrations of foundational algorithms at meaningful scale. In this context, Mitsui & Co. and Mitsubishi Electric are taking a pragmatic view of quantum progress—focusing on how close the field is to executing core algorithmic primitives that underpin many potential industrial applications, rather than relying on abstract milestones or timelines.

, the industrial giants teamed up with ˰ to measure how close we are to running the Quantum Fourier Transform (QFT), a widely-used algorithmic primitive, at scales necessary for industrial applications. In the process, the team successfully ran one of the largest instances of the approximate QFT ever demonstrated. This achievement matters because the QFT is an essential primitive that underpins many of the quantum algorithms expected to deliver practical advantages.

You may have heard of the (classical) Fourier transform (FT), due to its ubiquity throughout modern computing. The FT is essential in everything from image analysis to data compression, with almost limitless applications in between. The quantum Fourier transform (QFT) is similar; it’s used in everything from chemistry to finance.

Because the QFT is a foundational primitive underpinning many quantum algorithms, demonstrating it at larger scales and higher fidelity is a practical way to measure quantum computing readiness. This is exactly the type of benchmarking that organizations should consider to understand where today’s systems are useful, and to see how fault-tolerant approaches are progressing. Ultimately, algorithm-level benchmarking like this is one of the most useful ways to understand not just where we are, but where we are going.

A Transformative Approach

Primitives like Fourier Transform are so widespread because they simplify problems by transforming them into something that is easier to deal with. At ˰, not only are they crucial for industrial applications but they can also simplify algorithms, making them possible to run now instead of later. This ‘transformational’ approach extends beyond the QFT - other transforms exist, and we have even invented our own quantum-native transforms.

Using our ˰ quantum computer and Guppy language, the joint team explored running the QFT on both physical qubits and on logical qubits, showing that fault tolerance is progressing quickly.  Running the QFT on 98 physical qubits; the paper shows a clear progression from previous results.

Then, using the Steane code, one of the best-studied quantum error correcting codes, the team used ˰’ 98 physical qubits to form 12 logical qubits, successfully running the QFT with the mechanisms of quantum error correction interwoven into the algorithm. This marks a crucial step forward for the field.

Foundational Progress

Taken together, these results provide a more concrete lens through which to view progress in quantum computing: not as abstract projections, but as measurable advances in the execution of foundational algorithms at increasing scale. By benchmarking the Quantum Fourier Transform on both physical and logical qubits, Mitsui & Co. and Mitsubishi Electric are helping to clarify what today’s hardware can already achieve, and where fault-tolerant approaches begin to extend those limits.

More broadly, the organizations best positioned to benefit from quantum computing will be those that focus on these foundational capabilities early, and use them to build a clear, evidence-based understanding of how the technology fits into their business goals.

technical
All
Blog
|
partnership
July 29, 2026
˰ and NVIDIA Validate Generative Quantum AI Framework for Pharmaceutical R&D

It is believed that unlocking answers to some of the most complex scientific and industrial problems will require the seamless integration of high-performance computing (HPC), generative AI (GenAI), and quantum computing. Toward this goal, ˰, NVIDIA, and a major pharmaceutical company have successfully demonstrated the first step in a proof-of-principle framework designed to connect these three distinct computing paradigms for industrially relevant computational chemistry.

This milestone, enabled by three industry leaders and experts in their respective domains, serves as a foundational capability that could support the development of future hybrid quantum-AI workflows to help optimize industrial research and development (R&D).

The potential value is a path toward more automated, repeatable, and scalable workflows for translating chemistry problems into executable quantum programs—capabilities that could eventually make hybrid computing easier to deploy in industrial R&D.

The GenQAI Framework

The framework, termed Generative Quantum AI (GenQAI), involved a quantum computer simulating a pharmaceutical compound using programming instructions generated by an AI model, which itself was trained on quantum data that was simulated using HPC.

While the vision for GenQAI explores how future industrial simulation workflows might be optimized by training AI models using quantum data derived directly from a quantum computer, the framework currently consists of four main technical steps:

  1. Simulating quantum data: The process began by simulating quantum data with NVIDIA accelerated computing using .
  2. Fine-tuning the AI: This simulated quantum data was used to fine-tune a pre-trained AI model from the open .
  3. Generating instructions: The AI model then generated quantum circuits, which are the programming instructions required for the quantum simulation.
  4. Validating accuracy: To validate the results, the circuits were run on ˰’s ˰ quantum computer using its InQuanto quantum chemistry platform.

The core novelty of this development lies within the process of the framework itself. In this proof-of-principle experiment, an AI model fine-tuned on simulated quantum data generated circuits that were successfully executed and validated on ˰’s ˰ system. Rather than delivering an immediate commercial advantage, this achievement establishes a credible, verifiable baseline for how HPC, AI, and quantum computing can function in tandem.

The Case Study

The validation of the framework represents an early step toward the goal of developing scalable architectures for the pharmaceutical industry.

With a shared view toward eventually scaling the framework for pharmaceutical R&D applications, the researchers simulated a pharmaceutical compound: imipramine. This anti-depressant was chosen because it serves as a model compound for drug degradation and shelf-life studies, which are standard components of the pharmaceutical R&D lifecycle.

Developing hybrid infrastructure that enterprises may adopt requires a deep, coordinated effort among domain experts. As such, this successful test highlights the value of combining the strengths of a quantum computing hardware and software leader (˰), with a hybrid-quantum classical platform (NVIDIA), and a leading enterprise end-user to build and test future computing capabilities for industrial chemistry.

Scaling the Framework

Although demonstrated on a pharmaceutical compound, the architecture could eventually inform similar molecular-simulation workflows in sectors such as energy, agriculture, advanced materials, and electronics. At this stage, it provides a reference for further testing and development.

Engage Further

here to explore the full technical details of this demonstration and contact our team to learn more about joining ˰’s enterprise partner network.

partnership
All
Blog
|
events
July 21, 2026
˰ SG Grand Challenge 2026

˰ is pleased to announce that applications are now open for the ˰ 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 ˰ 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 ˰ 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 ˰ 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.

events
All