Gibt es eine allgemeine Aussage darüber, welche Arten von Problemen mit einem Quantencomputer effizienter gelöst werden können?

Gibt es eine allgemeine Aussage darüber, welche Arten von Problemen mit Quantencomputern effizienter gelöst werden können (nur Quantengatemodell)? Haben die Probleme, für die heute ein Algorithmus bekannt ist, eine gemeinsame Eigenschaft?

Soweit ich verstehe, hilft Quanten-Computing beim Problem der versteckten Untergruppen (Shor). Der Algorithmus von Grover beschleunigt die Suche. Ich habe gelesen, dass Quantenalgorithmen eine Beschleunigung bewirken können, wenn Sie nach einer 'globalen Eigenschaft' einer Funktion suchen (Grover / Deutsch).

1. Gibt es eine präzisere und korrektere Aussage darüber, wo Quantencomputer helfen können?
2. Kann man eine Erklärung geben, warum die Quantenphysik dort helfen kann (am besten etwas Tieferes, um 'Störungen auszunutzen')? Und warum hilft es möglicherweise nicht bei anderen Problemen (zB bei NP-kompletten Problemen)?

Gibt es relevante Papiere, die genau das diskutieren?

Ich hatte diese Frage schon einmal auf cstheory.stackexchange.com gestellt, aber möglicherweise ist sie hier besser geeignet.

Zur allgemeinen Hilfsbereitschaft bei der Berechnung

Ohne es vielleicht zu bemerken, stellen Sie eine Version einer der schwierigsten Fragen, die Sie möglicherweise über theoretische Informatik stellen können. Sie können dieselbe Frage zu klassischen Computern stellen, nur anstatt zu fragen, ob das Hinzufügen von 'Quantumness' hilfreich ist, können Sie Folgendes fragen:

• Gibt es eine präzise Aussage darüber, wo randomisierte Algorithmen helfen können?

  Es ist möglich, hier etwas sehr vages zu sagen - wenn Sie denken, dass es viele Lösungen gibt (oder dass es viele Lösungen für ein Unterproblem gibt), es jedoch schwierig sein könnte, eine systematisch zu konstruieren, ist es hilfreich, wenn Sie in der Lage sind, Lösungen zu finden zufällige Auswahl, um das Problem der systematischen Konstruktion zu überwinden. Aber Vorsicht, manchmal ist der Grund, warum Sie wissen, dass es zahlreiche Lösungen für ein Teilproblem gibt, der, dass es einen Beweis unter Verwendung der probabilistischen Methode gibt . Wenn dies der Fall ist, wissen Sie, dass die Anzahl der Lösungen durch die Reduktion auf einen hilfreichen randomisierten Algorithmus reichlich ist!

  Es gibt keine einfache Beschreibung, wann ein randomisierter Algorithmus hilfreich sein kann, es sei denn, Sie haben eine andere Möglichkeit, die Tatsache zu rechtfertigen, dass die Anzahl der Lösungen für diese Fälle reichlich ist. Und wenn Sie genügend Hilfsbereitschaft verlangen (ein superpolynomischer Vorteil), fragen Sie sich, ob , was ein ungelöstes Problem in der Komplexitätstheorie ist. $\mathsf P \ne \mathsf{BPP}$
  
  

• Gibt es eine kurze Aussage darüber, wo parallelisierte Algorithmen helfen können?

  Hier ist es vielleicht etwas besser. Wenn ein Problem so aussieht, als ob es in viele unabhängige Unterprobleme zerlegt werden kann, kann es parallelisiert werden - obwohl dies ein vages Kriterium ist, dass Sie es erkennen, wenn Sie es sehen. Die wichtigste Frage ist, werden Sie es wissen , wenn Sie es sehen? Hätten Sie gedacht, dass die Machbarkeitsprüfung von linearen Gleichungssystemen über die Rationalen nicht nur parallelisierbar ist, sondern auch mit -Tiefenschaltungen gelöst werden kann [vgl.  Comput. Komplex. 8 (S. 99-126), 1999 ]?$O(\log^2 n)$

  Eine Art und Weise, wie Menschen versuchen, ein Gesamtbild dafür zu zeichnen, besteht darin, sich der Frage aus der entgegengesetzten Richtung zu nähern und zu sagen, wann bekannt ist, dass ein parallelisierter Algorithmus nicht hilft. Insbesondere hilft es nicht, wenn das Problem einen von Natur aus sequenziellen Aspekt hat. Dies ist jedoch kreisförmig, da "sequentiell" nur bedeutet, dass die Struktur, die Sie für das Problem sehen können, nicht parallelisiert ist.

  Auch hier gibt es keine einfache, umfassende Beschreibung, wann ein parallelisierter Algorithmus Abhilfe schaffen kann. Und wenn Sie genügend Hilfsbereitschaftsansprüche haben (eine polylogarithmische Obergrenze für die Zeitdauer unter der Annahme einer polynomiellen Parallelisierung), dann fragen Sie sich, ob $\mathsf P \ne \mathsf{NC}$ , was wiederum ein ungelöstes Problem in der Komplexitätstheorie ist .
  
  

Die Aussichten für "präzise und korrekte Beschreibungen, wann [X] hilfreich ist" sehen zu diesem Zeitpunkt nicht allzu gut aus. Auch wenn Sie protestieren könnten, dass wir hier zu streng sind: Aus Gründen der Forderung nach mehr als einem Polynomvorteil konnten wir nicht einmal behaupten, dass nicht deterministische Turing-Maschinen "hilfreich" waren (was eindeutig absurd ist). Wir sollten keine so hohe Messlatte fordern - da es keine Techniken gibt, um die Erfüllbarkeit effizient zu lösen, sollten wir zumindest akzeptieren, dass wir eine nicht deterministische Turing-Maschine in der Tat sehr hilfreich finden , wenn wir sie irgendwie erhalten könnten . Dies unterscheidet sich jedoch davon, genau zu charakterisieren , für welche Probleme wir es hilfreich finden würden.

Zur Hilfsbereitschaft von Quantencomputern

Gibt es etwas , was wir sagen können, wenn Quantencomputer hilfreich sind?

Wir können dies sagen: Ein Quantencomputer kann nur etwas Interessantes tun, wenn er die Struktur eines Problems ausnutzt, die für einen klassischen Computer nicht verfügbar ist. (Dies wird durch die von Ihnen erwähnten Bemerkungen zu einer "globalen Eigenschaft" eines Problems angedeutet.) Aber wir können mehr als das sagen: Probleme, die von Quantencomputern im Einheitsschaltungsmodell gelöst werden, werden einige Merkmale dieses Problems als Einheitsoperatoren hervorrufen . Die Merkmale des Problems, die für klassische Computer nicht verfügbar sind, sind alle, die keine (nachweislich) statistisch signifikante Beziehung zur Standardbasis haben.

• Im Fall von Shors Algorithmus sind dies die Eigenwerte eines Permutationsoperators, der als Multiplikation über einen Ring definiert ist.
• $\pm 1$

Es ist nicht besonders überraschend zu sehen, dass sich die Informationen in beiden Fällen auf Eigenwerte und Eigenvektoren beziehen. Dies ist ein hervorragendes Beispiel für eine Eigenschaft eines Betreibers, die keine sinnvolle Beziehung zur Standardbasis haben muss. Es gibt jedoch keinen besonderen Grund, warum die Information ein Eigenwert sein muss. Alles, was benötigt wird, ist, in der Lage zu sein, einen einheitlichen Operator zu beschreiben, der ein relevantes Merkmal des Problems codiert, das aus der Inspektion der Standardbasis nicht ersichtlich ist, aber auf eine andere leicht zu beschreibende Weise zugänglich ist .

Letztendlich besagt dies nur, dass ein Quantencomputer nützlich ist, wenn Sie einen Quantenalgorithmus zur Lösung eines Problems finden können. Zumindest handelt es sich jedoch um einen groben Überblick über eine Strategie zum Auffinden von Quantenalgorithmen, der nicht schlechter ist als der grobe Überblick über Strategien, die ich oben für randomisierte oder parallelisierte Algorithmen beschrieben habe.

Anmerkungen, wann ein Quantencomputer "hilfreich" ist

Wie andere hier angemerkt haben, hängt "wo Quantencomputer helfen können" davon ab, was Sie mit "Hilfe" meinen.

• Shors Algorithmus wird in solchen Diskussionen oft auf den Prüfstand gestellt, und hin und wieder wird darauf hingewiesen, dass wir nicht wissen, dass die Faktorisierung in der Polynomzeit nicht lösbar ist. Wissen wir also eigentlich, dass "Quantencomputing hilfreich wäre, um Zahlen zu faktorisieren"?

  Abgesehen von den Schwierigkeiten bei der Realisierung von Quantencomputern, denke ich, lautet die vernünftige Antwort hier "Ja". nicht, weil wir wissen, dass Sie mit herkömmlichen Computern nicht effizient arbeiten können, sondern weil wir nicht wissen, wie Sie dies mit herkömmlichen Computern tun würden. Wenn Ihnen Quantencomputer dabei helfen, etwas zu tun, für das Sie keinen besseren Ansatz haben, scheint mir dies "hilfreich" zu sein.

• $O(2^{0.386\,n})$

  Vielleicht ist der Algorithmus von Grover als solcher nicht besonders hilfreich. Es kann jedoch hilfreich sein, wenn Sie damit cleverere klassische Strategien erarbeiten, die über die Brute-Force-Suche hinausgehen: Durch Amplitudenverstärkung , die natürliche Verallgemeinerung des Grover-Algorithmus auf allgemeinere Einstellungen, können wir die Leistung vieler nicht-trivialer Algorithmen für verbessern SAT (siehe z. B. [ACM SIGACT News  36 (S. 103–108), 2005 - kostenloser PDF-Link ]; Tipp an Martin Schwarz, der mich in den Kommentaren auf diesen Verweis hingewiesen hat).

  Wie bei Grovers Algorithmus führt die Amplitudenverstärkung nur zu einer Beschleunigung des Polynoms. In der Praxis kann jedoch auch eine Beschleunigung des Polynoms interessant sein, wenn sie nicht durch den mit dem Schutz der Quanteninformationen vor Rauschen verbundenen Overhead verschlechtert wird.

TL; DR: Nein, wir haben keine genaue "allgemeine" Aussage darüber, welche Art von Problemen Quantencomputer komplexitätstheoretisch lösen können . Wir haben jedoch eine grobe Vorstellung.

Laut Wikipedia-Unterartikel zur Relation zur rechnerischen Komplexitätstheorie

Die Klasse von Problemen, die von Quantencomputern effizient gelöst werden können, wird als BQP für "Bounded Error, Quantum, Polynomial Time" bezeichnet. Quantencomputer führen nur probabilistische Algorithmen aus , sodass BQP auf Quantencomputern das Gegenstück zu BPP ("Bounded Error, Probabilistic, Polynomial Time") auf klassischen Computern ist. Es ist definiert als die Menge von Problemen, die mit einem Polynom-Zeit-Algorithmus lösbar sind, dessen Fehlerwahrscheinlichkeit von der Hälfte abgegrenzt ist . Ein Quantencomputer soll ein Problem "lösen", wenn seine Antwort in jedem Fall mit hoher Wahrscheinlichkeit richtig ist. Wenn diese Lösung in Polynomialzeit ausgeführt wird, liegt das Problem bei BQP.

BQP ist in der Komplexitätsklasse #P (oder genauer in der zugehörigen Klasse der Entscheidungsprobleme P ^#P ) enthalten, die eine Unterklasse von PSPACE ist .

Es wird vermutet, dass BQP von NP-vollständig und einer strengen Obermenge von P getrennt ist, aber das ist nicht bekannt. Sowohl die ganzzahlige Faktorisierung als auch das diskrete Protokoll sind in BQP enthalten. Beide dieser Probleme sind NP- Probleme, bei denen der Verdacht besteht, dass sie außerhalb von BPP und daher außerhalb von P liegen. Beide sind vermutlich nicht NP-vollständig. Es gibt ein weit verbreitetes Missverständnis, dass Quantencomputer NP-vollständige Probleme in der Polynomzeit lösen können. Es ist nicht bekannt, dass dies wahr ist, und es wird allgemein vermutet, dass es falsch ist.

Die Fähigkeit eines Quantencomputers, klassische Algorithmen zu beschleunigen, unterliegt starren Grenzen - obere Grenzen der Komplexität der Quantenberechnung. Der überwiegende Teil der klassischen Berechnungen kann auf einem Quantencomputer nicht beschleunigt werden. Eine ähnliche Tatsache tritt für bestimmte Rechenaufgaben auf, wie das Suchproblem, für das der Algorithmus von Grover optimal ist.

${\displaystyle O({\sqrt[{3}]{N}})}$$\displaystyle O({\sqrt {N}})$

Obwohl Quantencomputer für einige Problemtypen möglicherweise schneller sind als klassische Computer, können die oben beschriebenen kein Problem lösen, das klassische Computer nicht bereits lösen können. Eine Turing-Maschine kann diese Quantencomputer simulieren, so dass ein solcher Quantencomputer niemals ein unentscheidbares Problem wie das Halteproblem lösen kann. Die Existenz von "normalen" Quantencomputern widerlegt die These von Church-Turing nicht. Es wurde spekuliert, dass Theorien der Quantengravitation wie die M-Theorie oder die Schleifenquantengravitation den Bau noch schnellerer Computer ermöglichen könnten. Derzeit ist die Definition der Berechnung in solchen Theorien aufgrund des Zeitproblems ein offenes Problem, dh es gibt derzeit keine offensichtliche Möglichkeit, zu beschreiben, was es für einen Beobachter bedeutet, Eingaben an einen Computer zu senden und später Ausgaben zu empfangen.

Was , warum Computer Quanten kann effizient BQP Probleme lösen:

1. $n$$2n$

2. Normalerweise endet die Berechnung auf einem Quantencomputer mit einer Messung. Dies führt zu einem Zusammenbruch des Quantenzustands in einen der Grundzustände. Man kann sagen, dass der Quantenzustand mit hoher Wahrscheinlichkeit als korrekt gemessen wird.

Interessanterweise erhalten wir die Komplexitätsklasse nach BQP , wenn wir theoretisch die Nachauswahl zulassen (die keine skalierbare praktische Implementierung hat) :

In der rechnerischen Komplexitätstheorie ist PostBQP eine Komplexitätsklasse, die aus allen auf einer Quantenturingmaschine mit Nachselektion und beschränktem Fehler in Polynomzeit lösbaren Rechenproblemen besteht (in dem Sinne, dass der Algorithmus mindestens zu 2/3 der Zeit korrekt ist) Eingänge). Die Nachauswahl wird jedoch nicht als Merkmal angesehen, das ein realistischer Computer (auch ein Quantencomputer) besitzen würde, dennoch sind Nachauswahlmaschinen aus theoretischer Sicht interessant.

Ich möchte hinzufügen, was @ Discrete Eidechse in den Kommentaren erwähnt. Sie haben nicht explizit definiert, was Sie unter "kann helfen" verstehen. Die Faustregel in der Komplexitätstheorie lautet jedoch, dass ein Quantencomputer bei der Lösung in Polynomzeit (mit einer Fehlergrenze) helfen kann, wenn die Klasse von Das Problem, das es lösen kann, liegt in BQP, aber nicht in P oder BPP. Die allgemeine Beziehung zwischen den oben diskutierten Komplexitätsklassen wird vermutet :

$\text{P $\subseteq$ BPP $\subseteq$ BQP $\subseteq$ PSPACE}$

P = PSPACE ist jedoch ein offenes Problem in der Informatik . Auch die Beziehung zwischen P und NP ist noch nicht bekannt.

Es gibt keine solche allgemeine Aussage und es ist unwahrscheinlich, dass es bald eine geben wird. Ich werde erklären, warum dies der Fall ist. Für eine teilweise Beantwortung Ihrer Frage kann ein Blick auf die Probleme in den beiden Komplexitätsklassen BQP und PostBQP hilfreich sein.

Die Komplexitätsklassen, die den Problemen am nächsten kommen, die von Quantencomputern des Quantengatemodells effizient gelöst werden können, sind

1. BQP ; und
2. PostBQP

BQP besteht aus den Problemen, die in Polynomialzeit auf einer Quantenschaltung gelöst werden können. Die wichtigsten Quantenalgorithmen, wie Shors Algorithmus, lösen Probleme in BQP.

PostBQP besteht aus den Problemen, die in polynomialer Zeit auf einer Quantenschaltung gelöst werden können, die zusätzlich eine Nachselektion durchführen kann. Dies ist viel leistungsfähiger als PostBQP$=$PP , eine Klasse, die PP enthält.

Derzeit gibt es jedoch keine Methoden, um die Nachselektion praktisch umzusetzen, weshalb PostBQP eher von theoretischem Interesse ist.

Die Beziehung zwischen P, NP und BQP ist derzeit nicht bekannt. und ein offenes Problem in der Größenordnung von P vs. NP. Als allgemeine Aussage darüber, welche Arten von Problemen mit Quantencomputern effizienter gelöst werden können, muss die Frage BQP vs. P beantwortet werden (wenn BQP = P, dann sind Quantencomputer anscheinend nicht effizienter (zumindest für Komplexitätstheoretiker)).

Ähnlich wie das Bild von Blue gefällt mir dieses vom Quanta Magazine besser, da es visuell zusammenzufassen scheint, wovon wir sprechen.