Operaciones cuánticas del grupo Clifford y computación clásica

12

El grupo Clifford de operadores cuánticos es generado por las operaciones cuánticas:

  • Z controlada ,
  • Hadamard y
  • =El |0 00 0El |+yoEl |11El |

Un circuito compuesto solo por estas puertas puede simularse eficientemente en una computadora clásica. Sin embargo, si entiendo correctamente, no todos los algoritmos clásicos se pueden implementar de manera eficiente utilizando las operaciones de grupo de Clifford, al menos hasta donde sabemos.

¿Existe una construcción para implementar, incluso de manera ineficiente o aproximadamente, un algoritmo clásico que utiliza las operaciones del grupo Clifford? Por ejemplo, ¿cómo implementa una puerta Toffoli usando las puertas del grupo Clifford, si es posible?

Antonio Valerio Miceli-Barone
fuente
2
La puerta Quantum Toffoli es universal para el cálculo cuántico, mientras que las puertas del grupo Clifford no son universales.
Mohammad Al-Turkistany
2
En mi opinión, la puerta de Toffoli por sí sola no es universal para la computación cuántica eficiente, ya que toma los estados de base computacional en otros estados de base computacional.
Antonio Valerio Miceli-Barone
2
El grupo Toffoli + Clifford es universal para el cálculo cuántico eficiente, si lo entiendo correctamente
Antonio Valerio Miceli-Barone

Respuestas:

22

Como se señaló en un comentario anterior, si fuera posible implementar coherentemente una puerta Toffoli usando las puertas del grupo Clifford, entonces el grupo Clifford sería universal para el cálculo cuántico. Se señaló en la Sección 5 de este documento que algo aún más fuerte es cierto: hablando informalmente, si existe una clase de circuitos cuánticos que se pueden simular eficientemente de manera clásica, y que es universal para la computación clásica , entonces BQP = BPP. Por lo tanto, esperaríamos que las clases simulables de circuitos cuánticos no sean universales para la computación clásica.

Los circuitos del grupo Clifford en sí mismos son particularmente débiles y corresponden a la clase de complejidad Parity-L, como se mostró aquí .

Ashley Montanaro
fuente
Gracias por las referencias. Ahora que lo mencionas, me parece recordar que Nielsen y Chuang describen una construcción de grupo Toffoli + Clifford que es universal para la computación cuántica (no puedo acceder al libro en este momento).
Antonio Valerio Miceli-Barone
44
De hecho, incluso solo tener puertas Toffoli y Hadamard es suficiente (ver el papel quant-ph / 0301040, por ejemplo).
Ashley Montanaro el
Considere unirse a: quantumcomputing.stackexchange.com .
Rob