-norm preservando máquinas de Turing

Lendo alguns tópicos recentes sobre computação quântica ( aqui , aqui e aqui ), lembro-me de uma pergunta interessante sobre o poder de algum tipo de máquina de preservação -norm.$\ell_p$

Para as pessoas que trabalham com a teoria da complexidade na complexidade quântica, um excelente texto introdutório é o artigo de Fortnow, cujo link foi publicado por Joshua Grochow aqui . Nesse artigo, a máquina quântica de Turing é apresentada como uma máquina de Turing probabilística generalizada. Basicamente, a máquina probabilística possui um estado normalizado sob a -norm, ou seja, . A evolução temporal da máquina é dada pela aplicação de uma matriz estocástica tal que , isto é, preserva a -norm. Então o estado no momento éℓ 1 ∥ s ∥ 1 = 1 P ∥ P s ∥ 1 = 1 P ℓ 1 t P t$s$$\ell_1$$\parallel s\parallel_1=1$$P$$\parallel Ps\parallel_1=1$$P$$\ell_1$$t$$P^ts$(a notação pode não ser precisa porque a multiplicação à esquerda ou à direita de depende de se é um vetor de linha ou coluna ou se as linhas ou colunas de são os subespaços que preservam a norma). Portanto, nesse sentido, a máquina probabilística de Turing é uma máquina preservadora de denotada por .s P ℓ 1 M ℓ $P$$s$$P$$\ell_1$$M^{\ell_1}$

Então, uma máquina quântica de Turing pode ser vista como tendo um estado com e matriz unitária (que preserva -norms) tal que é o estado no momento onde . Esta é uma máquina preservadora de denotada por .∥ s ∥ 2 = $s$$\parallel s\parallel_2=1$ℓ 2 P t s t ∥ P t s ∥ 2 = 1 ℓ 2 M ℓ $P$$\ell_2$$P^ts$$t$$\parallel P^ts\parallel_2=1$$\ell_2$$M^{\ell_2}$

Em geral, uma máquina de preservação -norm seja denotada por .H ℓ $\ell_p$$M^{\ell_p}$

Então, minhas perguntas são:

(1) Qual é o poder das máquinas de preservação -orm para finito ? Mais formalmente, podemos provar que, para qualquer e , se , existe uma linguagem e uma máquina modo que decida com eficiência e não há uma máquina M ^ {\ ell_p} que decide de forma eficiente L . Por exemplo, isso poderia ser uma generalização da pergunta, é NP \ subseteq BQP ? p p q q > p L M ℓ q M ℓ q L M ℓ p L N P ⊆ B Q $\ell_p$$p$$p$$q$$q>p$$L$$M^{\ell_q}$$M^{\ell_q}$$L$$M^{\ell_p}$$L$$NP \subseteq BQP$

(2) E quanto a $p=\infty$ ? Aqui, o valor máximo dos componentes do vetor de estado é 1.

(3) Essas questões vão além da unitariedade, portanto, não se espera que ela concorde com a mecânica quântica. Em geral, o que acontece com a computação se você relaxar a restrição de unidade nas operações? Existem trabalhos sobre a permissão de operadores não lineares (consulte Aaronson 2005 ).

(4) Talvez o mais importante, seja universal? Eu acho que isso é claro, porque para casos particulares é universal. Mas o que acontece com a universalidade quando $p=\infty$ ?

Esta não é uma resposta completa para as perguntas, mas é muito longo para escrever como um comentário. Ele expande meu comentário anterior.

A pergunta “O que acontece com a computação se os axiomas da mecânica quântica são modificados um pouco?” É abordada em grande detalhe por um divertido artigo [Aar04] de Scott Aaronson. Acredito que suas perguntas sejam essencialmente respondidas na primeira metade da Seção 2 de [Aar04].

Aaronson mostra que se p> 0 ep p 2, então uma matriz que preserva a norma p para todos os vetores é necessariamente uma matriz de permutação generalizada (um produto de uma matriz de permutação e de uma matriz diagonal). Ele afirma que o mesmo vale no caso p = ∞. Tudo isso vale tanto para mais como para mais. Observe que isso inclui o caso de p = 1: matrizes estocásticas preservam a norma 1 para vetores não negativos, mas não para todos os vetores em geral.

Eu acho que uma máquina de Turing probabilística generalizada como em [For00] tem uma matriz de permutação generalizada como sua matriz de transição global somente se for uma máquina de Turing determinística, mas eu não tenho uma prova em mãos.

Aaronson discute também várias outras modificações dos axiomas da mecânica quântica no artigo. Por exemplo, se alterarmos a regra de medição (em vez do conjunto de portas permitidas) para que o resultado x ocorra com probabilidade | α _x | ^p / ∑ _y | α _y | ^p , onde α _y é a amplitude de | y⟩, esse “computador quântico” pode resolver qualquer problema em PP (incluindo problemas completos de NP) em tempo polinomial, a menos que p = 2 (Proposição 5).

Referências

[Aar04] Scott Aaronson. A mecânica quântica é uma ilha no espaço teórico? Em Anais da Conferência de Växjö, “Teoria Quântica: Reconsideração de Fundações”, 2004. arXiv: quant-ph / 0401062 v2.

[For00] Lance Fortnow. A visão de um teórico da complexidade da computação quântica. Em computação: o Simpósio Australiano de Teoria (CATS 2000), pp. 58–72, janeiro de 2000. http://dx.doi.org/10.1016/S1571-0661(05)80330-5

Houve um artigo de Aaronson no qual é mostrado que quando não existe realmente nenhuma matriz de preservação de normas. Mas você pode considerar matrizes que não aumentam a norma . Naturalmente, você gostaria que a regra de Born desse probabilidades . O problema é que, se a norma do vetor de estado diminuir, as probabilidades não serão mais uma. Aaronson considerou o caso em que você renormalizaria o vetor após cada etapa (veja os links na resposta de @ Tsuyoshi acima). Acredito que a conclusão foi que essas máquinas teriam grande poder.$p \not\in \{1,2\}$$\ell_p$$\left| \psi_i \right|^p$

Como alternativa, em vez de renormalizar o vetor de estado, você pode simplesmente aceitar que as probabilidades não somam 1 e interpretar a probabilidade "restante" como correspondendo a um resultado "reprovado". Nesse caso, você pode modificar os argumentos em Laplante, Magniez , para obter um adversário vinculado a . Basicamente, você pode interpolar entre os casos e que são dados no Teorema 1. Acontece que a complexidade da pesquisa não estruturada (pense no algoritmo de Grover) é . Mas nunca consegui encontrar um limite superior correspondente aqui. Para responder sua pergunta em , eu pude (IIRC) mostrar que o poder computacional deℓ 1 ℓ 2 Ω ( N 1 / p ) ℓ ∞ ℓ p ℓ q 1 / p + 1 / q = 1 ℓ p$\ell_p$$\ell_1$$\ell_2$$\Omega(N^{1/p})$$\ell_\infty$$\ell_p$ para problemas de decisão era equivalente ao onde (basicamente tomando a transposição de todos os operadores). Suponho que esses circuitos tenham uma potência estritamente crescente à medida que aumenta de 1 (clássica) a 2 (quântica).$\ell_q$$1/p+1/q=1$$\ell_p$$p$