Quantenanaloga der SPACE-Komplexitätsklassen

Wir betrachten häufig Komplexitätsklassen, bei denen wir in Bezug auf den Platz, den unsere Turing-Maschine verwenden kann, begrenzt sind, zum Beispiel: oder . Es scheint, dass es in der frühen Komplexitätstheorie viel Erfolg mit diesen Klassen wie dem Raumhierarchiesatz und dem Erstellen wichtiger Klassen wie und . Gibt es analoge Definitionen für die Quantenberechnung? Oder gibt es einen offensichtlichen Grund, warum das Quantenanalog nicht interessant wäre? $\textbf{DSPACE}(f(n))$ $\textbf{NSPACE}(f(n))$ $\textbf{L}$ $\textbf{PSPACE}$

Es scheint wichtig zu sein, eine Klasse wie - eine Quantenversion von : Erfordert eine logarithmische Anzahl von Qubits (oder vielleicht verwendet ein Quantenthermometer logarithmischen Raum). $\textbf{QL}$ $\textbf{L}$

cc.complexity-theory complexity-classes quantum-computing space-bounded Artem Kaznatcheev
quelle

whoops, scheint wie ein Quantenanalog von PSPACE bereits definiert zu sein: BQPSPACE und es ist gleich PSPACE.

Artem Kaznatcheev

Vielleicht möchten Sie "Space-bounded Quantum Complexity" von John Watrous ( cs.uwaterloo.ca/~watrous/Papers/… )

Abel Molina,

@Abel das könnte eine Antwort sein.

Suresh Venkat

Für Raumklassen über dem Polynomraum sind die Quantenklassen und die klassischen Klassen gleich. Was den Quantenlograum angeht, kann ich nicht viel sagen. Ich würde vermuten, dass alles, was wir sagen können,

L \subseteq B Q L \subseteq D S P A C E (\log^{2} n)

$L \subseteq BQL \subseteq DSPACE(\log^2 n)$

Robin Kothari

@Suresh Sicher, ich habe den Link als Antwort hinzugefügt und auch einen Teil der Informationen in die Zusammenfassung aufgenommen.

Abel Molina

Antworten:

Vielleicht möchten Sie die weltraumgebundene Quantenkomplexität überprüfen von John Watrous .

$s=\Omega(\log n)$ $s$ $O(s)$ $s$ $NC^2(2^s) \subseteq DSPACE(s^2) \cap DTIME(2^{O(s)})$

Abel Molina
quelle

Do you mean

Ω (\log n)

$\Omega(\log n)$ ? Also, what is

N C^{2} (2^{s})

$NC^2(2^s)$ ?

Robin Kothari

@Robin:

N C^{2} (2^{s})

$NC^2(2^s)$ is the class of problems solvable by a

s

$s$ -space uniform family of Boolean circuits, with size

2^{O (s)}

$2^{O(s)}$ , depth

O (s^{2})

$O(s^2)$ , and bounded fan-in.

Alessandro Cosentino

@Robin Ja, das meine ich, habe es in meiner Antwort geändert. Ich glaube, dass Alessandro Definition für

N C^{2} (2^{s})

$NC^2(2^s)$ ist richtig.

Abel Molina

Für sublogarithmische Raumgrenzen hat sich gezeigt, dass Quanten stärker sind als klassische

Abuzer Yakaryılmaz, AC Cem Say, "Ungebundene Fehlerquantenberechnung mit kleinen Raumgrenzen", Information and Computation, Vol. 209, S. 873-892, 2011. (etwas ältere Version bei arXiv: 1007.3624 )

und

Abuzer Yakaryılmaz, AC Cem Say, "Sprachen, die von nichtdeterministischen quantenendlichen Automaten erkannt werden", Quantum Information and Computation, Vol. 10, S. 747-770, 2010. ( arXiv: 0902.2081 )

für den unbegrenzten Fehlerfall. Das Papier

A. Ambainis und J. Watrous. Finite Zweiwege-Automaten mit Quantenzuständen und klassischen Zuständen. Theoretical Computer Science, 287 (1): 299–311, 2002 ( arXiv: cs / 9911009v1 )

zusammen mit der Tatsache, dass die Palindromsprache von probabilistischen Turing-Maschinen mit sublogarithmischem Raum nicht erkannt werden kann, zeigen Sie, dass dies auch für den begrenzten Fehlerfall gilt.

Cem Say
quelle