Algoritmo quântico para sistemas lineares de equações (HHL09): Etapa 1 - Confusão quanto ao uso do algoritmo de estimativa de fase

Estou tentando entender o famoso algoritmo Quantum (?) Para sistemas de equações lineares (Harrow, Hassidim & Lloyd, 2009) (mais conhecido popularmente como o algoritmo HHL09 ) há algum tempo, agora.

Na primeira página, eles dizem :

Esboçamos aqui a idéia básica do nosso algoritmo e, em seguida, discutimos mais detalhadamente na próxima seção. Dado um Hermitian matriz , e uma unidade de vetor , suponha que nós gostaríamos de encontrar satisfazendo . (Discutimos questões de eficiência posteriores, bem como como as suposições que fizemos sobre e podem ser relaxadas.) Primeiro, o algoritmo representa como um estado quântico . Em seguida, usamos técnicas de simulação hamiltoniana [3, 4] para aplicar aA → b → x A → x = → b A → b → b | b ⟩ = Σ N i = 1 b i | i ⟩ e i A t | b i ⟩ t A | b ⟩ Um λ j Σ j = N j = 1 β j | você $N\times N$$A$$\vec{b}$$\vec{x}$$A\vec{x} = \vec{b}$$A$$\vec{b}$$\vec{b}$$|b\rangle = \sum_{i=1}^{N}b_i|i\rangle$$e^{iAt}$$|b_i\rangle$para uma superposição de tempos diferentes . Essa capacidade de exponenciar traduz, por meio da conhecida técnica de estimativa de fase [5–7], na capacidade de decompor na base própria de e encontrar os valores próprios correspondentes Informalmente, o estado do O sistema após este estágio está próximo de , em que é a base do vetor próprio de e .$t$$A$$|b\rangle$$A$$\lambda_j$u j A | b ⟩ = Σ j = N j = 1 β j | u j$\sum_{j=1}^{j=N} \beta_j |u_j\rangle|\lambda_j\rangle$$u_j$$A$$|b\rangle = \sum_{j=1}^{j=N} \beta_j|u_j\rangle$

Por enquanto, tudo bem. Conforme descrito em Nielsen & Chuang no capítulo " A transformada quântica de Fourier e suas aplicações ", o algoritmo de estimativa de fase é usado para estimar em que é o valor próprio correspondente a um vetor próprio do operador unitária .e i 2 pi φ | u ⟩ $\varphi$$e^{i2\pi \varphi}$$|u\rangle$$U$

Aqui está a parte relevante da Nielsen & Chuang:

O algoritmo de estimativa de fase usa dois registros. O primeiro registro contém qubits inicialmente no estado . A escolha de depende de duas coisas: o número de dígitos de precisão que desejamos ter em nossa estimativa para e com que probabilidade desejamos que o procedimento de estimativa de fase seja bem-sucedido. A dependência de dessas quantidades emerge naturalmente da análise a seguir.| 0 ⟩ t φ $t$$|0\rangle$$t$$\varphi$$t$

O segundo registro começa no estado e contém quantos qubits são necessários para armazenar . A estimativa de fase é realizada em dois estágios. Primeiro, aplicamos o circuito mostrado na Figura 5.2. O circuito começa aplicando uma transformação Hadamard ao primeiro registro, seguida pela aplicação de operações controladas no segundo registro, com elevado a potências sucessivas de dois. O estado final do primeiro registro é facilmente visto como sendo:| u ⟩ U $|u\rangle$$|u\rangle$$U$$U$

$$\frac{1}{2^{t/2}}\left(|0\rangle+\text{exp}(2\pi i 2^{t-1}\varphi)|1\rangle)(|0\rangle+\text{exp}(2\pi i 2^{t-2}\varphi)|1\rangle)...(|0\rangle+\text{exp}(2\pi i 2^{0}\varphi)|1\rangle\right)= \frac{1}{2^{t/2}}\sum_{k=0}^{2^{t}-1}\text{exp}(2\pi i \varphi k)|k\rangle$$

O segundo estágio da estimativa de fase é aplicar a transformada de Fourier quântica inversa no primeiro registro. Isso é obtido revertendo o circuito para a transformada quântica de Fourier na seção anterior (Exercício 5.5) e pode ser feito nas etapas . O terceiro e último estágio da estimativa de fase é ler o estado do primeiro registro fazendo uma medição na base computacional. Mostraremos que isso fornece uma estimativa muito boa de . Um esquema geral do algoritmo é mostrado na Figura 5.3.$\Theta (t^2)$$\varphi$

Para aprimorar nossa intuição sobre o funcionamento da estimativa de fase, suponha que possa ser expresso exatamente como int bits, como . Então o estado (5.20) resultante do primeiro estágio da estimativa de fase pode ser reescritoφ = 0. φ 1 . . . φ $\varphi$$\varphi = 0.\varphi_1 ... \varphi_t$

$$\frac{1}{2^{t/2}}(|0\rangle + \exp(2\pi i 0.\varphi_t|1\rangle)(|0\rangle + \exp(2\pi i 0.\varphi_{t-1}\varphi_t|1\rangle)...(|0\rangle + \exp(2\pi i 0.\varphi_1...\varphi_t|1\rangle)$$

O segundo estágio da estimativa de fase é aplicar a transformada de Fourier quântica inversa. Mas comparando a equação anterior com a forma do produto para a transformada de Fourier, Equação (5.4), vemos que o estado de saída do segundo estágio é o estado do produto . Uma medida na base computacional, portanto, nos dá exatamente!$|\varphi_1 ...\varphi_t\rangle$$\varphi$

Resumindo, o algoritmo de estimativa de fase permite estimar a fase de um autovalor de um operador unitário , dado o vetor correspondente . Uma característica essencial no coração deste procedimento é a capacidade da transformação inversa de Fourier para realizar a transformação$\varphi$$U$$|u\rangle$

$$\frac{1}{2^{t/2}}\sum_{j = 0}^{2^t-1}\exp(2\pi i \varphi j)|j\rangle |u\rangle \to |\tilde \varphi \rangle |u\rangle$$

Vamos prosseguir daqui. Encontrei um belo diagrama de circuitos para o algoritmo HHL09 aqui ^{[ ]$\dagger$} :

Etapa 1 (estimativa de fase):

No primeiro passo do algoritmo HHL09 o mesmo conceito (do algoritmo padrão Quantum fase de estimativa como descrito em Nielsen e Chuang) é usado. No entanto, devemos ter em mente que por si só não é um operador unitário. No entanto, se assumirmos que é Hermitian então o exponencial é unitária (não se preocupe, há existe uma solução alternativa no caso de não é Hermitian!). $A$$A$$e^{iAt}$$A$

Aqui, podemos escrever . Há outro ponto sutil envolvido aqui. Nós não sabemos os autovetores de antemão (mas nós sabemos que para qualquer matriz unitária de tamanho existem autovetores ortonormais). Além disso, precisamos lembrar a nós mesmos que, se os autovalores de forem , os autovalores de serão . Se compararmos isso com a forma de autovalores dados em Nielsen e Chuang para isto é, se $U=e^{iAt}$$|u_j\rangle$$U$$N\times N$$N$$A$$\lambda_j$$e^{iAt}$$e^{i \lambda_j t}$$U$$e^{2\pi i \varphi} \equiv e^{ i \lambda_j t}$, encontraríamos . Neste caso, começamos no estado (o qual pode ser escrito como uma superposição dos vectores próprios de isto é ) em vez de qualquer vetor próprio de , no que diz respeito ao segundo registro de qubits. Se tivéssemos começado no estado , teríamos terminado com ie (considerando que | b⟩$\varphi = \frac{\lambda_j t}{2\pi}$$|b\rangle$$U$$\sum_{j=1}^{j=N}\beta_j|u_j\rangle$$|u_j\rangle$$U$$|u\rangle \otimes (|0\rangle)^{\otimes t}$$|u\rangle \otimes |\tilde\varphi\rangle$$|u_j\rangle \otimes |\tilde{\frac{\lambda_j t}{2\pi}}\rangle$$\lambda_j$é o valor próprio associado ao vetor próprio de ). Agora, se começarmos pela superposição de vetores próprios , devemos terminar com .$|u_j\rangle$$A$$\sum_{j=1}^{j=N}\beta_j|u_j\rangle$$\sum_{j=1}^{j=N}\beta_j|u_j\rangle\otimes |\tilde{\frac{\lambda_j t}{2\pi}}\rangle$

Questão:

Parte 1 : No artigo do HHL09 , eles escreveram sobre o estado do sistema após a etapa de Estimativa de Fase ser . No entanto, pelo que escrevi acima, parece-me que o estado do sistema deveria ser .$\sum_{j=1}^{j=N}\beta_j|u_j\rangle\otimes |\tilde\lambda_j\rangle$$\sum_{j=1}^{j=N}\beta_j|u_j\rangle\otimes |\tilde{\frac{\lambda_j t}{2\pi}}\rangle$

O que estou perdendo aqui? Onde o fator desapareceu em seu algoritmo?$\frac{t}{2\pi}$

Edit: A Parte 2 foi solicitada aqui para tornar as perguntas individuais mais focadas.

^{Também tenho várias confusões sobre as Etapas 2 e 3 do algoritmo HHL09, mas decidi publicá-las como threads de perguntas separadas, pois esta está se tornando muito longa. Vou adicionar os links a esses tópicos de perguntas, neste post, depois que eles forem criados.}

[ ]: experimentos de criptografia homomórfica na plataforma de computação em nuvem da IBM em nuvem Huang et al. (2016)$\dagger$

Depende dos papéis, mas vi duas abordagens:

1. Na maioria dos artigos que li sobre o algoritmo HHL e sua implementação, o tempo de evolução hamiltoniano é modo que esse fator desapareça, ou seja, .t = t 0 = 2 $t$$t = t_0 = 2\pi$

2. O valor próprio aproximado é geralmente escrito . Em alguns trabalhos, essa notação realmente significa "a aproximação do verdadeiro autovalor " e, em outros trabalhos, parece incluir nessa definição, ou seja, " é a aproximação do valor de ".$\tilde \lambda$$\lambda$$\frac{t}{2\pi}$$\tilde \lambda$$\frac{\lambda t}{2\pi}$

Aqui estão alguns links:

1. Algoritmos de sistemas lineares quânticos: um primer (Dervovic, Herbster, Mountney, Severini, Usher & Wossnig, 2018) : um artigo completo e muito bom sobre o algoritmo HHL e algumas melhorias descobertas. O artigo é de 22 de fevereiro de 2018. O valor de seu interesse é abordado pela primeira vez na página 30, na legenda da Figura 5, e é fixado em .$t$$2\pi$

2. Projeto de circuito quântico para resolver sistemas lineares de equações (Cao, Daskin, Frankel & Kais, 2013) (pegue a v2 e não a v3): uma implementação detalhada do algoritmo HHL para uma matriz 4x4 fixa. Se você planeja usar o artigo, avise-o de que existem alguns erros nele. Posso fornecer os que encontrei se estiver interessado. O valor de (que é indicado como neste artigo) é fixado em na segunda página (no início da coluna da direita).$t$$t_0$$2\pi$

3. Computação quântica experimental para resolver sistemas de equações lineares (Cai, Weedbrook, Su, Chen, Gu, Zhu, Li, Liu, Lu & Pan, 2013) : uma implementação do algoritmo HHL para uma matriz 2x2 em uma configuração experimental. Eles corrigem na legenda da Figura 1.$t = 2\pi$

4. Realização experimental do algoritmo quântico para resolver sistemas lineares de equações (Pan, Cao, Yao, Li, Ju, Peng, Kais & Du, 2013) : implementação de HHL para uma matriz 2x2. A implementação é semelhante à apresentada no segundo ponto acima, com a matriz 4x4. Eles corrigem na página 3, ponto de marcador n ° 2.$t_0 = 2\pi$

O que estou perdendo aqui? Onde o fator desapareceu em seu algoritmo?$\frac{t}{2\pi}$

Lembre-se de que, na notação Dirac, o que você escreve dentro do ket é um rótulo arbitrário que se refere a algo mais abstrato. Portanto, é verdade que você está encontrando o vetor próprio (aproximado) para , que tem valor próprio e, portanto, o que você está extraindo é , mas isso é o mesmo que o vetor próprio de com valor próprio , e é o que está sendo referido na notação. Mas se você quiser ser bem claro, pode escrever comoe - i λ t λ t / ( 2 π ) A $U$$e^{-i\lambda t}$$\lambda t/(2\pi)$$A$$\lambda$

| autovetor aproximado de para o qual o autovalor é e de para o qual autovalor se ,e - i λ t A λ $U$$e^{-i\lambda t}$$A$$\lambda\rangle$

mas talvez, em vez de escrever isso toda vez, possamos escrever por de brevidade!$|\tilde\lambda\rangle$