Algoritmo cuántico para sistemas lineales de ecuaciones (HHL09): Paso 1

Algoritmo cuántico para sistemas lineales de ecuaciones (HHL09): Paso 1 - Número de qubits necesarios

Esta es una continuación del algoritmo cuántico para sistemas lineales de ecuaciones (HHL09): Paso 1 - Confusión con respecto al uso del algoritmo de estimación de fase

Preguntas (cont.):

Parte 2: No estoy exactamente seguro de cuántos qubits se necesitarán para el Paso 1 del HHL09 .

En Nielsen y Chuang (sección 5.2.1, edición del décimo aniversario) dicen:

Por lo tanto, para obtener precisión bits con probabilidad de éxito al menos , elegimos $\varphi$ $n$ $1-\epsilon$

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

Por lo tanto, decimos que queremos una precisión del es decir y una precisión de -bits por o Habíamos necesitar $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$

Aparte de eso, ya que puede representarse como una suma de vectores propios linealmente independientes de una matriz unidimensional , necesitaríamos mínimo qubits para producir una espacio vectorial que tiene al menos - dimensiones. Entonces, necesitamos para el segundo registro. $|b\rangle$ $N$ $N\times N$ $A$ $\lceil{\log_2(N)\rceil}$ $N$ $\lceil{\log_2(N)\rceil}$

Ahora, para el primer registro, no solo qubits no serán suficientes para representar los valores propios , eso es porque necesitaremos más bits para representar cada precisamente hasta -bits. $\lceil{\log_2(N)\rceil}$ $N$ $|\lambda_j\rangle$ $|\lambda_j\rangle$ $n$

Supongo que deberíamos usar nuevamente la fórmula en este caso. Si queremos que cada valor propio se represente con una precisión de bits y una precisión del , necesitaríamos para el primer registro. Además, se necesita un qubit más para la 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}$

Por lo tanto, deberíamos necesitar un total de qubits para el Paso 1 del algoritmo HHL09 . Eso es bastante! $(6+1)\lceil{\log_2(N)\rceil}+1$

Digamos que queremos resolver un sistema de ecuaciones lineales manera que sea hermitiano y que en sí mismo requiera qubits! En caso de que no sea hermitiano, necesitaríamos aún más qubits. Estoy en lo cierto? $2\times 2$ $A$ $7\lceil{\log_2(2)\rceil}+1 = 8$ $A$

Sin embargo, en este documento ^{[ ] $\dagger\dagger$} en la página 6, afirman que usaron el algoritmo HHL09 para estimar el pseudoinverso de que tiene un tamaño de ~ . En ese documento, se define como: $A$ $200\times 200$ $A$

UNA : = (\begin{matrix} W - γ {yo}_{re} & PAGS \\ PAGS & 0 0 \end{matrix})

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

donde , y son todas matrices . $P$ $W$ $\Bbb I_d$ $d\times d$

En el simulado relacionado con H1N1, Lloyd et al. han afirmado haber hecho, . Además, afirman que utilizaron el algoritmo HHL09 para estimar el pseudoinverso de (que tiene un tamaño de ). Eso necesitaría un mínimo de qubits para simular. No tengo idea de cómo podrían hacerlo usando las computadoras cuánticas actuales o las simulaciones de computadoras cuánticas. Hasta donde yo sé, IBM Q Experience actualmente admite ~ qubits (eso tampoco es tan versátil como su versión de bits). $d = 100$ $A$ $200\times 200$ $7\lceil{\log_2(200)\rceil}+1 = 7(8)+1 = 57$ $15$ $5$

¿Me estoy perdiendo de algo? ¿Este Paso 1 realmente requiere un número menor de qubits de lo que he estimado?

[ ]: una red neuronal Quantum Hopfield Lloyd et al. (2018) $\dagger\dagger$

algorithm hhl-algorithm neural-network Sanchayan Dutta
fuente

@Nelimee That proviene de la fórmula . Denota el número de qubits en el "primer registro" necesario para representar cada o a bits de precisión y con un precisión.

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

Si bien mi respuesta puede parecer trivial ahora, en realidad me llevó unos buenos 3 días resolver todo porque, entre otras cosas, los documentos no estaban claros. Sin embargo, creo que ahora tengo el número correcto de qubits, y el número resultante deja bastante claro por qué los autores de este artículo sobre H1N1 podrían simular fácilmente el número requerido de qubits (al menos para el "paso 1").

user1271772

Respuestas:

El cálculo de la inversa de una matriz se puede hacer aplicando HHL con diferentes (específicamente, HHL se aplica veces, una vez para cada vector de base computacional utilizado como ) $N\times N$ $N$ $\vec{b}_i$ $N$ $\vec{b}_i$

En cada caso, la estimación de fase debe hacerse para una matriz $N \times N$

El número de qubits necesarios para la estimación de fase está escrito en la página 249 de la edición del décimo aniversario de N&C:

"El procedimiento de estimación de fase cuántica utiliza dos registros. El primer registro contiene qubits". $t$

"El segundo registro [...] contiene tantos qubits como sea necesario para almacenar ", donde es un vector dimensional. $|u\rangle$ $|u\rangle$ $N$

Entonces tiene razón en que necesitaríamos qubits para el primer registro, y qubits para el segundo registro. $6$ $\log N=8$

Esto es 14 qubits en total para hacer la parte de inicialización de fase de cada iteración HHL involucrada en el cálculo de la inversa de una matriz. 14 qubits está dentro de las capacidades de una computadora portátil.

usuario1271772
fuente

No tengo mucha experiencia con simulaciones que no sean jugar un poco con IBM Quantum Experience. ¿Qué usarías para simular 14 qubits? Hasta ahora, nunca he visto el modelo de circuito para matrices mayores de . La simulación hamiltoniana parece la parte más difícil de HHL.

4 \times 4

$4\times 4$

Sanchayan Dutta

En su comentario, se utilizan dos significados diferentes de "simulación". La "simulación hamiltoniana" es parte de HHL, que se realiza con qubits, por ejemplo, en la Sección 4.2 de este . "Lo que usarías para simular 14 qubits" se refiere a un tipo diferente de simulación, que no usa qubits sino bits clásicos, y esto es lo que hicieron los autores del artículo H1N1. Generaron las matrices (probablemente en MATLAB usando la función KRON que hace productos tensoriales) y simularon el

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

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

control de

Sí, soy consciente de que la simulación hamiltoniana es parte de HHL. Sin embargo, me preguntaba si usaban una computadora cuántica real como la versión IBM 16 qubit o IBM 20 qubit. Esa función KRON en MATLAB suena interesante (pero es clásica), pero estaba pensando en la posibilidad de hacerlo en el IBM 16 qubit one (que desafortunadamente no tiene todas las puertas necesarias), y por lo tanto, Necesito aproximar las puertas (no estoy completamente seguro de cómo).

Sanchayan Dutta

Además, creo que hay otro problema con su estimación del número de qubits: "Aquí el problema proviene de la precisión fija versus la dimensión no fija N. Como tiene una precisión fija,

) qubits son suficientes para codificar los valores propios a la precisión dada, pero podría tener más de

) valores propios "(vea la discusión en el chat relacionada con esto).

3

$3$

6

$6$

2^{3}

$2^3$

2^{6}

$2^6$

Sanchayan Dutta

Si usaran IBM, lo diría en el periódico. Si busca "IBM" no aparece nada. A medida que leas más artículos y adquieras más experiencia, será cada vez más obvio para ti cuando alguien use una computadora cuántica o simplemente simule una. Aquí lo simularon en una computadora clásica (quizás usando MATLAB). En cuanto al "problema en mi estimación del número de qubits", desafortunadamente no puedo entender cuál es el problema. Acabo de dar el número de qubits requeridos para la estimación de fase de una matriz de 200 x 200. N&C dice que son t qubits para el registro 1 y log_2 (N) para el registro 2.

user1271772