nach oben

Erschienen in:

2016 | OriginalPaper | Buchkapitel

Using \(\pi \)DDs for Nearest Neighbor Optimization of Quantum Circuits

verfasst von : Robert Wille, Nils Quetschlich, Yuma Inoue, Norihito Yasuda, Shin-ichi Minato

Erschienen in: Reversible Computation

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Recent accomplishments in the development of quantum circuits motivated research in Computer-Aided Design for quantum circuits. Here, how to consider physical constraints in general and so-called nearest neighbor constraints in particular is an objective of recent developments. Re-ordering the given qubits in a circuit provides thereby a common strategy in order to reduce the corresponding costs. But since this leads to a significant complexity, existing solutions either worked towards a single order only (and, hence, exclude better options) or suffer from high runtimes when considering all possible options. In this work, we provide an alternative which utilizes so-called \(\pi \)DDs for this purpose. They allow for the efficient representation and manipulation of sets of permutations and, hence, provide the ideal data-structure for the considered problem. Experimental evaluations confirm that, by utilizing \(\pi \)DDs, optimal or almost optimal results can be generated in a fraction of the time needed by exact solutions.

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

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Design of p-Valued Deutsch Quantum Gates with Multiple Control Signals and Mixed Polarity

Nächstes Kapitel Circular CNOT Circuits: Definition, Analysis and Application to Fault-Tolerant Quantum Circuits

Nielsen, M., Chuang, I.: Quantum Computation and Quantum Information. Cambridge Univ. Press, Cambridge (2000)MATH

Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: Foundations of Computer Science, pp. 124–134 (1994)

Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Theory of Computing, pp. 212–219 (1996)

Gupta, P., Agrawal, A., Jha, N.K.: An algorithm for synthesis of reversible logic circuits. IEEE Trans. CAD 25(11), 2317–2330 (2006)CrossRef

Maslov, D., Dueck, G.W., Miller, D.M.: Techniques for the synthesis of reversible Toffoli networks. ACM Trans. Des. Autom. Electron. Syst. 12(4), 1–20 (2007)CrossRef

Saeedi, M., Sedighi, M., Zamani, M.S.: A novel synthesis algorithm for reversible circuits. In: International Conference on CAD, pp. 65–68 (2007)

Wille, R., Große, D., Dueck, G., Drechsler, R.: Reversible logic synthesis with output permutation. In: VLSI Design, pp. 189–194 (2009)

Große, D., Wille, R., Dueck, G.W., Drechsler, R.: Exact multiple control Toffoli network synthesis with SAT techniques. IEEE Trans. CAD 28(5), 703–715 (2009)CrossRef

Wille, R., Drechsler, R.: BDD-based synthesis of reversible logic for large functions. In: Design Automation Conference, pp. 270–275 (2009)

10.

Saeedi, M., Sedighi, M., Zamani, M.S.: A library-based synthesis methodology for reversible logic. Microelectron. J. 41(4), 185–194 (2010)CrossRef

11.

Saeedi, M., Zamani, M.S., Sedighi, M., Sasanian, Z.: Reversible circuit synthesis using a cycle-based approach. J. Emerg. Technol. Comput. Syst. 6(4), 1–26 (2010)CrossRef

12.

Soeken, M., Wille, R., Hilken, C., Przigoda, N., Drechsler, R.: Synthesis of reversible circuits with minimal lines for large functions. In: ASP Design Automation Conference, pp. 85–92 (2012)

13.

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)

14.

Miller, D.M., Wille, R., Sasanian, Z.: Elementary quantum gate realizations for multiple-control Toffolli gates. In: International Symposium on Multi-valued Logic, pp. 288–293 (2011)

15.

Sasanian, Z., Wille, R., Miller, D.M.: Realizing reversible circuits using a new class of quantum gates. In: Design Automation Conference, pp. 36–41 (2012)

16.

Wille, R., Soeken, M., Otterstedt, C., Drechsler, R.: Improving the mapping of reversible circuits to quantum circuits using multiple target lines. In: ASP Design Automation Conference, pp. 85–92 (2013)

17.

Shende, V.V., Bullock, S.S., Markov, I.L.: Synthesis of quantum-logic circuits. IEEE Trans. CAD 25(6), 1000–1010 (2006)CrossRef

18.

Hung, W., Song, X., Yang, G., Yang, J., Perkowski, M.: Optimal synthesis of multiple output Boolean functions using a set of quantum gates by symbolic reachability analysis. IEEE Trans. CAD 25(9), 1652–1663 (2006)CrossRef

19.

Große, D., Wille, R., Dueck, G.W., Drechsler, R.: Exact synthesis of elementary quantum gate circuits. Multiple-Valued Logic Soft Comput. 15(4), 270–275 (2009)MathSciNetMATH

20.

Saeedi, M., Arabzadeh, M., Zamani, M.S., Sedighi, M.: Block-based quantum-logic synthesis. Quant. Inf. Comput. 11(3&4), 262–277 (2011)MathSciNetMATH

21.

Niemann, P., Wille, R., Drechsler, R.: Efficient synthesis of quantum circuits implementing Clifford group operations. In: ASP Design Automation Conference, pp. 483–488 (2014)

22.

Saeedi, M., Wille, R., Drechsler, R.: Synthesis of quantum circuits for linear nearest neighbor architectures. Quant. Inf. Proc. 10(3), 355–377 (2011)MathSciNetCrossRefMATH

23.

Khan, M.H.: Cost reduction in nearest neighbour based synthesis of quantum Boolean circuits. Eng. Lett. 16(1), 1–5 (2008)

24.

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: Conference on Quantum, Nano and Micro Technologies, pp. 26–33 (2009)

25.

Shafaei, A., Saeedi, M., Pedram, M.: Optimization of quantum circuits for interaction distance in linear nearest neighbor architectures. In: Design Automation Conference, pp. 41–46 (2013)

26.

Wille, R., Lye, A., Drechsler, R.: Optimal SWAP gate insertion for nearest neighbor quantum circuits. In: ASP Design Automation Conference, pp. 489–494 (2014)

27.

Wille, R., Lye, A., Drechsler, R.: Exact reordering of circuit lines for nearest neighbor quantum architectures. IEEE Trans. CAD 33(12), 1818–1831 (2014)CrossRef

28.

Minato, S.: \(\pi \)DD: a new decision diagram for efficient problem solving in permutation space. In: Conference on Theory and Applications of Satisfiability Testing, pp. 90–104 (2011)

29.

Fowler, A.G., Devitt, S.J., Hollenberg, L.C.L.: Implementation of Shor’s algorithm on a linear nearest neighbour qubit array. Quant. Inf. Comput. 4, 237–245 (2004)MathSciNetMATH

30.

Meter, R.V., Oskin, M.: Architectural implications of quantum computing technologies. J. Emerg. Technol. Comput. Syst. 2(1), 31–63 (2006)CrossRef

31.

Ross, M., Oskin, M.: Quantum computing. Comm. ACM 51(7), 12–13 (2008)CrossRef

32.

Amini, J.M., Uys, H., Wesenberg, J.H., Seidelin, S., Britton, J., Bollinger, J.J., Leibfried, D., Ospelkaus, C., VanDevender, A.P., Wineland, D.J.: Toward scalable ion traps for quantum information processing. New J. Phys. 12(3), 033031 (2010)CrossRef

33.

Kumph, M., Brownnutt, M., Blatt, R.: Two-dimensional arrays of radio-frequency ion traps with addressable interactions. New J. Phys. 13(7), 073043 (2011)CrossRef

34.

Nickerson, N.H., Li, Y., Benjamin, S.C.: Topological quantum computing with a very noisy network and local error rates approaching one percent. Nat. Commun. 4, 1756 (2013)CrossRef

35.

Devitt, S.J., Fowler, A.G., Stephens, A.M., Greentree, A.D., Hollenberg, L.C.L., Munro, W.J., Nemoto, K.: Architectural design for a topological cluster state quantum computer. New J. Phys. 11(8), 083032 (2009)CrossRef

36.

Yao, N.Y., Gong, Z.X., Laumann, C.R., Bennett, S.D., Duan, L.M., Lukin, M.D., Jiang, L., Gorshkov, A.V.: Quantum logic between remote quantum registers. Phys. Rev. A 87, 022306 (2013)CrossRef

37.

Herrera-Martí, D.A., Fowler, A.G., Jennings, D., Rudolph, T.: Photonic implementation for the topological cluster-state quantum computer. Phys. Rev. A 82, 032332 (2010)CrossRef

38.

Jones, N.C., Van Meter, R., Fowler, A.G., McMahon, P.L., Kim, J., Ladd, T.D., Yamamoto, Y.: Layered architecture for quantum computing. Phys. Rev. X 2, 031007 (2012)

39.

Ohliger, M., Eisert, J.: Efficient measurement-based quantum computing with continuous-variable systems. Phys. Rev. A 85, 062318 (2012)CrossRef

40.

DiVincenzo, D.P., Solgun, F.: Multi-qubit parity measurement in circuit quantum electrodynamics. New J. Phys. 15(7), 075001 (2013)CrossRef

41.

Gebser, M., Kaufmann, B., Neumann, A., Schaub, T.: Conflict-driven answer set solving. In: International Joint Conference on Artificial Intelligence, pp. 386–392 (2007)

42.

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 Multi-valued Logic, pp. 220–225 (2008). RevLib is available at http://www.revlib.org

Titel: Using DDs for Nearest Neighbor Optimization of Quantum Circuits
verfasst von: Robert Wille
Nils Quetschlich
Yuma Inoue
Norihito Yasuda
Shin-ichi Minato
Verlag: Springer International Publishing
Buch: Reversible Computation
Print ISBN: 978-3-319-40577-3

Electronic ISBN: 978-3-319-40578-0

Copyright-Jahr: 2016
DOI: https://doi.org/10.1007/978-3-319-40578-0_14

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"