Probleme ohne bekannten Quantenvorteil

Ich habe mich gefragt, was die Liste der aktuellen natürlichen Rechenprobleme ist, für die es keinen bekannten Komplexitätsvorteil bei der Verwendung eines Quantencomputers gibt.

Zunächst einmal denke ich, dass die Berechnung der Bearbeitungsentfernung eine ist, für die der schnellste bekannte Quantenalgorithmus der schnellste bekannte klassische zu sein scheint. Vorläufiger würde ich auch das Sortieren als ein weiteres Problem vorschlagen, für das keine Quantenbeschleunigung bekannt ist (im Vergleich zum schnellsten bekannten Wort-RAM-Algorithmus für Stückkosten).

Obwohl ich keine harte Einschränkung festlegen möchte, interessiere ich mich besonders für Probleme in NP und / oder Probleme ohne bekannte effiziente klassische Lösung.

Auf Vorschlag von Juan Bermejo Vega folgt hier eine weitere Klarstellung. Ich interessiere mich für Probleme in NP, für die derzeit überhaupt kein großer Vorteil der Zeit-Komplexität bekannt ist, wenn Sie einen Quantencomputer verwenden. $O$

Ich konzentriere mich nicht auf Fälle, in denen wir beweisen können, dass es keinen Vorteil gibt, noch konzentriere ich mich auf exponentielle Beschleunigungen (dh Polynom wäre auch in Ordnung). Bisher scheinen die einzigen zwei Beispiele die in meiner Frage zu sein, was sehr überraschend erscheint, wenn es wirklich wahr ist.

ds.algorithms quantum-computing big-list Lembik
quelle

Komplexitätsvorteil, da die Gesamtlaufzeit nicht beschleunigt wird oder der Sprachkurs während der Operation geschlossen wird?

Ryan

@ Ryan Ich meinte keine Beschleunigung in der Gesamtlaufzeit. Danke für die Frage.

Lembik

Alles schon Polynomzeit. :-)

Kasterma

@kasterma Ich denke nicht, dass das richtig ist. Es gibt viele Poly-Time-Probleme, für die es derzeit eine Quantenbeschleunigung gibt.

Lembik

Ich würde vorschlagen, diese Frage zu verfeinern und anzugeben, ob (a) es sich um "keinen nachweisbaren Quantenvorteil" gegenüber "keinen bekannten Quantenvorteil" handelt; ob (b) es sich um exponentielle oder polynomielle Beschleunigungen handelt (in Bezug auf Probleme, die nicht in P oder BPP vorliegen); und ob (c) andere Arten von Beschleunigungen (z. B. logarithmische Beschleunigungen aufgrund von Problemen innerhalb von P oder BPP) zulässig sind.

Juan Bermejo Vega

Antworten:

Dies ist nicht in NP, sondern vergleichsbasierte Sortierung. Die Untergrenze von ist informationstheoretisch. $\Omega(n \log n)$

Tyson Williams
quelle

Die gebundene Informationstheorie zeigt nicht, dass Quantenalgorithmen sie nicht schlagen können. (Betrachten Sie den Grover-Algorithmus .)

$\:$

$\;\;\;\;$

@ RickyDemer Ich bin mir nicht sicher, was du denkst. Informationstheoretische Argumente gelten unabhängig vom Berechnungsmodell. Bei einer unstrukturierten Suche ist die Eingabe ein Array von Elementen und ein Zielelement , und die Ausgabe ist ein Index so dass (von dem ich der Einfachheit halber annehme, dass es existiert). Da bei jeder Abfrage ein Bit gelernt wird, besagt die Informationstheorie, dass jeder Algorithmus Abfragen durchführen muss. Der Algorithmus von Grover bei -Anfragen ist weit davon entfernt, an diese Grenze gebunden zu sein, sondern weniger als diese.

A

$A$

n

$n$

x

$x$

i

$i$

A [i] = x

$A[i] = x$

\log n

$\log n$

Θ (\sqrt{n})

$\Theta(\sqrt{n})$

Tyson Williams

Soweit ich weiß, gelten entropie- / zählbasierte Argumente für Quantenalgorithmen nicht sofort, da es sich um Wahrscheinlichkeitsverteilungen und nicht um Überlagerungen von Quantenzuständen handelt. Die von geordnete Suchuntergrenze war beispielsweise ein FOCS-Papier von Ambainis, und die Sortieruntergrenze scheint auch einige Arbeiten zu erfordern. Arxiv.org/abs/quant-ph/0102078 . Es scheint also, dass Ihre Behauptung richtig ist, aber nicht so unmittelbar, wie Sie es vorschlagen.

Ω (\log n)

$\Omega(\log n)$

Sasho Nikolov

@SashoNikolov Das unstrukturierte Suchproblem, wie ich es für Ricky definiert habe, bot keine Option zum Fehlschlagen. Das Argument, das ich gegeben habe, gilt für dieses Problem. Die von Ambainis bei FOCS angegebene Untergrenze (die ich nicht finden konnte) ist wahrscheinlich für das allgemeinere Problem, bei dem nur einer mit geringer Wahrscheinlichkeit erfolgreich sein muss. Gleiches gilt für das Problem des Sortierens und des arXiv-Papiers, auf das Sie verlinken.

Tyson Williams

@SashoNikolov: Ich stimme dem zu, was du geschrieben hast. Informationstheoretische Grenzen der Form Tyson beschreiben, wo "ein Bit mit einer Abfrage gelernt wird" nicht unbedingt für Quanten gelten. Betrachten Sie das Bernstein-Vazirani-Problem, bei dem die Ausgabe des Problems Bits beträgt und daher eine klassische Maschine aus informationstheoretischen Gründen Abfragen durchführen muss, aber ein Quantencomputer kann dies mit 1 Abfrage tun.

n

$n$

n

$n$

Robin Kothari

Kürzlich hat dieses Papier in SODA 2018 einen Konstantfaktor-Approximationsalgorithmus für die Bearbeitungsentfernung in Quantencomputern mit subquadratischer Zeit gezeigt. Es ist zu beachten, dass noch kein Algorithmus zur Approximation konstanter Faktoren für die Bearbeitungsentfernung in klassischen Computern mit subquadratischer Zeit bekannt ist. Darüber hinaus wird angenommen, dass ein solcher Algorithmus in klassischen Computern nicht existiert.

Mohemnist
quelle

Ich denke nicht, dass der letzte Satz richtig ist. Eine klassische Lösung mit derselben Komplexität hat keine Konsequenzen für die Komplexität.

Lembik

@Lembik Du hattest recht. Das Papier hat das vorherige Papier irgendwie dequantisiert und einen Algorithmus zur Approximation konstanter Faktoren für die Bearbeitungsentfernung in subquadratischer Zeitkomplexität gefunden. Weitere Informationen finden Sie in diesem Blogbeitrag .

Mohemnist