La simulación hamiltoniana está completa con BQP

14

Muchos artículos afirman que la simulación hamiltoniana es completa BQP (por ejemplo, la simulación hamiltoniana con una dependencia casi óptima de todos los parámetros y la simulación hamiltoniana por Qubitización ).

Es fácil ver que la simulación hamiltoniana es difícil para BQP porque cualquier algoritmo cuántico puede reducirse a la simulación hamiltoniana, pero ¿cómo es la simulación hamiltoniana en BQP?

es decir, ¿cuál es exactamente el problema de decisión de simulación hamiltoniana en BQP y bajo qué condiciones en el hamiltoniano?

gruposgruposgrupos
fuente

Respuestas:

14

Hay muchas variantes diferentes, particularmente con respecto a las condiciones en el Hamiltoniano. Es un poco un juego, por ejemplo, tratar de encontrar la clase más simple posible de hamiltonianos para la cual la simulación aún está completa con BQP.

La declaración será más o menos similar a: let ser un estado producto (normalizado), H sea un hamiltoniano de alguna clase particular (por ejemplo, que consiste solamente de acoplamientos del vecino más cercano en un retículo unidimensional), O un observable que comprende un producto tensor de operadores de un cuerpo de manera que , y será un tiempo. Dada la promesa de que es mayor que menor que para alguna (por ejemplo, ), decide cuál es el caso.|ψHO^t Psi | e i H t O e - i H t | Psi 1O^1tψ|eiHtO^eiHt|ψ112+aaa=112aaa=16


Más detalles

La simulación hamiltoniana es dura para BQP

La construcción básica (originalmente debido a Feynman, aquí modificada un poco) básicamente muestra cómo puede diseñar un Hamiltoniano que implemente cualquier cálculo cuántico, incluido cualquier cálculo completo de BQP. El observable que mediría es solo en un qubit de salida particular, los dos resultados de medición corresponden a 'sí' y 'no'.Z

El tipo más simple de hamiltoniano que se te ocurra es considerar un cálculo de unitarios secuenciales actúan sobre qubits, comenzando desde un estado . Luego puede introducir qubits adicionales y especificar el Hamiltoniano Si prepara su estado inicial como , luego de un tiempo , estará en un estado dondeU n M | 0 M N H = 2N1UnM|0MNEl | 1| 0( N - 1 ) | 0M Nπ/4| 0

H=2Nn=1N1n(Nn)(|1001|n,n+1U+|0110|n,n+1U).
|1|0(N1)|0MNπ/4|0(N1)|1|Φ|Φes la salida del cálculo deseado. Las fuerzas de acoplamiento divertidas que he usado aquí, las se eligen específicamente para dar una evolución determinista, y están relacionadas con el concepto de transferencia de estado perfecto . Por lo general, verá resultados expresados ​​con acoplamientos iguales, pero con evolución probabilística.n(Nn)

Para ver cómo funciona, defina un conjunto de estados La acción del hamiltoniano es entonces que demuestra que la evolución está restringida a un subespacio que está representado por una matriz tridiagonal (que es la cosa específica estudiada en la transferencia de estado perfecto).

|ψn=|0(n1)|1|0Nn(Un1Un2U1|0M).
H|ψn=2N(n1)(N+1n)|ψn1+2Nn(Nn)|ψn+1,
N×N

Por supuesto, este hamiltoniano no tiene propiedades particularmente agradables: es altamente no local, por ejemplo. Hay muchos trucos que se pueden jugar para simplificar el Hamiltoniano a ser, por ejemplo, unidimensional. Incluso puede ser invariablemente traslacional si lo desea, a costa de tener que preparar un estado de producto inicial más complejo (en ese punto, el cálculo ya no está codificado en el Hamiltoniano, que es universal, sino que está codificado en el estado de entrada) . Ver aquí , por ejemplo.

Simulación Hamiltoniana

Una computadora cuántica puede simular la evolución de cualquier Hamiltoniano que sea local en alguna red, actuando en un estado inicial del producto, durante un tiempo que no sea más que polinómico en el tamaño del sistema, y ​​cualquier medición implementable eficientemente se puede aplicar a estimar un observable. En este sentido, puede ver que la simulación hamiltoniana no es más difícil que un cálculo cuántico, el contrapunto a la afirmación anterior de que el cálculo cuántico no es más difícil que la simulación hamiltoniana.

Hay muchas maneras de hacer esto (y ha habido algunos documentos recientes que muestran mejoras significativas en la escala de errores para ciertas clases de hamiltonianos). Hre es bastante simple. Tome la Hamiltonian que desea simular. Divídalo en diferentes partes, , cada una de las cuales conmuta. Por ejemplo, en un Hamiltoniano vecino más cercano en algún gráfico, no necesita más piezas que el grado máximo del gráfico. Luego Trotteriza la evolución, escribiendo la aproximación Entonces, solo tiene que construir un circuito que implemente términos como , que se compone de términos de conmutaciónHHi

eiHt(eiH1δteiH2δteiHnδt)t/δt
eiH1δtH1=nhn, cada uno de los cuales actúa solo en un pequeño número de qubits. Dado que esto es solo unitario en un pequeño número de términos, una computadora cuántica universal puede implementarlo.
eiH1δt=neihnδt
DaftWullie
fuente