Un circuito cuántico puede usar cualquier operador unitario. Su matriz es exponencial en el número de bits de entrada. En la práctica, ¿cómo puede ser esto posible (aparte de los operadores que son productos tensoriales), es decir, cómo se puede construir una matriz de tamaño exponencial?
La clave es que en realidad no construyes una matriz. Sí, si desea simular un cálculo cuántico en una computadora clásica, un método es construir la matriz unitaria correspondiente, y esto es esencialmente por qué (a menos que haya una estructura especial) es imposible realizar de manera eficiente una simulación clásica de cálculo cuántico.
Las operaciones cuánticas básicas que utilizamos están pensadas de esta manera: solo haces algo a uno o dos qubits a la vez y lo conviertes en un tamaño exponencial al agregar identidades ("no hacer nada") a todos los otros qubits. La combinación de un pequeño número de estos que actúan en diferentes conjuntos de qubits puede crear algunas matrices unitarias que no son productos tensoriales.
Ahora, mientras que una computadora cuántica puede en principio implementar cualquier operador unitario, la universalidad en ese sentido no dice nada sobre cuánto tiempo lleva la construcción. La inmensa, abrumadora, la mayoría de ellos no tienen tiempo exponencial de implementar. El cómputo cuántico está específicamente interesado en encontrar esa zona de Ricitos de Oro, ese pequeño número de instancias que pueden implementarse en tiempo polinómico y dar un cálculo interesante que no puede calcularse en tiempo polinómico en una computadora clásica.
Tenga en cuenta que no hay nada específicamente cuántico sobre esto.
La dimensión de estas matrices también aumenta claramente exponencialmente con el número de bits, pero esto no es un problema, ya que no tiene conexión con lo difícil que es implementar la operación correspondiente, por las razones expuestas en la otra respuesta .