Traq: Estimating the Quantum Cost of Classical Programs
summary
Traq provides an automated pipeline that compiles a classical CPL source language to unitary quantum code, extracts three cost functions (worst-case have cost, input-dependent expected cost, and unitary cost) in a query-count cost model, and solves error constraints (ε1, ε2) to guarantee the compiled quantum program stays within the chosen failure bound. The system proves compiler and cost soundness, implements primitives like Grover search, amplitude amplification and Simon, and ships as a 9000-line Haskell package with crypto and optimization case studies, producing concrete query counts that predict realistic speedups. sound compiler+cost guarantees
AI-written summary · about
chapters (7)
- 0:00TraQ introduction
- 3:54TraQ’s core idea
- 8:05Cost model in TraQ
- 11:17Formal guarantees
- 13:44Implementation and supported primitives
- 14:47Future directions
- 15:31Q&A
related talks
17mEnabling Accuracy-Aware Quantum Compilers using Symbolic Resource Estimation
39mBuilding a Compiler for Quantum Computers
42mQuantum program analysis: Verification and Testing
55mScalable Quantum Compilation With Jasp
32mOptimal Quantum Programs
33mVerified Compilation of Quantum Oracles
19mThe T-Complexity Costs of Error Correction for Control Flow in Quantum Computation
37mResource-Efficient Quantum Computing by Breaking Abstractions