Welche Ergebnisse machen den Quantenraum interessant?

17

Die zeitbegrenzte Quantenberechnung ist offensichtlich sehr interessant. Was ist mit weltraumgebundener Quantenberechnung?

Ich kenne viele interessante Ergebnisse für die Quantenberechnung mit sublogarithmischen Raumgrenzen und verschiedenen Arten von Quantenautomatenmodellen.

Andererseits wurde gezeigt, dass Wahrscheinlichkeit und Quantenraum für unbegrenzte Fehler für jeden konstruierbaren Raum äquivalent sind (Watrous, 1999 und 2003 ).s(n)∈Ω(Log⁡(n))

Ich frage mich , ob es einige konkrete Ergebnisse machen Quanten Raum interessant (mit Ausnahme von sublogarithmic-Raum und Automaten - Modelle).

(Mir ist dieser Eintrag bekannt: Quantenanaloga der SPACE-Komplexitätsklassen .)

quantum-computing space-bounded Abuzer Yakaryilmaz
quelle
1
Entschuldigen Sie die Unwissenheit. Welche Beziehung besteht zwischen raumbegrenzter Quantenberechnung und Quantenschaltungsmodell?
Alex "qubeat"
1
@ Alex'qubeat ': Es ist praktisch, Turing-Maschinen für weltraumgebundene Berechnungen zu verwenden. Das Schaltungsmodell eignet sich für zeitlich begrenzte Berechnungen.
Abuzer Yakaryilmaz
1
Warum ist es bequemer? Ist es im Quanten- oder im klassischen Fall zweckmäßig? Aus naiver Sicht ist es für (klassische) Turingmaschinen unbeschränkter Platz.
Alex "qubeat"
1
@ Alex'qubeat ': Es ist sowohl für klassische als auch für Quantenfälle geeignet. Ich kann Ihnen das grundlegende Papier zu diesem Thema von Stearns, Hartmanis und Lewis wärmstens empfehlen: "Hierarchies of memory limited computations" ( computer.org/portal/web/csdl/doi/10.1109/FOCS.1965.11 ). Sie können auch beide Artikel von Watrous (oben erwähnt) und einen kürzlich erschienenen Artikel von Melkebeek und Watson ( theoryofcomputing.org/articles/v008a001 ) lesen .
Abuzer Yakaryilmaz
1
Vielen Dank, ich habe gesehen, aber es gibt auch Arbeit Quanten mit Schaltungen arxiv.org/abs/0908.1467 , dass zumindest nicht aus der Not leidet mit wenigen unterschiedlichen Definitionen von QTM zu verwalten.
Alex "qubeat"

Antworten: