Existe um análogo quântico da Complexidade de Kolmogorov?

Question

A Complexidade de Kolmogorov (interpretada em termos do programa mais curto computando uma string) e a Entropia de Shannon são bastante semelhantes .

Visto que existe uma entropia quântica, é razoável perguntar se existe um análogo quântico da complexidade de Kolmogorov que dá origem a algum tipo de interpretação de programa "quântica" mais curta ou outra interpretação adequada que corresponda à entropia quântica ?

Qual é a analogia certa e a equivalência certa para a entropia quântica ?

Answer 1

Visto que existe uma máquina de Turing de comprimento constante que simula qualquer computador quântico, uma versão quântica da complexidade de Kolmogorov seria diferente de qualquer complexidade de Kolmogorov clássica por no máximo uma constante.

Answer 2

Teorema 6 aqui https://arxiv.org/pdf/quant-ph/0005018.pdf é uma relação entre o QC e a entropia de von Neumann (S) https://arxiv.org/abs/0712.4377é outra boa referência. Minha intuição muito aproximada de por que a ligação entre S e QC não é tão forte quanto aquela entre a entropia de Shannon (H) e a Complexidade de Kolmogorov (K) é: Se cadeias de bits,$x$, são desenhados de acordo com alguma distribuição $p$ então $H(p)$ é o valor esperado de $K(x)$. Então, ambos$K$ e $H$medir, em certo sentido, a complexidade. Agora deixe$\mu$ e $\rho$ser uma matriz de densidade com os mesmos autovalores, mas com diferentes autovetores. Suponha que os vetores próprios de$\mu$ são mais complexos (no sentido de $QC$) do que aqueles de $\rho$. Ou seja,$QC(\rho)<QC(\mu)$. Agora,$S(\rho)=S(\mu)$como S depende apenas dos autovalores, não dos autovetores. Assim, por estar cego para a complexidade dos autovetores, S se torna não relacionado ao CQ.

Existem infinitos qubitstrings cujos segmentos iniciais têm alto QC (assintoticamente), mas zero entropia de von-Neumann. Por exemplo, pegue um real 1-aleatório e construa um qubitstring infinito,$\rho$ dele (veja https://arxiv.org/abs/1709.08422) Embora os segmentos iniciais de$\rho$ têm alto QC (pelo teorema 4.4 em https://arxiv.org/abs/1709.08422), eles têm entropia de von Neumann zero, pois são estados puros. Isso funciona essencialmente devido ao simples fato de que, embora os estados puros possam ter alto QC, todos os estados puros têm entropia de von Neumann zero.

https://arxiv.org/abs/2008.03584 contém alguns resultados na seção 5 sobre a entropia de von-Neumann de sequências infinitas.

Em resumo, a entropia de von Neumann de uma matriz de densidade mede a entropia da distribuição dada por seus autovalores e ignora a complexidade algorítmica de seus autovetores.