Welche Art von Algorithmen ist mit einem Quantencomputer schneller?

Ich bin ein CS-Anfänger und lerne Algorithmen. Ich habe gehört, dass selbst mit Quantencomputern allgemeine Sortieralgorithmen niemals eine bessere Zeit als können. Ich weiß jedoch auch, dass Factoring-Algorithmen viel schneller sind. Im Allgemeinen, welche Art von Algorithmen würde mit Quantencomputern wesentlich schneller werden? $n\log n$

algorithms quantum-computing hgund
quelle

Ich schlage vor, Sie formulieren Ihre Frage neu. Sie fragen sich wirklich, welche Probleme mit Quantencomputern schneller gelöst werden können.

Yuval Filmus

Scott Aaronson (der Quantencomputer-Guru) hat (zwei Versionen von a) genau über dieses Thema gesprochen, mit dem Titel * Wann genau bieten Quantencomputer eine Beschleunigung? ". Sie finden sie (oder besser gesagt) hier: scottaaronson.com/ Gespräche .

Yuval Filmus

Soweit ich weiß, keine . Wir brauchen neue Algorithmen. (Siehe Yuvals ersten Kommentar.)

Raphael

Es ist nicht wirklich bewiesen, dass Factoring schneller ist, nur vermutet usw., es ist eine offene Frage P? = BQP usw.

vzn

Eng verwandt: Warum und wie ist ein Quantencomputer schneller als ein normaler Computer?

Gilles 'SO - hör auf böse zu sein'

Antworten:

$k$ $a^{k} = b$ $a$ $b$
Der Grover-Algorithmus beschleunigt die Suche nach unsortierten Listen quadratisch (was für viele Algorithmen als Beschleunigung verwendet werden kann).
Die Simulation von Quantensystemen erfolgt ebenfalls in BQP, auf einem klassischen TM jedoch exponentiell langsamer.
Das Lösen der Pellschen Gleichung (nicht wirklich eine Gleichung) erfolgt in BQP, einer weiteren exponentiellen Beschleunigung.
Es gibt auch eine Reihe anderer, dunklerer Probleme, die in BQP auftreten, aber anscheinend nicht in P. Wocjan und Zhang einen guten Ausgangspunkt bieten , um sie auszugraben.

Luke Mathieson
quelle