Kontext :
Es gibt mehrere Artikel , die die Auswirkungen geschlossener zeitlicher Kurven (CTCs) auf die Quantenkomplexität untersuchen. Im Jahr 2008 veröffentlichten Aaronson und Watrous ihre berühmte Arbeit zu diesem Thema, die zeigt, dass bestimmte Formen der Zeitreise klassische und Quantencomputer gleichwertig machen können, dh Quantencomputer bieten keinen Rechenvorteil, wenn sie Informationen über zeitlich geschlossene Kurven in die Vergangenheit senden können.
Fragen :
Die Zusammenfassung besagt eindeutig, dass geschlossene zeitliche Kurven nicht bekannt sind. Warum genau interessieren sich Komplexitätstheoretiker für dieses Thema? Bietet das Studium von CTCs einen nicht trivialen Einblick in die Grundlagen der Komplexitätstheorie?
Gibt es andere Weltlinien , die im Kontext der Komplexitätstheorie populär untersucht werden? Wenn ja, warum? Wenn nicht, warum nicht (und was ist dann das Besondere an CTCs)?
Ich bin nicht wirklich dazu gekommen, die CTC-Papiere durchzuarbeiten, aber ich versuche, mir hier ein Bild vom "großen Bild" zu machen, um die Motivation zu verstehen, die hinter dem Studium dieses Themas steckt.
Hinweis : Ich habe zuvor im Rahmen der Quanteninformationstheorie auf Quantum Computing SE danach gefragt , aber hier versuche ich speziell , dies durch die Linsen eines Komplexitätstheoretikers oder Informatikers zu betrachten.
Antworten:
Ich denke, die große Frage hier ist: "Wie sieht die Komplexität / Leistungsfähigkeit von Algorithmen in unserem Universum aus?" Wenn wir Relativitätstheorie und QM ignorieren, sind einfache Vanille-Turing-Maschinen ein anständiges Modell. Relativitätstheorie und QM sind jedoch unsere derzeit besten physikalischen Theorien zur Erklärung des Universums. Daher stellt sich die Frage, ob relativistische oder Quanteneffekte die Komplexitätslandschaft verändern.
Im Fall von QM ist dies nun auch durch das Potenzial für die Entwicklung funktionierender Quantencomputer motiviert. Im Fall von CTCs sind sie meines Erachtens nach der Relativitätstheorie zulässig, obwohl nicht bekannt ist, dass sie existieren. Die Frage ist also: Wenn sie existieren würden und wir sie nutzen könnten, was könnten Computer sonst noch tun / wie ändert sich die Komplexität? (Gleiches gilt für QM, wir sind nur näher an den vorhandenen Quantencomputern.)
Zum Schluss noch ein bisschen über den persönlichen Geschmack; Obwohl dies subjektiv ist, geht es bei der Frage selbst zumindest ein wenig um den subjektiven Geschmack, daher hoffe ich, dass dies angemessen ist. Ich möchte hier (freundlicherweise) ein wenig mit Usul nicht einverstanden sein. Ich denke nicht, dass alle Ressourcen für (die meisten) Komplexitätstheoretiker unbedingt interessant sind. Beispielsweise kann man auf einer Turing-Maschine Kopfumkehrungen als Ressource betrachten (wie oft ändert der Bandkopf während einer Berechnung die Richtung?). Man kann sogar zeigen, dass dies ein Blum-Komplexitätsmaß ist, mit Lücken-, Beschleunigungs- und Hierarchiesätzen analog zu Zeit oder Raum. Ich habe dies als eine unterhaltsame Übung in Grundstudiengängen gesehen, aber nicht viel Forschung darüber gesehen. Warum? Vielleicht Sie, weil es sich modellabhängiger und weniger relevant für andere Dinge anfühlt, die den Menschen in Bezug auf die Komplexität von Algorithmen wichtig sind. In ähnlicher Weise studieren Menschen Hyperberechnung (was könnte ein TM mit unendlich vielen Schritten tun); Es gibt sicherlich mehr Forschung zu diesem Thema, aber ich denke, es ist weniger gut motiviert von der physischen Realität ... Mein Punkt hier ist nicht, bestimmte Forschungsrichtungen zu verleumden (tatsächlich denke ich, dass sie etwas interessant sind), sondern mehr, was ich nicht tue Ich glaube nicht, dass Komplexitätstheoretiker notwendigerweise "per Definition" an CTCs interessiert sind, sondern es gibt zusätzliche Überlegungen, die dazu führen, dass sie für viele interessant sind. (Und natürlich finden sie wahrscheinlich nicht alle Komplexitätstheoretiker interessant!) Es gibt sicherlich mehr Forschung zu diesem Thema, aber ich denke, es ist weniger gut motiviert von der physischen Realität ... Mein Punkt hier ist nicht, bestimmte Forschungsrichtungen zu verleumden (tatsächlich denke ich, dass sie etwas interessant sind), sondern mehr, was ich nicht tue Ich glaube nicht, dass Komplexitätstheoretiker notwendigerweise "per Definition" an CTCs interessiert sind, sondern es gibt zusätzliche Überlegungen, die dazu führen, dass sie für viele interessant sind. (Und natürlich finden sie wahrscheinlich nicht alle Komplexitätstheoretiker interessant!) Es gibt sicherlich mehr Forschung zu diesem Thema, aber ich denke, es ist weniger gut motiviert von der physischen Realität ... Mein Punkt hier ist nicht, bestimmte Forschungsrichtungen zu verleumden (tatsächlich denke ich, dass sie etwas interessant sind), sondern mehr, was ich nicht tue Ich glaube nicht, dass Komplexitätstheoretiker notwendigerweise "per Definition" an CTCs interessiert sind, sondern es gibt zusätzliche Überlegungen, die dazu führen, dass sie für viele interessant sind. (Und natürlich finden sie wahrscheinlich nicht alle Komplexitätstheoretiker interessant!) Vielmehr gibt es zusätzliche Überlegungen, die dazu führen, dass sie für viele interessant sind. (Und natürlich finden sie wahrscheinlich nicht alle Komplexitätstheoretiker interessant!) Vielmehr gibt es zusätzliche Überlegungen, die dazu führen, dass sie für viele interessant sind. (Und natürlich finden sie wahrscheinlich nicht alle Komplexitätstheoretiker interessant!)
quelle
Entschuldigen Sie die sehr "große" Antwort eines Nicht-Quantentheoretikers, aber dieser Kontrast könnte helfen: Sie könnten Algorithmen als das Studium der Lösung von Rechenproblemen beschreiben, während die Komplexitätstheorie die in der Theorie erforderlichen Ressourcen (insbesondere die Zeit) untersucht um sie zu lösen. Wie schwer sind diese Probleme wirklich auf einer fundamentalen Ebene und wie werden sie nach Ressourcenanforderungen klassifiziert? Diese Frage wird als interessant angesehen, unabhängig davon, wie viele oder welche Arten von Ressourcen mickrigen Menschen zufällig zur Verfügung stehen.
Die Frage, wie viel Zeit theoretisch zur Lösung eines Problems benötigt wird, ändert sich, wenn Sie CTCs zulassen. Daher sind sie per Definition für die Komplexitätstheorie interessant.
Ich denke, Ihre erste Frage ist wie die Frage, warum Theoretiker der Berechenbarkeit Turing-Grade über Null studieren würden. es ist was sie tun.
quelle
Wenn man Geodäten als eine geometrische Weltlinienanalyse der Grover-Suche betrachtet, zeigen Sie unter einer Metrik, dass die Grover-Suche einer Geodät folgt. Auch bei kleinen Störungen funktioniert die Grover-Suche gut. Bei einer Störung kann die Grover-Suche unter einer Art Kahler-Metrik - der Fubini-Study-Metrik - einer geodätischen Suche nicht folgen, siehe Störungsstudie . Referenzen für Optimalität und Informationsgeometrie der Grover-Suche .
Alvarez et al. Zeigten zunächst, dass die Grover-Suche einer Geodät unter der Fubini-Study-Metrik folgt, und untersuchten andere Quantenalgorithmen wie den Shors-Algorithmus. Obwohl dies im Zusammenhang mit Fisher-Informationen durchgeführt wurde, zeigte sich dennoch, dass unter der Fubini-Studie die Grover-Suche einer geodätischen Suche folgt. Außerdem zeigen Alvarez et al. Unter Fisher-Informationsannahmen: "Shors Faktorisierung bewahrt keine konstanten Fisher-Informationen."
quelle