Os solucionadores de álgebra linear clássica podem implementar algoritmos quânticos com acelerações semelhantes?
Um algoritmo quântico começa com um registro de qubits em um estado inicial, um operador unitário (o algoritmo) manipula o estado desses qubits e, em seguida, o estado dos qubits é lido (ou pelo menos algumas informações sobre o estado em um único execução do algoritmo).
Parece-me que um computador quântico responde à questão dos atos unitários no estado quântico. Isso é "apenas" uma questão de álgebra linear. Parece-me, então, que os computadores quânticos podem ser vistos como calculadores de álgebra linear.
Por que então precisamos da mecânica quântica? Não podemos encontrar um sistema clássico que implemente operações de álgebra linear e usar isso para implementar os algoritmos que foram projetados para computadores quânticos? É claro que os computadores digitais clássicos não serão suficientes, essas máquinas são baseadas no processamento binário de informações, ao invés da manipulação de vetores em um espaço dimensional elevado.
Pergunta: Há algum candidato para solucionador de álgebra linear clássica (computadores analógicos clássicos) que poderia implementar os algoritmos do "computador quântico" enquanto desfruta de uma aceleração semelhante em relação aos computadores clássicos digitais?
Pergunta 2: Talvez eu esteja simplificando demais, reduzindo um computador quântico a simplesmente um solucionador de álgebra linear. É este o caso? Que complexidade estou encobrindo?
Respostas
A complexidade que você está omitindo é que, no caso geral, você precisa armazenar $2^n$ amplitudes complexas para até mesmo representar um $n$sistema qubit classicamente. Portanto, para um computador quântico de, digamos, 1000 qubits, você precisa armazenar$2^{1000}$amplitudes complexas. Mesmo se você usar um átomo por amplitude para fazer isso, ainda assim ficará sem átomos no universo observável.
Pelo que eu sei, o acima exposto é o argumento geral. No entanto, ainda pode haver maneiras de representar certos algoritmos quânticos de uma maneira classicamente tratável, utilizando alguns insights inteligentes para economizar nas necessidades de representação do algoritmo, indo assim abaixo do$2^n$requerimento. Mas é provável que seja específico do problema e improvável que funcione no caso geral.
De acordo com a declaração da pergunta sobre computação digital vs. analógica, existem outros tópicos neste site que perguntaram sobre propostas semelhantes. Veja, por exemplo, aqui e aqui . Entre outras coisas, os sistemas analógicos clássicos não podem entrar em emaranhamento; portanto, a reformulação de um computador quântico como um computador analógico não levará à mesma aceleração observada.
No entanto, na sequência da resposta de @Attila Kun, existem problemas específicos em álgebra linear / aprendizado de máquina que tiveram algoritmos quânticos rápidos, mas foram reformulados como algoritmos clássicos com acelerações semelhantes.
Por exemplo, o problema de recomendação usado pela Netflix / Amazon / etc. tem um algoritmo rápido em um computador quântico. Este algoritmo mostrou uma melhoria exponencial em relação ao (então) algoritmo clássico mais conhecido.
No entanto, na tentativa de provar que o algoritmo quântico era realmente superior, E. Tang mostrou que havia de fato um "sistema clássico que implementa operações de álgebra linear e usa [s] isso para implementar os algoritmos que foram projetados para computadores quânticos".
O trabalho de Tang deu início a um programa de desquantização - isto é, redesenhar algoritmos quânticos rápidos em álgebra linear / aprendizado de máquina como algoritmos clássicos rápidos. Um artigo da Quanta Magazine descreve o problema e a abordagem de Tang.
Quais problemas são passíveis de desquantização é uma área ativa de pesquisa, como este tópico discute. Isso pode depender da classificação das matrizes consideradas.