Reproduce “Complexity separations for optimal matchgate-Clifford synthesis” 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
Berta Casas, Diego García-Martín, Yuxuan Zhang
The authors study synthesis of matchgate–Clifford circuits, seeking the fewest allowed Majorana braids for a given target. They represent circuits as signed permutations of Majorana modes and analyze how connectivity affects synthesis. Paths and complete graphs admit optimal classical algorithms, while the decision problem for arbitrary tree connectivity is NP-complete. On tested path random walks, fitted gate-count growth is lower than Qiskit’s and pytket’s.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.