Transcript Document
Introduction to Reversible Ckts Igor Markov University of Michigan Electrical Engineering & Computer Science Outline Historical motivation Arbitrary computations via reversible Rev. ckts: basic definitions & examples Recent implementations in CMOS Reversible synthesis & other EDA tasks Novel motivations for reversible circuits Inherently reversible computations Quantum circuits Historical Motivation Every lost bit causes an energy loss C. Bennett, 1973, IBM J. of R & D ~ the kinetic energy of one molecule in air Idea: try to avoid those energy costs Adiabatic circuits Asymptotically energy lossless (Time ∞ ) S. Younis and T. Knight, 1994, Workshop on Low Power Design Implementing Arbitrary Computations via Reversible Toffoli 1980, Theorem 4.1: Any finite function can be written as a product of trivial encoder bijection f trivial decoder Constructive procedure argument Adds variables 0 0 result f ? ? Definitions Reversible bit-based computation (e.g., Toffoli 1980) N bits at input N bits at output Every input & output bit-string possible Bijection These restrictions apply to gates & ckts Additional restriction: no fanout Acyclic comb. circuits interesting enough NOT gate Examples k-CNOT gate, a.k.a. generalized Toffoli (k+1)-inputs and (k+1)-outputs Values on the first k inputs are unchanged Last input is negated iff the first k are all 1s x x y CNOT gate x y y x z Toffoli gate x y zxy “CNT” gate library A Reversible Circuit and Truth Table x X’ x y z x y z 0 0 0 0 0 0 y 0 0 1 0 0 1 zxy 0 1 0 0 1 1 0 1 1 0 1 0 1 0 0 1 0 0 1 0 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 0 x’ x zxy x’y=z y Equiv. to a CNOT gate Proof by exhaustive simulation Proof by symbolic arguments Implementations in CMOS B. Desoete and A. De Vos “A reversible carry-look-ahead adder using control gates”, Integration, the VLSI Journal, Reversible 4-bit adder vol. 33 (2002), 384 transistors pp. 89-104 no power rails Identities for Reversible Ckts Temporary Storage / Garbage Bits How Much Temporary Storage Do We Need ? Toffoli (MIT TR, 1980) Odd permutations require at least 1 line of temporary storage Shende et al., ICCAD `02 Even permutations need no temp storage Odd permutations need 1 line and no more Constructive synthesis procedure (not implemented) Comb. Synthesis Formulations Straightforward Given a full truth table, find a circuit Shende et al. show an optimal procedure (all 3-line circuits synthesized in mins) With don’t cares The function of one output bit is restricted Iwama et al. (DAC `02): heuristic, transformation-based synthesis, may use many lines of temp. storage Other EDA Tasks Fault testing in reversible circuits K. Patel et al. (VTS `02): reversible circuits require very few test vectors Equivalence checking Difficulties with empirical validation Circuit / gate costs ? Circuit benchmarks ? New Motivation: Inherently Reversible Applications Information is re-coded, but none is lost or added Digital signal processing Cryptography Communications Computer graphics Micro-processor instructions for Bit-permutations Butterfly operation from FFT New Motivation: Quantum Ckts Not related to low power Quantum circuits operate on linear combinations of bit-strings E.g., (|0>+|1>)/2, (|00>+i|11>)/2 Linear: are expressed by matrices Reversibility implied by quantum mechanics A conventional reversible gate, can be extended by linearity, e.g., a quantum inverter is just 01 10 Classical Versus Quantum Ckts Circuit identities for conventional reversible gates (e.g., CNOT and Toffoli) do not change in the quantum context Conventional techniques applicable when there are no purely quantum gates “Conventional subroutines” of q. programs Purely quantum gates required in apps Open problem: synthesis with purely quantum gates Thank you!