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

12

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.

blk
quelle
3
Ich habe versehentlich für das Schließen als "Off-Topic" gestimmt, weil ich dachte, ich würde über eine andere Frage abstimmen und auf den falschen Tabulator geklickt. Ich denke, dies ist eine großartige Frage, die perfekt zum Thema passt, aber das System lässt mich meine versehentliche Abstimmung nicht zurückziehen.
Artem Kaznatcheev

Antworten:

8

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

Robin Kothari
quelle
2
Ich möchte hier nur auf etwas hinweisen. Wenn das Ziel darin besteht, die Untergrenze für Simons Algorithmus mit der Polynommethode zu ermitteln, in eine gegnerische zu verwandeln und dann wieder in einen Lerngraph-Algorithmus zu verwandeln, würde dies wahrscheinlich nicht funktionieren. (Wenn ich es wäre, würde ich es direkt im Lerndiagramm-Framework finden). Unsere Reduktion erfolgt von der Polynommethode zur multiplikativen Gegnermethode (die stärker ist als der allgemeine Zusatz). Mir ist kein Zusammenhang mit span-Programmen bekannt, da es sich bei der Methode des multiplikativen Gegners nicht um ein SDP handelt.
Loïck
1
@Loïck: Richtig. Selbst wenn die optimale additive Gegenmatrix für Simons Problem gefunden wird, ist es nicht klar, wie ein Span-Programm (oder eine Lernkurve) dafür erstellt werden soll.
Robin Kothari