Welche Art von Algorithmen ist mit einem Quantencomputer schneller?

11

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?nlogn

hgund
quelle
1
Ich schlage vor, Sie formulieren Ihre Frage neu. Sie fragen sich wirklich, welche Probleme mit Quantencomputern schneller gelöst werden können.
Yuval Filmus
1
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:

12
  • kak=bab
  • 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