Abstract
Reversible logic circuits have been historically motivated by theoretical research in low-power electronics as well as practical improvement of bit manipulation transforms in cryptography and computer graphics. Recently, reversible circuits have attracted interest as components of quantum algorithms, as well as in photonic and nano-computing technologies where some switching devices offer no signal gain. Research in generating reversible logic distinguishes between circuit synthesis, postsynthesis optimization, and technology mapping. In this survey, we review algorithmic paradigms—search based, cycle based, transformation based, and BDD based—as well as specific algorithms for reversible synthesis, both exact and heuristic. We conclude the survey by outlining key open challenges in synthesis of reversible and quantum logic, as well as most common misconceptions.
- Aaronson, S. and Gottesman, D. 2004. Improved simulation of stabilizer circuits. Phys. Rev. A 70.Google ScholarCross Ref
- Altepeter, J., Jeffrey, E., and Kwiat, P. 2005. Photonic state tomography. Adv. At. Mol. Opt. Phys. 52. 105--159.Google Scholar
- Arabzadeh, M. and Saeedi, M. 2011. RCviewer+, A viewer/analyzer for reversible and quantum circuits, version 1.88. http://ceit.aut.ac.ir/QDA/RCV.htm.Google Scholar
- Arabzadeh, M., Saeedi, M., and Saheb Zamani, M. 2010. Rule-Based optimization of reversible circuits. In Proceedings of the Asia and South Pacific Design Automation Conference. 849--854. Google ScholarDigital Library
- Asano, M. and Ishii, C. 2005. New structural quantum circuit simulating a toffoli gate. arXiv:quant-ph/0512016.Google Scholar
- Bacon, D. and Van Dam, W. 2010. Recent progress in quantum algorithms. Comm. ACM 53, 84--93. Google ScholarDigital Library
- Barenco, A., Bennett, C., Cleve, R., Divincenzo, D., Margolus, N., Shor, P., Sleator, T., Smolin, J., and Weinfurter, H. 1995. Elementary gates for quantum computation. Phys. Rev. A 52, 3457--3467.Google ScholarCross Ref
- Beckman, D., Chari, A. N., Devabhaktuni, S., and Preskill, J. 1996. Efficient networks for quantum factoring. Phys. Rev. A 54, 2, 1034--1063.Google ScholarCross Ref
- Bennett, C. H. 1973. Logical reversibility of computation. IBM J. Res. Dev. 17, 6, 525--532. Google ScholarDigital Library
- Bergholm, V., Vartiainen, J. J., Möttönen, M., and Salomaa, M. M. 2005. Quantum circuits with uniformly controlled one-qubit gates. Phys. Rev. A 71.Google ScholarCross Ref
- Bollig, B., Löbbing, M., Sauerhoff, M., and Wegener, I. 1999. On the complexity of the hidden weighted bit function for various bdd models. Informatique Theorique et Appl. 33, 2, 103--116.Google ScholarCross Ref
- Bryant, R. 1986. Graph-Based algorithms for boolean function manipulation. IEEE Trans. Comput. 35, 8, 677--691. Google ScholarDigital Library
- Bushnell, M. and Agrawal, V. 2000. Essentials of Electronic Testing for Digital, Memory and Mixed-Signal VLSI Circuits. Kluwer.Google Scholar
- Cheung, D. 2004. Improved bounds for the approximate qft. In Proceedings of the International Symposium on Information and Communication Technologies. 1--6. Google ScholarDigital Library
- Cheung, D., Maslov, D., Mathew, J., and Pradhan, D. K. 2009. On the design and optimization of a quantum polynomial-time attack on elliptic curve cryptography. Quant. Inf. Comput. 9, 7&8, 610--621. Google ScholarDigital Library
- Cheung, D., Maslov, D., and Severini., S. 2007. Translation techniques between quantum circuit architectures. In Proceedings of the Workshop on Quantum Information.Google Scholar
- Childs, A. M. and Van Dam, W. 2010. Quantum algorithms for algebraic problems. Rev. Mod. Phys. 82, 1, 1--52.Google ScholarCross Ref
- Choi, B. and Van Meter, R. 2008. Effects of interaction distance on quantum addition circuits. quant-ph/0809.4317. Google ScholarDigital Library
- Cuccaro, S. A., Draper, T. G., Kutin, S. A., and Moulton, D. P. 2005. A new quantum ripple-carry addition circuit. In Proceedings of the Workshop on Quantum Information.Google Scholar
- Dally, W. and Towles, B. 2003. Principles and Practices of Interconnection Networks. Morgan Kaufmann. Google ScholarDigital Library
- De Vos, A. 2010a. Reversible computer hardware. Electron. Notes Theor. Comput. Sci. 253, 6, 17--22. Google ScholarDigital Library
- De Vos, A. 2010b. Reversible Computing. Wiley-VCH.Google Scholar
- De Vos, A., Raa, B., and Storme, L. 2002. Generating the group of reversible logic gates. J. Phys. A 35, 33, 7063.Google Scholar
- Desoete, B. and De Vos, A. 2002. A reversible carry-look-ahead adder using control gates. Integr. VLSI J. 33, 1, 89--104. Google ScholarDigital Library
- Dimitrov, V. S., Jarvinen, K. U., and Adikari, J. 2011. Area-Efficient multipliers based on multiple-radix representations. IEEE Trans. Comput. 60, 2, 189--201. Google ScholarDigital Library
- Donald, J. and Jha, N. K. 2008. Reversible logic synthesis with fredkin and peres gates. J. Emerg. Technol. Comput. Syst. 4, 1, 2:1--2:19. Google ScholarDigital Library
- Doucçot, B., Ioffe, L. B., and Vidal, J. 2004. Discrete non-abelian gauge theories in josephson-junction arrays and quantum computation. Phys. Rev. B 69, 21.Google Scholar
- Egner, S., Püschel, M., and Beth, T. 1997. Decomposing a permutation into a conjugated tensor product. In Proceedings of the International Symposium on Symbolic and Algebraic Computation. 101--108. Google ScholarDigital Library
- Fazel, K., Thornton, M., and Rice, J. 2007. ESOP-Based toffoli gate cascade generation. In Proceedings of the IEEE Pacific Rim Conference on Communications. 206--209.Google Scholar
- Fei, X., Jiang-Feng, D., Ming-Jun, S., Xian-Yi, Z., Rong-Dian, H., and Ji-Hui, W. 2002. Realization of the fredkin gate by three transition pulses in a nuclear magnetic resonance quantum information processor. Chinese Phys. Lett. 19, 8, 1048.Google ScholarCross Ref
- Feynman, R. 1986. Quantum mechanical computers. Found. Phys. 16, 6, 507--531.Google ScholarCross Ref
- Fowler, A. G., Devitt, S. J., and Hollenberg, L. C. L. 2004a. Implementation of shor's algorithm on a linear nearest neighbour qubit array. Quant. Inf. Comput. 4, 237--245. Google ScholarDigital Library
- Fowler, A. G., Hill, C. D., and Hollenberg, L. C. L. 2004b. Quantum error correction on linear nearest neighbor qubit arrays. Phys. Rev. A 69, 4.Google ScholarCross Ref
- Fredkin, E. F. and Toffoli, T. 1982. Conservative logic. Int. J. Theor. Phys. 21, 3/4, 219--253.Google ScholarCross Ref
- Gao, W.-B., Xu, P., Yao, X.-C., Gühne, O., Cabello, A., Lu, C.-Y., Peng, C.-Z., Chen, Z.-B., and Pan, J.-W. 2010. Experimental realization of a controlled-not gate with four-photon six-qubit cluster states. Phys. Rev. Lett. 104, 2.Google ScholarCross Ref
- Glück, R. and Kawabe, M. 2005. A method for automatic program inversion based on ir(0) parsing. Fundam. Inf. 66, 4, 367--395. Google ScholarDigital Library
- Golubitsky, O., Falconer, S. M., and Maslov, D. 2010. Synthesis of the optimal 4-bit reversible circuits. In Proceedings of the Design Automation Conference. 653--656. Google ScholarDigital Library
- Golubitsky, O. and Maslov, D. 2011. A study of optimal 4-bit reversible toffoli circuits and their synthesis. arXiv:1103.2686. Google ScholarDigital Library
- Grassl, M. 2003. Circuits for quantum error-correcting codes. http://iaks-www.ira.uka.de/home/grassl/QECC/index.html.Google Scholar
- Grosse, D., Wille, R., Dueck, G., and Drechsler, R. 2009. Exact multiple-control toffoli network synthesis with SAT techniques. IEEE Trans. Comput. Aid. Des. 28, 5, 703--715. Google ScholarDigital Library
- Gupta, P., Agrawal, A., and Jha, N. 2006. An algorithm for synthesis of reversible logic circuits. IEEE Trans. Comput Aid. Des. 25, 11, 2317--2330. Google ScholarDigital Library
- Hachtel, G. D. and Somenzi, F. 2000. Logic Synthesis and Verification Algorithms. Kluwer. Google ScholarDigital Library
- Häffner, H., Hänsel, W., Roos, C. F., Benhelm, J., Al Kar, D. C., Chwalla, M., Körber, T., Rapol, U. D., Riebe, M., Schmidt, P. O., Becher, C., Gühne, O., Dür, W., and Blatt, R. 2005. Scalable multiparticle entanglement of trapped ions. Nature 438, 643--646.Google ScholarCross Ref
- Hilewitz, Y. and Lee, R. B. 2008. Fast bit gather, bit scatter and bit permutation instructions for commodity microprocessors. J. Signal Process. Syst. 53, 145--169. Google ScholarDigital Library
- Hirata, Y., Nakanishi, M., Yamashita, S., and Nakashima, Y. 2011. An efficient conversion of quantum circuits to a linear nearest neighbor architecture. Quant. Inf. Comput. 11, 1--2, 142--166. Google ScholarDigital Library
- Hung, W., Song, X., Yang, G., Yang, J., and Perkowski, M. 2006. Optimal synthesis of multiple output boolean functions using a set of quantum gates by symbolic reachability analysis. IEEE Trans. Comput. Aid. Des. 25, 9, 1652--1663. Google ScholarDigital Library
- Iwama, K., Kambayashi, Y., and Yamashita, S. 2002. Transformation rules for designing cnot-based quantum circuits. In Proceedings of the Design Automation Conference. 419--424. Google ScholarDigital Library
- Jerrum, M., Sinclair, A., and Vigoda, E. 2004. A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. J. ACM 51, 4, 671--697. Google ScholarDigital Library
- Kane, B. 1998. A silicon-based nuclear spin quantum computer. Nature 393, 133--137.Google ScholarCross Ref
- Kerntopf, P. 2004. A new heuristic algorithm for reversible logic synthesis. In Proceedings of the Design Automation Conference. 834--837. Google ScholarDigital Library
- Kim, S., Ziesler, C. H., and Papaefthymiou, M. C. 2005. Charge-Recovery computing on silicon. IEEE Trans. Comput. 54, 6, 651--659. Google ScholarDigital Library
- Korf, R. 1999. Artificial intelligence search algorithms. In Algorithms Theory Computation Handbook., CRC Press.Google Scholar
- Kutin, S., Moulton, D., and Smithline, L. 2007. Computation at a distance. Chicago J. Theor. Comput. Sci.Google Scholar
- Kutin, S. A. 2007. Shor's algorithm on a nearest-neighbor machine. In Proceedings of the Asian Conference on Quantu Information Science.Google Scholar
- Laforest, M., Simon, D., Boileau, J.-C., Baugh, J., Ditty, M., and Laflamme, R. 2007. Using error correction to determine the noise model. Phys. Rev. A 75, 1, 133--137.Google ScholarCross Ref
- Lagarias, J. C. and Odlyzko, A. M. 1987. Computing {pi}(x): An analytic method. J. Algor. 8, 2, 173--191. Google ScholarDigital Library
- Landauer, R. 1961. Irreversibility and heat generation in the computing process. IBM J. Res. Dev. 5, 183--191. Google ScholarDigital Library
- Lee, S., Lee, S., Kim, T., Lee, J. S., Biamonte, J., and Perkowski, M. 2006. The cost of quantum gate primitives. J. Multiple-Valued Logic Soft Comput. 12, 5--6.Google Scholar
- Markov, I. L. and Roy, J. A. 2003. On sub-optimallity and scalability of logic synthesis tools. In Proceedings of the International Workshop on Logic Synthesis.Google Scholar
- Markov, I. L. and Saeedi, M. 2012. Constant-optimized quantum circuits for modular multiplication and exponentiation. Quantum Info. Comput. 12, 5--6, 361--394. Google ScholarDigital Library
- Markov, I. L. and Saeedi, M. 2013. Faster quantum number factoring via circuit synthesis. Phys. Rev. A 87, 012310.Google ScholarCross Ref
- Maslov, D. 2007. Linear depth stabilizer and quantum fourier transformation circuits with no auxiliary qubits in finite neighbor quantum architectures. Phys. Rev. A 76.Google ScholarCross Ref
- Maslov, D. 2011. Reversible logic synthesis benchmarks page. http://www.cs.uvic.ca/~dmaslov/.Google Scholar
- Maslov, D. and Dueck, G. 2003. Improved quantum cost for n-bit toffoli gates. Electron. Lett. 39, 25, 1790--1791.Google ScholarCross Ref
- Maslov, D. and Dueck, G. 2004. Reversible cascades with minimal garbage. IEEE Trans. Comput. Aid. Des. 23, 11, 1497--1509. Google ScholarDigital Library
- Maslov, D., Dueck, G., and Miller, D. 2005a. Synthesis of fredkin-toffoli reversible networks. IEEE Trans. VLSI Syst. 13, 6, 765--769. Google ScholarDigital Library
- Maslov, D., Dueck, G., and Miller, D. 2005b. Toffoli network synthesis with templates. IEEE Trans. Comput. Aid. Des. 24, 6, 807--817. Google ScholarDigital Library
- Maslov, D., Dueck, G., Miller, D., and Negrevergne, C. 2008a. Quantum circuit simplification and level compaction. IEEE Trans. Comput. Aid. Des. 27, 3, 436--444. Google ScholarDigital Library
- Maslov, D., Dueck, G. W., AND Miller, D. M. 2007. Techniques for the synthesis of reversible Toffoli networks. ACM Trans. Des. Autom. Electron. Syst. 12, 4, 42:1--42:28. Google ScholarDigital Library
- Maslov, D., Falconer, S. M., and Mosca, M. 2008b. Quantum circuit placement. IEEE Trans. Comput. Aid. Des. 27, 4, 752--763. Google ScholarDigital Library
- Maslov, D. and Saeedi, M. 2011. Reversible circuit optimization via leaving the Boolean domain. IEEE Trans. Comput. Aid. Des. 30, 6, 806--816. Google ScholarDigital Library
- McGregor, J. P. and Lee, R. B. 2003. Architectural techniques for accelerating subword permutations with repetitions. IEEE Trans. VLSI 11, 325--335. Google ScholarDigital Library
- Miller, D. and Sasanian, Z. 2010. Improving the NCV realization of multiple-control Toffoli gates. In Proceedings of the International Workshop on Boolean Problems. 37--44.Google Scholar
- Miller, D. M., Maslov, D., and Dueck, G. W. 2003. A transformation based algorithm for reversible logic synthesis. In Proceedings of the Design Automation Conference. 318--323. Google ScholarDigital Library
- Miller, D. M., Wille, R., and Drechsler, R. 2010. Reducing reversible circuit cost by adding lines. In Proceedings of the International Symposium on Multiple-Valued Logic. 217--222. Google ScholarDigital Library
- Mishchenko, A. and Perkowski, M. 2002. Logic synthesis of reversible wave cascades. In Proceedings of the International Workshop on Logic Synthesis. 197--202.Google Scholar
- Moore, C. and Crutchfield, J. P. 2000. Quantum automata and quantum grammars. Theor. Comput. Sci. 237, 1--2, 275--306. Google ScholarDigital Library
- Morita, K. 2008. Reversible computing and cellular automata - A survey. Theor. Comput. Sci. 395, 1, 101--131. Google ScholarDigital Library
- Möttönen, M. and Vartiainen, J. J. 2006. Decompositions of general quantum gates. In Trends in Quantum Computing Research. NOVA Publishers, Chapter 7.Google Scholar
- Negrevergne, C., Mahesh, T. S., Ryan, C. A., Ditty, M., Cyr-Racine, F., Power, W., Boulant, N., Havel, T., Cory, D. G., and Laflamme, R. 2006. Benchmarking quantum control methods on a 12-qubit system. Phys. Rev. Lett. 96, 17.Google ScholarCross Ref
- Nielsen, M. and Chuang, I. 2000. Quantum Computation and Quantum Information. Cambridge University Press, Cambridge, UK. Google ScholarDigital Library
- Patel, K. N., Markov, I. L., and Hayes, J. P. 2008. Optimal synthesis of linear reversible circuits. Quant. Inf. Comput. 8, 3--4, 282--294. Google ScholarDigital Library
- Peres, A. 1985. Reversible logic and quantum computers. Phys. Rev. A 32, 3266--3276.Google ScholarCross Ref
- Pérez-Delgado, C. A., Mosca, M., Cappellaro, P., and Cory, D. G. 2006. Single spin measurement using cellular automata techniques. Phys. Rev. Lett. 97, 10, 100501.Google ScholarCross Ref
- Polian, I., Fiehn, T., Becker, B., and Hayes, J. P. 2005. A family of logical fault models for reversible circuits. In Proceedings of the Asian Test Symposium. 422--427. Google ScholarDigital Library
- Politi, A., Matthews, J. C. F., and O'Brien, J. L. 2009. Shor's quantum factoring algorithm on a photonic chip. Sci. 325, 5945, 1221.Google Scholar
- Prasad, A. K., Shende, V. V., Markov, I. L., Hayes, J. P., and Patel, K. N. 2006. Data structures and algorithms for simplifying reversible circuits. J. Emerg. Technol. Comput. Syst. 2, 4, 277--293. Google ScholarDigital Library
- Rentergem, Y. V., Vos, A. D., and Keyser, K. D. 2007. Six synthesis methods for reversible logic. Open Syst. Inf. Dynam. 14, 1, 91--116. Google ScholarDigital Library
- Saeedi, M., Arabzadeh, M., Saheb Zamani, M., and Sedighi, M. 2011a. Block-based quantum-logic synthesis. Quant. Inf. Comput. 11, 3--4, 0262--0277. Google ScholarDigital Library
- Saeedi, M., Saheb Zamani, M., and Sedighi, M. 2007a. Reversible circuit synthesis using a cycle-based approach. In Proceedings of the International Symposium on VLSI. 428--436.Google Scholar
- Saeedi, M., Saheb Zamani, M., Sedighi, M., and Sasanian, Z. 2010a. Synthesis of reversible circuit using cycle-based approach. J. Emerg. Technol. Comput. Syst. 6, 4, 13:1--13:26. Google ScholarDigital Library
- Saeedi, M., Sedighi, M., and Saheb Zamani, M. 2007b. A novel synthesis algorithm for reversible circuits. In Proceedings of the International Conference on Computer-Aided Design. 65--68. Google ScholarDigital Library
- Saeedi, M., Sedighi, M., and Saheb Zamani, M. 2010b. A library-based synthesis methodology for reversible logic. Microelectron. J. 41, 4, 185--194. Google ScholarDigital Library
- Saeedi, M., Wille, R., and Drechsler, R. 2011b. Synthesis of quantum circuits for linear nearest neighbor architectures. Quant. Inf. Proc. 10, 3, 355--377. Google ScholarDigital Library
- Shende, V., Bullock, S., and Markov, I. L. 2006. Synthesis of quantum-logic circuits. IEEE Trans. Comput. Aid. Des. 25, 6, 1000--1010. Google ScholarDigital Library
- Shende, V. V. and Markov, I. L. 2009. On the CNOT-cost of TOFFOLI gates. Quant. Inf. Comput. 9, 5--6, 461--486. Google ScholarDigital Library
- Shende, V. V., Markov, I. L., and Bullock, S. S. 2004. Minimal universal two-qubit quantum circuits. Phys. Rev. A 69, 062321.Google ScholarCross Ref
- Shende, V. V., Prasad, A. K., Markov, I. L., and Hayes, J. P. 2003. Synthesis of reversible logic circuits. IEEE Trans. Comput. Aid. Des. 22, 6, 710--722. Google ScholarDigital Library
- Shi, Y.-Y., Duan, L.-M., and Vidal, G. 2006. Classical simulation of quantum many-body systems with a tree tensor network. Phys. Rev. A 74, 2.Google ScholarCross Ref
- Shi, Z. and Lee, R. B. 2000. Bit permutation instructions for accelerating software cryptography. In Proceedings of the International Conference on Application-Specific Systems, Architectures, and Processors. 138--148. Google ScholarDigital Library
- Skinner, A. J., Davenport, M. E., and Kane, B. E. 2003. Hydrogenic spin quantum computing in silicon: A digital approach. Phys. Rev. Lett. 90, 8, 087901.Google ScholarCross Ref
- Skoneczny, M., Van Rentergem, Y., and De Vos, A. 2008. Reversible fourier transform chip. Mixed Des. Integr. Circ. Syst., 281--286.Google Scholar
- Soeken, M., Frehse, S., Wille, R., and Drechsler, R. 2010a. RevKit: A toolkit for reversible circuit design. In Proceedings of the Workshop on Reversible Computation. http://www.revkit.org.Google Scholar
- Soeken, M., Wille, R., Dueck, G. W., and Drechsler, R. 2010b. Window optimization of reversible and quantum circuits. Des. Diagnost. Elec. Circ. Syst., 341--345.Google Scholar
- Storme, L., Vos, A. D., and Jacobs, G. 1999. Group theoretical aspects of reversible logic gates. J. Universal Comput. Sci. 5, 5, 307--321.Google Scholar
- Svore, K. M., Aho, A. V., Cross, A. W., Chuang, I., and Markov, I. L. 2006. A layered software architecture for quantum computing design tools. Comput. 39, 74--83. Google ScholarDigital Library
- Takahashi, Y. and Kunihiro, N. 2008. A fast quantum circuit for addition with few qubits. Quant. Inf. Comput. 8, 6--7, 636--649. Google ScholarDigital Library
- Takahashi, Y., Kunihiro, N., and Ohta, K. 2007. The quantum Fourier transform on a linear nearest neighbor architecture. Quant. Inf. Comput. 7, 4, 383--391. Google ScholarDigital Library
- Takahashi, Y., Tani, S., and Kunihiro, N. 2010. Quantum addition circuits and unbounded fan-out. Quant. Inf. Comput. 10, 9--10, 872--890. Google ScholarDigital Library
- Toffoli, T. 1980. Reversible computing. Tech. memo MIT/LCS/TM-151, MIT Lab.Google Scholar
- Van Meter, R. and Itoh, K. M. 2005. Fast quantum modular exponentiation. Phys. Rev. A 71, 5.Google ScholarCross Ref
- Van Meter, R. and Oskin, M. 2006. Architectural implications of quantum computing technologies. J. Emerg. Technol. Comput. Syst. 2, 1, 31--63. Google ScholarDigital Library
- Viamontes, G., Markov, I. L., and Hayes, J. P. 2009. Quantum Circuit Simulation. Springer. Google ScholarDigital Library
- Viamontes, G. F., Markov, I. L., and Hayes, J. P. 2007. Checking equivalence of quantum circuits and states. In Proceedings of the International Conference on Computer-Aided Design. 69--74. Google ScholarDigital Library
- Visan, A. M., Polyakov, A., Solanki, P. S., Arya, K., Denniston, T., and Cooperman, G. 2009. Temporal debugging using URDB. CoRR abs/0910.5046.Google Scholar
- Von Neumann, J. 1966. Theory of Self-Reproducing Automata. University of Illinois Press. Google ScholarDigital Library
- Wille, R. and Drechsler, R. 2009. BDD-Based synthesis of reversible logic for large functions. In Proceedings of the Design Automation Conference. 270--275. Google ScholarDigital Library
- Wille, R. and Drechsler, R. 2010. Towards a Design Flow for Reversible Logic. Springer.Google Scholar
- Wille, R., Grosse, D., Miller, D. M., and Drechsler, R. 2009. Equivalence checking of reversible circuits. In Proceedings of the International Symposium on Multiple-Valued Logic. 324--330. Google ScholarDigital Library
- Wille, R., Grosse, D., Teuber, L., Dueck, G. W., and Drechsler, R. 2008a. RevLib: An online resource for reversible functions and reversible circuits. In Proceedings of the International Symposium on Multiple-Valued Logic. 220--225. Google ScholarDigital Library
- Wille, R., Le, H. M., Dueck, G. W., and Grosse, D. 2008b. Quantified synthesis of reversible logic. In Proceedings of the Conference on Design, Automation, and Test in Europe. 1015--1020. Google ScholarDigital Library
- Wille, R., Offermann, S., and Drechsler, R. 2010a. SyReC: A programming language for synthesis of reversible circuits. In Proceedings of the Forum on Specification and Design Languages.Google Scholar
- Wille, R., Soeken, M., and Drechsler, R. 2010b. Reducing the number of lines in reversible circuits. In Proceedings of the Design Automation Conference. 647--652. Google ScholarDigital Library
- Yamashita, S. and Markov, I. L. 2010. Fast equivalence-checking for quantum circuits. Quant. Inf. Comput. 9, 9--10, 721--734. Google ScholarDigital Library
- Yang, G., Song, X., Hung, W. N., Xie, F., and Perkowski, M. A. 2006. Group theory based synthesis of binary reversible circuits. Lecture Notes in Computer Science, vol. 3959, Springer, 365--374. Google ScholarDigital Library
- Yang, G., Song, X., Hung, W. N. N., and Perkowski, M. A. 2008. Bi-directional synthesis of 4-bit reversible circuits. Comput. J. 51, 207--215. Google ScholarDigital Library
- Yokoyama, T., Axelsen, H. B., and Glück, R. 2008. Principles of a reversible programming language. Comput. Frontiers, 43--54. Google ScholarDigital Library
- Zhang, J., Vala, J., Sastry, S., and Whaley, K. B. 2003. Geometric theory of nonlocal two-qubit operations. Phys. Rev. A 67, 4, 042313. AC.Google ScholarCross Ref
Index Terms
- Synthesis and optimization of reversible circuits—a survey
Recommendations
Reversible circuit synthesis using a cycle-based approach
Reversible logic has applications in various research areas, including signal processing, cryptography and quantum computation. In this article, direct NCT-based synthesis of a given k-cycle in a cycle-based synthesis scenario is examined. To this end, ...
Synthesis of the optimal 4-bit reversible circuits
DAC '10: Proceedings of the 47th Design Automation ConferenceOptimal synthesis of reversible functions is a non-trivial problem. One of the major limiting factors in computing such circuits is the sheer number of reversible functions. Even restricting synthesis to 4-bit reversible functions results in a ...
A Study of Optimal 4-Bit Reversible Toffoli Circuits and Their Synthesis
Optimal synthesis of reversible functions is a nontrivial problem. One of the major limiting factors in computing such circuits is the sheer number of reversible functions. Even restricting synthesis to 4-bit reversible functions results in a huge ...
Comments