2004/06/30 by Vivek Shende, Vivek V. Shende, Stephen S. Bullock +1 · 9 citations
Computer Science · Physics and Astronomy · #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum-Dot Cellular Automata #quant-ph
paper · pdf · doi:10.1109/tcad.2005.855930
published as IEEE Trans. on Computer-Aided Design, vol. 25, no. 6, June 2006, pp.1000 - 1010 · 18 pages; v5 fixes minor bugs; v4 is a complete rewrite of v3, with 6x more content, a theory of quantum multiplexors and Quantum Shannon Decomposition. A key result on generic circuit synthesis has been improved to ~23/48*4^n CNOTs for n qubits
arxiv created 2006/04/18 · openalex publication_date 2006/05/12 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/31
We discuss efficient quantum logic circuits which perform two tasks: (i) implementing generic quantum computations and (ii) initializing quantum registers. In contrast to conventional computing, the latter task is nontrivial because the state-space of an n-qubit register is not finite and contains exponential superpositions of classical bit strings. Our proposed circuits are asymptotically optimal for respective tasks and improve published results by at least a factor of two. The circuits for generic quantum computation constructed by our algorithms are the most efficient known today in terms of the number of expensive gates (quantum controlled-NOTs). They are based on an analogue of the Shannon decomposition of Boolean functions and a new circuit block, quantum multiplexor, that generalizes several known constructions. A theoretical lower bound implies that our circuits cannot be improved by more than a factor of two. We additionally show how to accommodate the severe architectural limitation of using only nearest-neighbor gates that is representative of current implementation technologies. This increases the number of gates by almost an order of magnitude, but preserves the asymptotic optimality of gate counts.