2003/11/03 by Alfred V. Aho, Krysta M. Svore, Aho, Alfred V. +1
Computer Science · Physics and Astronomy · #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph) #Quantum-Dot Cellular Automata #quant-ph
paper · pdf · doi:10.48550/arxiv.quant-ph/0311008
17 pages, LaTex
arxiv created 2003/11/03 · openalex publication_date 2003/11/03 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The design and optimization of quantum circuits is central to quantum computation. This paper presents new algorithms for compiling arbitrary 2n x 2n unitary matrices into efficient circuits of (n-1)-controlled single-qubit and (n-1)-controlled-NOT gates. We first present a general algebraic optimization technique, which we call the Palindrome Transform, that can be used to minimize the number of self-inverting gates in quantum circuits consisting of concatenations of palindromic subcircuits. For a fixed column ordering of two-level decomposition, we then give an numerative algorithm for minimal (n-1)-controlled-NOT circuit construction, which we call the Palindromic Optimization Algorithm. Our work dramatically reduces the number of gates generated by the conventional two-level decomposition method for constructing quantum circuits of (n-1)-controlled single-qubit and (n-1)-controlled-NOT gates.