¿Qué resultados hacen que el espacio cuántico sea interesante?

17

El cálculo cuántico limitado en el tiempo es obviamente muy interesante. ¿Qué pasa con el cálculo cuántico limitado por el espacio?

Conozco muchos resultados interesantes para la computación cuántica con límites de espacio sublogarítmico y varios tipos de modelos de autómatas cuánticos.

Por otro lado, se demostró que el espacio cuántico y probabilístico de error ilimitado es equivalente para cualquier espacio construible (Watrous, 1999 y 2003 ).s(n)∈Ω(log⁡(n))

Me pregunto si hay algunos resultados específicos que hagan interesante el espacio cuántico (al excluir el espacio sublogarítmico y los modelos de autómatas).

(Soy consciente de esta entrada: análogos cuánticos de las clases de complejidad SPACE ).

quantum-computing space-bounded Abuzer Yakaryilmaz
fuente
1
Perdón por la ignorancia. ¿Cuál es la relación entre la computación cuántica limitada al espacio y el modelo de circuito cuántico?
Alex 'qubeat' el
1
@ Alex'qubeat ': es conveniente utilizar máquinas de Turing para el cálculo limitado por el espacio. El modelo de circuito es apropiado para el cálculo con límite de tiempo.
Abuzer Yakaryilmaz
1
¿Por qué es más conveniente? ¿Es conveniente en caso cuántico o clásico? Desde un punto de vista ingenuo, el espacio ilimitado es más conveniente para las máquinas Turing (clásicas).
Alex 'qubeat' el
1
@ Alex'qubeat ': es conveniente tanto para casos clásicos como cuánticos. Puedo recomendar el artículo fundamental sobre este tema de Stearns, Hartmanis y Lewis: "Jerarquías de cálculos limitados de memoria" ( computer.org/portal/web/csdl/doi/10.1109/FOCS.1965.11 ). También puede consultar los documentos de Watrous (mencionados anteriormente) y un artículo reciente de Melkebeek y Watson ( theoryofcomputing.org/articles/v008a001 ).
Abuzer Yakaryilmaz
1
Gracias, lo he visto, pero también hay trabajo usando circuitos cuánticos arxiv.org/abs/0908.1467 que, al menos, no tiene la necesidad de administrar con pocas definiciones diferentes de QTM.
Alex 'qubeat'

Respuestas: