Algoritmo cuántico para sistemas lineales de ecuaciones (HHL09): Paso 2 - Qué es

9

Esta es una secuela del algoritmo Quantum para sistemas lineales de ecuaciones (HHL09): Paso 1 - Confusión con respecto al uso del algoritmo de estimación de fase y el algoritmo Quantum para sistemas lineales de ecuaciones (HHL09): Paso 1 - Número de qubits necesarios .


En el artículo: Algoritmo cuántico para sistemas lineales de ecuaciones (Harrow, Hassidim y Lloyd, 2009) , lo que se escribe en la porción

El siguiente paso es descomponer en la base del vector propio, utilizando la estimación de fase [5–7]. Denote por los vectores propios de (o equivalente, de ), y por los valores propios correspondientes.|b|ujAeiAtλj

en la página hace algún sentido para mí (las confusiones arriba hasta que no han sido abordados en las entradas anteriores vinculados arriba). Sin embargo, la siguiente porción, es decir, la rotación parece un poco críptica.2R(λ1)

Let

|Ψ0:=2Tτ=0T1sinπ(τ+12)T|τ

por alguna gran . Los coeficientes de se eligen (siguiendo [5-7]) para minimizar una cierta función de pérdida cuadrática que aparece en nuestro análisis de errores (ver [13] para más detalles).| Ψ 0T|Ψ0

A continuación, aplicamos la evolución condicional hamiltoniana en , donde . | Ψ 0 C| b t 0 = O ( κ / ε )τ=0T1|ττ|CeiAτt0/T|Ψ0C|bt0=O(κ/ϵ)

Preguntas:

1. ¿Qué es exactamente ? ¿Qué significan y ? No tengo idea de dónde esta expresión gigantesca viene de repente y cuál es su uso.T tau |Ψ0Tτ

2Tτ=0T1sinπ(τ+12)T|τ

2. Después del paso de estimación de fase, el estado de nuestro sistema es aparentemente :

(j=1j=Nβj|uj|λ~j)|0ancilla

Esto seguramente no se puede escribir como es decir

(j=1j=Nβj|uj)(j=1j=N|λ~j)|0ancilla

|b(j=1j=N|λ~j)|0ancilla

Por lo tanto, está claro que no está disponible por separado en el segundo registro. ¡Así que no tengo idea de cómo están preparando un estado como en primer lugar! Además, ¿qué significa esa en el superíndice de ?| Ψ 0 C| b C | Ψ 0 C|b|Ψ0C|bC|Ψ0C

3. ¿De dónde aparece esta expresión ? ¿De qué sirve simularlo? ¿Y qué es en ? κ O ( κ / ϵ )τ=0T1|ττ|CeiAτt0/TκO(κ/ϵ)

Sanchayan Dutta
fuente

Respuestas:

5

1. Definiciones

Los nombres y símbolos utilizados en esta respuesta siguen los definidos en los algoritmos de sistemas lineales cuánticos: un cebador (Dervovic, Herbster, Mountney, Severini, Usher & Wossnig, 2018) . Un retiro se realiza a continuación.

1.1 Nombres de registro

Los nombres de los registros se definen en la Figura 5 de los algoritmos de sistemas lineales cuánticos: un cebador (Dervovic, Herbster, Mountney, Severini, Usher & Wossnig, 2018) (reproducido a continuación):

  • S (1 qubit) es el registro ancilla utilizado para verificar si la salida es válida o no.
  • nC ( qubits) es el registro del reloj, es decir, el registro utilizado para estimar los valores propios del hamiltoniano con estimación de fase cuántica (QPE).n
  • m A x = b x S | 1 I ( qubits) es el registro que almacena el lado derecho de la ecuación . Almacena , el resultado de la ecuación, cuando se mide como al final del algoritmo.mAx=bxS|1

Algoritmo HHL

2. Acerca de :|Ψ0

  1. ¿Qué es exactamente ?|Ψ0

    C|Ψ0 es un posible estado inicial del registro de reloj .C

  2. ¿Qué significan y ?τTτ

    T | Ψ 0 T | Ψ 0 T 2 n CT representa un gran número entero positivo. Esta debe ser lo más grande posible porque la expresión de minimiza asintóticamente un error dado para que crezca hasta el infinito. En la expresión de , será , el número de estados posibles para el reloj del cuanto .T|Ψ0T|Ψ0T2nC

    τ es solo el índice de suma

  3. ¿Por qué una expresión tan gigantesca para ?|Ψ0

    Vea la publicación de DaftWullie para una explicación detallada.

    Siguiendo las citas en el algoritmo Quantum para sistemas lineales de ecuaciones (Harrow, Hassidim & Lloyd, 2009 v3) terminamos con:

    1. La versión anterior del mismo algoritmo cuántico en papel para sistemas lineales de ecuaciones (Harrow, Hassidim & Lloyd, 2009 v2) . Los autores revisaron el documento 2 veces (hay 3 versiones del documento original de HHL) y la versión n ° 3 no incluye toda la información proporcionada en las versiones anteriores. En el V2 (sección A.3. A partir de la página 17), los autores proporcionan un análisis detallado del error con este estado inicial especial.
    2. Relojes cuánticos óptimos (Buzek, Derka, Massar, 1998) donde la expresión de se da como en la ecuación 10. No tengo el conocimiento para entiendo completamente esta parte, pero parece que esta expresión es "óptima" en algún sentido.| Ψ o p t|Ψ0|Ψopt

3. Preparación de :|Ψ0

Como se dijo en la parte anterior, es un estado inicial. No se preparan después del procedimiento de estimación de fase. El orden de las oraciones no es realmente óptimo en el trabajo. El procedimiento de estimación de fase que utilizan en el documento es un poco diferente del algoritmo de estimación de fase "clásico" representado en el circuito cuántico vinculado en la parte 1, y es por eso que lo explican en detalle.| Ψ 0 |Ψ0|Ψ0

Su algoritmo de estimación de fase es:

  1. Preparar el Estado en el registro . C|Ψ0C
  2. Aplique la evolución condicional hamiltoniana a los registros e (que están en el estado ).I | Ψ 0 | b CI|Ψ0|b
  3. Aplique la transformada cuántica de Fourier al estado resultante.

Finalmente, la en significa que el estado se almacena en el registro . Esta es una notación breve y conveniente para realizar un seguimiento de los registros utilizados.| Ψ 0 C | Ψ 0 CC|Ψ0C|Ψ0C

4. Simulación hamiltoniana:

En primer lugar, es el número de condición ( página de Wikipedia sobre "número de condición" ) de la matriz .AκA

τ=0T1|ττ|CeiAτt0/T es la representación matemática de una puerta cuántica.

La primera parte de la suma es una parte de control. Significa que la operación será controlada por el estado del primer registro cuántico (el registro como nos dice el exponente). C|ττ|CC

La segunda parte es la puerta de "simulación hamiltoniana", es decir, una puerta cuántica que aplicará la matriz unitaria dada por al segundo registro (el registro que está en el estado inicial ). I | b eiAτt0/TI|b

La suma total es la representación matemática de la operación U controlada en el circuito cuántico de "1. Definiciones", con .U=eiAτt0/T

Nelimee
fuente
3

En respuesta a su primera pregunta, escribí algunas notas hace algún tiempo sobre mi comprensión de cómo funcionaba. La notación es probablemente un poco diferente (he intentado ponerla más en línea, pero es fácil perder bits), pero intenta explicar esa elección del estado . También parece haber algunos factores de flotando en algunos lugares.1|Ψ012

Cuando estudiamos por primera vez la estimación de fase, generalmente estamos pensando en eso con respecto al uso en algún algoritmo particular, como el algoritmo de Shor. Esto tiene un objetivo específico: obtener la mejor aproximación de bit al valor propio. O lo haces, o no lo haces, y la descripción de la estimación de fase se ajusta específicamente para dar la mayor probabilidad de éxito posible.t

En HHL, estamos tratando de producir algún estado donde , haciendo uso de la estimación de fase. La precisión de la aproximación de esto dependerá mucho más críticamente de una estimación precisa de los valores propios que están cerca de 0 en lugar de aquellos que están lejos de 0. Un paso obvio, por lo tanto, es intentar modificar el protocolo de estimación de fase para que que usar 'contenedores' de ancho fijo para aproximar las fases de ( y es el número de qubits en el registro de estimación de fase), podríamos especificar un conjunto de para| b=Σjβj| λj2π/Te-iAtT=2ttφyy{0,1}tφC(φ,φ')φ'φ

|ϕ=jβjλj|λj,
|b=jβj|λj2π/TeiAtT=2ttϕyy{0,1}t para que actúe como el centro de cada bin para que podamos tener una precisión mucho mayor cerca de la fase 0. En términos más generales, puede especificar una función de compensación por cuán tolerante puede ser con los errores en función de la fase . La naturaleza precisa de esta función se puede ajustar a una aplicación determinada y la figura particular de mérito que utilizará para determinar el éxito. En el caso del algoritmo de Shor, nuestra figura de mérito era simplemente este protocolo de agrupamiento: teníamos éxito si la respuesta estaba en el contenedor correcto y sin éxito fuera de él. Este no será el caso en HHL, cuyo éxito se capta más razonablemente por una medida continua como la fidelidad. Entonces, para el caso general, designaremos una función de costoϕC(ϕ,ϕ)que especifica una penalización por las respuestas si la fase verdadera es .ϕϕ

Recuerde que el protocolo de estimación de fase estándar funcionó al producir un estado de entrada que era la superposición uniforme de todos los estados básicos para . Este estado se utilizó para controlar la aplicación secuencial de múltiples compuertas controladas , seguidas de una transformada inversa de Fourier. Imaginemos que podríamos reemplazar el estado de entrada con algún otro estado y luego el resto del protocolo podría Trabajar como antes. Por ahora, ignoraremos la cuestión de cuán difícil es producir el nuevo estado , ya que solo estamos tratando de transmitir el concepto básico. A partir de este estado, el uso de la controlada|xx{0,1}tU

|Ψ0=x{0,1}tαx|x,
|Ψ0Ucompuertas (dirigidas a un vector propio de de valor propio ), produce el estado Aplicando la transformada inversa de Fourier se obtiene La probabilidad de obtener una respuesta (es decir, ) es por lo que el valor esperado de la función de costo, suponiendo una distribución aleatoria de , es Uϕ
x{0,1}tαxeiϕx|x.
1Tx,y{0,1}teix(ϕ2πyM)αx|y.
yϕ=2πy/T
1T|x{0,1}teix(ϕ2πyT)αx|2
ϕ
C¯=12πT02πdϕy{0,1}t|x{0,1}teix(ϕ2πyT)αx|2C(ϕ,2πy/T),
y nuestra tarea es seleccionar las amplitudes que minimizan esto para cualquier realización específica de . Si hacemos la suposición simplificadora de que es solo una función de , entonces podemos hacer un cambio de variable en la integración para dar como señalamos, es probable que la medida más útil sea una medida de fidelidad. Considere que tenemos un estadoαxC(ϕ,ϕ)C(ϕ,ϕ)ϕϕ
C¯=12π02πdϕ|x{0,1}teixϕαx|2C(ϕ),
|+y deseamos implementar el unitario , pero implementamos . La fidelidad mide qué tan bien esto logra la tarea deseada, entonces tomamos ya que en el caso ideal , entonces el error, que es lo que queremos minimizar, puede tomarse como . Esta será sin duda la función correcta para evaluar cualquierUϕ=|00|+eiϕ|11|Uϕ=|00|+eiϕ|11|
F=|+|UϕU|+|2=cos2(ϕϕ2),
C(ϕϕ)=sin2(ϕϕ2),
F=11FUt, pero para la tarea más general de modificar las amplitudes, no solo las fases, los efectos de las imprecisiones se propagan a través del protocolo de una manera menos trivial, por lo que es difícil demostrar la optimización, aunque la función ya proporcionará alguna mejora sobre la superposición uniforme de estados. Continuando con este formulario, tenemos La integral sobre ahora se puede realizar, por lo que queremos minimizar la función Esto se puede expresar sucintamente como C(ϕϕ)
C¯=12π02πdϕ|x{0,1}teixϕαx|2sin2(12ϕ),
ϕ
12x,y=0T1αxαy(δx,y12δx,y112δx,y+1).
minΨ0|H|Ψ0
donde La elección óptima de es el vector propio mínimo de la matriz , y es el valor propio mínimo Crucialmente, para grande , escala como lugar de que habríamos obtenido de la opción de acoplamiento uniforme
H=12x,y=0T1(δx,y12δx,y112δx,y+1)|xy|.
|Ψ0H ˉ C ˉ C =1
αx=2T+1sin((x+1)πT+1),
C¯T ˉ C 1/T21/Tαx=1/
C¯=1212cos(πT+1).
TC¯1/T21/Tαx=1/T. Esto produce un beneficio significativo para el análisis de errores.

Si desea obtener el mismo como se informa en el documento HHL, creo que debe agregar los términos al Hamiltoniano. Sin embargo, no tengo justificación para hacerlo, pero esta es probablemente mi falla.- 1|Ψ014(|0T1|+|T10|)

DaftWullie
fuente