A menudo consideramos clases de complejidad donde estamos limitados en la cantidad de espacio que nuestra máquina Turing puede usar, por ejemplo: o NSPACE ( f ( n ) ) . Parece que al principio de la teoría de la complejidad hubo mucho éxito con estas clases, como el teorema de la jerarquía espacial y la creación de clases importantes como L y PSPACE . ¿Hay definiciones análogas para la computación cuántica? ¿O hay alguna razón obvia por la cual el análogo cuántico no sería interesante?
Parece que sería importante tener una clase como --- una versión cuántica de : requiere un número logarítmico de qubits (o tal vez una TM cuántica usa espacio logarítmico).
cc.complexity-theory
complexity-classes
quantum-computing
space-bounded
Artem Kaznatcheev
fuente
fuente
Respuestas:
Es posible que desee verificar la complejidad cuántica limitada por el espacio , por John Watrous.
Ahí tiene el resultado de que para cualquier , una máquina de Turing cuántica que se ejecuta en el espacio s puede ser simulada por una máquina de Turing probabilística con un error ilimitado que se ejecuta en el espacio O ( s ) . También tiene que cualquier máquina Quantum Turing que se ejecute en el espacio s se puede simular en N C 2 ( 2 s ) ⊆ D S P A C E ( s 2 ) ∩ D T I M E (s=Ω(logn) s O(s) s NC2(2s)⊆DSPACE(s2)∩DTIME(2O(s))
fuente
Para los límites del espacio sublogarítmico, se ha demostrado que Quantum es más poderoso que el clásico, ver
Abuzer Yakaryılmaz, AC Cem Say, "Computación cuántica de error ilimitado con pequeños límites de espacio", Información y Computación, vol. 209, pp.873-892, 2011. (versión ligeramente anterior en arXiv: 1007.3624 )
y
Abuzer Yakaryılmaz, AC Cem Say, "Idiomas reconocidos por autómatas cuánticos finitos no deterministas", Quantum Information and Computation, vol. 10, págs. 747-770, 2010. ( arXiv: 0902.2081 )
para el caso de error ilimitado. El papel
A. Ambainis y J. Watrous. Autómatas finitos bidireccionales con estados cuánticos y clásicos. Informática teórica, 287 (1): 299–311, 2002, ( arXiv: cs / 9911009v1 )
junto con el hecho de que el lenguaje palíndromo no puede ser reconocido por las máquinas probabilísticas de Turing con espacio sublogarítmico, muestran que lo mismo también es cierto para el caso de error acotado.
fuente