Quais resultados tornam o espaço quântico interessante?

17

A computação quântica limitada no tempo é obviamente muito interessante. E quanto à computação quântica limitada ao espaço?

Conheço muitos resultados interessantes para computação quântica com limites de espaço sublogarítmicos e vários tipos de modelos de autômatos quânticos.

Por outro lado, foi demonstrado que o espaço probabilístico e quântico de erro ilimitado é equivalente a qualquer espaço construtível (Watrous, 1999 e 2003 ).s(n)∈Ω(registro⁡(n))

Gostaria de saber se existem resultados específicos que tornam o espaço quântico interessante ( excluindo modelos de espaço sublogarítmico e autômatos).

(Estou ciente desta entrada: análogos quânticos das classes de complexidade SPACE .)

quantum-computing space-bounded Abuzer Yakaryilmaz
fonte
11
Desculpe pela ignorância. Qual é a relação entre computação quântica limitada no espaço e modelo de circuito quântico?
Alex 'qubeat'
11
@ Alex'qubeat ': É conveniente usar máquinas de Turing para cálculos com espaço limitado. O modelo de circuito é apropriado para computação limitada no tempo.
Abuzer Yakaryilmaz
11
Por que é mais conveniente? É conveniente em caso quântico ou clássico? Do ponto de vista ingênuo, é um espaço ilimitado mais conveniente para máquinas de Turing (clássicas).
Alex 'qubeat'
11
@ Alex'qubeat ': É conveniente para casos clássicos e quânticos. Posso recomendar o artigo fundamental sobre Stearns, Hartmanis e Lewis sobre esse assunto: "Hierarquias de cálculos com memória limitada" ( computer.org/portal/web/csdl/doi/10.1109/FOCS.1965.11 ). Você também pode verificar os artigos de Watrous (mencionados acima) e um artigo recente de Melkebeek e Watson ( theoryofcomputing.org/articles/v008a001 ).
Abuzer Yakaryilmaz
11
Obrigado, eu já vi isso, mas também há trabalhos usando circuitos quânticos arxiv.org/abs/0908.1467 que, pelo menos, não sofrem com a necessidade de gerenciar com poucas definições diferentes de QTM.
Alex 'qubeat'

Respostas:

5

Eu acho que o novo resultado de Amnon Ta-Shma é uma boa resposta para minha própria pergunta.

... mostramos que o inverso de uma matriz bem condicionada pode ser aproximado no espaço de registro quântico com medições intermediárias. Isso deve ser comparado com o algoritmo clássico mais conhecido para o problema que requer espaço . Também mostramos como aproximar o espectro de uma matriz normal ou os valores singulares de uma matriz arbitrária, com precisão aditiva , e como aproximar a decomposição de valor singular (SVD) de uma matriz cujos valores singulares estão bem separados. ...Ω(registro2⁡n)ϵ

Abuzer Yakaryilmaz
fonte