Computación cuántica: relación entre el modelo hamiltoniano y el modelo unitario

16

Al desarrollar algoritmos en computación cuántica, noté que hay dos modelos principales en los que se hace esto. Algunos algoritmos - como para el problema del árbol de Hamilton NAND (Farhi, Goldstone, Guttman) - trabajo mediante el diseño de un hamiltoniano y un estado inicial y, a continuación, dejar evolucionar el sistema de acuerdo con la ecuación de Schrödinger para un tiempo antes de realizar una medición.t

Otros algoritmos, como el Algoritmo de Shor para factorizar, funcionan diseñando una secuencia de transformaciones unitarias (análogas a las compuertas) y aplicando estas transformaciones de una en una a un estado inicial antes de realizar una medición.

Mi pregunta es, como novato en computación cuántica, ¿cuál es la relación entre el modelo hamiltoniano y el modelo de transformación unitaria? Algunos algoritmos, como el problema del árbol NAND, se han adaptado para trabajar con una secuencia de transformaciones unitarias (Childs, Cleve, Jordan, Yonge-Mallo). ¿Se puede transformar cada algoritmo en un modelo en un algoritmo correspondiente en el otro? Por ejemplo, dada una secuencia de transformaciones unitarias para resolver un problema particular, ¿es posible diseñar un hamiltoniano y resolver el problema en ese modelo? ¿Qué pasa con la otra dirección? Si es así, ¿cuál es la relación entre el tiempo en que el sistema debe evolucionar y el número de transformaciones unitarias (compuertas) requeridas para resolver el problema?

He encontrado varios otros problemas para los cuales parece ser el caso, pero no hay argumentos claros o pruebas que indiquen que esto siempre es posible o incluso cierto. Quizás es porque no sé cómo se llama este problema, así que no estoy seguro de qué buscar.

usuario340082710
fuente
3
Cada algoritmo de tiempo polinómico en uno corresponde a un algoritmo de tiempo polinómico en el otro, pero no está claro que el grado del polinomio sea el mismo. Esperemos que alguien presente referencias. Estos resultados se demostraron en los primeros días de la computación cuántica, y ahora debería haber mejores pruebas de estos teoremas.
Peter Shor
¿Se relaciona esto con lo que se conoce como la imagen de Heisenberg vs Schroedinger de QM que se relaciona con cómo se definen los operadores? Además, si no está cubierto en Nielsen y Chuang , ¡eso parecería ser un gran descuido! el documento del árbol NAND utiliza "oráculos hamiltonianos" que parecen ser introducidos por Farhi / Gutmann 1998. Aquí hay un buen artículo de encuesta sobre los oráculos hamiltonianos por Mochon 2007
vzn
El enlace del libro que proporcionó es en realidad el libro de texto que utilizamos en mi curso de pregrado en Procesamiento de información cuántica. El libro está realmente orientado hacia el enfoque unitario (también en el contexto de los oráculos), pero no tanto en el contexto de los hamiltonianos. Mi curso de pregrado se centró desde una perspectiva cs y no desde una perspectiva física, por eso estoy más familiarizado con el modelo Unitario.
user340082710
El documento que proporcionó también es una buena referencia en general, pero tampoco creo que aborde mi pregunta. Por último, he echado un vistazo a la imagen de Heisenberg vs Schroedinger de QM, y parece estar relacionada, pero creo que mi pregunta es diferente (aunque podría estar equivocado: fue difícil seguir las entradas de Wikipedia).
user340082710
Creo que hay diferentes maneras de interpretar su pregunta y, en lugar de responder a todas las interpretaciones, me gustaría preguntarle lo siguiente: ¿Podría ser más preciso sobre la versión del modelo hamiltoniano que tiene en mente? ¿Cuál es la medida de complejidad en este modelo? (es decir, ¿qué es lo que cuenta lo difícil que es resolver un problema en el modelo hamiltoniano?) ¿Cómo se da la entrada al problema? ¿Se da explícitamente o tiene que consultar la entrada a través de un oráculo?
Robin Kothari

Respuestas:

10

Para demostrar que la evolución hamiltoniana puede simular el modelo de circuito, se puede usar el cálculo universal en papel por caminata cuántica de partículas múltiples , que muestra que un tipo muy específico de evolución hamiltoniana (caminatas cuánticas de partículas múltiples) es BQP completo, y así puede simular El modelo del circuito.

Aquí hay una encuesta sobre la simulación de la evolución cuántica en una computadora cuántica. Se pueden usar las técnicas en este artículo para simular el modelo de evolución hamiltoniana de las computadoras cuánticas. Para hacer esto, uno necesita usar "Trotterización", que disminuye sustancialmente la eficiencia de la simulación (aunque solo introduce una explosión polinómica en el tiempo de cálculo).

Peter Shor
fuente
¡Gracias! Estas referencias se ven bastante bien y deberían poder darme una idea de cómo se hace esto.
user340082710