Können klassische lineare Algebra-Löser Quantenalgorithmen mit ähnlichen Beschleunigungen implementieren?
Ein Quantenalgorithmus beginnt mit einem Register von Qubits in einem Anfangszustand, ein einheitlicher Operator (der Algorithmus) manipuliert den Zustand dieser Qubits und dann wird der Zustand der Qubits ausgelesen (oder zumindest einige Informationen über den Zustand eines einzelnen Lauf des Algorithmus).
Es scheint mir, dass ein Quantencomputer die Frage nach den einheitlichen Handlungen auf den Quantenzustand beantwortet. Dies ist "nur" eine Frage der linearen Algebra. Es fällt mir also auf, dass Quantencomputer als lineare Algebra-Rechner angesehen werden können.
Warum brauchen wir dann die Quantenmechanik? Können wir nicht ein klassisches System finden, das lineare Algebraoperationen implementiert, und dieses verwenden, um die Algorithmen zu implementieren, die für Quantencomputer entwickelt wurden? Natürlich werden klassische digitale Computer nicht ausreichen, diese Maschinen basieren eher auf der binären Verarbeitung von Informationen als auf der Manipulation von Vektoren in einem hochdimensionalen Raum.
Frage: Gibt es Kandidaten für klassische lineare Algebra-Löser (klassische analoge Computer), die die "Quantencomputer" -Algorithmen implementieren könnten, während sie eine ähnliche Beschleunigung gegenüber digitalen klassischen Computern genießen?
Frage 2: Vielleicht bin ich zu stark vereinfacht, indem ich einen Quantencomputer einfach zu einem linearen Algebra-Löser mache. Ist das der Fall? Welche Komplexität beschönige ich?
Antworten
Die Komplexität, die Sie beschönigen, besteht darin, dass Sie sie im Allgemeinen speichern müssen $2^n$ komplexe Amplituden, um sogar eine darzustellen $n$Qubit-System klassisch. Daher müssen Sie für einen Quantencomputer mit beispielsweise 1000 Qubits speichern$2^{1000}$komplexe Amplituden. Selbst wenn Sie dazu ein Atom pro Amplitude verwenden, gehen Ihnen im beobachtbaren Universum immer noch die Atome aus.
Soweit ich weiß, ist das Obige das allgemeine Argument. Es könnte jedoch immer noch Möglichkeiten geben, bestimmte Quantenalgorithmen auf klassisch nachvollziehbare Weise darzustellen, indem einige clevere Erkenntnisse genutzt werden, um die Darstellungsbedürfnisse des Algorithmus einzusparen und damit unter die zu gehen$2^n$Anforderung. Dies ist jedoch wahrscheinlich problemspezifisch und funktioniert im allgemeinen Fall wahrscheinlich nicht.
Gemäß der Aussage der Frage zu digitalen und analogen Berechnungen gibt es auf dieser Website andere Themen, die sich nach ähnlichen Vorschlägen erkundigt haben. Siehe zB hier und hier . Unter anderem können sich klassische analoge Systeme nicht verwickeln; Eine Neufassung eines Quantencomputers als analoger Computer führt daher nicht zu derselben beobachteten Beschleunigung.
Nach der Antwort von @Attila Kun gibt es jedoch spezifische Probleme bei der linearen Algebra / beim maschinellen Lernen, die schnelle Quantenalgorithmen hatten, aber als klassische Algorithmen mit ähnlichen Beschleunigungen neu formuliert wurden.
Zum Beispiel das von Netflix / Amazon / etc. Verwendete Empfehlungsproblem . hat einen schnellen Algorithmus auf einem Quantencomputer. Dieser Algorithmus zeigte eine exponentielle Verbesserung gegenüber dem (damals) bekanntesten klassischen Algorithmus.
Bei dem Versuch zu beweisen, dass der Quantenalgorithmus wirklich überlegen war, zeigte E. Tang jedoch, dass es tatsächlich ein "klassisches System gibt, das lineare Algebraoperationen implementiert und dieses verwendet, um die für Quantencomputer entwickelten Algorithmen zu implementieren".
Tangs Arbeit hat ein Programm zur Dequantisierung gestartet - dh die Neugestaltung schneller Quantenalgorithmen in der linearen Algebra / des maschinellen Lernens als schnelle klassische Algorithmen. Ein Artikel im Quanta Magazine beschreibt das Problem und Tangs Ansatz.
Welche Probleme dieser Dequantisierung zugänglich sind, ist ein aktives Forschungsgebiet, wie in diesem Thread erörtert wird. Dies kann vom Rang der betrachteten Matrizen abhängen.