IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · 2006 · 681 citations · 43 references
ComputingComputer EngineeringComputer ScienceAlgorithmsQuantum ComputingQuantum MechanicsLogic SynthesisQuantum BitsQuantum CircuitsQuantum ComputationQuantum GatesQuantum Hardware ArchitecturesBoolean FunctionsDigital Logic CircuitsQuantum Circuit ConstructionQuantum Circuit DecompositionQuantum Circuit SynthesisQuantum Gate SynthesisRegistersShannon Entropy
Quantum register state‑space is infinite with exponential superpositions, and a theoretical lower bound limits circuit improvements to at most a factor of two. The paper aims to design efficient quantum logic circuits for generic computation and register initialization, while addressing nearest‑neighbor gate constraints. The circuits use a Shannon‑decomposition analogue and a novel quantum multiplexor, and are adapted to nearest‑neighbor architectures. The resulting circuits are asymptotically optimal, outperform existing designs by at least a factor of two, and remain optimal even when constrained to nearest‑neighbor gates, though gate counts rise by nearly an order of magnitude.
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.
43
<i>Quantum Computation and Quantum Information</i>
Michael A. Nielsen, Isaac L. Chuang, Lov K. Grover · American Journal of Physics · 2002 · 22.7K citations
Quantum computation and quantum information
Jim Law · ACM SIGSOFT Software Engineering Notes · 2001 · 19.2K citations
Computing, Computer Science, Physics +13
Quantum cryptography: Public key distribution and coin tossing
C. H. Bennett · arXiv (Cornell University) · 2020 · 5.4K citations · Full text
Computing, Computer Science, Physics +15
Elementary gates for quantum computation
Adriano Barenco, Charles H. Bennett, Richard Cleve et al. · Physical Review A · 1995 · 4.4K citations · Full text