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
Start single access now
Request access for companies
EXTENDED SEARCH
Log in
Top

Hint

Swipe to navigate through the chapters of this book

Published in:
Einführung Read chapter Read first chapter

2023 | OriginalPaper | Chapter

3. Quantencomputing und Programmierung

Authors : Riccardo Bassoli, Holger Boche, Christian Deppe, Roberto Ferrara, Frank H. P. Fitzek, Gisbert Janssen, Sajad Saeedinaeeni

Published in: Quantenkommunikationsnetze

Publisher: Springer International Publishing

Log in

Zusammenfassung

Der Grund für die Entwicklung der Quanteninformatik liegt nicht nur im Erreichen einer höheren Rechenkapazität, sondern auch darin, Quantensysteme richtig simulieren und numerisch untersuchen zu können. Es ist immer noch nicht klar, was die Gesamtheit aller Berechnungsaufgaben für Quantennetzwerke ist und welche Aufgaben mit einem Quantencomputer gelöst werden müssen oder vorzugsweise gelöst werden. Ziel dieses Kapitels ist es, ein Verständnis für die zentralen Quantenideen zu vermitteln, die zu den Standard-Must-Do-Themen in der Quantenberechnung gehören und die ihre Anwendung in Quantennetzwerken finden könnten.

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 Grundlegender Hintergrund
next chapter Quanteninformationstheorie
Footnotes
1
Klassische Computer haben sich so weit entwickelt, dass sogar die höheren Befehlssätze kommerzieller Prozessoren (x86, ARM usw.) standardisiert wurden.
 
2
Im Gegensatz zu klassischen Operationen können Quantenoperationen nicht exakt mit einer endlichen oder abzählbaren Anzahl von Gattern implementiert werden, da die Menge der Operationen auf einer beliebigen Anzahl von Qubits kontinuierlich ist. Das Einzige, worauf wir hoffen können, ist, eine dichte Teilmenge zu erzeugen, so wie die natürlichen Zahlen die dichte Menge der rationalen Zahlen in den reellen Zahlen erzeugen. Selbst wenn eine exakte Umsetzung möglich wäre, ist eine einfache Annäherung die physikalisch relevante Bedingung, da aufgrund der Unmöglichkeit, in der Praxis exakte Operationen und Messungen durchzuführen, das Ergebnis einer realen Quantenberechnung nur mit einer kleinen, aber von Null verschiedenen Fehlerwahrscheinlichkeit ermittelt werden kann.
 
3
Ganz zu schweigen von einem standardisierten Satz von Quantenprozessorbefehlen.
 
4
Einige Gründe sind im Folgenden aufgelistet: Algorithmen sind auch dann noch zeitaufwendig, wenn die Komplexität ein Polynom hohen Grades ist. In der Praxis kommen unterschiedliche Kostenfaktoren ins Spiel, wobei einige Grundoperationen viel teurer sein können als andere (Multiplikation vs. Addition) und der Speicherzugriff berücksichtigt werden muss (Cache vs. RAM-Operationen). Manchmal können die versteckten Konstanten so groß sein, dass der Skalierungsvorteil unpraktisch und der Algorithmus unbrauchbar wird. Für die Multiplikation von n × n Matrizen sind beispielsweise mindestens n2 Skalarmultiplikationen (die Anzahl der Ausgabewerte) erforderlich, und die Implementierung der Definition ohne Optimierung erfordert n3 Multiplikationen. Es wurde bewiesen, dass die Matrixmultiplikation eine Komplexität von höchstens n2,4 aufweist [CW90] Der gefundene Algorithmus ist jedoch unpraktisch und bringt auf den heutigen Computern keinen Vorteil [Ili89]. Es gibt einen praktischen Algorithmus, der n∼2,7 Multiplikationen verwendet [Str69].
 
5
Alle diese Beispiele hängen mit der Komplexität der Fourier-Transformation zusammen, wie wir später sehen werden.
 
6
Wir verwenden das Additionssymbol, obwohl es üblich ist, nicht-kommutative Operationen als Produkte zu schreiben.
 
7
Dies gilt allgemein für jeden normalen Operator K. K† K = KK† ist zudem erfüllt, was bedeutet, dass der hermitesche und der antihermitesche Teil K ± K† gleichzeitig diagonalisiert werden können und somit K mit einem komplexen Spektrum diagonalisiert werden kann. Mit anderen Worten: Jeder normale Operator kann gemessen werden, indem man gleichzeitig seinen hermiteschen und seinen antihermiteschen Teil misst.
 
8
Die Probleme, die effizient gelöst werden können, bilden die Komplexitätsklasse P. Die Probleme, für die eine behauptete Lösung effizient überprüft werden kann, bilden die Komplexitätsklasse NP, die P und die meisten praktisch relevanten Probleme enthält. Eine Möglichkeit, Probleme zu konstruieren, die nicht in NP sind, ist der Versuch, die Lösungen von Problemen in NP oder sogar P zu zählen [Val79].
 
9
Atome und Moleküle haben unendlich viele Energieniveaus, aber nur endlich viele können simuliert werden. Das simulierte Molekül wird eine theoretische Annäherung mit endlich vielen Energieniveaus sein.
 
Literature
[AG04]
Aaronson, S., & Gottesman, D. (2004). Improved simulation of stabilizer circuits. Physical Review A, 70(5), 052328. CrossRef
[ABO08]
Aharonov, D., & Ben-Or, M. (2008). Fault-tolerant quantum computation with constant error rate. SIAM Journal on Computing, 38(4), 1207–1282. MathSciNetCrossRefMATH
[BA12]
Band, Y., & Avishai, Y. (2012). Quantum mechanics with applications to nanotechnology and information science (1. Aufl.). Academic. MATH
[BBC+95]
Barenco, A., Bennett, C. H., Cleve, R., DiVincenzo, D. P., Margolus, N., Shor, P., et al. (1995). Elementary gates for quantum computation. Physical Review A, 52(5), 3457–3467. CrossRef
[Ben73]
[BBBV97]
Bennett, C. H., Bernstein, E., Brassard, G., & Vazirani, U. (1997). Strengths and weaknesses of quantum computing. SIAM Journal on Computing, 26(5), 1510–1523. MathSciNetCrossRefMATH
[Ber10]
Bernstein, D. J. (2010). Grover vs. mceliece. In N. Sendrier (Hrsg.), Post-quantum cryptography (S. 73–80). Springer. CrossRef
[BGS13]
Bocharov, A., Gurevich, Y., & Svore, K. M. (2013). Efficient decomposition of single-qubit gates into v basis circuits. Physical Review A, 88(1), 012313. CrossRef
[BAB+18]
Botsinis, P., Alanis, D., Babar, Z., Nguyen, H. V., Chandra, D., Ng, S. X., & Hanzo, L. (2018). Quantum search algorithms for wireless communications. IEEE Communications Surveys & Tutorials, 21(2), 1209–1242. CrossRef
[BMP+00]
Boykin, P. O., Mor, T., Pulver, M., Roychowdhury, V., & Vatan, F. (2000). A new universal and fault-tolerant quantum basis. Information Processing Letters, 75(3), 101–107. MathSciNetCrossRefMATH
[BKL+19]
Brandão, F. G. S. L., Kalev, A., Li, T., Lin, C. Y.-Y., Svore, K. M., & Wu, X. (2019). Quantum SDP solvers: Large speed-ups, optimality, and applications to quantum learning. In C. Baier, I. Chatzigiannakis, P. Flocchini, & S. Leonardi (Hrsg.), 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs) (Bd. 132, S. 27:1–27:14). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
[BS17]
Brandao, F. G. S. L., & Svore, K. M. (2017). Quantum speed-ups for solving semidefinite programs. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) (S. 415–426). CrossRef
[CW90]
Coppersmith, D., & Winograd, S. (1990). Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation, 9(3), 251–280. Computational algebraic complexity editorial. MathSciNetCrossRefMATH
[DiV00]
DiVincenzo, D. P. (2000). The physical implementation of quantum computation. Fortschritte der Physik, 48(9–11), 771–783. CrossRefMATH
[EHKS14]
Eisenträger, K., Hallgren, S., Kitaev, A. Y., & Song, F. (2014). A quantum algorithm for computing the unit group of an arbitrary degree number field. In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, STOC’14 (S. 293–302). Association for Computing Machinery. CrossRefMATH
[Fey99]
Feynman, R. P. (1999). Simulating physics with computers. International Journal of Theoretical Physics, 21(6–7), 467–488. MathSciNet
[FSG09]
Fowler, A. G., Stephens, A. M., & Groszkowski, P. (2009). High-threshold universal quantum computation on the surface code. Physical Review A, 80(5), 052312. CrossRef
[Got97]
Gottesman, D. (1997). Stabilizer codes and quantum error correction. Ph.D. thesis, California Institute of Technology.
[Got98a]
Gottesman, D. (1998). The Heisenberg representation of quantum computers. In Group22: Proceedings of the XXII International Colloquium on Group Theoretic Methods in Physics (S. 32–43). International Press.
[Hal07]
Hallgren, S. (2007). Polynomial-time quantum algorithms for Pell’s equation and the principal ideal problem. Journal of ACM, 54(1), 4. MathSciNetCrossRefMATH
[Ili89]
Iliopoulos, C. S. (1989). Worst-case complexity bounds on algorithms for computing the canonical structure of infinite abelian groups and solving systems of linear diophantine equations. SIAM Journal on Computing, 18(4), 670–678. MathSciNetCrossRefMATH
[JL17]
Johansson, N., & Larsson, J. (2017). Efficient classical simulation of the Deutsch–Jozsa and Simon’s algorithms. Quantum Information Processing, 16(9), 233. MathSciNetCrossRefMATH
[KP17]
Kerenidis, I., & Prakash, A. (2017). Quantum recommendation systems. In C. H. Papadimitriou (Hrsg.), 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs) (Bd. 67, S. 49:1–49:21). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
[KC18]
Kim, T., & Choi, B.-S. (2018). Efficient decomposition methods for controlled R n using a single ancillary qubit. Scientific Reports, 8(1), 1–7.
[Kit95]
Kitaev, A. Y. (1995). Quantum measurements and the Abelian stabilizer problem. arXiv:quantph/9511026
[Kit97a]
Kitaev, A. Y. (1997). Quantum computations: Algorithms and error correction. Uspekhi Matematicheskikh Nauk, 52(6), 53–112. MathSciNetMATH
[KMM13]
Kliuchnikov, V., Maslov, D., & Mosca, M. (2013). Fast and efficient exact synthesis of single qubit unitaries generated by Clifford and T gates. Quantum Information & Computation, 13(7–8), 607–630. MathSciNetCrossRef
[NC10]
Nielsen, M. A., & Chuang, I. L. (2010). Quantum computation and quantum information (10. Aufl.). Cambridge University Press. MATH
[OBK+16]
O’Malley, P. J. J., Babbush, R., Kivlichan, I. D., Romero, J., McClean, J. R., Barends, R., et al. (2016). Scalable quantum simulation of molecular energies. Physical Review X, 6, 031007. CrossRef
[Orú14]
Orús, R. (2014). A practical introduction to tensor networks: Matrix product states and projected entangled pair states. Annals of Physics, 349, 117–158. MathSciNetCrossRefMATH
[Orú19]
Orús, R. (2019). Tensor networks for complex quantum systems. Nature Reviews Physics, 1(9), 538–550. CrossRef
[Pre98b]
Preskill, J. (1998). Lecture notes for physics: Quantum information and computation (S. 322). CreateSpace Independent Publishing Platform.
[Pre12]
Preskill, J. (2012). Quantum computing and the entanglement frontier. Technical Report Caltech authors:20120516-084322874, California Institute of Technology.
[Pre18]
Preskill, J. (2018). Quantum computing in the NISQ era and beyond. Quantum, 2, 79. CrossRef
[RS16]
Ross, N. J., & Selinger, P. (2016). Optimal ancilla-free Clifford+T approximation of z-rotations. Quantum Information & Computation, 16(11–12), 901–953. MathSciNetCrossRef
[RG02]
Rudolph, T., & Grover, L. (2002). A 2 rebit gate universal for quantum computing. arXiv:quant-ph/0210187
[Shi03]
Shi, Y. (2003). Both Toffoli and controlled-NOT need little help to do universal quantum computing. Quantum Information and Computation, 3(1), 84–92. MathSciNetCrossRefMATH
[Str69]
[Tan19]
Tang, E. (2019). A quantum-inspired classical algorithm for recommendation systems. In Proceedings of the 51st annual ACM SIGACT symposium on theory of computing, STOC 2019 (S. 217–228). Association for Computing Machinery. CrossRef
[Val79]
[Win78]
[WBC15]
Wood, C. J., Biamonte, J. D., & Cory, D. G. (2015). Tensor networks and graphical calculus for open quantum systems. Quantum Information and Computation, 15(9–10), 759–811. MathSciNetCrossRef
Metadata
Title
Quantencomputing und Programmierung
Authors
Riccardo Bassoli
Holger Boche
Christian Deppe
Roberto Ferrara
Frank H. P. Fitzek
Gisbert Janssen
Sajad Saeedinaeeni
Copyright Year
2023
Book
Quantenkommunikationsnetze

Print ISBN: 978-3-031-26325-5

Electronic ISBN: 978-3-031-26326-2

Copyright Year: 2023

DOI
https://doi.org/10.1007/978-3-031-26326-2_3