Reversible Pebbling - Parallel Quantum Circuits with Low Amortized Space-Time Complexity

Learn about parallel quantum circuits and reversible pebbling in this conference talk from TQC 2024 that introduces a novel approach to constructing quantum circuits with efficient amortized space-time complexity. Explore how the parallel reversible pebbling game on directed graphs can be used to transform classical irreversible algorithms into quantum algorithms with only sub-polynomial overhead in cumulative complexity. Discover a practical framework for developing parallel quantum circuits by leveraging existing classical pebbling game research, particularly when working with data-dependency graphs. The presentation, delivered at the 19th Conference on the Theory of Quantum Computation, Communication and Cryptography at OIST Japan, demonstrates how to achieve quantum oracle implementations for functions by focusing on the simpler task of designing CC-efficient classical algorithms.