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.
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.
fuente
Respuestas:
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).
fuente