Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Introduction Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

5. Optimizations and Complexity Analysis on the Quantum Level

verfasst von : Nabila Abdessaied, Rolf Drechsler

Erschienen in: Reversible and Quantum Circuits

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

After mapping a reversible circuit into a functionally equivalent quantum circuit, the resulting circuit is not optimal with respect to considered cost metrics due to the existing non-optimal synthesis as well as mapping approaches, particularly for large circuits. Moreover, physical developments for emerging technologies constantly lead to new constraints, e.g., the depth and the NNC. For that reason, post-mapping optimizations are applied to optimize the value of the cost metrics with respect to the used library. In particular, many existing optimization methods target the reduction of the quantum cost and the depth [83, 128] of quantum circuits. In the following section, related work is summarized. Afterwards, a depth optimization approach is given in Sect. 5.2. Then, in Sect. 5.3 an algorithm for reducing the quantum cost is explained. Finally a study of the complexity of quantum implementations is given in Sect. 5.4.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren
Vorheriges Kapitel Optimization and Complexity Analysis on the Mapping Level
Nächstes Kapitel Conclusions
Literatur
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)
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.
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)
39.
De Vos, A., Van Rentergem, Y.: Young subgroups for reversible computers. Adv. Math. Commun. 2 (2), 183–200 (2008)
40.
Desoete, B., De Vos, A.: A reversible carry-look-ahead adder using control gates. Integr. VLSI J. 33 (1), 89–104 (2002)
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)
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)
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)
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
Metadaten
Titel
Optimizations and Complexity Analysis on the Quantum Level
verfasst von
Nabila Abdessaied
Rolf Drechsler
Copyright-Jahr
2016
Buch
Reversible and Quantum Circuits

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

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

Copyright-Jahr: 2016

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

Neuer Inhalt

    Bildnachweise