The DOI matches its Crossref record; 17 of the 17 references it cites were found in a registry or an index.
Synthesis of reversible logic circuits
Abstract
Reversible or information-lossless circuits have applications in digital signal processing, communication, computer graphics, and cryptography. They are also a fundamental requirement in the emerging field of quantum computation. We investigate the synthesis of reversible circuits that employ a minimum number of gates and contain no redundant input-output line-pairs (temporary storage channels). We prove constructively that every even permutation can be implemented without temporary storage using NOT, CNOT, and TOFFOLI gates. We describe an algorithm for the synthesis of optimal circuits and study the reversible functions on three wires, reporting the distribution of circuit sizes. We also study canonical circuit decompositions where gates of the same kind are grouped together. Finally, in an application important to quantum computing, we synthesize oracle circuits for Grover's search algorithm, and show a significant improvement over a previously proposed synthesis algorithm.
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: 10th Anniversary Edition
Nielsen, M. A., & Chuang, I. L. (2012) · doi:10.1017/cbo9780511976667 · Cited by 8,436
Elementary gates for quantum computation
Barenco, A., Bennett, C. H., Cleve, R., DiVincenzo, D. P., Margolus, N., Shor, P., Sleator, T., Smolin, J. A., & Weinfurter, H. (1995) · Physical Review A · doi:10.1103/physreva.52.3457 · Cited by 4,311
Logical Reversibility of Computation
Bennett, C. H. (1973) · IBM Journal of Research and Development · doi:10.1147/rd.176.0525 · Cited by 3,679
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 6×
“Toffoli [20] gives constructions for an arbitrary reversible or irreversible function in terms of a certain gate library.”
InfluentialFeynman, R. P. (1985) · Optics News · doi:10.1364/on.11.2.000011 · Cited by 1,023
A framework for fast quantum mechanical algorithms
Grover, L. K. (1998) · Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98 · doi:10.1145/276698.276712 · Cited by 240
Toward an architecture for quantum programming
Bettelli, S., Calarco, T., & Serafini, L. (2003) · The European Physical Journal D · doi:10.1140/epjd/e2003-00242-2 · Cited by 178
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
Cited by
Improved simulation of stabilizer circuits
Aaronson, S., & Gottesman, D. (2004) · Physical Review A · doi:10.1103/physreva.70.052328 · Cited by 1,515
Synthesis of quantum-logic circuits
Shende, V. V., Bullock, S. S., & Markov, I. L. (2006) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/tcad.2005.855930 · Cited by 669
Self-citationA Meet-in-the-Middle Algorithm for Fast Synthesis of Depth-Optimal Quantum Circuits
Amy, M., Maslov, D., Mosca, M., & Roetteler, M. (2013) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/tcad.2013.2244643 · Cited by 549
“Maslov and Miller [18] also examined synthesis of 3-bit circuits over this gate set, using a pruned breadth-first search similar to [27] rather than formal methods.”
MethodRevLib: 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
An 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
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
Self-citationHung, W. N. N., Song, X., Yang, G., Yang, J., & Perkowski, M. (2006) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/tcad.2005.858352 · Cited by 261
Quantum circuit optimizations for NISQ architectures
Nash, B., Gheorghiu, V., & Mosca, M. (2020) · Quantum Science and Technology · doi:10.1088/2058-9565/ab79b1 · Cited by 139
Arbitrary two-qubit computation in 23 elementary gates
Bullock, S. S., & Markov, I. L. (2003) · Physical Review A · doi:10.1103/physreva.68.012318 · Cited by 59
Self-citationThe Classification of Reversible Bit Operations
Aaronson, S., Grier, D., & Schaeffer, L. (2015) · arXiv · doi:10.48550/arxiv.1504.05155 · Cited by 33
“[25] gave a slightly more complicated construction that uses only 1 ancilla bit (assuming that we have CNOT and NOT gates in addition to Toffoli gates), and that also gives explicit bounds on the number of Toffoli gates required based on the number of fixed points of the permutation.”
BackgroundMethodQuantum Safe Lightweight Cryptography with Quantum Permutation Pad
Kuang, R., Lou, D., He, A., & Conlon, A. (2021) · 2021 IEEE 6th International Conference on Computer and Communication Systems (ICCCS) · doi:10.1109/icccs52626.2021.9449247 · Cited by 21
On security of image ciphers based on logic circuits and chaotic permutations
Annaby, M. H., Ayad, H., & Rushdi, M. A. (2018) · Multimedia Tools and Applications · doi:10.1007/s11042-017-5439-6 · Cited by 6
Metadata
- Authors
- Shende, V. V., Prasad, A. K., Markov, I. L., & Hayes, J. P.
- Venue
- IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Published
- 2003-06
- Volume
- 22
- Issue
- 6
- Pages
- 710-722
- ISSN
- 0278-0070 (ISSN-L)
- OpenAlex
- W2146532505
- Cited by
- 568
- References
- 17
- FWCI
- 15.66
- Type
- journal article
- 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.