On Exact Sizes of Minimal CNOT Circuits

Jens Emil Christensen, Søren Fuglede Jørgensen, Andreas Pavlogiannis, Jaco van de Pol · 2025

Read On Exact Sizes of Minimal CNOT Circuits by Jens Emil Christensen, Søren Fuglede Jørgensen, Andreas Pavlogiannis, Jaco van de Pol (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-01467.txt.

Description

Jens Emil Christensen, Søren Fuglede Jørgensen, Andreas Pavlogiannis, and Jaco van de Pol compute the exact sizes of the smallest CNOT circuits. CNOT gates are basic building blocks in reversible and quantum computing. Algebraically, CNOT circuits on n qubits match the general linear group over the field of two elements, and finding a minimal circuit means finding distances in its Cayley graph. That graph grows super-exponentially, which blocked past searches.

A new distance method lets the team synthesize optimal circuits that were out of reach, covering all circuits on seven qubits. Two theory results support the method: a full account of the graph's isometries, and polynomial formulas for sphere sizes at fixed distance.

Catalog record

CREATORJens Emil Christensen, Søren Fuglede Jørgensen, Andreas Pavlogiannis, Jaco van de Pol
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE49 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-01467

Browse the full library · About the Tower of Babel