Diskussion:Grover-Algorithmus

unverständlich

ok, ich bin zwar informatiker (momentan lehrling), verstehe aber kein wort. kann bitte mal jemand diesen artikel auf deutsch schreiben?

--TheWinner 19:28, 16. Jun. 2007 (CEST)The Winner

Genau das meine ich auch.. und ich bin schon lange fertig mit dem Studium... -- 178.0.112.112 00:05, 23. Mär. 2011 (CET)

evtl. einen Link dazu einbauen .. Links unten auf der Seite wird das ganze gezeigt http://www.research.ibm.com/quantum/ (nicht signierter Beitrag von 213.179.137.2 (Diskussion) 16:34, 4. Mai 2016 (CEST))

einziger Beweis?

ich habe gleich am Anfang der Seite gelesen, dass dies der einzige Beweis wäre; was ist mit dem Deutsch-Problem (bzw. dem verallgemeinerten) ?

---

Und was ist in diesem Zusammenhang mit dem Shor-Algorithmus der zur Faktorisierung von Zahlen nützlich ist?

ACL 07.01.2010 (nicht signierter Beitrag von 87.122.116.239 (Diskussion | Beiträge) 19:16, 7. Jan. 2010 (CET))

Ja der Shor-Algorithmus kann doch die Primfaktorzerlegung in polynomialer Zeit durchführen und nicht in exponentialer Zeit wie heutzutage. Hab eig. keine Ahnung von diesen Themen, ist einfach was ich heute so gelesen habe auf der Wikipedia. 188.62.46.90 00:11, 12. Jan. 2010 (CET)

wie in Fussnote 2 angemerkt, ist Shor zwar exponentiell schneller als der beste bekannte klassische Algorithmus, aber es gibt keinen Beweis, dass es keinen polynomialen klassischen Algorithmus geben kann (während das Suchen in der ungeordneten Datenbank klassisch im Mittel nicht schneller als O(N) gehen kann).

Dass Grover der "einzige Beweis" sei, hat mich auch zunächst irritiert. Aber es ist wohl strenggenommen schon korrekt: Deutsch-Jozsa und Simon sind Orakel-Probleme und zeigen nur, dasss ein QC+passendes Orakel schneller ist als ein klassischer Computer+klassisches Orakel. Da es keinen Beweis gibt, dass die Quantenmechanik nicht effizient auf einem klassischen Computer simuliert werden kann, ist auch "Quantensimulation" kein Beleg. Vorschläge wie [1] zeigen auch "bloss", dass Quantencomputer schneller sind als klassische wenn bestimmte (unbewiesene, aber allgemein für sehr wahrscheinlich gehaltene) Annahmen aus der Komplexitätstheorie erfüllt sind. --Qcomp 16:32, 23. Mär. 2011 (CET)

NP-Probleme

Weiter kann er zur Lösung NP-vollständiger Probleme eingesetzt werden, indem er die Menge aller möglichen Probleme durchläuft

[2] widerspricht dem. Ich kenne mich mit dem Thema nicht aus, wäre nett, wenn jemand was dazu beitragen könnte.--94.220.140.24 17:04, 16. Feb. 2010 (CET)

Grover kann schon den ${\sqrt {N}}$-speedup auch für NP-vollständige Probleme liefern: ein (nicht-effizientes) klassisches Verfahren (z.B. für das Problem des Handlungsreisenden ist: (1) generiere alle möglichen Routen $(r_{1},r_{2},...r_{N})$ durch $N$ Punkte $r_{i}$ (2) suche in der Liste aller Routen nach der kürzesten (bzw nach allen, die kürzer als $L$ sind). Da sich der Quantenzustand "Überlagerung aller möglichen Routen" effizient herstellen lässt und wenn sich für jede Route effizient ihre Länge berechnen lässt, dann kann $U_{L}=2P_{{\text{Route}}<=L}-I$ angewandt und somit Grover zum Auffinden von kurzen Routen verwendet werden. (vgl. Kap 6.4 in Nielsen/Chuang oder Martin Fürer: Solving NP-Complete Problems with Quantum Search). Natürlich bleibt das Problem damit exponentiell schwierig, aber $2^{n/2}\ll 2^{n}$ für grosse $n$. nebenbei: Brassard hat eine schöne Anwendung (zum Grover-Speedup eines exponentiell schwierigen Problems) in der Cryptanalysis vorgeschlagen: [3] --Qcomp 16:00, 23. Mär. 2011 (CET)

etwas laienverständlicher und weniger technisch

Hallo, ich wüsste gerne, wie Gover prinzipiell funktioniert. Ich stelle mir vor, dass man unbeschränkt viele gleichzeitig laufenden Threads aufrufen kann. Ist das so? Dann kann man das auch schnell mit einer Skizze erklären (und es würde in diesem Fall sogar nicht-probabilistisch gehen). Anyway: Würde mich freuen, wenn jemand dem Artikel einen Absatz "Grundidee" oder "Verfahrensprinzip" oder Ähnliches hinzufügen könnte.

Vielen Dank! (nicht signierter Beitrag von 88.77.3.100 (Diskussion) 01:10, 17. Mär. 2015 (CET))