Y a-t-il eu une avancée vraiment révolutionnaire dans les algorithmes quantiques depuis Grover et Shor?

(Désolé pour une question quelque peu amateur)

J'ai étudié l'informatique quantique de 2004 à 2007, mais depuis j'ai perdu la trace du terrain. À l'époque, il y avait beaucoup de battage médiatique et de discussions sur le CQ pouvant résoudre toutes sortes de problèmes en surclassant les ordinateurs classiques, mais dans la pratique, il n'y avait vraiment que deux percées théoriques:

• L'algorithme de Shor, qui a montré une accélération significative, mais qui avait une applicabilité limitée, et n'était pas vraiment utile en dehors de la factorisation entière.
• L'algorithme de Grover, qui était applicable à une catégorie plus large de problèmes (car il pouvait être utilisé pour résoudre des problèmes NP-Complete), mais qui ne montrait qu'une accélération polynomiale par rapport aux ordinateurs classiques.

Le recuit quantique a également été discuté, mais il n'était pas clair s'il était vraiment meilleur que le recuit simulé classique ou non. Le contrôle qualité basé sur la mesure et la représentation graphique de l'état du contrôle qualité étaient également des sujets d'actualité, mais rien de définitif n'avait été prouvé sur ce front non plus.

Y a-t-il eu des progrès dans le domaine des algorithmes quantiques depuis lors? En particulier:

• Y a-t-il eu des algorithmes vraiment révolutionnaires en plus de Grover et Shor?
• Y a-t-il eu des progrès dans la définition de la relation de BQP avec P, BPP et NP?
• Avons-nous fait des progrès dans la compréhension de la nature de l'accélération quantique autre que de dire que "cela doit être dû à l'intrication"?

Y a-t-il eu des algorithmes vraiment révolutionnaires en plus de Grover et Shor?

Cela dépend de ce que vous entendez par «vraiment révolutionnaire». Grover et Shor sont particulièrement uniques car ce sont vraiment les premiers cas qui ont montré des types d'accélération particulièrement précieux avec un ordinateur quantique (par exemple l'amélioration exponentielle présumée pour Shor) et ils avaient des applications de tueur pour des communautés spécifiques.

Il y a eu quelques algorithmes quantiques qui ont été conçus depuis, et je pense que trois méritent particulièrement d'être mentionnés:

• L' algorithme BQP-complete pour évaluer le polynôme de Jones à des points particuliers. Je mentionne cela parce que, à part des choses plus évidentes comme la simulation hamiltonienne, je pense que c'était le premier algorithme complet BQP, donc il montre vraiment toute la puissance d'un ordinateur quantique.

• L' algorithme HHL pour résoudre des équations linéaires. C'est un peu drôle car il ressemble plus à un sous-programme quantique, avec des entrées et sorties quantiques. Cependant, il est également complet pour BQP et reçoit actuellement beaucoup d'attention, en raison d'applications potentielles en apprentissage automatique et similaires. Je suppose que c'est le meilleur candidat pour vraiment révolutionnaire, mais c'est une question d'opinion.

• Chimie quantique . Je sais très peu de choses à ce sujet, mais les algorithmes se sont considérablement développés depuis l'époque que vous mentionnez, et ils ont toujours été cités comme l'une des applications utiles d'un ordinateur quantique.

Y a-t-il eu des progrès dans la définition de la relation de BQP avec P, BPP et NP?

Essentiellement, non. Nous savons que BQP contient du BPP, et nous ne connaissons pas la relation entre BQP et NP.

Avons-nous fait des progrès dans la compréhension de la nature de l'accélération quantique autre que de dire que "cela doit être dû à l'intrication"?

Même à l'époque où vous l'étiez à l'origine, je dirais que c'était plus précisément défini que cela. Il y a (et il y avait) de bonnes comparaisons entre les ensembles de portes universelles (potentiellement capables de donner une accélération exponentielle) et les ensembles de portes classiquement simulables. Par exemple, rappelez-vous que les portes de Clifford produisent un enchevêtrement mais sont classiquement simulables. Non pas qu'il soit simple d'énoncer précisément ce qui est requis de manière plus pédagogique.

Peut-être que certains progrès ont été réalisés en ce qui concerne d'autres modèles de calcul. Par exemple, le modèle DQC1 est mieux compris - il s'agit d'un modèle qui semble avoir une accélération par rapport aux algorithmes classiques, mais il est peu probable qu'il soit capable de calculs BQP complets (mais avant de vous laisser entraîner dans le battage médiatique que vous pourriez trouver en ligne , il y a un enchevêtrement présent lors du calcul).

D'un autre côté, le type de déclaration "c'est à cause de l'intrication" n'est toujours pas entièrement résolu. Oui, pour le calcul quantique à l'état pur, il doit y avoir un enchevêtrement car sinon le système est facile à simuler, mais pour les états mixtes séparables, nous ne savons pas s'ils peuvent être utilisés pour les calculs, ou s'ils peuvent être simulés efficacement.

En outre, on pourrait essayer de poser une question plus perspicace: avons-nous fait des progrès dans la compréhension des problèmes qui se prêtent à une accélération quantique? C'est subtilement différent parce que si vous pensez qu'un ordinateur quantique vous donne de nouvelles portes logiques qu'un ordinateur classique n'a pas, alors il est évident que pour obtenir une accélération, vous devez utiliser ces nouvelles portes. Cependant, il n'est pas clair que chaque problème puisse être soumis à de tels avantages. Lesquels? Il y a des classes de problèmes où l'on peut espérer une accélération, mais je pense que cela repose toujours sur l'intuition individuelle. Cela peut probablement encore être dit à propos des algorithmes classiques. Vous avez écrit un algorithme x. Existe-t-il une meilleure version classique? Peut-être pas, ou peut-être que vous ne le voyez pas. C'est pourquoi nous ne savons pas si P = NP.

L'algorithme Kerenidis-Prakash était révolutionnaire, jusqu'à ce qu'Ewin Tang corrige le terrain:

Magazine Quanta: Une avancée majeure en informatique quantique rendue obsolète par un adolescent .