Reproduce “On the Hardness of Approximate Quantum Circuit Membership and Optimization” 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
Adam Husted Kjelstrøm, Jaco van de Pol, Andreas Pavlogiannis
The authors show that deciding whether a quantum circuit lies within an allowed error of any zero-cost implementation is PP-hard, even without a promise about its distance. They reduce a Boolean formula’s satisfying-assignment fraction to circuit distance. With an exactly Clifford+T gate set, non-Clifford gate-count optimization is PP-hard in the operator metric for P-time-computable tolerances below √2/4; matching upper bounds remain open.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.