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
Quantum Information Processing
Erschienen in: Quantum Information Processing 10/2013

01.10.2013

Line ordering of reversible circuits for linear nearest neighbor realization

verfasst von: Mohammad AlFailakawi, Laila AlTerkawi, Imtiaz Ahmad, Suha Hamdan

Erschienen in: Quantum Information Processing | Ausgabe 10/2013

Einloggen

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

search-config
loading …

Abstract

Real quantum computing technologies have different restrictions and constraints which need to be considered during circuit synthesis. In certain technologies, only physically adjacent qubits can interact, which restricts their realizations to only linear nearest neighbor (LNN) architecture. In this work, we formulate the line ordering problem in LNN architecture as task assignment problem to find a mapping (permutation) between task graph and processor graph with minimum cost. We propose two different approaches, a greedy heuristic and a meta-heuristic algorithm based on Harmony Search to solve the task assignment problem. Experimental results show that our algorithms were able to reduce the quantum cost of benchmark circuits by approximately 30 % on average. Moreover, the proposed algorithms were compared to one recently proposed ordering algorithm and were found to further improve the cost by approximately 16 %.
Vorheriger Artikel The monogamy relation and quantum phase transition in one-dimensional anisotropic XXZ model
Nächster Artikel Testing Hardy’s ladder proof of nonlocality by joint measurements of qubits

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
Literatur
1.
Ahmad, I., Mohammad, MGh, Salman, A.A., Hamdan, S.A.: Broadcast scheduling in packet radio networks using harmony search algorithm. Expert Syst. Appl. 39(1), 1526–1535 (2012)CrossRef
2.
Alia, O.M., Mandava, R.: The variants of the harmony search algorithm: an overview. Artif. Intell. Rev. 36(1), 49–68 (2011)CrossRef
3.
4.
Arabzadeh, M., Saeedi, M., Zamani, M. S.: Rule-based optimization of reversible circuits. In: 15th Asia and South Pacific Design Automation Conference (ASP-DAC), pp. 849–854 (2010)
5.
Chakrabarti, A., Sur-Kolay, S.: Nearest neighbour based synthesis of quantum boolean circuits. Eng. Lett. 15(2), 356–361 (2007)
6.
7.
Cheung, D., Maslov, D., Severini, S.: Translation techniques between quantum circuit architectures. In: Workshop on Quantum Information Processing (2007)
8.
Choi, B.S., Meter, R.V.: On the effect of quantum interaction distance on quantum addition circuits. ACM J. Emerg. Technol. Comput. Syst. 7(3), 11:1–11:17 (2011)
9.
Donald, J., Jha, N.K.: Reversible logic synthesis with fredkin and peres gates. ACM J. Emerg. Technol. Comput. Syst. 4(1), 2:1–2:19 (2008)
10.
Drechsler, R., Wille, R.: Reversible circuits: Recent accomplishments and future challenges for an emerging technology. In: Progress in VLSI Design and Test, volume LNCS 7373, pp. 383–392 (2012)
11.
Fazel, K., Thornton, M.A., Rice, J.E.: Esop-based toffoli gate cascade generation. In: IEEE Pacific Rim Conference on Communications, Computers and Signal Processing, pp. 206–209 (2007)
12.
Feynman, R.P.: Simulating Physics with Computers. Westview Press, Boulder (2002)
13.
Fowler, A.G., Hill, C.D., Hollenberg, L.C.L.: Quantum error correction on linear nearest neighbor qubit arrays. Phys. Rev. A 69(4), 042314.1042314.4 (2004)
14.
Geem, Z.W.: Novel derivative of harmony search algorithm for discrete design variables. Appl. Math. Comput. 199(1), 223–230 (2008)MathSciNetCrossRefMATH
15.
Geem, Z.W.: Music-Inspired Harmony Search Algorithm: Theory and Applications. Springer, Berlin (2009)CrossRef
16.
Geem, Z.W., Kim, J., Loganathan, G.: A new heuristic optimization algorithm. Simulation 76(2), 60–68 (2001)CrossRef
17.
Golubitsky, O., Maslov, D.: A study of optimal 4-bit reversible toffoli circuits and their synthesis. IEEE Trans. Comput. 61(9), 1341–1353 (2012)MathSciNetCrossRef
18.
Grover, L.: Quantum computers can search arbitrarily large databases by a single query. Phys. Rev. Lett. 79(23), 4709–4712 (1997)ADSCrossRef
19.
Gupta, P., Agrawal, A., Jha, N.K.: An algorithm for synthesis of reversible logic circuits. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 25(11), 2317–2330 (2006)CrossRef
20.
Haffner, H., Hansel, W., Roos, C. F., Benhelm, J., Chek-al-kar, D., Chwalla, M., Korber, T., Rapol, U. D., Riebe, M., Schmidt, P. O., Becher, C., Guhne, O., Dur, W., Blatt, R.: Scalable multiparticle entanglement of trapped ions. Nature 438(7068), 643–646, 12 (2005)
21.
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: Third International Conference on Quantum, Nano and Micro Technologies, pp. 26–33 (2009)
22.
Hirata, Y., Nakanishi, M., Yamashita, S., Nakashima, Y.: An efficient conversion of quantum circuits to a linear nearest neighbor architecture. Quantum Inf. Comput. 11(1), 142–166 (2011)MathSciNetMATH
23.
24.
Kassal, I., Whitfield, J.D., Perdomo-Ortiz, A., Yung, M.H., Aspuru-Guzik, A.: Simulating chemistry using quantum computers. Annu. Rev. Phys. Chem. 62(1), 185–207 (2011)ADSCrossRef
25.
Kerntopf, P.: A new heuristic algorithm for reversible logic synthesis. In: 41st Design Automation Conference, pp. 834–837 (2004)
26.
Kerntopf, P., Perkowski, M., Podlaski, K.: Synthesis of reversible circuits: A view on the state-of-the-art. In: 12th IEEE Conference on Nanotechnology (IEEE-NANO), pp. 1–6, (2012)
27.
Khan, M.H.: Cost reduction in nearest neighbour based synthesis of quantum boolean circuits. Eng. Lett. 16, 1–5 (2008)ADS
28.
Khan, M.H.A., Perkowski, M.A.: Multi-output esop synthesis with cascades of new reversible gate family. In: International Symposium On Representations and Methodology of Future Compo Technology (2003)
29.
Kutin, S.A.: Shor’s algorithm on a nearest-neighbor machine. In: Asian Conference on Quantum Information Science (AQIS) (2007)
30.
Lee, C. H., Lee, D., Kim, M.: Optimal task assignment in linear networks. IEEE Trans. Comput. 41(7), 877–880 (1992)
31.
Lee, S., Lee, S., Kim, T., Lee, J., Biamonte, J., Perkowski, M.: The cost of quantum gate primitives. J. Multivalued Log. Soft Comput. 12, 5–6 (2006)MathSciNet
32.
Magniez, F., Santha, M., Szegedy, M.: Quantum algorithms for the triangle problem. In: 16th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1109–1117 (2005)
33.
Maslov, D., Dueck, G. W., Miller, D. M.: Techniques for the synthesis of reversible toffoli networks. ACM Trans. Des. Autom. Electron. Syst. 12(4), 42:142:28 (2007)
34.
Meter, R.V., Oskin, M.: Architectural implications of quantum computing technologies. ACM J. Emerg. Technol. Comput. Syst. 2(1), 31–63 (2006)CrossRef
35.
Miller, D.M., Maslov, D., Dueck, G.W.: A transformation based algorithm for reversible logic synthesis. In: 40th annual Design Automation Conference (2003)
36.
Negrevergne, C., Mahesh, T.S., Ryan, C.A., Ditty, M., Cyr-Racine, F., Power, W., Boulant, N., Havel, T., Cory, D.G., Laflamme, R.: Benchmarking quantum control methods on a 12-qubit system. Phys. Rev. Lett. 96, 170501 (2006)ADSCrossRef
37.
Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2002)
38.
Patel, K. N., Markov, I. L., Hayes, J. P.: Efficient synthesis of linear reversible circuits. In: International Workshop on Logic Synthesis (IWLS), pp. 4470–4477 (2004)
39.
Patel, K.N., Markov, I.L., Hayes, J.P.: Optimal synthesis of linear reversible circuits. Quantum Inf. Comput. 8(3), 282–294 (2008)MathSciNetMATH
40.
Perkowski, M., Lukac, M., Shah, D., Kameyama, M.: Synthesis of quantum circuits in linear nearest neighbor model using positive davio lattices. Electron. Energ. 24(1), 71–87 (2011)CrossRef
41.
Saeedi, M., Markov, I. L.: Synthesis and optimization of reversible circuits—a survey. ACM Comput. Surv. 45(2), 21:1–21:34 (2013)
42.
Saeedi, M., Wille, R., Drechsler, R.: Synthesis of quantum circuits for linear nearest neighbor architectures. Quantum Inf. Process. 10(3), 355–377 (2011)MathSciNetCrossRefMATH
43.
Saeedi, M., Zamani, M.S., Sedighi, M., Sasanian, Z.: Reversible circuit synthesis using a cycle-based approach. ACM J. Emerg. Technol. Comput. Syst. 6(4), 1–26 (2010)CrossRef
44.
Salman, A.A., Ahmad, I., Al-Rushood, H., Hamdan, S.: Solving the task assignment problem using harmony search algorithm. Evolv. Syst. (2012)
45.
Schaeffer, B., Perkowski, M.: Linear reversible circuit synthesis in the linear nearest-neighbor model. In: 42nd IEEE International Symposium on, Multiple-Valued Logic, pp. 157–160 (2012)
46.
Shende, V.V., Bullock, S.S., Markov, I.L.: Synthesis of quantum-logic circuits. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 25(6), 1000–1010 (2006)CrossRef
47.
Shende, V.V., Markov, I.L.: On the cnot-cost of toffoli gates. Quantum Inf. Comput. 9(5), 461–486 (2009)MathSciNetMATH
48.
Shende, V.V., Prasad, A.K., Markov, I.L., Hayes, J.P.: Synthesis of reversible logic circuits. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 22(6), 710–722 (2003)CrossRef
49.
Shor, P.: Polynomial time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484–1509 (1997)MathSciNetCrossRefMATH
50.
Takahashi, Y., Kunihiro, N., Ohta, K.: The quantum fourier transform on a linear nearest neighbor architecture. Quantum Inf. Comput. 7(4), 383–391 (2007)MathSciNetMATH
51.
Wang, D., Sun, S., Chen, H.: Matrix-based algorithm for 4-qubit reversible logic circuits synthesis. Energy Procedia 13, 365–371 (2011)MathSciNetCrossRef
52.
Wille, R., Drechsler, R.: Bdd-based synthesis of reversible logic for large functions. In: 46th Annual Design Automation Conference, pp. 270–275 (2009)
53.
Wille, R., Grosse, D., Teuber, L., Dueck, G. W., Drechsler, R.: Revlib: An online resource for reversible functions and reversible circuits. In: 38th IEEE International Symposium on Multiple Valued Logic, pp. 220–225 (2008)
54.
Wille, R., Saeedi, M., Drechsler, R.: Synthesis of reversible functions beyond gate count and quantum cost. In: International Workshop on Logic Synthesis (IWLS) (2009)
55.
Younes, A., Miller, J.F.: Representation of boolean quantum circuits as reed muller expansions. Int. J. Electron. 91(7), 431–444 (2004)CrossRef
Metadaten
Titel
Line ordering of reversible circuits for linear nearest neighbor realization
verfasst von
Mohammad AlFailakawi
Laila AlTerkawi
Imtiaz Ahmad
Suha Hamdan
Publikationsdatum
01.10.2013
Verlag
Springer US
Erschienen in
Quantum Information Processing / Ausgabe 10/2013
Print ISSN: 1570-0755
Elektronische ISSN: 1573-1332
DOI
https://doi.org/10.1007/s11128-013-0601-1

Weitere Artikel der Ausgabe 10/2013

Quantum Information Processing 10/2013 Zur Ausgabe

OriginalPaper

Fault tolerant quantum key distributions using entanglement swapping of GHZ states over collective-noise channels

OriginalPaper

An efficient quantum search engine on unsorted database

OriginalPaper

A quantum physical design flow using ILP and graph drawing

OriginalPaper

Stationary quantum correlations in Tavis–Cumming model induced by continuous dephasing process

BriefCommunication

Comment on “Dynamic quantum secret sharing”

OriginalPaper

Random quantum evolution

Neuer Inhalt

    Bildnachweise