Können Quantenalgorithmen mit exponentieller Beschleunigung mit span-Programmen neu generiert werden?

Es ist nun bekannt, dass die untere Grenze des allgemeinen Gegners die Komplexität von Quantenabfragen aufgrund der bahnbrechenden Arbeiten von Reichardt et al. Dieselbe Arbeitslinie stellt auch Verbindungen zum Span-Programm-Framework her, um Quantenalgorithmen zu entwerfen.

Viele interessante Quantenalgorithmen, einschließlich solcher mit exponentieller Beschleunigung wie Simons Algorithmus und Shors Algorithmus zur Periodensuche, können im Quantenabfragemodell ausgedrückt werden.

Gibt es eine Arbeit, die im allgemeinen Gegnermodell Untergrenzen für diese Algorithmen aufzeigt? Gibt es eine Arbeit, die Simons oder Shors Algorithmen im Rahmen des Span-Programms neu ableitet?

Offensichtlich wurden nur Quantenalgorithmen mit polynomieller Beschleunigung wie die von Grover mithilfe von Span-Programmen (oder Belovs Lerngraph) neu abgeleitet.

Es gibt Arbeiten von Korian et al. Untergrenzen für Simon mit der Polynommethode anzeigen, aber es ist anscheinend kein Weg bekannt, die Untergrenzen der Polynommethode in allgemeine Untergrenzen des Gegners zu übersetzen.

Ich denke, Ihre Frage enthält mindestens 3 Fragen. Ich habe nicht auf alle eine zufriedenstellende Antwort, daher ist dies keine vollständige Antwort. Hoffentlich gibt es mehr Antworten, die alle Ihre Fragen beantworten.

Die Frage im Titel: Können Quantenalgorithmen mit exponentieller Beschleunigung mit span-Programmen neu generiert werden?

Wie Sie bereits bemerkt haben, charakterisiert der allgemeine Widersacher die Komplexität der Quantenabfrage aller Entscheidungsprobleme, einschließlich der Versprechungsprobleme, für die wir eine exponentielle Beschleunigung haben. Im Prinzip gibt es also ein span-Programm, das das Problem der versteckten Abelschen Untergruppen löst. Dies ist das Abfrageproblem, das in Simons und Shors Algorithmen verwendet wird. Ob es dafür ein explizites Span-Programm gibt, ist Ihre nächste Frage.

Gibt es eine Arbeit, die Simons oder Shors Algorithmen im Rahmen des Span-Programms neu ableitet?

Ich habe noch nie von solchen Ergebnissen gehört. Ich kenne kein Span-Programm für Simons Problem oder ein anderes AHSP.

Gibt es eine Möglichkeit, Polynom-Methode-Untergrenzen in allgemeine gegnerische Untergrenzen zu übersetzen?

Ja, ich glaube schon. Ich kann das Papier mit diesem Ergebnis nicht finden, aber ich kann Ihnen einen Link zu einem Vortrag von Jérémie Roland geben . In der Zusammenfassung des Vortrags sagt er Folgendes:

... Genauer gesagt werden wir zeigen, dass die multiplikative Gegnermethode, eine Variation der ursprünglichen Gegnermethode, nicht nur die verallgemeinerte Gegnermethode, sondern auch die Polynommethode verallgemeinert, so dass sie im Wesentlichen alle bekannten Methoden der unteren Schranke umfasst. Daher bietet dies einen konstruktiven Ansatz, um polynomiale Untergrenzen in das Framework der gegnerischen Methode zu werfen.

Update : Der Artikel ist jetzt online verfügbar: Explizite Beziehung zwischen allen untergeordneten Techniken für die Komplexität von Quantenabfragen von Loïck Magnin und Jérémie Roland