Reproduce “Quantum Programming in Polylogarithmic Time” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Florent Ferrari, Emmanuel Hainry, Romain Péchoux, Mário Silva
Researchers from École Normale Supérieure de Lyon and Université de Lorraine introduce `plp` (PolyLog Programs), a quantum programming language that formally characterizes `fbqpolylog`, the class of functions computable in polylogarithmic quantum time with bounded error. They demonstrate that `plp` programs terminate, are reversible, and compile into uniform quantum circuits with polylogarithmic depth, thereby providing a high-level abstraction for efficient quantum algorithms.
Key insights
- Recursive program structures, when combined with specific argument size reduction and sequential execution limits, can directly correspond to polylogarithmic time complexity in quantum computation.
- A programming language can provide a precise and intuitive characterization for sub-polynomial quantum complexity classes, bridging the gap between abstract theoretical models and practical programming paradigms.
- Formal properties like termination and inherent reversibility can be designed into quantum programming languages, which are fundamental for physically realizable quantum computation and formal verification.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.