Les solveurs d'algèbre linéaire classique peuvent-ils implémenter des algorithmes quantiques avec des accélérations similaires?
Un algorithme quantique commence par un registre de qubits dans un état initial, un opérateur unitaire (l'algorithme) manipule l'état de ces qubits, puis l'état des qubits est lu (ou au moins des informations sur l'état sur un seul exécution de l'algorithme).
Il me semble qu'un ordinateur quantique répond à la question des actes unitaires sur l'état quantique. C'est "juste" une question d'algèbre linéaire. Il me semble donc que les ordinateurs quantiques peuvent être considérés comme des calculateurs d'algèbre linéaire.
Pourquoi alors avons-nous besoin de la mécanique quantique? Ne pouvons-nous pas trouver un système classique qui implémente des opérations d'algèbre linéaire et l'utilise pour implémenter les algorithmes qui ont été conçus pour les ordinateurs quantiques? Bien sûr, les ordinateurs numériques classiques ne suffiront pas, ces machines sont basées sur le traitement binaire de l'information plutôt que sur la manipulation de vecteurs dans un espace de grande dimension.
Question: Y a-t-il des candidats pour les solveurs d'algèbre linéaire classique (ordinateurs analogiques classiques) qui pourraient implémenter les algorithmes de "l'ordinateur quantique" tout en bénéficiant d'une accélération similaire sur les ordinateurs classiques numériques?
Question 2: Je simplifie peut-être trop en réduisant un ordinateur quantique à un simple solveur d'algèbre linéaire. Est-ce le cas? Quelle complexité est-ce que je passe sous silence?
Réponses
La complexité que vous passez sous silence est que, dans le cas général, vous devez stocker $2^n$ amplitudes complexes pour représenter même un $n$système de qubit classiquement. Par conséquent, pour un ordinateur quantique de disons 1000 qubits, vous devez stocker$2^{1000}$amplitudes complexes. Même si vous utilisez un atome par amplitude pour ce faire, vous êtes toujours à court d'atomes dans l'univers observable.
Autant que je sache, ce qui précède est l'argument général. Cependant, il pourrait encore y avoir des moyens de représenter certains algorithmes quantiques d'une manière classiquement traitable en utilisant des informations intelligentes pour économiser sur les besoins de représentation de l'algorithme, allant ainsi en dessous du$2^n$exigence. Mais cela est susceptible d'être spécifique au problème et peu susceptible de fonctionner dans le cas général.
Conformément à la déclaration de la question concernant le calcul numérique par rapport au calcul analogique, il existe d'autres fils sur ce site qui se sont renseignés sur des propositions similaires. Voir, par exemple, ici et ici . Entre autres choses, les systèmes analogiques classiques ne peuvent pas s'engager dans l'intrication; ainsi refondre un ordinateur quantique en un ordinateur analogique ne conduira pas à la même accélération observée.
Néanmoins, suite à la réponse de @Attila Kun, il existe des problèmes spécifiques en algèbre linéaire / apprentissage automatique qui ont eu des algorithmes quantiques rapides mais qui ont été refondus en algorithmes classiques ayant des accélérations similaires.
Par exemple, le problème de recommandation utilisé par Netflix / Amazon / etc. a un algorithme rapide sur un ordinateur quantique. Cet algorithme a montré une amélioration exponentielle par rapport à l'algorithme classique (alors) le plus connu.
Cependant, en essayant de prouver que l'algorithme quantique était vraiment supérieur, E. Tang a montré qu'il y avait effectivement un "système classique qui implémente des opérations d'algèbre linéaire et l'utilise pour implémenter les algorithmes qui ont été conçus pour les ordinateurs quantiques".
Les travaux de Tang ont lancé un programme de déquantification - c'est-à-dire de refonte des algorithmes quantiques rapides en algèbre linéaire / apprentissage automatique en tant qu'algorithmes classiques rapides. Un article du Quanta Magazine décrit le problème et l'approche de Tang.
Les problèmes susceptibles de faire l'objet de cette déquantification constituent un domaine de recherche actif, comme l' explique ce fil de discussion. Cela peut dépendre du rang des matrices considérées.