Reproduce “Computational Complexity of Clifford Template Compilation: Are Quantum Computers Useful for Compiling Quantum Circuits?” 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
Keisuke Fujii
The paper studies Clifford template compilation: choosing repetition counts that map one input Pauli to a target up to phase. It compares unrestricted integer repetitions with zero-or-one choices. For commuting actions, unrestricted reachability is in NP intersect BQP, with search, while binary feasibility is NP-complete even for CNOT-only operations. This search contains finite-field discrete logarithm, without establishing quantum speedup.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.