Minimum Synthesis Cost of CNOT Circuits
| Title: | Minimum Synthesis Cost of CNOT Circuits |
|---|---|
| Authors: | Bu, Alan, Fan, Evan, Joo, Robert Sanghyeon |
| Publication Year: | 2024 |
| Collection: | Mathematics Quantum Physics |
| Subject Terms: | Quantum Physics, Mathematics - Combinatorics |
| More Details: | Optimizing the size and depth of CNOT circuits is an active area of research in quantum computing and is particularly relevant for circuits synthesized from the Clifford + T universal gate set. Although many techniques exist for finding short syntheses, it is difficult to assess how close to optimal these syntheses are without an exponential brute-force search. We use a novel method of categorizing CNOT gates in a synthesis to obtain a strict lower bound computable in $O(n^{\omega})$ time on the minimum number of gates needed to synthesize a given CNOT circuit, where $\omega$ denotes the matrix multiplication constant and $n$ is the number of qubits involved. Applying our framework, we prove that $3(n-1)$ gate syntheses of the $n$-cycle circuit are optimal and provide insight into their structure. We also generalize this result to permutation circuits. For linear reversible circuits with $ n = 3, 4, 5$ qubits, our lower bound is optimal for 100%, 67.7%, and 23.1% of circuits and is accurate to within one CNOT gate in 100%, 99.5%, and 83.0% of circuits respectively. We also introduce an algorithm that efficiently determines whether certain circuits can be synthesized with fewer than $n$ CNOT gates. Comment: 14 pages, 12 figures |
| Document Type: | Working Paper |
| Access URL: | http://arxiv.org/abs/2408.07898 |
| Accession Number: | edsarx.2408.07898 |
| Database: | arXiv |
| Description not available. |