Análogos quânticos das classes de complexidade SPACE

Costumamos considerar classes de complexidade em que estamos limitados na quantidade de espaço que nossa máquina de Turing pode usar, por exemplo: ou . Parece que no início da teoria da complexidade houve muito sucesso com essas classes, como o teorema da hierarquia espacial e a criação de classes importantes como e . Existem definições análogas para computação quântica? Ou existe alguma razão óbvia para que o análogo quântico não seja interessante? $\textbf{DSPACE}(f(n))$ $\textbf{NSPACE}(f(n))$ $\textbf{L}$ $\textbf{PSPACE}$

Parece que seria importante ter uma classe como - uma versão quântica de : requer um número logarítmico de qubits (ou talvez uma TM quântica use espaço logarítmico). $\textbf{QL}$ $\textbf{L}$

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

gritos, parece que um análogo quântico do PSPACE já está definido: BQPSPACE e é igual ao PSPACE.

Artem Kaznatcheev

Convém verificar "Complexidade quântica limitada pelo espaço", de John Watrous ( cs.uwaterloo.ca/~watrous/Papers/… )

Abel Molina

@ Abel isso poderia ser uma resposta.

Suresh Venkat

Para classes espaciais acima do espaço polinomial, as classes quântica e clássica são iguais. Quanto ao espaço de log quântico, não posso dizer muito. Eu suporia que tudo o que podemos dizer é

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 Claro, adicionei o link como resposta e incluí parte das informações no resumo também.

Abel Molina

Respostas:

Você pode verificar a Complexidade Quântica Limitada pelo Espaço , de John Watrous.

Lá você tem o resultado que para qualquer , a Máquina de Turing quântica funcionando no espaço pode ser simulado por uma máquina de Turing probabilística com o erro ilimitada em execução no espaço . Você também tem que qualquer máquina de Turing Quantum em execução no espaço pode ser simulada em $s=\Omega(\log n)$ $s$ $O(s)$ $s$ $NC^2(2^s) \subseteq DSPACE(s^2) \cap DTIME(2^{O(s)})$

Abel Molina
fonte

Você quer dizer

? Além disso, o que é

Ω (\log n)

$\Omega(\log n)$

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

$NC^2(2^s)$

precisa saber é o seguinte

@ Robin:

é a classe de problemas solucionáveis por uma família uniforme de espaços

de circuitos booleanos, com tamanho

, profundidade

e ventilador limitado.

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

$NC^2(2^s)$

s

$s$

2^{O (s)}

$2^{O(s)}$

O (s^{2})

$O(s^2)$

Alessandro Cosentino

@ Robin Sim, quero dizer isso, mudou na minha resposta. Eu acredito que a definição de Alessandro para

está correta.

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

$NC^2(2^s)$

Abel Molina

Para limites espaciais sublogarítmicos, o quantum provou ser mais poderoso que o clássico, consulte

Abuzer Yakaryılmaz, AC Cem Say, “Computação quântica de erro ilimitado com limites de espaço pequenos”, Information and Computation, vol. 209, pp.873-892, 2011. (versão ligeiramente mais antiga no arXiv: 1007.3624 )

Abuzer Yakaryılmaz, AC Cem Say, “Línguas reconhecidas por autômatos finitos quânticos não determinísticos”, Quantum Information and Computation, vol. 10, pp. 747-770, 2010. ( arXiv: 0902.2081 )

para o caso de erro ilimitado. O papel

A. Ambainis e J. Watrous. Autômatos finitos bidirecionais com estados quânticos e clássicos. Ciência da Computação Teórica, 287 (1): 299–311, 2002, ( arXiv: cs / 9911009v1 )

juntamente com o fato de que a linguagem palíndromo não pode ser reconhecida por máquinas probabilísticas de Turing com espaço sublogarítmico, mostram que o mesmo também é verdadeiro para o caso de erro limitado.

Cem Say
fonte