Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Introduction Read chapter Read first chapter

2016 | OriginalPaper | Chapter

2. Background

Authors : Nabila Abdessaied, Rolf Drechsler

Published in: Reversible and Quantum Circuits

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

To keep the book self-contained, this chapter briefly introduces the basics on reversible logic, quantum circuits, and other required concepts. The chapter consists of seven parts: the first section introduces the basic definitions and notations of Boolean functions while the second section reviews existing Boolean decomposition. The third and the fourth sections give an overview of exclusive sum of products and Boolean satisfiability, respectively. The fifth section provides a summary on the principles of reversible logic required later in this book. Similarly, the sixth section gives an introduction on quantum computation and quantum circuits. The later section details the different metrics used as a quality-measure of reversible and quantum realizations. Finally, decision diagrams are reviewed.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now
previous chapter Introduction
next chapter Optimizations and Complexity Analysis on the Reversible Level
Literature
1.
Abdessaied, N., Soeken, M., Wille, R., Drechsler, R.: Exact template matching using Boolean satisfiability. In: International Symposium on Multiple-Valued Logic, pp. 328–333. IEEE, New York (2013)
2.
Abdessaied, N., Wille, R., Soeken, M., Drechsler, R.: Reducing the depth of quantum circuits using additional circuit lines. In: Reversible Computation, pp. 221–233. Springer, New York (2013)
3.
Abdessaied, N., Soeken, M., Drechsler, R.: Quantum circuit optimization by Hadamard gate reduction. In: Reversible Computation, pp. 149–162. Springer, New York (2014)
4.
Abdessaied, N., Soeken, M., Thomsen, M.K., Drechsler, R.: Upper bounds for reversible circuits based on Young subgroups. Inf. Process. Lett. 114 (6), 282–286 (2014)CrossRefMATHMathSciNet
5.
Abdessaied, N., Soeken, M., Drechsler, R.: Technology mapping for quantum circuits using Boolean functional decomposition. In: Reversible Computation, pp. 149–162. Springer, New York (2015)
6.
Abdessaied, N., Soeken, M., Dueck, G.W., Drechsler, R.: Reversible circuit rewriting with simulated annealing. In: International Conference on Very Large Scale Integration, pp. 286–291. IEEE, New York (2015)
7.
Abdessaied, N., Amy, M., Soeken, M., Drechsler, R.: Complexity of reversible circuits and their quantum implementations. Theor. Comput. Sci. 618, 85–106 (2016)CrossRefMATHMathSciNet
8.
Abdessaied, N., Amy, M., Soeken, M., Drechsler, R.: Technology mapping of reversible circuits to Clifford + T quantum circuits. In: International Symposium on Multiple-Valued Logic. IEEE (2016, accepted)
9.
Abdessaied, N., Miller, D.M., Soeken, M., Drechsler, R.: Optimization of NCV and Cliffford + T quantum circuits (in preparation)
10.
Amy, M., Maslov, D., Mosca, M., Roetteler, M.: A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits. Trans. CAD Integr. Circuits Syst. 32 (6), 818–830 (2013)CrossRef
11.
Amy, M., Maslov, D., Mosca, M.: Polynomial-time T-depth optimization of Clifford + T circuits via matroid partitioning. Trans. Comput.-Aided Des. Integr. Circuits Syst. 33 (10), 1476–1489 (2014)CrossRef
12.
Arabzadeh, M., Saeedi, M., Zamani, M.S.: Rule-based optimization of reversible circuits. In: Asia and South Pacific Design Automation Conference, pp. 849–854 (2010)
13.
Arabzadeh, M., Zamani, M., Sedighi, M., Saeedi, M.: Logical-depth-oriented reversible logic synthesis. In: Proceedings of the International Workshop on Logic and Synthesis (2011)MATH
14.
Arabzadeh, M., Saheb Zamani, M., Sedighi, M., Saeedi, M.: Depth-optimized reversible circuit synthesis. Quantum Inf. Process. 12 (4), 1677–1699 (2013)CrossRefMATHMathSciNet
15.
Barenco, A., Bennett, C.H., Cleve, R., DiVinchenzo, D., Margolus, N., Shor, P., Sleator, T., Smolin, J., Weinfurter, H.: Elementary gates for quantum computation. Am. Phys. Soc. 52, 3457–3467 (1995)
16.
Bell, J.S.: Speakable and Unspeakable in Quantum Mechanics: Collected Papers on Quantum Philosophy. Cambridge University Press, Cambridge (2004)CrossRef
17.
18.
Berut, A., Arakelyan, A., Petrosyan, A., Ciliberto, S., Dillenschneider, R., Lutz, E.: Experimental verification of landauer’s principle linking information and thermodynamics. Nature 483, 187–189 (2012)CrossRef
19.
Biere, A., Cimatti, A., Clarke, E., Zhu, Y.: Symbolicv model checking without BDDs. In: Tools and Algorithms for the Construction and Analysis of Systems, vol. 1579, pp. 193–207. Springer, Heidelberg (1999)
20.
Bocharov, A., Svore, K.M.: A depth-optimal canonical form for single-qubit quantum circuits (2012). arXiv preprint arXiv:1206.3223
21.
Bozzano, M., Bruttomesso, R., Cimatti, A., Junttila, T., van Rossum, P., Schulz, S., Sebastiani, R.: The mathsat 3 system. In: Conference on Automated Deduction, pp. 315–321. Springer, New York (2005)
22.
Bravyi, S., Kitaev, A.: Universal quantum computation with ideal Clifford gates and noisy ancillas. Phys. Rev. A 71, 022316 (2005). doi:10.​1103/​PhysRevA.​71.​022316. http://​link.​aps.​org/​doi/​10.​1103/​PhysRevA.​71.​022316
23.
Brummayer, R., Biere, A.: Boolector: an efficient SMT solver for bit-vectors and arrays. In: Tools and Algorithms for the Construction and Analysis of Systems, pp. 174–177. Springer, New York (2009)
24.
Bruttomesso, R., Cimatti, A., Franzén, A., Griggio, A., Sebastiani, R.: The MathSAT 4 SMT solver. In: Computer Aided Verification, pp. 299–303. Springer, New York (2008)
25.
Bryant, R.E.: Graph-based algorithms for Boolean function manipulation. IEEE Trans. Comp. 35 (8), 677–691 (1986)CrossRefMATH
26.
Buhrman, H., Cleve, R., Laurent, M., Linden, N., Schrijver, A., Unger, F.: New limits on fault-tolerant quantum computation. In: Symposium on Foundations of Computer Science, pp. 411–419. IEEE, New York (2006)
27.
Chakrabarti, A., Sur-Kolay, S.: Nearest neighbour based synthesis of quantum Boolean circuits. Eng. Lett. 15, 356–361 (2007)
28.
Chuang, I.L., Yamamoto, Y.: A simple quantum computer (1995). arXiv preprint quant-ph/9505011
29.
Clarke, E.M., Biere, A., Raimi, R., Zhu, Y.: Bounded model checking using satisfiability solving. Formal Methods Syst. Des. 19 (1), 7–34 (2001)CrossRefMATH
30.
Cook, S.A.: The complexity of theorem-proving procedures. In: ACM Symposium on Theory of Computing, pp. 151–158. ACM, New York (1971)
31.
Curtis, H.A.: A New Approach to the Design of Switching Circuits. van Nostrand, Princeton, NJ (1962)
32.
Datta, K., Gokhale, A., Sengupta, I., Rahaman, H.: An esop-based reversible circuit synthesis flow using simulated annealing. In: Applied Computation and Security Systems, pp. 131–144. Springer, New York (2015)
33.
Datta, K., Sengupta, I., Rahaman, H.: A post-synthesis optimization technique for reversible circuits exploiting negative control lines. Trans. Comput. 64 (4), 1208–1214 (2015)CrossRefMathSciNet
34.
Davio, M., Thayse, A., Deschamps, J.P.: Discrete and switching functions. McGraw-Hill, New York (1978)MATH
35.
36.
37.
de Moura, L.M., Bjørner, N.: Z3: an efficient SMT solver. In: Tools and Algorithms for the Construction and Analysis of Systems, pp. 337–340. Springer, New York (2008)
38.
De Vos, A.: Reversible Computing: Fundamentals, Quantum Computing and Applications. Wiley, London (2010)CrossRefMATH
39.
40.
Desoete, B., De Vos, A.: A reversible carry-look-ahead adder using control gates. Integr. VLSI J. 33 (1), 89–104 (2002)CrossRefMATH
41.
Deutsch, D., Jozsa, R.: Rapid solution of problems by quantum computation. R. Soc. Lond. Ser. A: Math. Phys. Sci. 439 (1907), 553–558 (1992)CrossRefMATHMathSciNet
42.
Devitt, S.J.: Classical control of large-scale quantum computers. In: International Conference Reversible Computation, pp. 26–39 (2014)
43.
Dürr, C., Heiligman, M., Høyer, P., Mhalla, M.: Quantum query complexity of some graph problems. In: Automata, Languages and Programming, pp. 481–493. Springer, New York (2004)
44.
45.
Eén, N., Sörensson, N.: An extensible SAT solver. In: SAT 2003. LNCS, vol. 2919, pp. 502–518. Springer, New York (2004)
46.
Fazel, K., Thornton, M., Rice, J.: Esop-based Toffoli gate cascade generation. In: Pacific Rim Conference on Communications, Computers and Signal Processing, pp. 206–209 (2007)
47.
Fowler, A., Devitt, S., Hollenberg, L.: Implementation of shor’s algorithm on a linear nearest neighbour qubit array. Quantum Inf. Comput. 4 (4), 237–251 (2004)MATHMathSciNet
48.
Fowler, A.G., Stephens, A.M., Groszkowski, P.: High-threshold universal quantum computation on the surface code. Phys. Rev. A 80 (5), 052312 (2009)CrossRef
49.
50.
Gaidukov, A.: Algorithm to derive minimum ESOP for 6-variable function. In: International Workshop on Boolean Problems, pp. 141–148 (2002)
51.
Giles, B., Selinger, P.: Exact synthesis of multiqubit Clifford + T circuits. Phys. Rev. A 87 (3), 032332 (2013)CrossRef
52.
Golubitsky, O., Maslov, D.: A study of optimal 4-bit reversible toffoli circuits and their synthesis. Trans. Comput. 61 (9), 1341–1353 (2012)CrossRefMathSciNet
53.
Gosset, D., Kliuchnikov, V., Mosca, M., Russo, V.: An algorithm for the T-count. Quantum Inf. Comput. 14 (15–16), 1261–1276 (2014)MathSciNet
54.
Große, D., Wille, R., Dueck, G.W., Drechsler, R.: Exact multiple control Toffoli network synthesis with SAT techniques. Trans. Comput.-Aided Des. Integr. Circuits Syst. 28 (5), 703–715 (2009)CrossRef
55.
Große, D., Wille, R., Dueck, G.W., Drechsler, R.: Exact synthesis of elementary quantum gate circuits. J. Multiple-Valued Log. Soft Comput. 15 (4), 283–300 (2009)MATHMathSciNet
56.
Grover, L.K.: A fast quantum mechanical algorithm for database search. In: The Twenty-Eighth Annual ACM Symposium on Theory of Computing, pp. 212–219. ACM, New York (1996)
57.
Haedicke, F., Frehse, S., Fey, G., Große, D., Drechsler, R.: metaSMT: focus on your application not on solver integration. In: International Workshop on Design and Implementation of Formal Tools and Systems (2011)
58.
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., Blatt, R.: Scalable multiparticle entanglement of trapped ions. Nature 438, 643–646 (2005)CrossRef
59.
Hirata, Y., Nakanishi, M., Yamashita, S., Nakashima, Y.: An efficient method to convert arbitrary quantum circuits to ones on a linear nearest neighbor architecture. In: International Conference on Quantum, Nano and Micro Technologies, pp. 26–33. IEEE, New York (2009)
60.
Hirayama, T., Nishitani, Y.: Exact minimization of AND-EXOR expressions of practical benchmark functions. J. Circuits Syst. Comput. 18 (3), 465–486 (2009)CrossRef
61.
Jones, N.C.: Logic synthesis for fault-tolerant quantum computers (2013). arXiv preprint arXiv:1310.7290
62.
Kane, B.: A silicon-based nuclear spin quantum computer. Nature 393, 133–137 (1998)CrossRef
63.
Khan, M.H.A.: Cost reduction in nearest neighbour based synthesis of quantum Boolean circuits. Eng. Lett. 16, 1–5 (2008)
64.
65.
Kliuchnikov, V., Maslov, D., Mosca, M.: Fast and efficient exact synthesis of single-qubit unitaries generated by Clifford and T gates. Quantum Inf. Comput. 13 (7–8), 607–630 (2013)MathSciNet
66.
Knill, E., Laflamme, R., Milburn, G.J.: A scheme for efficient quantum computation with linear optics. Nature 409 (1), 46–52 (2001)CrossRefMATH
67.
Knuth, D.E.: The Art of Computer Programming, vol. 4A. Addison-Wesley, Upper Saddle River, NJ (2011)
68.
Laforest, M., Simon, D., Boileau, J.C., Baugh, J., Ditty, M., Laflamme, R.: Using error correction to determine the noise model. Phys. Rev. A 75, 133–137 (2007)CrossRef
69.
70.
Larrabee, T.: Test pattern generation using Boolean satisfiability. Trans. Comput.-Aided Des. Integr. Circuits Syst. 11 (1), 4–15 (1992)CrossRef
71.
Lindgren, P., Drechsler, R., Becker, B.: Improved minimization methods of pseudo kronecker expressions for multiple output functions. In: International Symposium on Circuits and Systems, vol. 6, pp. 187–190 (1998)
72.
Marques-Silva, J., Sakallah, K.: GRASP: A search algorithm for propositional satisfiability. Trans. Comput. 48 (5), 506–521 (1999)CrossRefMathSciNet
73.
Maslov, D.: Reversible logic synthesis benchmarks page. Available at http://​webhome.​cs.​uvic.​ca~dmaslov/​.​ Last accessed Jan 2011
74.
Maslov, D.: Reversible logic synthesis. Ph.D. thesis, University of New Brunswick (2003)
75.
Maslov, D., Dueck, G.: Improved quantum cost for n-bit toffoli gates. Electron. Lett. 39, 1790 (2003)CrossRef
76.
Maslov, D., Dueck, G.W.: Reversible cascades with minimal garbage. Trans. Comput.-Aided Des. Integr. Circuits Syst. 23 (11), 1497–1509 (2004)CrossRef
77.
Maslov, D., Miller, D.M.: Comparison of the cost metrics through investigation of the relation between optimal NCV and optimal NCT three-qubit reversible circuits. IET Comput. Digit. Tech. 1 (2), 98–104 (2007)CrossRef
78.
Maslov, D., Dueck, G., Miller, D.: Simplification of toffoli networks via templates. In: Symposium on Integrated Circuits and Systems Design, pp. 53–58 (2003)
79.
Maslov, D., Miller, D.M., Dueck, G.W.: Fredkin/Toffoli templates for reversible logic synthesis. In: International Conference on Computer Aided Design, pp. 256–261 (2003)
80.
Maslov, D., Dueck, G.W., Miller, D.M.: Toffoli network synthesis with templates. Trans. Comput.-Aided Des. Integr. Circuits Syst. 24 (6), 807–817 (2005)CrossRef
81.
Maslov, D., Young, C., Dueck, G.W., Miller, D.M.: Quantum circuit simplification using templates. In: Design Automation and Test in Europe, pp. 1208–1213 (2005)
82.
Maslov, D., Dueck, G.W., Miller, D.M.: Techniques for the synthesis of reversible toffoli networks. Trans. Des. Autom. Electron. Syst. 12 (4), 42 (2007)CrossRef
83.
Maslov, D., Dueck, G., Miller, D., Negrevergne, C.: Quantum circuit simplification and level compaction. Trans. Comput.-Aided Des. Integr. Circuits Syst. 27 (3), 436–444 (2008)CrossRef
84.
Meter, R.V., Oskin, M.: Architectural implications of quantum computing technologies. ACM J. Emerg. Technol. Comput. Syst. 2 (1), 31–63 (2006)CrossRef
85.
Miller, D.M., Dueck, G.W.: Spectral techniques for reversible logic synthesis. In: International Symposium on Representations and Methodology of Future Computing Technology, pp. 56–62 (2003)
86.
Miller, D.M., Sasanian, Z.: Lowering the quantum gate cost of reversible circuits. In: International Midwest Symposium on Circuits and Systems, pp. 260–263. IEEE, New York (2010)
87.
Miller, D., Thornton, M.: QMDD: a decision diagram structure for reversible and quantum circuits. In: International Symposium on Multiple-Valued Logic, pp. 30–30 (2006)
88.
Miller, D.M., Maslov, D., Dueck, G.W.: A transformation based algorithm for reversible logic synthesis. In: Design Automation Conference, pp. 318–323 (2003)
89.
Miller, D.M., Wille, R., Dueck, G.W.: Synthesizing reversible circuits for irreversible functions. In: Euromicro Conference on Digital System Design, Architectures, Methods and Tools, pp. 749–756. IEEE, New York (2009)
90.
Miller, D.M., Wille, R., Drechsler, R.: Reducing reversible circuit cost by adding lines. In: International Symposium on Multiple-Valued Logic, pp. 217–222. IEEE, New York (2010)
91.
Miller, D.M., Wille, R., Sasanian, Z.: Elementary quantum gate realizations for multiple-control Toffolli gates. In: International Symposium on Multiple-Valued Logic, pp. 217–222. IEEE, New York (2011)
92.
Miller, D.M., Soeken, M., Drechsler, R.: Mapping NCV circuits to optimized Clifford + T circuits. In: Reversible Computation, pp. 163–175. Springer, New York (2014)
93.
Mishchenko, A., Perkowski, M.: Fast heuristic minimization of exclusive-sums-of-products. In: International Workshop on Applications of the Reed-Muller Expansion in Circuit Design, pp. 242–250 (2001)
94.
Mishchenko, A., Steinbach, B., Perkowski, M.A.: An algorithm for bi-decomposition of logic functions. In: Design Automation Conference, pp. 103–108 (2001)
95.
Moskewicz, M., Madigan, C., Zhao, Y., Zhang, L., Malik, S.: Chaff: engineering an efficient SAT solver. In: Design Automation Conference, pp. 530–535 (2001)
96.
97.
Nakahara, M., Ohmi, T.: Quantum computing: from linear algebra to physical realizations. CRC Press, West Palm Beach, FL (2008)CrossRefMATH
98.
Nielsen, M., Chuang, I.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000)MATH
99.
Niemann, P., Wille, R., Drechsler, R.: On the Q in QMDDs: efficient representation of quantum functionality in the QMDD data-structure. In: Reversible Computation, pp. 125–140. Springer, New York (2013)
100.
Patra, P., Fussell, D.S.: On efficient adiabatic design of MOS circuits. In: Information, Physics, and Computation. Citeseer (1996)
101.
102.
Prasad, M.R., Biere, A., Gupta, A.: A survey of recent advances in SAT-based formal verification. Int. J. Softw. Tools Technol. Transf. 7 (2), 156–173 (2005)CrossRef
103.
Rahman, M.M., Dueck, G.W.: An algorithm to find quantum templates. In: Congress on Evolutionary Computation, pp. 1–7. IEEE, New York (2012)
104.
Rahman, M.M., Dueck, G.W.: Properties of quantum templates. In: Reversible Computation, pp. 125–137. Springer, New York (2013)
105.
Rahman, M.M., Dueck, G.W., Horton, J.: Exact template matching using graphs. Tech. rep., Technical Report TR13–224, Faculty of Computer Science, University of New Brunswick (2013)
106.
Rahman, M.M., Dueck, G.W., Horton, J.D.: An algorithm for quantum template matching. ACM J. Emerg. Technol. Comput. Syst. 11 (3), 31 (2014)CrossRef
107.
Saeedi, M., Markov, I.: Synthesis and optimization of reversible circuits-a survey. ACM Comput. Surv. 45 (2), 21 (2013)CrossRefMATH
108.
Saeedi, M., Zamani, M.S., Sedighi, M., Sasanian, Z.: Reversible circuit synthesis using a cycle-based approach. J. Emerg. Technol. 6 (4), 13 (2010)
109.
Sarkar, M., Ghosal, P., Mohanty, S.P.: Reversible circuit synthesis using ACO and SA based quine-McCluskey method. In: Midwest Symposium on Circuits and Systems, pp. 416–419 (2013)
110.
Sasanian, Z.: Technology mapping and optimization for reversible and quantum. Ph.D. thesis, University of Victoria (2012)
111.
Sasanian, Z., Miller, D.M.: NCV realization of MCT gates with mixed controls. In: Pacific Rim Conference on Communications, Computers and Signal Processing, pp. 567–571. IEEE, New York (2011)
112.
Sasanian, Z., Miller, D.M.: Reversible and quantum circuit optimization: a functional approach. In: Reversible Computation, pp. 112–124. Springer, New York (2013)
113.
Sasao, T.: AND-EXOR expressions and their optimization. In: Sasao, T. (ed.) Logic Synthesis and Optimization, pp. 287–312. Kluwer Academic Publisher, Dordecht (1993)CrossRef
114.
Sasao, T.: An exact minimization of AND-EXOR expressions using BDDs. In: International Workshop on Applications of the Reed-Muller Expansion in Circuit Design, pp. 91–98 (1993)
115.
Sasao, T.: An exact minimization of AND-EXOR expressions using reduced covering functions. In: International Symposium on the Synthesis and Simulation Meeting and International Interchange, pp. 374–383 (1993)
116.
Sasao, T.: EXMIN2: a simplification algorithm for exclusive-OR-sum-of-products expressions for multiple-valued-input two-valued-output functions. IEEE Trans. Comput. Aided Des. 12 (5), 621–632 (1993)CrossRef
117.
Sasao, T., Matsuura, M.: DECOMPOS: an integrated system for functional decomposition. In: International Workshop on Logic Synthesis, pp. 471–477 (1998)
118.
Scott, N., Dueck, G., Maslov, D.: Improving template matching for minimizing reversible toffoli cascades. In: International Reed-Muller Workshop (2005)
119.
Scott, N., Dueck, G., Maslov, D.: Improving template matching for minimizing reversible toffoli cascades. In: International Symposium on Representations and Methodology of Future Computing Technologies (2005)
120.
Selinger, P.: Quantum circuits of T-depth one. Phys. Rev. A 87 (4), 042302 (2013)CrossRef
121.
Shannon, C.E.: A symbolic analysis of relay and switching circuits. Trans. Am. Inst. Electr. Eng. 57 (38–80), 713–723 (1938)CrossRef
122.
Shende, V.V., Prasad, A.K., Markov, I.L., Hayes, J.P.: Synthesis of reversible logic circuits. Trans. Comput.-Aided Des. Integr. Circuits Syst. 22 (6), 710–722 (2003)CrossRef
123.
Shi, J., Fey, G., Drechsler, R., Glowatz, A., Hapke, F., Schloffel, J.: PASSAT: efficient sat-based test pattern generation for industrial circuits. In: Computer Society Annual Symposium on VLSI, pp. 212–217. IEEE, New York (2005)
124.
Shiou-An, W., Chin-Yung, L., Sy-Yen, K., et al.: An XQDD-based verification method for quantum circuits. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 91 (2), 584–594 (2008)
125.
Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. Found. Comput. Sci. 124–134 (1994)
126.
Smith, A., Veneris, A., Fahim Ali, M., Viglas, A.: Fault diagnosis and logic debugging using Boolean satisfiability. Trans. Comput.-Aided Des. Integr. Circuits Syst. 24 (10), 1606–1621 (2005)CrossRef
127.
Soeken, M., Thomsen, M.K.: White dots do matter: rewriting reversible logic circuits. In: Reversible Computation, pp. 196–208. Springer, New York (2013)
128.
Soeken, M., Wille, R., Dueck, G., Drechsler, R.: Window optimization of reversible and quantum circuits. In: International Symposium on Design and Diagnostics of Electronic Circuits and Systems, pp. 341–345 (2010)
129.
Soeken, M., Frehse, S., Wille, R., Drechsler, R.: Revkit: a toolkit for reversible circuit design. J. Multiple-Valued Log. Soft Comput. 18 (1) (2012). RevKit is available at http://​www.​revkit.​org
130.
Soeken, M., Sasanian, Z., Wille, R., Miller, D.M., Drechsler, R.: Optimizing the mapping of reversible circuits to four-valued quantum gate circuits. In: International Symposium on Multiple-Valued Logic, pp. 173–178. IEEE, New York (2012)
131.
Soeken, M., Wille, R., Hilken, C., Przigoda, N., Drechsler, R.: Synthesis of reversible circuits with minimal lines for large functions. In: Asia and South Pacific Design Automation Conference, pp. 85–92. IEEE, New York (2012)
132.
Soeken, M., Wille, R., Otterstedt, C., Drechsler, R.: A synthesis flow for sequential reversible circuits. In: International Symposium on Multiple-Valued Logic, pp. 299–304. IEEE, New York (2012)
133.
Soeken, M., Miller, D.M., Drechsler, R.: Quantum circuits employing roots of the Pauli matrices. Phys. Rev. A 88, 042322 (2013)CrossRef
134.
Soeken, M., Abdessaied, N., Drechsler, R.: A framework for reversible circuit complexity. In: International Workshop on Boolean Problems, pp. 123–128 (2014)
135.
Soeken, M., Tague, L., Dueck, G.W., Drechsler, R.: Ancilla-free synthesis of large reversible functions using binary decision diagrams. J. Symb. Comput. 73, 1–26 (2016)CrossRefMATHMathSciNet
136.
Soeken, M., Wille, R., Keszocze, O., Miller, D.M., Drechsler, R.: Embedding of large Boolean functions for reversible logic. ACM J. Emerg. Technol. Comput. Syst. 12 (4), 41 (2015)CrossRef
137.
Stergiou, S., Papakonstantinou, G.: Exact minimization of esop expressions with less than eight product terms. J. Circuits Syst. Comput. 13 (01), 1–15 (2004)CrossRef
138.
Szyprowski, M., Kerntopf, P.: Low quantum cost realization of generalized Peres and Toffoli gates with multiple-control signals. In: Conference on Nanotechnology, pp. 802–807. IEEE, New York (2013)
139.
Toffoli, T.: Reversible computing. In: de Bakker, W., van Leeuwen, J. (eds.) Automata, Languages and Programming, p. 632. Springer, New York (1980). Technical Memo MIT/LCS/TM-151, MIT Lab. for Comput. Sci.
140.
Van Rentergem, Y., De Vos, A., Storme, L.: Implementing an arbitrary reversible logic gate. J. Phys. A Math. Gen. 38 (16), 3555–3577 (2005)CrossRefMATHMathSciNet
141.
Vandersypen, L.M.K., Steffen, M., Breyta, G., Yannoni, C.S., Sherwood, M.H., Chuang, I.L.: Experimental realization of Shor’s quantum factoring algorithm using nuclear magnetic resonance. Nature 414, 883 (2001)CrossRef
142.
Vemuri, N., Kalla, P., Tessier, R.: BDD-based logic synthesis for LUT-based FPGAs. ACM Trans. Des. Autom. Electr. Syst. 7 (4), 501–525 (2002)CrossRef
143.
Viamontes, G.F., Markov, I.L., Hayes, J.P.: Quantum Circuit Simulation. Springer, Dordrecht/Heidelberg/London/New York (2009)CrossRefMATH
144.
Weinstein, Y.S.: Non-fault tolerant t-gates for the [7,1,3] quantum error correction code. Am. Phys. Soc. 87 (3), 032320, 6 (2013).
145.
Wille, R., Drechsler, R.: BDD-based synthesis of reversible logic for large functions. In: Design Automation Conference, pp. 270–275. ACM, New York (2009)
146.
Wille, R., Große, D.: Fast exact Toffoli network synthesis of reversible logic. In: International Conference on Computer Aided Design, pp. 60–64 (2007)
147.
Wille, R., Große, D., Teuber, L., Dueck, G.W., Drechsler, R.: RevLib: an online resource for reversible functions and reversible circuits. In: International Symposium on Multiple-Valued Logic, pp. 220–225. IEEE, New York (2008). RevLib is available at http://​www.​revlib.​org
148.
Wille, R., Soeken, M., Drechsler, R.: Reducing the number of lines in reversible circuits. In: Design Automation Conference, pp. 647–652. IEEE, New York (2010)
149.
Wille, R., Soeken, M., Przigoda, N., Drechsler, R.: Exact synthesis of Toffoli gate circuits with negative control lines. In: International Symposium on Multiple-Valued Logic, pp. 69–74. IEEE, New York (2012)
150.
Wille, R., Soeken, M., Otterstedt, C., Drechsler, R.: Improving the mapping of reversible circuits to quantum circuits using multiple target lines. In: Asia and South Pacific Design Automation Conference, pp. 145–150 (2013)
151.
Wille, R., Lye, A., Drechsler, R.: Considering nearest neighbor constraints of quantum circuits at the reversible circuit level. Quantum Inf. Process. 13 (2), 185–199 (2014)CrossRefMATH
152.
Wille, R., Soeken, M., Miller, D.M., Drechsler, R.: Trading off circuit lines and gate costs in the synthesis of reversible logic. Integr. VLSI J. 47 (2), 284–294 (2014)CrossRef
153.
Yamashita, S., Markov, I.L.: Fast equivalence-checking for quantum circuits. In: IEEE/ACM International Symposium on Nanoscale Architectures, pp. 23–28. IEEE, New York (2010)
154.
Yamashita, S., Minato, S.i., Miller, D.M.: Synthesis of semi-classical quantum circuits. J. Multiple-Valued Log. Soft Comput. 18 (1) (2012)
155.
Yanushkevich, S.N., Miller, D.M., Shmerko, V.P., Stankovic, R.S.: Decision Diagram Techniques for Micro-and Nanoelectronic Design Handbook. CRC Press, West Palm Beach, FL (2005)CrossRef
156.
Zhang, J., Sinha, S., Mishchenko, A., Brayton, R., Chrzanowska-Jeske, M.: Simulation and satisfiability in logic synthesis. In: Proceedings of Workshop on Logic and Synthesis, pp. 161–168 (2005)
157.
Zhirnov, V.V., Cavin, R.K., Hutchby, J.A., Bourianoff, G.I.: Limits to binary logic switch scaling-a gedanken model. IEEE 91 (11), 1934–1939 (2003)CrossRef
Metadata
Title
Background
Authors
Nabila Abdessaied
Rolf Drechsler
Copyright Year
2016
Book
Reversible and Quantum Circuits

Print ISBN: 978-3-319-31935-3

Electronic ISBN: 978-3-319-31937-7

Copyright Year: 2016

DOI
https://doi.org/10.1007/978-3-319-31937-7_2