Die Darstellung des Raz-Tal-Resultats im Abschnitt gefällt mich nicht recht: Dass ein Quantencomputer relativ zu einem Orakel mehr kann als ein klassischer Computer (=BPP) ist doch schon spätestens seit Simons Algorithmus bekannt (und unabhängig davon, ob BQP=NP). Bei Raz-Tal geht es, soweit ich es verstehe, darum, dass BQP (relativ zu einem Orakel) nicht in der polynomialen Hierarchie liegt (zu der Simons Problem meines Wissens nicht gehört), das heisst es liefert weitere Information wie sich BQP von den klassisch effizient lösbaren Problemen unterscheidet (und wird vielleicht mal ein wichtiger Schritt auf dem Weg zu einem BQPNP-Beweis gewesen sein). Aber das im ersten Satz des Abschnitts genannte Problem ist immer noch offen, denn für die Orakel, relativ zu denen Trennungen gezeigt wurden, ist keine effiziente Realisierung bekannt. Daher finde ich den Abschnitt irreführend, ich bin aber kein Komplexitätsexperte. Was man hier mE sagen sollte ist (1) es gibt keinen Beweis dafür, dass BQPBPP (also dass die vom Quantencomputer effizient lösbaren Probleme strikt mehr sind als die klassisch effizient lösbaren), (2) eine Trennung lässt sich für Sampling-Probleme zeigen, wenn man annimmt, dass die Polynomialzeithierarchie nicht kollabiert (vgl. BosonSampling etc.) (3) eine Trennung lässt sich auch relativ zu bestimmten Orakeln zeigen (Bernstein-Vazirani, Simon, ..., Raz-Tal), aber das sagt nichts über die Trennung ohne Orakel. (4) Es gibt konkrete Probleme, für die ein effizienter Quantenalgorithmus bekannt ist, aber kein effizienter klassischer Algorithmus (Primfaktorzerlegung, Quantensimulation). Die Kerenidis-Tang-Geschichte gehört hier mE eigentlich nicht hin. Ggf könnte man sie als Beispiel bringen, dass mein Punkt (4) nicht viel bedeuten muss. -- Meinungen? -- Qcomp 22:58, 22. Jan. 2022 (CET)