Technical Summary: Computer Science Challenges in Quantum Computing: Early Fault-Tolerance and Beyond

1. Problem Statement

The field of quantum computing is transitioning from the Noisy Intermediate-Scale Quantum (NISQ) era to the era of early fault-tolerant quantum computing. While hardware capabilities are improving, the primary bottlenecks for achieving practical utility are shifting from device physics to computer-science-driven system design, integration, and evaluation.

Current challenges include:

• Resource Constraints: Early fault-tolerant systems will operate with small numbers of logical qubits, tight constraints on error rates, connectivity, latency, and classical control overhead.
• Theoretical Gaps: There is a lack of rigorous understanding regarding which problems admit quantum advantage under realistic, non-oracle (white-box) models and early fault-tolerant constraints.
• System Integration: A disconnect exists between theoretical Quantum Error Correction (QEC) protocols and heterogeneous hardware implementations. There is a shortage of automated tools for designing, compiling, and verifying fault-tolerant systems at scale.
• Evaluation Deficits: Existing benchmarks often focus on physical metrics rather than logical performance, failing to capture end-to-end trade-offs (space-time overhead, decoding latency, classical control costs) necessary for evaluating early fault-tolerant systems.

The report posits that progress in this regime should be viewed primarily as structured learning about costs, limits, and failure modes, rather than as definitive demonstrations of quantum advantage.

2. Methodology

This report synthesizes community input gathered through a one-day workshop held at the IEEE Quantum Week (September 5, 2025) with 90 attendees. The methodology involved:

1. Workshop Structure: Lightning talks by community experts followed by breakout sessions led by the report's co-authors.
2. Synthesis: Scribe notes from these sessions were assembled, polished, and iteratively refined with feedback from workshop speakers and additional community members.
3. Framework: The analysis is organized around four core pillars of computer science research: Algorithms/Complexity/Cryptography, Error Correction/Fault Tolerance, Software, and Architecture.
4. Cross-Cutting Themes: The report identifies unifying themes that permeate all four areas: Verification and Trust, Heterogeneity, Co-design, and Automation.

The report is intentionally technology- and institution-agnostic, aiming to identify structural bottlenecks rather than predict specific timelines.

3. Key Contributions

The report organizes research challenges into four distinct areas, each framed by a central question and specific milestones.

A. Algorithms, Complexity, and Cryptography

• Central Question: What problems admit quantum advantage?
• Key Contributions:
  • Beyond Black Box: Advocates for moving from oracle-based models to "white box" models where algorithms analyze inputs directly. It calls for evidence of advantage under realistic assumptions (e.g., cryptographic hardness) rather than unconditional separations.
  • Average-Case Analysis: Proposes importing tools from statistical physics and information theory (e.g., belief propagation, replica method) to study average-case complexity, which may better reflect natural settings than worst-case analysis.
  • Dequantization: Emphasizes the "cat-and-mouse" dynamic where classical algorithms attempt to match quantum performance. Developing frameworks to understand when quantum algorithms can be "dequantized" is crucial for validating advantage.
  • Intrinsically Quantum Problems: Highlights the need for complexity foundations for tasks where inputs/outputs are quantum states (e.g., learning quantum channels).
  • Early Fault-Tolerant Models: Calls for complexity frameworks that account for limited logical qubits, restricted circuit depth, and residual noise.

B. Error Correction and Fault Tolerance

• Central Question: Can quantum error correction be designed and deployed at scale?
• Key Contributions:
  • Architectural Interfaces: Proposes developing modular abstractions for codes, decoders, and runtimes to facilitate co-design between hardware, software, and applications.
  • Heterogeneity: Addresses the need to manage systems with diverse qubit modalities and error correction codes (e.g., surface codes, qLDPC) tailored to specific tasks (memory vs. compute).
  • Design Automation (QDA): Argues for the development of Quantum Design Automation tools to synthesize QEC implementations, manage massive parameter spaces, and automate the construction of fault-tolerant experiments.
  • Verification: Stresses the need for mathematical definitions of correctness in QEC and the use of formal methods (theorem provers, model checking) to verify execution without relying on full classical simulation.

C. Software

• Central Question: Can software run efficiently and reliably across diverse hardware?
• Key Contributions:
  • Programming Languages: Calls for high-level languages with formal semantics that support fault tolerance, hybrid execution, and domain-specific abstractions (e.g., Hamiltonian simulation).
  • Compilers and IRs: Identifies the need for intermediate representations (IRs) that capture mid-circuit measurement and error correction. It advocates for open-source, extensible compiler stacks (inspired by LLVM/MLIR) that can handle dynamic compilation and optimization across heterogeneous backends.
  • Verification and Synthesis: Highlights the necessity of formal verification for compilers and programs, especially as simulation becomes infeasible. It also notes the challenge of scaling program synthesis (mapping unitaries to circuits) beyond small qubit counts.
  • AI for Software: Suggests using AI/ML for circuit synthesis, decoding, and noise modeling, but emphasizes the need for symbolic methods to ensure reliability and interpretability.

D. Architecture

• Central Question: Can domain-specific machines enable earlier usefulness?
• Key Contributions:
  • Domain-Specific Machines: Proposes targeting specific workload classes (e.g., Hamiltonian simulation, structured linear algebra) with tailored architectures to achieve early utility, rather than waiting for general-purpose machines.
  • Disaggregated Models: Suggests moving away from a "sea of qubits" model to a disaggregated architecture with distinct zones for memory (dense codes), compute (surface codes), and magic state generation.
  • Distributed Quantum Computing (DQC): Identifies the need for architectural support for low-latency communication between modular quantum processors.
  • Benchmarks: Calls for parameterized, automated benchmarks that separate space, time, and classical control costs to reveal architectural trade-offs.

4. Results and Signals of Progress

The report does not present experimental data but defines signals of progress and milestones for the community to aim for:

• Algorithms: Emergence of problem families with robust evidence for quantum advantage that resists dequantization; clarity on assumptions; and development of average-case complexity tools.
• Error Correction: Reduction in manual tuning effort; demonstrable scalability of automated QEC design workflows; and end-to-end evaluations exposing trade-offs between fidelity, latency, and cost.
• Software: Increased portability of programs across platforms; transparent cost models; and verification techniques that scale beyond classical simulation.
• Architecture: Architectural studies connecting design choices to application-level outcomes; reproducible comparisons using shared benchmarks; and designs demonstrating benefits for specific workload classes.

Shared Benchmarks: The report emphasizes that benchmarks must be end-to-end, scalable, and parameterized. They should measure logical performance (logical error rates, overheads) rather than just physical metrics, and include both advantage-oriented kernels and application-motivated workloads.

5. Significance and Claims

The report claims that early fault-tolerant quantum computing represents a period of structured learning. Its significance lies in:

1. Shifting the Focus: Moving the community's attention from pure hardware scaling to the critical role of computer science in system design, integration, and evaluation.
2. Defining the Research Landscape: Providing a coherent framework for computer scientists to address the specific bottlenecks of the early fault-tolerant regime (e.g., space-time overhead, decoding latency).
3. Promoting Co-Design: Arguing that automation and co-design across algorithms, software, and architecture are essential to manage the complexity of heterogeneous, fault-tolerant systems.
4. Establishing Trust: Highlighting that as quantum computations exceed classical simulability, verification and trustworthy evaluation become prerequisites for scientific and practical adoption.

The authors conclude that success in the next several years will not be defined by solving a single grand challenge, but by the emergence of reproducible executions of parameterized workloads, transparent accounting of resource costs, and stable abstractions that make co-design routine. This disciplined approach is presented as the foundation for building scalable and ultimately useful quantum computers.