The DOI matches its Crossref record; 21 of the 21 references it cites were found in a registry or an index.
A transformation based algorithm for reversible logic synthesis
Abstract
A digital combinational logic circuit is reversible if it maps each input pattern to a unique output pattern. Such circuits are of interest in quantum computing, optical computing, nanotechnology and low-power CMOS design. Synthesis approaches are not well developed for reversible circuits even for small numbers of inputs and outputs.In this paper, a transformation based algorithm for the synthesis of such a reversible circuit in terms of n × n Toffoli gates is presented. Initially, a circuit is constructed by a single pass through the specification with minimal look-ahead and no back-tracking. Reduction rules are then applied by simple template matching. The method produces near-optimal results for 3-input circuits and also produces very good results for larger problems.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Quantum Computation and Quantum Information
Nielsen, M. A., Chuang, I., & Grover, L. K. (2002) · American Journal of Physics · doi:10.1119/1.1463744 · Cited by 21,895
Quantum computation and quantum information
Law, J. (2001) · ACM SIGSOFT Software Engineering Notes · doi:10.1145/505482.505499 · Cited by 18,842
A scheme for efficient quantum computation with linear optics
Knill, E., Laflamme, R., & Milburn, G. J. (2001) · Nature · doi:10.1038/35051009 · Cited by 5,880
Irreversibility and heat generation in the computing process
Landauer, R. (1961) · IBM Journal of Research and Development · doi:10.1147/rd.53.0183 · Cited by 4,980
Logical Reversibility of Computation
Bennett, C. H. (1973) · IBM Journal of Research and Development · doi:10.1147/rd.176.0525 · Cited by 3,679 · cited 1×
“Initially, a circuit is constructed by a single pass through the specification with minimal lookahead and no back-tracking.”
BackgroundIrreversibility and heat generation in the computing process
Landauer, R. (2000) · IBM Journal of Research and Development · doi:10.1147/rd.441.0261 · Cited by 2,585
Fredkin, E., & Toffoli, T. (1982) · International Journal of Theoretical Physics · doi:10.1007/bf01857727 · Cited by 1,896
Feynman, R. P. (1986) · Foundations of Physics · doi:10.1007/bf01886518 · Cited by 1,770
Toffoli, T. (1980) · Lecture Notes in Computer Science · doi:10.1007/3-540-10003-2_104 · Cited by 1,523 · cited 3×
“An m -input, m -output, totally-speci(cid:12)ed Boolean function f ( X ) , X = f x 1 ; x 2 ; :::; x m g is reversible if it maps each input assignment to a unique output assignment.”
InfluentialFredkin, E., & Toffoli, T. (2001) · Cited by 1,302
Feynman, R. P. (1985) · Optics News · doi:10.1364/on.11.2.000011 · Cited by 1,023
Efficient adder circuits based on a conservative reversible logic gate
Bruce, J. W., Thornton, M. A., Shivakumaraiah, L., Kokate, P. S., & Li, X. (2003) · Proceedings IEEE Computer Society Annual Symposium on VLSI. New Paradigms for VLSI Systems Design. ISVLSI 2002 · doi:10.1109/isvlsi.2002.1016879 · Cited by 172
Reversible logic circuit synthesis
Shende, V., Prasad, A. K., Markov, I. L., & Hayes, J. P. (2002) · Digest of technical papers/Digest of technical papers - IEEE/ACM International Conference on Computer-Aided Design · doi:10.1145/774572.774625 · Cited by 168
Transformation rules for designing CNOT-based quantum circuits
Iwama, K., Kambayashi, Y., & Yamashita, S. (2002) · Proceedings of the 39th conference on Design automation - DAC '02 · doi:10.1145/513918.514026 · Cited by 164
Two types of mechanical reversible logic
Merkle, R. C. (1993) · Nanotechnology · doi:10.1088/0957-4484/4/2/007 · Cited by 152
Logic synthesis of reversible wave cascades
Mishchenko, A., & Perkowski, M. A. (2002) · PDXScholar (Portland State University) · Cited by 136
Spectral Techniques for Reversible Logic Synthesis
Miller, D. M., & Dueck, G. W. (2002) · Cited by 97
Self-citationGARBAGE IN REVERSIBLE DESIGN OF MULTIPLE OUTPUT FUNCTIONS
Maslov, D., & Dueck, G. W. (2003) · Cited by 85
Self-citationA Hierarchical Approach to Computer-Aided Design of Quantum Circuits
Perkowski, M. A., Lukáč, M., Kerntopf, P., Pivtoraiko, M., Folgheraiter, M., Choi, Y. W., Kim, J.-W., Lee, D., Hwangbo, W., & Kim, H. (2003) · PDXScholar (Portland State University) · Cited by 64
Regularity and Symmetry as a Base for Efficient Realization of Reversible Logic Circuits
Perkowski, M. A., Kerntopf, P., Buller, A., Chrzanowska-Jeske, M., Mishchenko, A., Song, X., Al‐Rabadi, A. N., Jóźwiak, L., & Coppola, A. (2001) · TU/e Research Portal · Cited by 59
Spectral and two-place decomposition techniques in reversible logic
Miller, D. M. (2003) · IEEE International Midwest Symposium on Circuits and Systems (MWSCAS) · doi:10.1109/mwscas.2002.1186906 · Cited by 58
Self-citation
Cited by
RevLib: An Online Resource for Reversible Functions and Reversible Circuits
Wille, R., Gro, D., Teuber, L., Dueck, G. W., & Drechsler, R. (2008) · 38th International Symposium on Multiple Valued Logic (ismvl 2008) · doi:10.1109/ismvl.2008.43 · Cited by 495
Self-citationAn Algorithm for Synthesis of Reversible Logic Circuits
Gupta, P., Agrawal, A., & Jha, N. K. (2006) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/tcad.2006.871622 · Cited by 379
An Efficient Methodology for Mapping Quantum Circuits to the IBM QX Architectures
Zulehner, A., Paler, A., & Wille, R. (2019) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/tcad.2018.2846658 · Cited by 372
BDD-based synthesis of reversible logic for large functions
Wille, R., & Drechsler, R. (2009) · Proceedings of the 46th Annual Design Automation Conference · doi:10.1145/1629911.1629984 · Cited by 323
Synthesis and optimization of reversible circuits—a survey
Saeedi, M., & Markov, I. L. (2013) · ACM Computing Surveys · doi:10.1145/2431211.2431220 · Cited by 298
Metadata
- Authors
- Miller, D. M., Maslov, D., & Dueck, G. W.
- Venue
- Proceedings of the 40th annual Design Automation Conference
- Publisher
- ACM
- Published
- 2003-06-02
- Pages
- 318-323
- ISSN
- 0738-100X (ISSN-L)
- OpenAlex
- W2155163387
- Cited by
- 493
- References
- 21
- FWCI
- 10.39
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.