PaperlayerView exact revision on arXiv

Source-linked AI summary

The Grand Challenge of Quantum Applications

Ryan Babbush, Robbie King, Sergio Boixo, William Huggins, Tanuj Khattar, Guang Hao Low, Jarrod R. McClean, Thomas O'Brien, Nicholas C. Rubin

arXiv:2511.09124v3quant-ph

TL;DR

Clear evidence of future application value is central to sustaining investment in quantum computing. This perspective maps the research pathway in five stages and identifies finding advantaged problem instances and connecting them to real-world uses as major hurdles.

  • Problem

    Sustaining investment in large-scale, error-corrected quantum computing depends on clear evidence of future value through concrete applications.

    Source: INTRODUCTION · p. 1

  • Method

    The perspective organizes research toward practical quantum applications into a five-stage framework, spanning theoretical advantage through compilation and resource estimation.

    Source: INTRODUCTION · p. 1, STAGE IV RESEARCH · p. 12, Compilation for early fault-tolerance · p. 15

  • Results

    Identifying concrete problem instances with quantum advantage and matching them to real-world applications are the most significant hurdles to expanding quantum applications.

    Source: OUTLOOK · p. 16

  • Takeaways & Limitations

    Resource estimation is premature before an advantage is established, and interesting estimates should be based on instances with quantum advantage.

    Source: STAGE IV RESEARCH · p. 12

    Stage V remains prospective: no quantum application has been implemented in hardware with conclusive advantage on a problem of real-world consequence.

    Source: THE FIVE STAGES OF QUANTUM… · p. 4

Abstract

from arXiv · show

This perspective outlines promising pathways and critical obstacles on the road to developing useful quantum computing applications, drawing on insights from the Google Quantum AI team. We propose a five-stage framework for this process, spanning from theoretical explorations of quantum advantage to the practicalities of compilation and resource estimation. For each stage, we discuss key trends, milestones, and inherent scientific and sociological impediments. We argue that two central stages -- identifying concrete problem instances expected to exhibit quantum advantage, and connecting such problems to real-world use cases -- represent essential and currently under-resourced challenges. Throughout, we touch upon related topics, including the promise of generative artificial intelligence for aspects of this research, criteria for compelling demonstrations of quantum advantage, and the future of compilation as we enter the era of early fault-tolerant quantum computing.

INTRODUCTION

The perspective frames practical quantum applications as a five-stage path from abstract algorithm discovery to deployment, while emphasizing verification and application relevance. It argues that verifiability is necessary, though insufficient, for useful quantum algorithms.

INTRODUCTION

  • Clear evidence of future value through concrete applications is important to sustaining investment in large-scale, error-corrected quantum computing.Source: INTRODUCTION · p. 1
  • The five stages run from abstract algorithm discovery through identifying advantageous instances, establishing real-world advantage, optimizing and estimating resources, and deployment.Source: INTRODUCTION · p. 1
  • The perspective focuses on computational speedups, particularly for fault-tolerant computers, rather than quantum advantage in sensing, metrology, or communication.Source: INTRODUCTION · p. 1

Focus on verifiability

  • Verifiability is necessary but insufficient for utility; useful quantum simulation output should at least be checkable by another quantum computer.Source: Focus on verifiability · pp. 1–2
  • Efficient classical verification is the highest standard, while cross-checks between quantum devices or against nature can provide experimentally testable predictions.Source: Focus on verifiability · p. 2

Focus on finding hard instances and ensembles

The perspective distinguishes abstract quantum speedups from useful applications, highlighting the need for hard, verifiable instances and paths from those instances to real-world problems. It favors beginning with a known quantum primitive and searching for problems matching its structure.

Focus on finding hard instances and ensembles

Focus on connecting to real-world applications

Focus on architecture in early fault-tolerance

Early fault-tolerant compilation requires resource-aware optimization rather than simple rules of thumb. The perspective argues that algorithmists can contribute through cost models and potential co-design of error-correction architecture.

Focus on architecture in early fault-tolerance

THE FIVE STAGES OF QUANTUM APPLICATIONS RESEARCH

The framework categorizes quantum application research from foundational theory through deployment, while recognizing that progression can skip stages or address several at once. It distinguishes abstract algorithms from identifying advantageous instances, connecting them to real-world problems, and estimating their practical costs.

Stage 0

  • Stage 0 develops foundational limits and complexity results that guide the search for speedups, but the perspective excludes it because it is not application development per se.Examples include classical simulation algorithms, query lower bounds, and no-go theorems; this research is typically abstract and primarily academic.Source: THE FIVE STAGES OF QUANTUM… · p. 3

Stage I

  • Stage I discovers and analyzes quantum algorithms or computational primitives, often using worst-case asymptotic complexity or simplified models such as query complexity.Examples include Grover’s and Simon’s algorithms, quantum phase estimation, and broad frameworks such as quantum adiabatic algorithms and quantum signal processing.Source: THE FIVE STAGES OF QUANTUM… · p. 3

Stage II

  • Stage II requires efficiently generating concrete instances expected to outperform the best-known classical algorithms, rather than relying only on worst-case speedups.An average-case super-quadratic speedup across an efficiently constructible ensemble is one example; results must also address input-dependent signals and competing classical algorithms.Source: THE FIVE STAGES OF QUANTUM… · p. 3

Stage III

  • Stage III connects an abstract advantage to a real-world problem where speedup is expected after accounting for practical constraints and overheads.Shor’s algorithm had an immediate application in breaking widely used cryptosystems; quantum simulation has also produced case studies, while other high-value links remain a major goal.Source: THE FIVE STAGES OF QUANTUM… · pp. 3–4

Stage IV

  • Stage IV shifts from asymptotic speedups to optimizing compilation and estimating finite resource costs for a specific use case.This includes estimating qubit and gate counts and developing compilers and software tools to streamline resource estimates.Source: THE FIVE STAGES OF QUANTUM… · p. 4

Stage V

  • Stage V is deployment into a practical workflow, but remains prospective because no hardware implementation has shown conclusive advantage on a consequential real-world problem.Certified random number generation is described as the closest current example, though its impact remains limited.Source: THE FIVE STAGES OF QUANTUM… · p. 4

STAGE I RESEARCH

Stage I research has produced active work on new algorithms, but foundational areas remain unevenly staffed. The perspective connects discovery to prior ideas and argues that incentives should support original, high-risk exploration.

Progress

  • Stage I has seen significant progress in quantum machine learning, Gibbs state preparation, and quantum algorithms for differential equations.Table I is described as a representative, non-comprehensive list of Stage I results with super-quadratic speedups.Source: STAGE I RESEARCH · p. 4, Table I · p. 5

Foundational research

  • Despite field growth, a smaller share of researchers appears to work on some foundational topics, including algebraic-structure algorithms such as the Hidden Subgroup Problem.The passage warns that post-quantum cryptography depends on a robust community effort to find quantum attacks, while only a small fraction of researchers with dual expertise are active in this area.Source: STAGE I RESEARCH · pp. 4–5

Research incentives

  • Structural incentives in academia and industry may encourage risk aversion, so evaluation and funding mechanisms should reward originality, problem-finding, and careful exploration.The perspective notes that a short paper with a genuinely new idea can redirect years of effort.Source: STAGE I RESEARCH · p. 5

Sources of discovery

  • Stage I discoveries often generalize or adapt mechanisms from earlier work, with prior algorithms and subroutines serving as inspiration for later results.Examples include Shor’s algorithm following Simon’s period-finding work and later Google work extending prior tensor PCA and differential-equation algorithms.Source: STAGE I RESEARCH · p. 5

Verifiability or reproducibility as necessary

The section proposes verifiability or quantum verifiability as a necessary, but not sufficient, filter for useful quantum computations. It contrasts sampling tasks with outputs whose quality can be checked, reproduced, or assessed through real-world feedback.

Verifiability

  • An output is verifiable when a classical or quantum computer can efficiently check its correctness without quantum communication.For tasks relevant to the classical world, measurable real-world performance can provide informal verification of a solution.Source: conditions for utility · p. 5

Quantum verifiability

  • An output is quantumly verifiable when a trusted quantum computer can verify it, including by reproducing the final answer on another device.For quantum simulations, the relevant answer is the final prediction, such as an expectation-value estimate, rather than the samples used to obtain it.Source: conditions for utility · pp. 5–6

Sampling tasks

  • Random circuit sampling is presented as failing the utility conditions because its outputs are believed to be neither efficiently verifiable nor reproducible, and lack efficiently discernible features.Sampling can still be useful when samples support meaningful information or features; the section contrasts that with random-circuit samples.Source: conditions for utility · p. 6

Demonstrations

  • Recent expectation-value demonstrations are described as progress toward useful quantum computing compared with sampling demonstrations, though they are not yet solving practical problems.The passage notes that some recent claims were challenged or simulated classically.Source: conditions for utility · p. 6

Scope

  • The proposed verifiability conditions are guiding principles rather than absolute criteria, and some computations may remain useful despite inefficient verification.Certified random number generation is given as an example outside the computational model considered in the work.Source: conditions for utility · p. 6

STAGE II RESEARCH

Stage II asks researchers to move beyond abstract or worst-case speedups by identifying concrete problem instances expected to exhibit verifiable quantum advantage. The perspective describes why this bridge is difficult and argues that it merits greater attention as both a route toward applications and a fundamental question about quantum physics.

Stage II criteria

  • Stage II requires concrete, efficiently generable instances with verifiable quantum advantage, such as an ensemble with super-quadratic speedup and probability of advantage vanishing at most polynomially.The authors cite Shor’s algorithm [34], DQI applied to optimal polynomial intersection, tensor PCA, and Pell’s equation [77] as examples.Source: STAGE II RESEARCH · p. 6
  • BQP-completeness and worst-case speedups do not by themselves specify classically hard input distributions, while natural ensembles may be classically easy on average.The authors distinguish abstract results such as Simon’s algorithm [20] and early QAOA [23] from later numerical QAOA studies that identified advantage for particular problem classes.Source: STAGE II RESEARCH · pp. 6–7

Instance classes

  • Stage II problems divide into finite collections of useful instances that may be learned from quantum-generated data and exponential ensembles whose solutions reveal little about other instances.The latter structure may make the advantage more durable against classical machine-learning generalization; Table II lists known examples of this type.Source: STAGE II RESEARCH · p. 7, Table II · p. 7

Scientific challenges

  • Highly entangled states can resist classical simulation yet scramble or thermalize, concentrating observables around predictable averages and letting trivial classical methods compete.A central challenge is finding problem classes with observable, non-classically-predictable corrections to this universal behavior.Source: STAGE II RESEARCH · p. 8
  • Classical competitors are improving practical heuristics, creating an asymmetry between theoretical or limited-simulation estimates of quantum performance and best-observed classical performance.The authors suggest scaled-up quantum hardware could help test heuristic performance and questions such as expectation-value concentration.Source: STAGE II RESEARCH · p. 8

Why Stage II matters

  • Even abstract or contrived instances can provide hard test cases for hardware and algorithmic milestones, while probing the boundary of complexity in quantum physics.The search may also inform many-body physics, but heuristic indicators such as disorder or proximity to phase transitions still require validation as sources of hard instances.Source: STAGE II RESEARCH · pp. 6, 8

STAGE III RESEARCH

Stage III seeks real-world problems where quantum advantage survives practical constraints, but such applications remain scarce outside cryptanalysis and quantum simulation. The perspective identifies both technical and sociological barriers and proposes an algorithm-first approach to connecting known speedups with domain problems.

The Stage III challenge

  • Outside cryptanalysis and quantum simulation, finding a real-world problem where theoretical speedup survives practical constraints remains a major bottleneck.The authors describe the scarcity of demonstrated use cases as an independent challenge, not merely a consequence of too few earlier-stage algorithms.Source: STAGE III RESEARCH · p. 9

Technical barriers

  • Promising algorithms often require restrictive conditions, and their mathematical structure can be difficult to find in real-world settings.For linear systems, HHL requires efficient preparation of b, sparse A, and polylog(N) condition number, while sampling x entries only in proportion to their magnitude.Source: STAGE III RESEARCH · p. 9

Sociological barriers

  • Application search also faces a knowledge gap between quantum algorithmists and domain specialists, since identifying matches requires breadth across disciplines.The authors contrast quantum simulation, where researchers often bring physics or chemistry expertise, with fields such as epidemiology and genomics.Source: STAGE III RESEARCH · p. 9

Application search

  • The authors favor an algorithm-first search: start from a known quantum primitive and look for real-world problems with matching structure, rather than starting from a customer’s hardest problem.Their planned compendium presents algorithms’ abstract problems and regimes of advantage in accessible terms so domain experts can identify possible matches.Source: STAGE III RESEARCH · p. 9
  • Generative AI may help Stage III by recognizing structural matches across fields, although the authors distinguish this from the creative leaps they associate with Stage I discovery.They report early success with an internal tool based on Gemini.Source: STAGE III RESEARCH · pp. 9–10

Connecting stages

  • The route through the stages need not be linear: established classical research on an important application can help identify where instances are difficult and inform Stage II criteria.The authors also invoke historical cases in which mathematical ideas gained practical uses only later, as grounds for optimism about theory-to-application bridges.Source: STAGE III RESEARCH · p. 10

Quantum simulation applications

Quantum simulation is a mature area for Stage III because problems map naturally to quantum computers, but real-world impact still depends on classical competition, scientific relevance, and practical bottlenecks. The perspective contrasts chemistry’s quantitative targets with solid-state opportunities and argues for instance-focused assessment alongside collaboration with domain experts.

Quantum simulation challenges

  • Quantum simulation’s natural problem-to-computer mapping makes it a mature Stage III area, but classical methods already model many weakly correlated systems and simulations must answer important physical questions.A speedup that misses the key bottleneck in a larger process may be useful without being transformative; drug discovery, for example, depends heavily on efficacy and toxicity assessment.Source: Quantum simulation applications · p. 10

Scientific value

  • Simulation can identify classically intractable calculations more easily than it can predict what new knowledge those calculations will yield, as illustrated by FeMoco.FeMoco is an enzyme involved in biological nitrogen fixation, but the industrial value of studying it is uncertain until simulations reveal what can be learned.Source: Quantum simulation applications · p. 10

Application domains

  • Quantum chemistry targets quantitative predictions for engineering, whereas condensed-matter models more often seek qualitative features such as phases of matter.A chemist may ask whether doping increases conductivity by 1% or 3%; a condensed-matter physicist may ask what doping improves conductivity or whether a material conducts.Source: Quantum simulation applications · p. 10
  • Solid-state applications may be more abundant because industrial targets often depend directly on electronic structure and longer correlation lengths can make systems classically difficult.The same complexity that challenges classical simulation also raises quantum resource demands.Source: Quantum simulation applications · pp. 10–11

Assessing practical value

  • The authors argue that practical chemistry should be judged on finite, high-interest instances rather than asymptotic scaling alone, while acknowledging that exponential speedup remains debated.For FeMoco, they report that no classical method has achieved the accuracy needed for definitive chemical insight despite intense effort, while high-overlap ground-state preparation is efficient.Source: Quantum simulation applications · p. 11

Application discovery

  • Domain-expert collaborations have produced Stage III case studies in drug discovery, battery development, and fusion-reactor simulation.The authors cite partnerships with Boehringer-Ingelheim, BASF, and Sandia National Laboratories.Source: Quantum simulation applications · p. 11

Future directions

  • Quantum computers may eventually support non-equilibrium simulation and applications such as driven superconductors or engineered chemical reactions, but this remains a speculative long-term vision.The authors call for collaboration with domain experts to identify concrete, impactful problems in this less-explored territory.Source: Quantum simulation applications · p. 11

STAGE IV RESEARCH

Stage IV refines algorithms, compiles them through logical and error-correction layers, and estimates or determines their physical resource needs. Resource estimates have improved for mature applications, but compilation remains demanding and must reflect realistic architecture and cost models.

Compilation stack

  • The compilation stack progresses from algorithmic refinement to logical gates, architecture-specific QEC primitives, and automated physical instructions.The QEC layer supports physical qubit and runtime estimates using code distances and cycle times; final physical instructions yield resource counts subject to decoding-feedback uncertainty.Source: STAGE IV RESEARCH · pp. 11–12

Resource progress

  • Stage IV research has reduced estimated resources by many orders of magnitude over the last decade for RSA-2048 space costs and FeMoco ground-state Toffoli-count time costs.The FeMoco estimates cover “small” 54-orbital and “large” 76-orbital active spaces.Source: Figure 2 · p. 12, STAGE IV RESEARCH · p. 12

Cost models

  • Resource estimates should use increasingly specific cost models, since all-to-all logical compilation and generic routing can produce loose upper bounds.Mindfulness of connectivity constraints and selection of non-Clifford resources can improve estimates; the relative cost of T and Clifford gates has also been questioned.Source: STAGE IV RESEARCH · p. 12

Physical implementation

  • Final physical estimates depend on the error-correction architecture, modularity overhead, and hardware-specific error-model simulations.The compilation process ultimately uses high-level parameters such as code distances and cycle times before automatic tools generate machine instructions.Source: STAGE IV RESEARCH · p. 12

Practical limitations

  • Manual work on Stages IV(b) and IV(c) is tedious and difficult to verify, and estimates often stop at IV(b) because optimized physical compilation is time-consuming and architecture-dependent.The authors cite more than a year of work on an 80-page paper to determine constant factors for an algorithm described asymptotically in a preceding 7-page paper.Source: STAGE IV RESEARCH · pp. 12–13

Tools and automation

  • Automated compilation and architecture-aware resource tools could support precise counts, comparisons among implementations, bottleneck identification, empirical optimization, and verification.The authors list Qualtran [45], Q# [46], QREF, Bartiq, Qrisp [49], and Silq [50] as examples.Source: STAGE IV RESEARCH · p. 13

Compilation for early fault-tolerance

Early fault-tolerant resource estimates depend on choices about algorithms, error correction, and hardware architecture. The section describes trade-offs in execution and estimation, the need for architecture-specific compilation, and tools and abstractions that may help researchers assess costs.

Compilation for early fault-tolerance

  • Early fault tolerance raises the question of compelling applications, with milestones ranging from classically intractable problems to scientific discoveries enabled by quantum simulation.The listed milestones include non-verifiable, quantumly verifiable, and classically verifiable demonstrations.Source: Compilation for early fault-tolerance · p. 13
  • Early-fault-tolerance algorithm evaluation lacks consensus, and reducing logical qubits can increase gates, code distance, and potentially total physical-qubit requirements.Final resource counts depend sensitively on the QEC architecture and detailed cost models, while codes, hardware, and compilation tools continue to evolve.Source: Compilation for early fault-tolerance · pp. 13–14
  • The Stage IV quantum-simulation compendium groups applications by estimated physical-qubit needs for surface-code advantage, but cross-architecture classifications are subjective and may omit important overheads and trade-offs.The passage also notes that ab initio solid-state simulations can be costly and need further cost reductions.Source: Table IV · p. 14
  • Resource-state routing and feedback can limit parallel non-Clifford operations, while parallel Clifford operations may increase ancilla space and total physical-qubit needs.In early fault tolerance, distilling fewer resource states to save physical qubits may require non-Clifford gate serialization.Source: Compilation for early fault-tolerance · pp. 14–15
  • Amplitude estimation uses O(G/ϵ) gates in one deep circuit, while sampling uses O(1/ϵ2) repetitions of a shallow G-gate circuit; naive sampling needs similar code distance and higher total runtime.Error mitigation may relax the code-distance requirement, but its added repetitions could favor amplitude estimation; the better choice depends on architecture, target fidelities, and error models.Source: Compilation for early fault-tolerance · p. 15
  • Fine-grained early-fault-tolerance cost estimates likely require full compilation to a specific architecture, while high-quality open-source academic compilers may remain scarce.Compilers are architecture-specific; hardware connectivity can affect code choice and the difficulty of implementing operations.Source: Compilation for early fault-tolerance · p. 15
  • Intermediate abstractions such as braiding diagrams, lattice surgery, or modified ZX calculus offer a middle ground between logical and physical circuits.FLASQ estimates surface-code resources from logical circuits compiled to a 2D grid; the authors also point to algorithm–hardware co-design studies.Source: Compilation for early fault-tolerance · p. 15

THE ECONOMICS OF QUANTUM APPLICATION DISCOVERY

The case for quantum applications depends on both reducing the perceived risk of fault-tolerant hardware and demonstrating credible commercial or scientific reward. The authors argue that incentives can leave high-quality application discovery underfunded, while warning against both hype and excessive cynicism.

THE ECONOMICS OF QUANTUM APPLICATION DISCOVERY

  • Hardware milestones such as higher qubit counts, lower error rates, and scalable error-correction experiments help derisk the effort and reassure investors that large-scale fault-tolerant computers are achievable.The authors frame hardware progress as reducing the primary risk to investment.Source: THE ECONOMICS OF QUANTUM APPLICATION… · p. 15
  • Application-driven commercial or scientific value is the investment-side reward, and a perceived slowdown in discovery may weaken expectations about future value.The authors describe market-size projections as influencing company valuations and the case for investment.Source: THE ECONOMICS OF QUANTUM APPLICATION… · p. 15
  • Credible application case studies should connect a broad use case to a specific example with quantifiable value and assess the resources needed for quantum advantage.The authors say the few comprehensive published case studies are largely in quantum simulation and cryptanalysis.Source: THE ECONOMICS OF QUANTUM APPLICATION… · p. 15
  • Exaggerated application narratives can confuse policy and business circles and risk eroding public trust, but counter-hype can discourage students and researchers working on applications.The authors caution against both unchecked hype and misleadingly cynical reactions.Source: THE ECONOMICS OF QUANTUM APPLICATION… · p. 16
  • Quantum application discovery faces a collective-action problem: companies may focus resources on defensible hardware advantages while expecting others or academics to carry the application-discovery effort.The authors describe this incentive structure as an equilibrium that can produce systemic under-investment in high-quality work.Source: THE ECONOMICS OF QUANTUM APPLICATION… · p. 16

OUTLOOK

The authors identify the middle stages of quantum-application development as the field’s main bottlenecks: finding concrete instances with quantum advantage and matching them to real-world uses. They describe technical and sociological challenges in both stages and argue that progress depends on strategic collaboration.

OUTLOOK

  • Identifying concrete problem instances with quantum advantage (Stage II) and matching them to real-world applications (Stage III) are the most significant hurdles to expanding quantum applications.The authors contrast these bottlenecks with progress in abstract algorithm discovery (Stage I) and optimization of selected use cases (Stage IV).Source: OUTLOOK · p. 16
  • Stage II requires instances that are complex enough to be classically intractable but structured enough to avoid outputs concentrating on trivial, classically predictable values.Stage III is constrained by a narrow window of quantum advantage and a knowledge gap between quantum-advantage experts and domain specialists who know where relevant structures may occur.Source: OUTLOOK · p. 16
  • The authors argue that continued investment in fault-tolerant computers depends on articulating a growing portfolio of valuable, achievable, and specific applications.They describe strategic, collaborative effort as a way to address the technical and sociological challenges.Source: OUTLOOK · p. 16
Loading 2511.09124v3…