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:
Tools for Quantum and Reversible Circuit Compilation Read chapter Read first chapter

2017 | OriginalPaper | Chapter

Exact Global Reordering for Nearest Neighbor Quantum Circuits Using A\(^{*}\)

Authors : Alwin Zulehner, Stefan Gasser, Robert Wille

Published in: Reversible Computation

Publisher: Springer International Publishing

Log in

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

search-config
loading …

Abstract

Since for certain realizations of quantum circuits only adjacent qubits may interact, qubits have to be frequently swapped – leading to a significant overhead. Therefore, optimizations such as exact global reordering have been proposed, where qubits are reordered such that the overall number of swaps is minimal. However, to guarantee minimality all n! possible permutations of qubits have to be considered in the worst case – which becomes intractable for larger circuits. In this work, we tackle the complexity of exact global reordering using an A* search algorithm. The sophisticated heuristics for the search algorithm proposed in this paper allow for solving the problem in a much more scalable fashion. In fact, experimental evaluations show that the proposed approach is capable of determining the best order of the qubits for circuits with up to 25 qubits, whereas the recent state-of-the-art already reaches its limits with circuits composed of 10 qubits.

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

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!

inform now
previous chapter Automatic Test Pattern Generation for Multiple Missing Gate Faults in Reversible Circuits
next chapter Improved Decomposition of Multiple-Control Ternary Toffoli Gates Using Muthukrishnan-Stroud Quantum Gates
Literature
1.
Nielsen, M., Chuang, I.: Quantum Computation and Quantum Information. Cambridge University Press, New York (2000)MATH
2.
Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484–1509 (1997)MathSciNetCrossRefMATH
3.
Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Symposium on the Theory of Computing, pp. 212–219 (1996)
4.
Saeedi, M., Wille, R., Drechsler, R.: Synthesis of quantum circuits for linear nearest neighbor architectures. Quantum Inform. Process. 10(3), 355–377 (2011)MathSciNetCrossRefMATH
5.
Khan, M.H.: Cost reduction in nearest neighbour based synthesis of quantum Boolean circuits. Eng. Lett. 16(1), 1–5 (2008)
6.
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)
7.
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)
8.
Wille, R., Quetschlich, N., Inoue, Y., Yasuda, N., Minato, S.: Using \(\pi \)DDs for nearest neighbor optimization of quantum circuits. In: Devitt, S., Lanese, I. (eds.) RC 2016. LNCS, vol. 9720, pp. 181–196. Springer, Cham (2016). doi:10.​1007/​978-3-319-40578-0_​14 CrossRef
9.
Wille, R., Keszocze, O., Walter, M., Rohrs, P., Chattopadhyay, A., Drechsler, R.: Look-ahead schemes for nearest neighbor optimization of 1d and 2d quantum circuits. In: ASP Design Automation Conference, pp. 292–297 (2016)
10.
Wille, R., Lye, A., Drechsler, R.: Optimal SWAP gate insertion for nearest neighbor quantum circuits. In: ASP Design Automation Conference, pp. 489–494 (2014)
11.
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
12.
Fowler, A.G., Devitt, S.J., Hollenberg, L.C.L.: Implementation of Shor’s algorithm on a linear nearest neighbour qubit array. Quantum Inform. Comput. 4, 237–245 (2004)MathSciNetMATH
13.
Meter, R.V., Oskin, M.: Architectural implications of quantum computing technologies. J. Emerg. Technol. Comput. Syst. 2(1), 31–63 (2006)CrossRef
14.
15.
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
16.
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
17.
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
18.
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
19.
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
20.
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
21.
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)
22.
Ohliger, M., Eisert, J.: Efficient measurement-based quantum computing with continuous-variable systems. Phys. Rev. A 85, 062318 (2012)CrossRef
23.
DiVincenzo, D.P., Solgun, F.: Multi-qubit parity measurement in circuit quantum electrodynamics. New J. Phys. 15(7), 075001 (2013)CrossRef
24.
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 Multi-Valued Logic, pp. 220–225 (2008). RevLib is available at http://​www.​revlib.​org
Metadata
Title
Exact Global Reordering for Nearest Neighbor Quantum Circuits Using A
Authors
Alwin Zulehner
Stefan Gasser
Robert Wille
Copyright Year
2017
Book
Reversible Computation

Print ISBN: 978-3-319-59935-9

Electronic ISBN: 978-3-319-59936-6

Copyright Year: 2017

DOI
https://doi.org/10.1007/978-3-319-59936-6_15

Premium Partner

    Image Credits