Algoritmo quântico para sistemas lineares de equações (HHL09): Etapa 1

Algoritmo quântico para sistemas lineares de equações (HHL09): Etapa 1 - Número de qubits necessários

Esta é uma continuação do algoritmo Quântico para sistemas lineares de equações (HHL09): Etapa 1 - Confusão em relação ao uso do algoritmo de estimativa de fase

Perguntas (continuação):

Parte 2: Não sei exatamente quantos qubits serão necessários para a Etapa 1 do HHL09 .

Em Nielsen e Chuang (seção 5.2.1, edição do 10º aniversário), eles dizem:

Assim, para obter com sucesso precisão de bits com probabilidade de sucesso de pelo menos , escolhemos $\varphi$ $n$ $1-\epsilon$

$t = n + ⌈ \log (2 + \frac{1}{2 ϵ}) ⌉$ $t=n+\lceil { \log(2+\frac{1}{2\epsilon})\rceil}$

Então, dizer que queremos uma precisão de ie e uma precisão de -bits para ou TEREMOS precisar $90\%$ $1-\epsilon = 0.9 \implies \epsilon = 0.1$ $3$ $\frac{\lambda_j t}{2\pi}$ $\lambda_j$

t = 3 + ⌈ \log_{2} (2 + \frac{1}{2 (0.1)}) ⌉ = 3 + 3 = 6

$t = 3 + \lceil { \log_2(2+\frac{1}{2 (0.1)})\rceil} = 3 + 3 = 6$

Para além de que, uma vez pode ser representado como uma soma de autovetores linearmente independentes de um matriz dimensional , precisaríamos mínimo qubits para produzir um espaço vetorial com pelo menos - dimensões. Portanto, precisamos de para o segundo registro. $|b\rangle$ $N$ $N\times N$ $A$ $\lceil{\log_2(N)\rceil}$ $N$ $\lceil{\log_2(N)\rceil}$

Agora, pela primeira registar não só qubits não serão suficientes para representar os valores próprios , é porque vamos precisar de mais bits para representar cada precisamente até bits. $\lceil{\log_2(N)\rceil}$ $N$ $|\lambda_j\rangle$ $|\lambda_j\rangle$ $n$

Eu acho que devemos usar novamente a fórmula . Se quisermos que cada autovalor seja representado com uma precisão de bits e uma precisão de , precisaremos de para o primeiro registro. Além disso, é necessário mais um qubit para a ancilla.

n + ⌈ \log (2 + \frac{1}{2 ϵ}) ⌉

$n+\lceil { \log(2+\frac{1}{2\epsilon})\rceil}$

| λ_{i} ⟩

$|\lambda_i\rangle$

3

$3$

90 %

$90\%$

6 \times ⌈ \log_{2} (N) ⌉

$6\times \lceil{\log_2(N)\rceil}$

Portanto, precisamos de um total de qubits para a Etapa 1 do algoritmo HHL09 . Isso é bastante! $(6+1)\lceil{\log_2(N)\rceil}+1$

Digamos que queremos resolver um sistema de equações linear , de modo que seja hermitiano, o que exigiria qubits! Caso não seja hermitiano, precisaríamos de ainda mais qubits. Estou certo? $2\times 2$ $A$ $7\lceil{\log_2(2)\rceil}+1 = 8$ $A$

No entanto, neste artigo ^{[ ] $\dagger\dagger$} na página 6, eles afirmam que usaram o algoritmo HHL09 para estimar o pseudoinverso de com tamanho ~ . Nesse artigo, é definido como: $A$ $200\times 200$ $A$

A := (\begin{matrix} W - γ I_{d} & P \\ P & 0 \end{matrix})

$A := \begin{pmatrix} W - \gamma \Bbb I_d & P \\ P & 0 \end{pmatrix}$

onde , e são todos matrizes. $P$ $W$ $\Bbb I_d$ $d\times d$

No simulador relacionado ao H1N1, Lloyd et al. afirmaram ter feito, . E alegam ainda que usaram o algoritmo HHL09 para estimar o pseudo-inverso de (que é do tamanho ). Seria necessário no mínimo qubits para simular. Não tenho idéia de como eles poderiam fazer isso usando os atuais computadores quânticos ou simulações quânticas. Até onde eu sei, o IBM Q Experience atualmente suporta ~ qubits (que também não é tão versátil quanto a versão de bits). $d = 100$ $A$ $200\times 200$ $7\lceil{\log_2(200)\rceil}+1 = 7(8)+1 = 57$ $15$ $5$

Estou faltando alguma coisa aqui? Esta Etapa 1 realmente exige um número menor de qubits do que o estimado?

[ ]: Uma Rede Neural Quantum Hopfield Lloyd et al. (2018) $\dagger\dagger$

algorithm hhl-algorithm neural-network Sanchayan Dutta
fonte

@Nelimee Que vem da fórmula . Ele indica o número de qubits no "primeiro registro" necessário para representar cada ou com bits de precisão e com precisão.

6

$6$

t = 3 + ⌈ \log_{2} (2 + \frac{1}{2 (0.1)}) ⌉ = 3 + 3 = 6

$t = 3 + \lceil { \log_2(2+\frac{1}{2 (0.1)})\rceil} = 3 + 3 = 6$

| λ_{j} ⟩

$|\lambda_j\rangle$

| \frac{λ_{j} t}{2 π} ⟩

$|\frac{\lambda_j t}{2\pi}\rangle$

3

$3$

90 %

$90\%$

Sanchayan Dutta

Embora minha resposta possa parecer trivial agora, na verdade demorei três dias para descobrir tudo, porque, entre outras coisas, os jornais não estavam claros. No entanto, acredito que tenho o número certo de qubits agora, e o número resultante deixa bem claro por que os autores deste artigo sobre o H1N1 poderiam simular facilmente o número necessário de qubits (pelo menos para a "etapa 1").

user1271772

Respostas:

O cálculo da inversa de uma matriz pode ser feito aplicando HHL com diferentes (especificamente, HHL é aplicado vezes, uma vez para cada vetor de base computacional usado como ) $N\times N$ $N$ $\vec{b}_i$ $N$ $\vec{b}_i$

Em cada caso, a estimativa de fase deve ser feita para uma matriz $N \times N$

O número de qubits necessários para a estimativa de fase está escrito na página 249 da edição de 10 anos da N&C:

"O procedimento de estimativa da fase quântica usa dois registros. O primeiro registro contém qubits." $t$

"O segundo registro [...] contém quantos qubits são necessários para armazenar ", onde é um vetor dimensional. $|u\rangle$ $|u\rangle$ $N$

Portanto, você está certo de que precisaríamos de qubits para o primeiro registro e qubits para o segundo registro. $6$ $\log N=8$

São 14 qubits no total para executar a parte de eliminação de fase de cada iteração HHL envolvida no cálculo da inversa de uma matriz. 14 qubits está dentro dos recursos de um laptop.

user1271772
fonte

Não tenho muita experiência com simulações além de brincar um pouco com o IBM Quantum Experience. O que você usaria para simular 14 qubits? Até agora, nunca vi o modelo de circuito com mais de matrizes. A simulação hamiltoniana parece a parte mais difícil do HHL.

4 \times 4

$4\times 4$

Sanchayan Dutta

No seu comentário, dois significados diferentes de "simulação" são usados. "Simulação Hamiltonian" é uma parte de HHL, que é feito com qubits, por exemplo na Seção 4.2 do presente . "O que você usaria para simular 14 qubits" refere-se a um tipo diferente de simulação, que não usa qubits, mas bits clássicos, e é isso que os autores do artigo H1N1 fizeram. Eles geraram as matrizes (provavelmente no MATLAB usando a função KRON que faz produtos tensores) e simularam o QC da maneira que você e eu fazemos para 4x4

2^{14} \times 2^{14}

$2^{14} \times 2^{14}$

user1271772

Sim, estou ciente de que a simulação hamiltoniana faz parte do HHL. No entanto, eu queria saber se eles usavam um computador quântico real como o IBM 16 qubit ou a versão IBM 20 qubit. Essa função KRON no MATLAB parece interessante (mas é clássica), mas eu estava pensando na possibilidade de fazê-lo no IBM 16 qubit one (que infelizmente não tem todos os portões necessários) e, portanto, teríamos precisa aproximar os portões (não sei bem como).

Sanchayan Dutta

Além disso, acho que há outro problema com sua estimativa do número de qubits: "Aqui o problema vem da precisão fixa versus a dimensão não fixa N. Como ele tem uma precisão fixa, (ou ) qubits são suficientes para codificar os autovalores para a precisão especificada, mas ele pode ter mais de (ou ) autovalores "(consulte a discussão no chat relacionada a isso).

3

$3$

6

$6$

2^{3}

$2^3$

2^{6}

$2^6$

Sanchayan Dutta

Se eles usassem a IBM, diria isso no jornal. Se você pesquisar "IBM", nada será exibido. À medida que você lê mais artigos e se torna mais experiente, torna-se cada vez mais óbvio para você quando alguém usa um computador quântico ou apenas simula um. Aqui eles o simularam em um computador clássico (talvez usando o MATLAB). Quanto ao "problema na minha estimativa do número de qubits", infelizmente não sou capaz de entender qual é o problema. Acabei de fornecer o número de qubits necessários para a estimativa de fase de uma matriz 200 x 200. N & C diz que é qubits t para registo 1 e log_2 (N) para registo 2.

user1271772