Quantenalgorithmen

Suchen mit nur einer Anfrage

Frank-Michael Krupp
[[Link]

Seminar im Sommersemester 2000

Universität Karlsruhe
Institut für Algorithmen und Kognitive Systeme (IAKS)
Betreuer: Dipl. Informatiker Markus Grassl
Juli 2000

Inhaltsverzeichnis
1 Einleitung 2

2 Motivation des Algorithmus 3

2.1 Standard-Grover-Suchalgorithmus . . . . . . . . . . . 3
2.2 Erster Ansatz . . . . . . . . . . . . . . . . . . . . . . 3
2.3 Codierungstrick . . . . . . . . . . . . . . . . . . . . . 3

3 Ablauf des Algorithmus 4

3.1 Spezifikation des Problems . . . . . . . . . . . . . . . 4
3.2 Initialisierung . . . . . . . . . . . . . . . . . . . . . . 5
3.3 Codierung der Anfrage . . . . . . . . . . . . . . . . . 6
3.4 Verarbeitung der Anfrage . . . . . . . . . . . . . . . 7
3.5 Inversion-About-Average . . . . . . . . . . . . . . . . 8
3.6 Auswertung . . . . . . . . . . . . . . . . . . . . . . . 9
3.7 Analyse . . . . . . . . . . . . . . . . . . . . . . . . . 11

4 Beispiel 11
Frank-Michael Krupp [Link] 2

1 Einleitung
Der Physik-Nobelpreisträger Richard Feynman entwickelte 1982 als
einer der ersten die Idee vom Computer, der mit Quanteneffekten
Informationen verarbeitet. Ein klassisches Teilchen kann sich nur in
einem bestimmten Zustand (0 oder 1) befinden. In der Quanten-
physik kann aber ein Teilchen in einem Zwischenzustand zwischen
mehreren Zuständen sein, der so genannten Superposition. Mit ei-
nem 8 Quantenbit(Qubit)-Register kann der Rechner in 28 Basis-
zuständen sein. Jede unitäre1 Operation wirkt sich auf alle Basis-
zustände gleichzeitig aus. Somit entsteht ein massiver Parallelrech-
ner. Die Messung dieser Superposition führt jedoch dazu, dass die
Teilchen wieder einen eindeutigen Zustand annehmen (Dekohärenz),
28 − 1 Zustände gehen unwiederbringlich verloren. Welcher Zustand
weiterbesteht, kann man mit dem Manipulieren der Wahrschein-
lichkeitsamplitude beeinflussen. Nach und nach entstanden spezielle
Algorithmen, die diese Besonderheiten ausnutzen konnten, und des-
halb statt exponentiellem nur noch polynomialen Aufwand benöti-
gen.
Der Durchbruch gelang Peter Shor 1994 mit einem Faktorisierungs-
algorithmus der statt exponentiellem Aufwand2 nur noch linearen
Aufwand braucht.[SH94]
Der Suchalgorithmus von Lov Grover (Bell Laboratories), mit dem
eine nicht strukturierte Datenbank, z. B. Telefonbuch p anhand be-
kannter Telefonnummer, bestehend aus N Elementen in N/4 Schrit-
ten und nicht wie bisher klassisch in N/2 Schritten durchsucht wer-
den kann, war der erste bedeutende Algorithmus mit dem man be-
weisen konnte, dass Quantenalgorithmen den klassischen Algorith-
men überlegen sind. Mit dem hier vorgestellten Algorithmus, von
Grover 1997 entwickelt, gelingt die Suche in O(1), also konstant vie-
len Anfragen. Er ist eine Abwandlung von Grovers ursprünglichen
Suchalgorithmus, deshalb gehe ich im folgenden Abschnitt kurz auf
diesen ein. Zu einem ähnlichen Resultat kamen Terhal und Smolin
[TS98] mit einem anderen Ansatz.
1A ∗ A∗ = I; alle unitären Transformationen erfüllen die Anforderung, reversibel zu sein
2 Aufwand des bisher schnellsten klassischen Algorithmus (Number field sieve):
1 2
O(e(log n) 3 (log log n) 3 )
Frank-Michael Krupp [Link] 3

2 Motivation des Algorithmus

2.1 Standard-Grover-Suchalgorithmus
Mit Grovers Algorithmus ist es möglich, aus einer Datenbank
√ von
n
N = 2 Einträgen ein markiertes Element x0 mit O( N ) Quan-
tenanfragen zu finden. Dies ist immer noch ein exponentieller Auf-
wand um die Nadel im Heuhaufen“ zu finden, leider wird es bis auf
”
konstante Faktoren auch nicht schneller gehen.
Grovers Algorithmus funktioniert kurzgefaßt so:
1. Erzeuge mit n Quantenbits eine Superposition aus 2n = N
Zuständen. Ein Basiszustand bezieht sich auf ein Element der
Datenbank.
2. Invertiere die Phase des gesuchten Zustandes.
3. Führe die Inversion-About-Average-Transformation durch, die
die Wahrscheinlichkeitsamplitude des Zustandes x0 anhebt.
√
4. Wiederhole Schritt 2 und 3 O( N ))-mal3 , man erhält bei der
anschließenden Messung des Quantensystems mit hoher Wahr-
scheinlichkeit den gesuchten Wert x0 .

2.2 Erster Ansatz

Wie kann man die Wiederholung der Schritte 2 und 3 einsparen? Ei-
ne Möglichkeit ist, die Anfragen zu parallelisieren, vgl. Abb. 1. Der
naive Ansatz besteht darin, viele Teilsysteme zu initialisieren, jeweils
einmal per Datenbankanfrage die Phase des gesuchten Zustands zu
invertieren und anzuheben und dann ohne weitere Wiederholungen
sofort zu messen. Bei dieser Messung erhält man in jedem Teilsystem
den gesuchten Zustand mit einer etwas höheren Wahrscheinlichkeit
als einen falschen Zustand. Eine Mehrheitsentscheidung unter den
gemessenen Zuständen liefert das gewünschte Ergebnis. Damit die-
se Mehrheitsentscheidung das richtige Ergebnis liefert, müssen sehr
viele Teilsysteme vorhanden sein, und da jedes eine Datenbankan-
frage durchführt, ist mit diesem ersten Ansatz nichts gewonnen.

2.3 Codierungstrick
Die Idee mit den Teilsystemen und der Mehrheitsentscheidung führ-
te Grover auf eine weitere Verbesserungsmöglichkeit. Durch eine ge-
schickte Codierung der Anfragen läßt sich ein Anfragevektor bilden.
3 Nicht häufiger, da dann an dem gewünschten Zustand vorbeigedreht wird. Die Wahr-

scheinlichkeit sinkt bei jeder Wiederholung.

Frank-Michael Krupp [Link] 4

  !"#$

.
8  





  
0. 
27   !"#$
612.
5  %&'( )**+
4. 3  




  
102/ 
- .   !"#$
, 






  


Abbildung 1: erster Ansatz für Parallelisierung

Dieser wird an die Datenbank geleitet und mit der Antwort und ei-
ner entsprechend trickreichen Codierung ist es möglich, wieder auf
die einzelnen Teilsysteme zurückzuschließen (vgl. Abb. 2).

Vc d
XVYb DeC<IB=J
OT YV
a
V
T QQW
[_` F >C; G =H I:J< 9:;<=>: =? K >C; G =;L DI;
W^] @AB=?;CD =E
\
[VZ
TXWY
UT V
SM R
Q
OM
NP

Abbildung 2: Parallelisierung mit geschickter Codierung

3 Ablauf des Algorithmus

3.1 Spezifikation des Problems
Die Aufgabe besteht darin, ein markiertes Element in einer nicht
strukturierten Datenbank von N = 2n Elementen A1 , . . . , AN = M
zu suchen. Dabei sollen möglichst wenig Anfragen ausreichen. Alle
Antworten bestehen aus 1 Bit, sprich ja/nein.
Andere Sichtweise: Es ist eine Funktion F (x) gegeben, finde ein
x0 , für das die Funktion den Wert 1 annimmt mit möglichst wenig
Frank-Michael Krupp [Link] 5

Funktionsauswertungen, d. h., zu F : M → {0, 1} finde x0 ∈ M mit

F (x0 ) = 1, wobei F (x) = 0 ∀x 6= x0
Im folgenden gebe es nur einen gesuchten Zustand.

3.2 Initialisierung
Erzeuge eine große Anzahl η identischer Teilsysteme (η = N (log N )2 ,
Erklärung in 3.7). Jedes System besteht aus ν Qubits, es können also
2ν = N verschiedene Zustände eingenommen werden. N ist zugleich
die Anzahl der Elemente in der zu durchsuchenden Datenbank, es
besteht eine Bijektion zwischen Zuständen und Datenbankelemen-
ten. Der Gesamtzustand ist wie folgt:
|ψ1 i = (|0i |0 i . . . |0i) ⊗ (|0i |0i . . . |0i) ⊗ |0i
| {z } | {z } |{z}
νη N 1
Zustand1 η Teilsysteme Anfrage
Initialisiere die Teilsysteme in einer Superposition. Dazu wird übli-
cherweise die Hadamard-(Fourier2)-Transformation
 verwendet. Dies
1 1
ist die unitäre Matrix H = √12 . Das Quantenbit (|0i,
1 −1
das anfangs mit der Wahrscheinlichkeit p = 1 bei einer späteren Mes-
sung den Wert 0 liefert, wird nun in den Zwischenzustand √12 (|0i + |1i )
gesetzt ( √12 sorgt für die Normierung). Bei einer Messung wird die-
ser Zustand zerstört und man erhält mit p = 21 den Wert 0 und mit
p = 12 den Wert 1. Diese Hadamard-Transformation wird auf die
ersten ην Bits und das letzte Bit angewendet und man erhält den
Zustand
   
(H ⊗ H ⊗ . . . ⊗ H ) ⊗ I ⊗ I ⊗ . . . ⊗ I  ⊗ H  |ψ1 i
| {z } | {z }
νη N

= (H |0i |0i) ⊗ ( I |0i |0i) ⊗ (H |0i)

= ((|0i + |1i) ⊗ . . . ⊗ (|0i + |1i)) ⊗ (0 ⊗ . . . ⊗ 0) ⊗ (|0i + |1i)
1
(Bem.: Der Normierungsfaktor √2νη+1 fehlt hier und wird auch im
weiteren nicht mehr mitgeführt).
Damit hat man nun in den η Teilsystemen  die gleichen Wahrschein-
1 1 1
lichkeitsamplituden √N , √N , . . . , √N . Rotiere die Phase des letz-
 
1 0
ten Quantenbits mit der Transformation Z = , dies
0 −1
Frank-Michael Krupp [Link] 6

invertiert die Phase des Quantenbit:

     
1 0 1 0
Z (|0i + |1i) = ∗ +
0 −1 0 1
   
1 0
= +
0 −1

= (|0i − |1i)

Zusammenfassend ist das Quantenregister nach diesem Initialisie-

rungsschritt in folgendem Zustand:

|ψ2 i = ((|0i + |1i) ⊗ . . . ⊗ (|0i + |1i)) ⊗ |0i⊗N ⊗ (|0i − |1i)

| {z }
⊗νη
Kurzschreibweise (|0i + |1i)
N ⊗η
P
oder |xi
x=1

3.3 Codierung der Anfrage

Nun folgt der Trick des Algorithmus. Die Information der νη Quan-
tenbits wird auf einen N Bit großen Indikatorvektor (χ1 , χ2 , χ3 , . . . , χN )
komprimiert. Durch die spezielle Wahl dieser Codierung wird es in
einem späteren Schritt möglich sein, die Antwort wieder auf das
gesamte System anzuwenden. Dieser Indikatorvektor berechnet sich
folgendermaßen: Jedes Teilsystem ist unabhängig von den anderen
und bezieht sich in der Basisdarstellung auf eines der 1, . . . , N Da-
tenbankelemente. Zähle die Teilsysteme, die mit dem Element j kor-
respondieren, prüfe, ob diese Zahl gerade ist und speichere die Pa-
rität in χj .

j = 1, . . . , N χj : {0, 1}νη → {0,

 1}
N
P
⊗η  1 falls Anzahl der xi mit
|xi 7→ Wert j ungerade
x=1  0 sonst

Diese zwischengespeicherten N Werte (0 oder 1) stellen die Anfrage

an die Datenbank dar. Diese Bits werden an das Datenbankorakel
gegeben, das dann die Antwort 0 oder 1 gibt. Weitere Anfragen
sind nicht erforderlich. Mit diesem 1 Bit Information der Antwort
wird es möglich sein, die zu dem gesuchten Zustand x0 gehörenden
Wahrscheinlichkeitsamplituden zu erhöhen.
Frank-Michael Krupp [Link] 7

Der Zustand nach diesem Schritt ist:

N
P
|ψ3 i = |x1 i |x2 i . . . |xη i ⊗ (|χ1 i ⊗ . . . ⊗ |χN i) ⊗ (|0i − |1i)
x=1

3.4 Verarbeitung der Anfrage

An die Datenbank wird der Indikatorvektor (χ1 , . . . , χN ) übergeben.
Wenn der zu x0 gehörende Indikator χx0 den Wert 1 hat, dann ist
die Antwort 1, ansonsten 0.

P (χ1 , . . . , χN ) → χx0
| {z } |{z}
Nbit 1bit

Betrachte dann die folgende Transformation

N
! + N
! +
X X
UP : |xi , (|0i − |1i) → |xi , (|0i − |1i) ⊕ P (x)
x=1 x=1

auf ein Teilsystem angewendet. Diese unitäre Transformation UP

wird in allen Zuständen, die sich auf x0 beziehen, die Amplitu-
de ändern und die übrigen Zustände und das hintere Hilfsbit un-
verändert lassen. Warum das so ist, ist ersichtlich, wenn man die
Zustände in die zwei Mengen A = {x|P (x) = 0} und B={x|P (x) =
1} aufteilt.
UP (|ψ,
(|0i − |1i)i) 
P
= UP |xi ⊗ (|0i − |1i)
x  
P P
= UP |xi + |xi ⊗ (|0i − |1i)
 x∈A x∈B 
P P P P
= UP |x, 0i − |x, 1i + |x, 0i − |x, 1i
 x∈A x∈A x∈B x∈B 
P P P P
= |x, 0 ⊕ 0i − |x, 1 ⊕ 0i + |x, 0 ⊕ 1i − |x, 1 ⊕ 1i
 x∈A x∈A x∈B  x∈B
P P P P
= |x, 0i − |x, 1i + |x, 1i − |x, 0i
x∈A x∈A  x∈B  x∈B
P P
= |xi − |xi ⊗ (|0i − |1i)
x∈A x∈B

Der ⊕-Operator ist XOR oder die bitweise Addition modulo 2.

Entscheidend ist, dass sich der Faktor (−1)P (x) in Tensorprodukten
nach vorne ziehen läßt und sich auf die einzelnen Teilsysteme in der
Frank-Michael Krupp [Link] 8

Form (−1)f (x) verteilen läßt. Diese Umformung ist nicht offensicht-
lich, der genaue mathematische Beweis ist in [GB97] zu finden, hier
ein vereinfachender Erklärungsversuch: Ist die Anzahl der Teilsys-
teme, die sich auf das x0 beziehen, gerade, so ergibt die Datenban-
kanfrage die 0 und damit (−1)0 = 1. Es kann eine gerade Anzahl
von 1 auf die Teilsysteme in der Form (−1)f (x) vor die betreffenden
Systeme verteilt werden ((−1)2n = 1). Ist die Anzahl dagegen unge-
rade, dann ist (−1)1 = −1 = (−1)2n+1 = (−1)f (x) .
Damit ist das Quantensystem im Zustand

 N
⊗η
P
|ψ4 i = f (x)
(−1) |xi ⊗ (|0i)⊗N ⊗ (|0i − |1i)
x=1

3.5 Inversion-About-Average
Nun kommt der anfangs erwähnte Inversion-About-Average-Operator
zum Zug, der wie folgt definiert ist
 
−1 + N2 2
N
2
N
... N
2
2
 N
−1 + N2 2
N
... N
2

 2 2 2 2 
D=  N N
−1 + N
. . . N

 .
.. .
.. .
.. . .. .
..


2 2 2 2
N N N
. . . −1 + N
Der Operator D ist unitär, DD∗ = I folgt aus einfachem Nachrech-
nen. Wende D auf jedes Teilsystem an:

D⊗η = D
| ⊗D⊗
{z. . . ⊗ D}
η−mal

Jedes Teilsystem hat den Wahrscheinlichkeitsvektor

 
 1 1 1 1 1 1 
 
 √ , √ . . . , √ , − √ , √ , . . . , √ 
 N N N | {zN} N N
an Stelle x0
Frank-Michael Krupp [Link] 9

D darauf angewendet ergibt:

 
√1
N
   √1 
2 2 2 2
−1 + N N N
... N

 ... N 

2 2 2 2
 −1 + ...   
 N
2 2
N N
2
N
2   √1 
 N N
−1 + N
... N
· N 
  √1

 .. .. .. ... ..  − N

 . . . .  
 √1N


2 2 2 2
N N N
. . . −1 + N
 
 ... 
√1

  N
√1 −1 + N2 + (N − 3) N2 √1 (1 − 4
)
N
N N
 √1 −1 + N2 + (N − 3) N2   √1 (1 − 4
 )
 N   N N


 ...  

  ... 

 √1 2 2
−1 + N + (N − 3) N   √1 (1 − 4
) 
 N   N N 
= √1 2 2

= √3

 N
1 − N + (N − 1) N   N


  
 √1 −1 + N2 + (N − 3) N2   √1 (1 − 4 ) 
 N   N N 
 ...

  ... 
1 4
√1 2
−1 + N + (N − 3) N 2 √ (1 − )
N N N

Für großes N ist 4/N nicht relevant und die Wahrscheinlichkeit des
Zustandes x0 steigt auf das Neunfache der übrigen.
Diese Transformation kann auch anhand der Abbildungen 3 - 5 ver-
anschaulicht werden.
Sei E = √1N . Der Zustand x0 wird invertiert und hat den Wert
−1E. Die Inversion-About-Average spiegelt den Zustand an der
durch den Durchschnitt der Amplituden gegebenen Achse. Da der
Zustand um −2E unter dieser Achse lag, ist er danach auf 1E −
(−2E) = 3E gestiegen.
Zwischenbemerkungen:
1. Im Standard-Grover-Suchalgorithmus
√ werden diese Operatio-
nen nun O( N )-mal wiederholt, dann ist die Wahrscheinlich-
keit hinreichend groß.
2. Diese Inversion-About-Average und somit der gesamte Algo-
rithmus funktioniert auch mit mehreren ausgewählten Zuständen,
allerdings darf die Anzahl nicht N/4 übersteigen, da dann nicht
mehr zwischen ausgewählten Zuständen und nicht ausgewähl-
ten differenziert werden kann.

3.6 Auswertung
Im letzten Schritt wird jedes der η Teilsysteme gemessen. Dadurch
geht durch Dekohärenz die Superposition verloren und man erhält in
Frank-Michael Krupp [Link] 10

Durchschnitt

Wahrscheinlichkeitsamplituden

Abbildung 3: Anfangsinitialisierung des Systems mit Wahrscheinlichkeitsvektor

( √1N , √1N , √1N , . . . , √1N , √1N , √1N , . . . , √1N )

Durchschnitt

X0

Wahrscheinlichkeitsamplituden

Abbildung 4: Zustand nach Inversion

( √1N , √1N , √1N , . . . , √1N , − √1N , √1N , . . . , √1N )

Durchschnitt

X0
Wahrscheinlichkeitsamplituden

Abbildung 5: Wahrscheinlichkeit anheben

( √1N , √1N , √1N , . . . , √1N , 3 √1N , √1N , . . . , √1N )
Frank-Michael Krupp [Link] 11

jedem Teilsystem eine Zahl zwischen 1 und N , die auf das entspre-
chende Datenbankelement verweist. Wie gesehen ist die Wahrschein-
lichkeit, dass bei den Systemen der richtige Zustand nicht zerstört
wird, etwas höher als bei den übrigen. Intuitiv ist klar, dass das
am häufigsten ausgewählte Element das gesuchte Element darstellt.
Eine geschlossene Formel läßt sich nur schwer angeben. Gesucht ist
die Wahrscheinlichkeit für das Ereignis x0 wird K-mal gemessen“
”
unter der Bedingung, dass alle anderen Zustände weniger als K-mal
gemessen werden (Binomialverteilung mit Parametern Anzahl η und
Erfolgswahrscheinlichkeit N9 ).
Für die Anzahl der Teilsysteme gilt: Es werden η = N log (N ) Teil-
systeme benötigt.
Erklärung:
Die
 Wahrscheinlichkeit,
 den gewünschten Zustand zu erhalten, ist
2
√3 = 9
, die Wahrscheinlichkeit für einen falschen Zustand ist
N N
1
ungefähr . Hat
man nun ν Teilsysteme folgt aus dem Gesetz der
N
großen Zahlen, dass die Wahrscheinlichkeiten gegeben sind durch
9η 1η
N
|{z} N
|{z}
1Zustand (N - 1) Zustände

Mit ν = KN erhält man 9K und 1K. Bei großem K sieht man, dass
die Wahrscheinlichkeit den richtigen Zustand zu messen größer ist,
als einen der N − 1 falschen.
Nach dem zentralen Grenzwerttheorem reicht die Wahl K = (log(N ))2
aus. Es sind somit N (log(N ))2 Teilsysteme zu verwenden. Eine ge-
nauere Herleitung findet sich in [Gro97].

3.7 Analyse
Der Algorithmus sieht sehr viel versprechend aus, die Einsparung der
Anfragen geht aber einher mit einem großen Anstieg an Vorbereitungs-
und Auswertungsschritten. Das Finden durch eine Anfrage hat also,
solange es nicht gelingt, den Extra-Aufwand zu vermindern, nur
theoretischen Wert, es sei denn, die Anfragen an eine Datenbank
kosten viel Zeit.

4 Beispiel
Zum Schluß ein Beispiel, das den Ablauf des Algorithmus anhand
einer Datenbank mit 23 = 8 Elementen A, B, C, D, E, F, G, H
verdeutlichen soll.
Frank-Michael Krupp [Link] 12

Es sei F das gesuchte Element. Es ist schon bei der geringen Größe
der Datenbank der große Vorbereitungsaufwand des Systems zu er-
kennen. Es sind nämlich 8(log 8)2 = 72 Teilsysteme zu initialisie-
ren. Jedes besteht aus 3 Quantenbits und wird mit der Hadamard-
Transformation in eine Superposition gebracht. Die Wahrscheinlich-
keitsamplitude ist dann:
 
1 1 1 1 1 1 1 1
√ ,√ ,√ ,√ ,√ ,√ ,√ ,√
8 8 8 8 8 8 8 8
Betrachte die Teilsysteme in der Basisdarstellung und stelle fest,
worauf sich die einzelnen Teilsysteme beziehen.
Man erhält beispielsweise für die 72 Teilsysteme die Verteilung
A B C D E F G H
9 5 7 16 13 12 3 7
und damit den Indikatorvektor
χA χB χC χD χE χF χG χH
1 1 1 0 1 0 1 1
Diese 8-Bit-Anfrage wird an das Orakel geleitet. Dieses sieht die 0 an
der gesuchten Stelle, und gibt gemäß der Funktion P (x) die 0 zurück.
(Wäre die Wertigkeit von F gleich 13, so wäre die Parität 1 und
das Orakel würde 1 zurückgeben). Gemäß der in 3.5 angegebenen
Umformung wird diese (−1)0 nach vorne in die Teilsysteme gezogen
und die Phase des Zustandes x0 in allen 72 Teilsystemen gedreht.
 
1 1 1 1 1 1 1 1
√ , √ , √ , √ , √ , −√ , √ , √
8 8 8 8 8 8 8 8
Darauf die Inversion-About-Average-Transformation angewendet er-
gibt:
 1   1 
 3 1 √ √
1 1 1 1 1 1 
−4 4 4 4 4 4 4 4  √18   √132 
 14 − 43 14 1
4
1
4
1
4
1
4
1
4  
  18  
  √132 

 1 1 3 1 1 1 1 1 √
 4 4
−4 4 4 4 4 4 

 8 
 


32 
 1 1 1 1 1
− 43 14 1 1 1   √   √ 
 4 4 4 4 4 4   8  =  132 
 1 1 1 1 3 1 1 1 · √1
 4 4 4 4
−4 4 4 4  8   √ 
  32 
 1 1 1 1 1 3
−4 4 1 1   1  √5 
4   − √8 
 4 
4 4 4 4  
 1 1 1 1 1 1 3
−4 4 1  
√1   √132 
4 4 4 4 4 4  8   32 
1 1 1 1 1 1 1
4 4 4 4 4 4 4
− 34 √1 √1
8 32

Die Wahrscheinlichkeit, bei der abschließenden Messung das richtige

Ergebnis zu erhalten, ist ( √532 )2 , das falsche erhält man mit Wahr-
scheinlichkeit ( √132 )2 . Betrachtet man nun die Wahrscheinlichkeit,
Frank-Michael Krupp [Link] 13

dass der richtige Zustand x0 mit absoluter Mehrheit gemessen wird

in bezug zur Anzahl der Teilsysteme, erkennt man, dass in diesem
Fall schon 15 Teilsysteme ausreichen um eine Wahrscheinlichkeit von
0,99 zu erreichen. Es ist offensichtlich, dass die 72 Teilsysteme aus-

Wahrscheinlichkeit
0,99

0,98

0,97

0,96

0,95

0,94

0,93

0,92

0,91

0,9
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

Teilsysteme

Abbildung 6: Wahrscheinlichkeitsverteilung

reichen um x0 zu bestimmen, denn beispielsweise ist P(falscher Zu-

stand wurde mehr als 37 mal gemessen)=10−3 , dagegen P(richtiger
Zustand weniger als 37 mal gemessen)=10−10 . Damit wird das ge-
suchte F sicher erkannt.
Die Wahrscheinlichkeiten liegen sogar noch höher, wenn man den ge-
naueren Ansatz der relativen Mehrheit mit bedingten Wahrschein-
lichkeiten verwendet.
In Abb. 6 ist für das obige Beispiel mit N = 8 die Wahrschein-
lichkeit, das richtige Ergebnis zu erhalten, in Abhängigkeit von der
Anzahl η der Teilsysteme dargestellt. Der alternierende Verlauf in
der Grafik läßt sich dadurch erklären, dass es schwieriger ist, eine
absolute Mehrheit bei einer geraden Menge zu bekommen, da dort
zwei Stimmen mehr benötigt. In der ungeraden Situation reicht eine
Stimme aus und deshalb ist die Wahrscheinlichkeit in diesen Fällen
höher.
Literatur
[Gru99] Gruska, Josef: Quantum Computing. London:McGraw-Hill,
1999
[RP98] Rieffel, Eleanor und Polak, Wolfgang: An Introduc-
tion to Quantum Computing for Non-Physicists.
Preprint at Los Alamos Physics Preprint Archive,
[Link]
[GB97] Grassl, Markus und Beth, Thomas: On the Com-
plexity of Quantum Searching Using Complex Que-
ries. Preprint at Los Alamos Physics Preprint Archive,
[Link]
[Gro97] Grover, Lov K.: Quantum Computers Can Search
Abritrarily Large Databases by a Single Query.
Preprint at Los Alamos Physics Preprint Archive,
[Link]
[TS98] Terhal, Barbara M. und Smolin, John A.: Single quantum
querying of a database. Preprint at Los Alamos Physics Pre-
print Archive, [Link]
[SH94] Shor, Peter W.: Algorithms for Quantum Computation:
Discrete Logarithm and Factoring. Preprint at Los Alamos
Physics Preprint Archive, [Link]
ph/9508027