¿Es la computación cuántica adiabática tan poderosa como el modelo de circuito?

9

Gran parte de la literatura de computación cuántica se centra en el modelo de circuito. La computación cuántica adiabática no se basa en aplicar una secuencia de operadores unitarios, sino en cambiar un hamiltoniano dependiente del tiempo. Estoy buscando información sobre cualquiera de los siguientes.

  1. ¿Es la computación cuántica adiabática tan poderosa como el modelo de circuito, o es inherentemente menos poderosa?
  2. ¿Existen clases de complejidad específicamente relacionadas con la computación adiabática en oposición al modelo de circuito?
  3. ¿Cómo se mide cuantitativamente el poder de la computación adiabática versus el poder del modelo de circuito?
cc.complexity-theory reference-request complexity-classes quantum-computing quantum-information vzn
fuente
ok NdB sí, no se formuló de la manera perfecta, gracias a los encuestados para aclaraciones, exactamente lo que se buscaba. surgió en reacción a la pregunta de otra persona en el chat , puede continuar la discusión allí por cualquier persona interesada. Estoy seguro de que otros con mayor reputación podrían resolver mejores preguntas, pero parece que hay una fuerte correlación inversa allí. En cuanto a bkg, todas las referencias que lo respaldaron se cortaron en la primera edición. Además, hace otra pregunta hace mucho tiempo que condujo a esta, pero esa otra pregunta se vaporizó. puf
VZN
2
Vi la edición anterior. Los comunicados de prensa no son artículos de investigación. Más concretamente, esencialmente cualquier artículo de investigación le habría indicado que la computación cuántica adiabática se basa esencialmente en qubit. No importa qué lo provocó: su pregunta no muestra mucho esfuerzo, y la actividad por el bien de la actividad es lo que StackExchange intenta evitar .
Niel de Beaudrap
3
Vzn: el punto es este: ¿por qué no investigas eso tú mismo? Y si después de investigar realmente no puede encontrar ninguna referencia, ¿por qué no hacer esa pregunta? Eso sería constructivo, y podría hacer (e investigar) esa pregunta sobre la computación cuántica en general, no solo la computación adiabática.
Niel de Beaudrap
44
@NieldeBeaudrap: Para mí, parecía que simplemente usaba el "modelo qubit" como sustituto del modelo de circuito, que por supuesto no es una sustitución precisa, pero entendí que ese era el significado de la pregunta.
Joe Fitzsimons
1
@JoeFitzsimons: bastante justo, ese es probablemente el enfoque más práctico, ya que implica que la pregunta tiene una respuesta sensata, es decir, las siguientes. Aunque vzn debería editar la pregunta para realmente hacer esa pregunta, si es así, para la posteridad.
Niel de Beaudrap

Respuestas:

19

Dos aclaraciones rápidas:

  1. El control de calidad adiabático generalmente está "basado en qubits" tanto como el control de calidad basado en un circuito, ¡no sé de dónde sacaste la idea de que no lo es! (Aunque uno también podría usar qutrits u otros componentes básicos, ya sea en el circuito o en los modelos adiabáticos).

  2. Como Mateus señaló, el resultado justamente famoso de Aharonov et al. dice que "el control de calidad adiabático es equivalente al control de calidad estándar". Pero ese resultado debe interpretarse con un poco de cuidado. Se cumple si el estado final del cálculo adiabático puede ser arbitrario, de modo que, en particular, el estado final pueda codificar toda la historia de un cálculo cuántico basado en circuitos. Sin embargo, si el estado final necesita ser un estado de base computacional clásico, como suele estar en el algoritmo de optimización adiabático(el ejemplo "original" de control de calidad adiabático) --- entonces el control de calidad adiabático ciertamente puede simularse en el modelo de circuito, pero no se conoce lo contrario y está lejos de ser claro. Entonces, con el último supuesto, es posible que la optimización adiabática realmente dé lugar a una nueva clase de complejidad intermedia entre BPP y BQP.

Scott Aaronson
fuente
3
El documento de Bacon y Flammia sobre el cómputo del estado del clúster adiabático parece dar una ruta alternativa que, hasta donde puedo ver, evita un poco la necesidad de una historia, aunque todavía tiene muchos qubits adicionales.
Joe Fitzsimons el
2
Sin embargo, el esquema Bacon & Flammia no tiene un estado fundamental único y, por lo tanto, difiere significativamente del AQC convencional.
Norbert Schuch el
3
@NorbertSchuch: Pero si agrega los términos de estabilizador adicionales al Hamiltoniano inicial correspondiente a la fijación del estado inicial, entonces el estado fundamental no es degenerado.
Joe Fitzsimons