Analogues quantiques des classes de complexité SPACE

Nous considérons souvent les classes de complexité où nous sommes limités dans la quantité d'espace que notre machine de Turing peut utiliser, par exemple: ou . Il semble qu'au début de la théorie de la complexité, il y eut beaucoup de succès avec ces classes telles que le théorème de la hiérarchie spatiale et la création sur des classes importantes comme et . Existe-t-il des définitions analogues pour le calcul quantique? Ou y a-t-il une raison évidente pour laquelle l'analogue quantique ne serait pas intéressant? $\textbf{DSPACE}(f(n))$ $\textbf{NSPACE}(f(n))$ $\textbf{L}$ $\textbf{PSPACE}$

Il semble qu'il serait important d'avoir une classe comme --- une version quantique de : nécessite un nombre logarithmique de qubits (ou peut-être qu'un quantum TM utilise l'espace logarithmique). $\textbf{QL}$ $\textbf{L}$

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

whoops, il semble qu'un analogue quantique de PSPACE soit déjà défini: BQPSPACE et il est égal à PSPACE.

Artem Kaznatcheev

Vous voudrez peut-être vérifier «Complexité quantique liée à l'espace», par John Watrous ( cs.uwaterloo.ca/~watrous/Papers/… )

Abel Molina

@Abel, cela pourrait être une réponse.

Suresh Venkat

Pour les classes spatiales supérieures à l'espace polynomial, les classes quantique et classique sont égales. Quant à l'espace journal quantique, je ne peux pas en dire beaucoup. Je suppose que tout ce que nous pouvons dire est

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 Bien sûr, j'ai ajouté le lien comme réponse et j'ai également inclus une partie des informations dans le résumé.

Abel Molina

Réponses:

Vous voudrez peut-être vérifier la complexité quantique limitée par l'espace , par John Watrous.

Là, vous avez le résultat que pour tout , une machine de Turing quantique fonctionnant dans l'espace peut être simulée par une machine de Turing probabiliste avec une erreur illimitée fonctionnant dans l'espace . Vous avez également la possibilité de simuler n'importe quelle machine de quantification fonctionnant dans l'espace en $s=\Omega(\log n)$ $s$ $O(s)$ $s$ $NC^2(2^s) \subseteq DSPACE(s^2) \cap DTIME(2^{O(s)})$

Abel Molina
la source

Ω (\log n)

$\Omega(\log n)$

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

$NC^2(2^s)$

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

$NC^2(2^s)$

s

$s$

2^{O (s)}

$2^{O(s)}$

O (s^{2})

$O(s^2)$

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

$NC^2(2^s)$ est correct.

Abel Molina

Pour les limites spatiales sublogarithmiques, le quantum s'est avéré plus puissant que le classique, voir

Abuzer Yakaryılmaz, AC Cem Say, «Calcul quantique à erreur illimitée avec de petites limites d'espace», Information et calcul, vol. 209, pp.873-892, 2011. (version légèrement plus ancienne sur arXiv: 1007.3624 )

Abuzer Yakaryılmaz, AC Cem Say, «Langues reconnues par des automates finis quantiques non déterministes», Information quantique et calcul, vol. 10, pp. 747-770, 2010. ( arXiv: 0902.2081 )

pour le cas d'erreur illimitée. Le papier

A. Ambainis et J. Watrous. Automates finis bidirectionnels avec états quantiques et classiques. Informatique théorique, 287 (1): 299-311, 2002, ( arXiv: cs / 9911009v1 )

avec le fait que le langage palindrome ne peut pas être reconnu par les machines probabilistes de Turing avec un espace sublogarithmique, montrent que cela est également vrai pour le cas d'erreur borné.

Cem Say
la source