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:
Limits? What Limits? Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

23. Quantum Computing

verfasst von : Bernhard Reus

Erschienen in: Limits of Computation

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

In this chapter we will look into a completely new way of computation based on quantum mechanics, harnessing the underlying parallelism of quantum effects and superposition in a controlled manner. Without going into too much detail, we will point out the role of probabilities and wave functions and mention some famous quantum algorithms. The difficulties of building quantum computers are outlined. It is explained to what extent quantum computing can provide speed-up and it is highlighted that quantum computers are unable to solve NP-complete problems in general (unless P \(=\) NP). Quantum computing also shows off the deep connections between complexity theory and physics.

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 Molecular Computing
Fußnoten
1
Richard Phillips Feynman (May 11, 1918–February 15, 1988) was an American theoretical physicist known for his work in quantum mechanics, quantum electrodynamics, particle physics and other areas. For his contributions to the development of quantum electrodynamics, Feynman, jointly with Julian Schwinger and Sin-Itiro Tomonaga, received the Nobel Prize in Physics in 1965. During his lifetime, Feynman became one of the best-known scientists in the world, helped by the fact that he was a supporting member of the Manhattan project responsible for the development of the atomic bomb, and a member of the Rogers Commission that investigated the 1986 Space Shuttle Challenger disaster. His fame also relies on the significant number of (popular) physics books he published. He is considered one of the greatest physicists of all time.
 
2
Erwin Rudolf Josef Alexander Schrödinger (12 August 1887–4 January 1961) was a famous Austrian physicist who developed a number of fundamental results in the field of quantum theory. He received the Nobel Prize for Physics in 1933.
 
3
Mentioned also in the episode “The Tangerine Factor” of the TV sitcom “The Big Bang Theory”.
 
4
This already uses multiple gate transistors that use a three-dimensional design to save space. Planar designs tend to leak current if they are too small. To reduce leaking the so-called FinFET architecture is used where the conducting channel is wrapped in a silicon-fin that gives the three-dimensional shape and the name. FET stands for field-effect transistor.
 
5
At the time of writing the Intel® 18-core Xeon® E5-2699 v3 (“Haswell-EP”) CPU seems to be among the top CPUs regarding transistor count with 5.56 billion (clock speed of 2.3 GHz) [22]. This is still 22 nm technology though, the latest 2015 releases use 14 nm technology but appear to have fewer transistors due to fewer cores.
 
6
In 1965 Moore predicted the number of transistors on a chip to double every year, which was then actually corrected to ‘every two years’ in 1975. Apparently, David House, an Intel executive at the time, then concluded “that the changes would cause computer performance to double every 18 months” [20]. This is the reason why sometimes 18 months is attributed wrongly to Moore’s statement.
 
7
Called “Cedric”. Note however that currently the transistors are still of “monster size”: 8000 nm.
 
8
This section can be skipped by readers not interested but is intended to motivate the study of linear algebra and complex numbers.
 
9
Sometimes also referred to as Euclidean norm.
 
10
Aaronson [1] uses the example of mirror flipping a two-dimensional shape. The movement must pass through the third dimension if done continuously.
 
11
A wave function is a periodic function in time and space.
 
12
Felix Bloch (23 October 1905–10 September 1983) was a Swiss born American physicist who won the Nobel Prize with Edward Mills Purcell in 1952. From 1954 to 1955 Bloch was the first Director-General of CERN (European Organization for Nuclear Research).
 
13
In [1], this is compared with the equation \(x^p+y^p =z^p\), which has positive integer solutions for x, y, z only if \(p=1\) or \(p=2\). The latter is known as “Fermat’s Last Theorem” (see footnote 14).
 
14
Pierre de Fermat (17 August 1601–12 January 1665) was a French lawyer and a mathematician who contributed to the development of infinitesimal calculus. He is most famous for his conjecture known as “Fermat’s Last Theorem”, a long standing open problem until Andrew Wiles (see footnote 15) eventually proved it in 1994 after years of hard work and numerous failures.
 
15
Sir Andrew John Wiles (born 11 April 1953) is a British mathematician at the University of Oxford. He won numerous awards for proving Fermat’s Last Theorem.
 
16
Which we are not able to do here.
 
17
Developed by the Quantum Architectures and Computation Group (QuArC) at Microsoft Research, Redmond USA.
 
18
The concrete value of the probability \(\frac{1}{3}\) is actually irrelevant and can be changed.
 
19
Which are unit vectors in the Hilbert space generated by the configuration space.
 
20
David Elieser Deutsch, (born 18 May 1953) is a British physicist at the University of Oxford.
 
21
Peter Williston Shor (born August 14, 1959) is an American professor of applied mathematics at MIT. For the discovery of the quantum factorisation algorithm, he was awarded the Gödel Prize in 1999.
 
22
Shor’s algorithm even appeared in the TV sitcom “Big Bang Theory”, episode “The Bat Jar Conjecture”. It was the answer to a question about factorisation by quantum computers in a “Physics Bowl” quiz.
 
23
The quantum Fourier transform and algebra [20].
 
24
Yes, this is another thesis.
 
25
Institute of Electrical and Electronics Engineers.
 
26
William Thomson, 1st Baron Kelvin (26 June 1824–17 December 1907) is known for his formulation of the laws of thermodynamics and the temperature scale with ‘absolute zero’ that bears his name.
 
27
Both types occur in science fiction movies about time travel, e.g. “Back to the Future”, which is, expectably, full of such paradoxes.
 
Literatur
1.
Aaronson, S.: Quantum Computing Since Democritus. Cambridge University Press, New York (2013)CrossRefMATH
2.
Bennett, C.H., Bernstein, E., Brassard, G., Vazirani, U.: Strengths and weaknesses of quantum computation. SIAM J. Comput. 26, 1510–1523 (1997)MathSciNetCrossRefMATH
3.
4.
Deutsch, D.: Quantum theory, the Church-Turing principle and the universal quantum computer. Proc. R. Soc. A 400, 97–117 (1985)MathSciNetCrossRefMATH
5.
6.
Deutsch, D.: The Fabric of Reality. Viking Adult, New York (1997)
7.
Edalat, A.: Quantum Computing. CreateSpace Independent Publishing Platform (2015)
8.
9.
Feynman, R.P.: QED: The Strange Theory of Light and Matter. Princeton Science Library, Princeton (1988)
10.
11.
12.
Green, A., Lumsdaine, P. L., Ross, N., Selinger, P., Valiron, B.: Quipper: A scalable quantum programming language. In Proceedings of PLDI 13, pp. 333–342, ACM (2013)
13.
14.
Kelvin on Science (Interview with Lord Kelvin). Reprinted in The Newark Advocate, April 26, 1902, p. 4 (1902)
15.
Li, T., Jevric, M., Hauptmann, J.R., Hviid, R., Wei, Z., Wang, R., Reeler, N.E.A., Thyrhaug, E., Petersen, S., Meyer, J.A.S., Bovet, N., Vosch, T., Nygård, J., Qiu, X., Hu, W., Liu, Y., Solomon, G.C., Kjaergaard, H.G., Bjørnholm, T., Nielsen, M.B., Laursen, B.W., Nørgaard, K.: Ultrathin reduced graphene oxide films as transparent top-contacts for light switchable solid-state molecular junctions. Adv. Mater. 25(30), 4064–4070 (2013)
16.
17.
Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, New York (2000)MATH
18.
19.
Rønnow, T.F., Wang, Z., Job, J., Boixo, S., Isakov, S.V., Wecker, D., Martinis, J.M., Lidar, D.A., Troyer, M.: Defining and detecting quantum speedup. Science 345(6195), 420–424 (2014)CrossRef
20.
Shor, P.W.: Algorithms for Quantum Computation: Discrete Logarithms and Factoring. In Goldwasser, S. (Ed.) Proceedings of the 35th IEEE Symposium on Foundations of Computer Science, pp. 124–134 (1994)
21.
Shor, P.W.: Polynomial-time algorithms for prime factorisation and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484–1509 (1997)
22.
23.
Shulaker, M.M., Hills, G., Patil, N., Wei, H., Chen, H.-Y., Philip Wong, H.-S., Mitra, S.: Carbon nanotube computer. Nature 501, 526–530 (2013)
24.
Song, H., Kim, Y., Jang, J.H., Jeong, H., Reed, M.A., Lee, T.: Observation of molecular orbital gating. Nature 462, 1039–1043 (2009)
25.
Wecker, D., Svore, K.M.: LIQUi| \(>\): A Software Design Architecture and Domain-Specific Language for Quantum Computing. Available via DIALOG: arxiv.​org/​abs/​1402.​4467. Accessed 23 June 2015 (2014)
Metadaten
Titel
Quantum Computing
verfasst von
Bernhard Reus
Copyright-Jahr
2016
Buch
Limits of Computation

Print ISBN: 978-3-319-27887-2

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

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-319-27889-6_23