Quantenanaloga der SPACE-Komplexitätsklassen

15

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 NSPACE ( f ( n ) ) . Es scheint, dass es in der frühen Komplexitätstheorie viel Erfolg mit diesen Klassen wie dem Raumhierarchiesatz und dem Erstellen wichtiger Klassen wie L und PSPACE gab . Gibt es analoge Definitionen für die Quantenberechnung? Oder gibt es einen offensichtlichen Grund, warum das Quantenanalog nicht interessant wäre?DSPACE(f(n))NSPACE(f(n))LPSPACE

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

Artem Kaznatcheev
quelle
whoops, scheint wie ein Quantenanalog von PSPACE bereits definiert zu sein: BQPSPACE und es ist gleich PSPACE.
Artem Kaznatcheev
9
Vielleicht möchten Sie "Space-bounded Quantum Complexity" von John Watrous ( cs.uwaterloo.ca/~watrous/Papers/… )
Abel Molina,
1
@Abel das könnte eine Antwort sein.
Suresh Venkat
2
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, . LBQLDSPACE(log2n)
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:

16

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

s=Ω(logn)sO(s)sNC2(2s)DSPACE(s2)DTIME(2O(s))

Abel Molina
quelle
1
Do you mean Ω(logn)? Also, what is NC2(2s)?
Robin Kothari
@Robin: NC2(2s) is the class of problems solvable by a s-space uniform family of Boolean circuits, with size 2O(s), depth O(s2), and bounded fan-in.
Alessandro Cosentino
@Robin Ja, das meine ich, habe es in meiner Antwort geändert. Ich glaube, dass Alessandro Definition fürNC2(2s)ist richtig.
Abel Molina
13

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