Google s'efforce de développer des processeurs améliorés quantiques qui utilisent des effets de mécanique quantique pour augmenter la vitesse à laquelle les données peuvent être traitées. À court terme, Google a conçu de nouveaux algorithmes améliorés quantiques qui fonctionnent en présence de bruit réaliste. L'algorithme d'optimisation d'approximation quantique, ou QAOA pour faire court, est la pierre angulaire d'un élan moderne vers le développement d'algorithmes améliorés quantiques et tolérants au bruit.

La célèbre approche adoptée par Google dans QAOA a suscité un vaste intérêt commercial et a enflammé une communauté de recherche mondiale pour explorer de nouvelles applications. Encore, on sait peu de choses sur les limites de performances ultimes de l'algorithme QAOA de Google.

Une équipe de scientifiques du laboratoire Deep Quantum de Skoltech a relevé ce défi contemporain. L'équipe entièrement Skoltech dirigée par le professeur Jacob Biamonte a découvert et quantifié ce qui semble être une limitation fondamentale de l'approche largement adoptée initiée par Google.

Rapports dans Lettres d'examen physique , les auteurs détaillent la découverte de soi-disant déficits d'accessibilité - les auteurs montrent que ces déficits limitent fondamentalement la capacité de la QAOA à même se rapprocher d'une solution à un problème, exemple.

Les résultats de l'équipe Skoltech font état d'une limitation claire de l'algorithme quantique variationnel QAOA. QAOA et d'autres algorithmes quantiques variationnels se sont avérés extrêmement difficiles à analyser à l'aide de techniques mathématiques connues en raison d'un processus de rétroaction interne quantique-classique. À savoir, un calcul quantique donné ne peut s'exécuter que pendant une durée déterminée. A l'intérieur de ce temps fixe, un nombre fixe d'opérations quantiques peut être exécuté. QAOA cherche à utiliser ces opérations quantiques de manière itérative en formant une séquence d'approximations de plus en plus optimales pour minimiser une fonction objectif. L'étude pose de nouvelles limites à ce processus.

Les auteurs ont découvert que la capacité de QAOA à approximer des solutions optimales pour tout circuit quantique à profondeur fixe dépend fondamentalement de la "densité" des problèmes. Dans le cas du problème appelé MAX-SAT, la densité peut être définie comme le rapport des contraintes du problème au nombre de variables. C'est ce qu'on appelle parfois la densité de clauses.

Les auteurs ont découvert des instances problématiques de haute densité avec des solutions optimales qui ne peuvent pas être approchées avec un succès garanti, quel que soit le temps d'exécution de l'algorithme.