¿Pueden los solucionadores de álgebra lineal clásica implementar algoritmos cuánticos con aceleraciones similares?
Un algoritmo cuántico comienza con un registro de qubits en un estado inicial, un operador unitario (el algoritmo) manipula el estado de esos qubits y luego se lee el estado de los qubits (o al menos alguna información sobre el estado en un solo ejecución del algoritmo).
Me parece que una computadora cuántica responde a la pregunta de los actos unitarios sobre el estado cuántico. Esto es "sólo" una cuestión de álgebra lineal. Me sorprende, entonces, que las computadoras cuánticas puedan verse como calculadoras de álgebra lineal.
Entonces, ¿por qué necesitamos la mecánica cuántica? ¿No podemos encontrar un sistema clásico que implemente operaciones de álgebra lineal y usarlo para implementar los algoritmos que han sido diseñados para computadoras cuánticas? Por supuesto, las computadoras digitales clásicas no serán suficientes, estas máquinas se basan en el procesamiento binario de información en lugar de la manipulación de vectores en un espacio de alta dimensión.
Pregunta: ¿Hay candidatos para solucionadores de álgebra lineal clásica (computadoras analógicas clásicas) que podrían implementar los algoritmos de la "computadora cuántica" mientras disfrutan de una aceleración similar a las computadoras clásicas digitales?
Pregunta 2: Quizás estoy simplificando demasiado al reducir una computadora cuántica a ser simplemente un solucionador de álgebra lineal. ¿Es este el caso? ¿Qué complejidad estoy pasando por alto?
Respuestas
La complejidad que está pasando por alto es que, en el caso general, necesita almacenar $2^n$ amplitudes complejas para representar incluso un $n$sistema qubit clásicamente. Por lo tanto, para una computadora cuántica de, digamos, 1000 qubits, necesita almacenar$2^{1000}$amplitudes complejas. Incluso si usa un átomo por amplitud para hacer esto, aún se queda sin átomos en el universo observable.
Hasta donde yo sé, lo anterior es el argumento general. Sin embargo, todavía podría haber formas de representar ciertos algoritmos cuánticos de una manera clásicamente manejable mediante la utilización de una visión inteligente para ahorrar en las necesidades de representación del algoritmo, yendo así por debajo del$2^n$requisito. Pero es probable que esto sea específico del problema y es poco probable que funcione en el caso general.
Según la declaración de la pregunta con respecto a la computación digital frente a la analógica, hay otros hilos en este sitio que han preguntado sobre propuestas similares. Vea, por ejemplo, aquí y aquí . Entre otras cosas, los sistemas analógicos clásicos no pueden enredarse; por lo tanto, reformular una computadora cuántica como una computadora analógica no conducirá a la misma aceleración observada.
No obstante, además de la respuesta de @Attila Kun, existen problemas específicos en álgebra lineal / aprendizaje automático que han tenido algoritmos cuánticos rápidos pero que se han reformulado como algoritmos clásicos con aceleraciones similares.
Por ejemplo, el problema de recomendación utilizado por Netflix / Amazon / etc. tiene un algoritmo rápido en una computadora cuántica. Este algoritmo mostró una mejora exponencial sobre el (entonces) algoritmo clásico más conocido.
Sin embargo, al intentar demostrar que el algoritmo cuántico era realmente superior, E. Tang demostró que de hecho había un "sistema clásico que implementa operaciones de álgebra lineal y usa esto para implementar los algoritmos que han sido diseñados para computadoras cuánticas".
El trabajo de Tang ha puesto en marcha un programa de descuantificación , es decir, de rediseñar algoritmos cuánticos rápidos en álgebra lineal / aprendizaje automático como algoritmos clásicos rápidos. Un artículo de Quanta Magazine describe el problema y el enfoque de Tang.
Qué problemas son susceptibles de esta descuantificación es un área activa de investigación, como se analiza en este hilo . Esto puede depender del rango de las matrices consideradas.