Fachrat Informatik - Forum

Hinweis:
0 XOR X -> X
1 XOR X -> Umgekehrt von X

für deine Frage: es gibt nur 2 möglichkeiten:
f(0) = 1 oder f(0) = 0. Für beide Fälle, das gilt. Probiere mal. Das hat mit "Try and error" gefunden, damit wir erste figur von zustand ((|0>-|1>)) erhalten können. Ich hoffe dass ich gut erzählen könnte. :-)

Eine Frage:

Buch seite 151, Beispiel 6.1

ich verstehe nicht, warum G(4)=1? er hat gesagt, wir erhalten senkrecht am Ende. Aber wir können "immer" mit 1 Schritt Senkrecht erhalten. Das heisst, wir brauchen immer nur 1 Grover Iteration!!!! Kann jemand das bitte erzählen?

Quoted

Original von Norton
Buch seite 151, Beispiel 6.1

ich verstehe nicht, warum G(4)=1?

Was genau ist Dir daran unklar? In Beispiel 6.1 sind doch alle für den Fall N = 4 relevanten Zahlenwerte genannt. Und diese ergeben, daß nur eine Iteration notwendig ist.

Quoted

Aber wir können "immer" mit 1 Schritt Senkrecht erhalten.

Wie kommst Du darauf?

Quoted

Wie kommst Du darauf?

Ich glaube wenn Sin(beta) is irgendwas, dann kann man mit (Pi/2)-ArcSin(beta) das Winkel -SsSx erhalten und das ist nur ein Schritt!

Ich weiss es eigentlich nicht, ob ich das gut verstanden habe!

Quoted

Original von Norton
Ich glaube wenn Sin(beta) is irgendwas, dann kann man mit (Pi/2)-ArcSin(beta) das Winkel -SsSx erhalten und das ist nur ein Schritt!

Ich weiss es eigentlich nicht, ob ich das gut verstanden habe!

Ich versuch's mal zu erklären:

Im folgenden sei |s> die gleichverteilte (positive) Superposition auf n = log_2(N) Bits. Der Algorithmus von Grover arbeitet auf einem Register |r>, das zu Beginn den Inhalt |s> hat.

Ist x^ das gesuchte Element, so lassen sich die Operationen des Algorithmus vollständig im von |s> und |x^> aufgespannten (2-dimensionalen) Vektorraum beschreiben.

Schritt 1: Spiegele |r> an der zu |x^> senkrecht verlaufenden Geraden durch den Nullpunkt.
Schritt 2: Spiegele |r> an der durch |s> verlaufenden Geraden.

Zwei aufeinander folgende Spiegelungen in zweidimensionalen Vektorräumen lassen sich als eine Drehung beschreiben. Der Drehwinkel ist dabei das Doppelte des Winkels zwischen den Spiegelachsen, hier also sin(Drehwinkel / 2) = <s|x^>.

Ziel ist es, den Inhalt des Registers so zu "drehen", daß |r> in dieselbe Richtung zeigt wie |x^>, also mit Messung zur Standardbasis |x^> am wahrscheinlichsten auftritt. Wir wollen also einen Winkel zu der zu |x^> senkrecht verlaufenden Geraden von 90 Grad, also Pi/2 erreichen. In jeder Iteration findet eine Drehung um den Drehwinkel statt, für große N ist dieser ungefähr 2 / sqrt(N).

Da wir mit dem Registerinhalt |s> starten, haben wir zu Beginn bereits einen Winkel von 1 / sqrt(N) zu der zu |x^> senkrecht verlaufenden Geraden erreicht.

Somit müssen wir insgesamt etwa sqrt(N) * Pi / 4 Drehungen (also Iterationen) ausführen.

Quoted

Original von Joachim
Schritt 1: Spiegele |r> an der zu |x^> senkrecht verlaufenden Geraden durch den Nullpunkt.
Schritt 2: Spiegele |r> an der durch |s> verlaufenden Geraden.

Um da gleich nochmal eventuelle Verwirrungen zu beseitigen:
Das Buch leitet auf eine äquivalente leicht andere Spiegelreihenfolge hin. Auf Seite 151 ist die Rede von S_s S_(x^)^T. ^T bezeichnet dabei einen zu x^ senkrechten Vektor. Damit wären die Schritte im Buch also:

Schritt 1: Spiegele |r> an der durch |x^> verlaufenden Geraden.
Schritt 2: Spiegele |r> an der zu |s> senkrecht verlaufenden Geraden durch den Nullpunkt.

Danke schön!!!

Noch eine Frage:

Buch Seite 218 und 219 (Beispiel 8.5)

Er hat gesagt: "erkennt man: nur Summanden |z> mit z.(001)T = 0 haben Amplitude ungleich 0." Ich verstehe diese Satz nicht.

In Schritt 7, ich verstehe auch nicht, wie er z1 und z2 berechnet hat und danach er hat gesagt "...aber nur t0 = 1 unterscheidet vom Nullvektor".

Kann jemand bitte das kurz erzählen? Danke!

Quoted

Original von Norton
Noch eine Frage:

Buch Seite 218 und 219 (Beispiel 8.5)

Er hat gesagt: "erkennt man: nur Summanden |z> mit z.(001)T = 0 haben Amplitude ungleich 0." Ich verstehe diese Satz nicht.

Rechne den letzten Term auf Seite 218 mal komplett aus (er läßt ja fast alle Summanden weg, angedeutet durch "..."), dann wirst Du sehen, was er meint.

Quoted

In Schritt 7, ich verstehe auch nicht, wie er z1 und z2 berechnet hat und danach er hat gesagt "...aber nur t0 = 1 unterscheidet vom Nullvektor".

Kann jemand bitte das kurz erzählen?

z1 und z2 sind einfach Ergebnisse der Messung in Schritt 6. Dazu wird der Algorithmus mehrfach ausgeführt, um linear unabhängige Ergebnisse zu erhalten.

t0, t1 und t2 beziehen sich auf Schritt 8 des Algorithmus (siehe Seite 217). Dort wird einfach nur ein lineares Gleichungssystem gelöst.

Entweder hab ichs nicht gefunden, oder übersehen.
Weiss jemand, wann die Noten voraussichtlich bekannt gegeben werden sollen und wann die Einsicht ist?

Quoted

Original von dfex
Entweder hab ichs nicht gefunden, oder übersehen.
Weiss jemand, wann die Noten voraussichtlich bekannt gegeben werden sollen und wann die Einsicht ist?

Ich hab vorhin Henning gefragt: Matthias Homeister kommt erst in knapp drei Wochen wieder nach Hannover. Dann wird er die Korrektur vornehmen. Ergebnisse wird es dann wohl so ungefähr zu dieser Zeit geben. Die Einsicht findet noch etwas später statt, da Henning demnächst für ein paar Wochen nicht in Hannover ist.

Ok, es ist ja jetzt ungefähr so diese Zeit
Wollte einfach mal hören, ob ihr schon etwas mehr wisst als der Rest..

Hallo,

die Ergebnisse hängen am Brett vorm Institut aus...