Análogos quânticos das classes de complexidade SPACE

15

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 NSPACE ( f ( n ) ) . 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 L e PSPACE . 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?DSPACE(f(n))NSPACE(f(n))euPSPACE

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

Artem Kaznatcheev
fonte
gritos, parece que um análogo quântico do PSPACE já está definido: BQPSPACE e é igual ao PSPACE.
Artem Kaznatcheev
9
Convém verificar "Complexidade quântica limitada pelo espaço", de John Watrous ( cs.uwaterloo.ca/~watrous/Papers/… )
Abel Molina
1
@ Abel isso poderia ser uma resposta.
Suresh Venkat
2
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 é . LBQLDSPACE(log2n)
Robin Kothari
@Suresh Claro, adicionei o link como resposta e incluí parte das informações no resumo também.
Abel Molina

Respostas:

16

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 s pode ser simulado por uma máquina de Turing probabilística com o erro ilimitada em execução no espaço O ( s ) . Você também tem que qualquer máquina de Turing Quantum em execução no espaço s pode ser simulada em N C 2 ( 2 s ) D S P A C E ( s 2 ) D T I M E (s=Ω(logn)sO(s)sNC2(2s)DSPACE(s2)DTIME(2O(s))

Abel Molina
fonte
1
Você quer dizer ? Além disso, o que é N C 2 ( 2 s ) ? Ω(logn)NC2(2s)
precisa saber é o seguinte
@ Robin: é a classe de problemas solucionáveis ​​por uma família uniforme de espaços s de circuitos booleanos, com tamanho 2 O ( s ) , profundidade O ( s 2 ) e ventilador limitado. NC2(2s)s2O(s)O(s2)
Alessandro Cosentino
@ Robin Sim, quero dizer isso, mudou na minha resposta. Eu acredito que a definição de Alessandro para está correta. NC2(2s)
Abel Molina
13

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 )

e

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