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

2001 | Buch

Introduction Kapitel lesen Erstes Kapitel lesen

Quantum Computing

verfasst von: Mika Hirvensalo

Verlag: Springer Berlin Heidelberg

Buchreihe : Natural Computing Series

Enthalten in: Professional Book Archive

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Über dieses Buch

The twentieth century witnessed the birth of revolutionary ideas in the phys­ ical sciences. These ideas began to shake the traditional view of the universe dating back to the days of Newton, even to the days of Galileo. Albert Ein­ stein is usually identified as the creator of the relativity theory, a theory that is used to model the behavior of the huge macrosystems of astronomy. An­ other new view of the physical world was supplied by quantum physics, which turned out to be successful in describing phenomena in the microworld, the behavior of particles of atomic size. Even though the first ideas of automatic information processing are quite old, I feel justified in saying that the twentieth century also witnessed the birth of computer science. As a mathematician, by the term "computer sci­ ence", I mean the more theoretical parts of this vast research area, such as the theory of formal languages, automata theory, complexity theory, and al­ gorithm design. I hope that readers who are used to a more flexible concept of "computer science" will forgive me. The idea of a computational device was crystallized into a mathematical form as a Turing machine by Alan Turing in the 1930s. Since then, the growth of computer science has been immense, but many problems in newer areas such as complexity theory are still waiting for a solution.

Inhaltsverzeichnis

Frontmatter
1. Introduction
Abstract
In connection to computational complexity, it could be stated that the theory of quantum computation was launched in the beginning of the 1980s. A most famous physicist, Nobel Prize winner Richard P. Feynman, proposed in his article [30] which appeared in 1982 that a quantum physical system of R particles cannot be simulated by an ordinary computer without an exponential slowdown in the efficiency of the simulation. However, a system of R particles in classical physics can be simulated well with only a polynomial slowdown. The main reason for this is that the description size of a particle system is linear in R in classical physics,1 but exponential in R according to quantum physics (In Section 1.4 we will learn about the quantum physics description). Feynman himself expressed:
But the full description of quantum mechanics for a large system with R particles is given by a function ψ (x l, x2, ... , x R , t) which we call the amplitude to find the particles xi,..., xR, and therefore, because it has too many variables, it cannot be simulated with a normal computer with a number of elements proportional to R or proportional to N. [30]
Feynman also suggested that this slowdown could be avoided by using a computer running according to the laws of quantum physics. This idea suggests, at least implicitly, that a quantum computer could operate exponentially faster than a deterministic classical one. In [30], Feynman also addressed the problem of simulating a quantum physical system with a probabilistic computer but due to interference phenomena, it appears to be a difficult problem.
Mika Hirvensalo
2. Devices for Computation
Abstract
To study computational processes we have to fix a computational device first. In this chapter, we study Turing machines and circuits as models of computation. We use the standard notations of formal language theory and represent these notations now briefly. An alphabet is any set A. The elements of an alphabet A are called letters. The concatenation of sets A and B is a set AB consisting of strings formed of any element of A followed by any element of B. Especially, A k is the set of strings of length k over A. These strings are also called words. The concatenation w l w 2 of words w 1 and w 2 is just the word w 1 followed by w 2. The length of a word w is denoted by |w| or ℓ(w) and defined as the number of the letters that constitute w. We also define A0 to be the set that contains only the empty word e having no letters, and A* = A0 ∪ A l ∪ A 2 ∪ ... is the set of all words over A. Mathematically speaking, A* is the free monoid generated by the elements of A, having the concatenation as the monoid operation and ϵ as the unit element.
Mika Hirvensalo
3. Fast Factorization
Abstract
In this chapter we represent Shor’s quantum algorithm for factoring integers. Shor’s algorithm can be better understood after studying quantum Fourier transforms. The issues related to Fourier transforms and other mathematical details are handled in Chapter 8, but a reader having a solid mathematical knowledge of these concepts is advised to ignore the references to Chapter 8.
Mika Hirvensalo
4. Finding the Hidden Subgroup
Abstract
In this brief chapter we present a quantum algorithm, which can be seen as a generalization of Shor’s algorithm. We can here explain, in a more structural manner, why quantum computers can speed up some computational problems. The so-called Simon’s hidden subgroup problem can be stated in a general form as follows [12]:
  • Input: A finite abelian group G and function ρ: G → R, where R is a finite set.
  • Promise: There exists a nontrivial subgroup H ≤ G such that ρ is constant and distinct on each coset of H.
  • Output: A generating set for H.
Mika Hirvensalo
5. Grover’s Search Algorithm
Abstract
Let us consider a children’s game called hiding the key : one player hides the key in the house, and the others try to find it. The one who has hidden the key is permanently advising the others by using phrases like “freezing”, “cold”, “warm”, and “hot”, depending on how close the seekers are to the hiding place. Without this advice, the game would obviously last much longer. Or, can you develop a strategy for finding the key without searching through the entire house?
Mika Hirvensalo
6. Complexity Lower Bounds for Quantum Circuits
Abstract
Unfortunately, the most interesting questions related to quantum complexity theory, for example, “Is NP contained in BQP or not?”, are extremely difficult and far beyond recent knowledge. In this chapter we will mention some complexity theoretical aspects of quantum computation, which may somehow illustrate these difficult questions.
Mika Hirvensalo
7. Appendix A: Quantum Physics
Abstract
We may say that quantum mechanics was born in the beginning of the twentieth century when experiments on atoms, molecules and radiation physics were not explained by classical physics. As an example, we mention the quantum hypothesis by Max Planck in 19001 in connection with the radiation of a black body.
Mika Hirvensalo
8. Appendix B: Mathematical Background
Abstract
The purpose of this chapter is to introduce the reader to the basic mathematical notions used in this book.
Mika Hirvensalo
Backmatter
Metadaten
Titel
Quantum Computing
verfasst von
Mika Hirvensalo
Copyright-Jahr
2001
Verlag
Springer Berlin Heidelberg
Electronic ISBN
978-3-662-04461-2
Print ISBN
978-3-662-04463-6
DOI
https://doi.org/10.1007/978-3-662-04461-2