Rigetti Computing, Inc. a annoncé qu'un projet de la Defense Advanced Research Projects Agency (DARPA) lui avait été attribué dans le cadre du programme Imagining Practical Applications for a Quantum Tomorrow (IMPAQT) afin de faire progresser les algorithmes quantiques pour la résolution de problèmes d'optimisation combinatoire. Le projet de M. Rigetti, intitulé Scheduling Problems with Efficient Encoding of Qubits (SPEEQ), vise à mettre au point un encodage novateur et efficace des problèmes d'optimisation sur des qubits, dans le but de permettre aux ordinateurs quantiques de l'ère NISQ de traiter des problèmes de plus grande envergure. Le projet s'intéressera plus particulièrement aux problèmes d'ordonnancement, qui font partie des types de problèmes d'optimisation combinatoire les plus connus et les plus répandus dans de nombreux secteurs, mais aussi des plus difficiles à résoudre. Les algorithmes quantiques actuels sont limités dans la taille des problèmes qu'ils peuvent résoudre par le nombre de qubits disponibles sur une QPU.

L'un des principaux objectifs du projet SPEEQ est de permettre aux algorithmes quantiques de résoudre des problèmes de grande taille afin de pouvoir effectuer de meilleures comparaisons avec les algorithmes heuristiques classiques actuels. Les problèmes résolus par les algorithmes hybrides quantiques-classiques actuellement évalués sont environ 100 fois plus petits que ceux résolus par les algorithmes classiques, ce qui signifie qu'il est difficile de déterminer comment ces algorithmes hybrides fonctionneront à l'échelle appropriée. Le projet SPEEQ est né des conclusions du projet de Rigetti pour le programme DARPA ONISQ, Scheduling Applications with Advanced Mixers (SAAM). En partenariat avec la NASA et l'USRA, Rigetti met en œuvre des algorithmes classiques quantiques hybrides pour résoudre des problèmes d'optimisation binaires en mappant ces problèmes sur des processeurs quantiques à des échelles croissantes.

L'équipe observe que les performances algorithmiques s'améliorent avec l'augmentation du nombre d'opérations quantiques. Cependant, la taille du problème dans le projet SAAM peut encore être résolue efficacement avec des algorithmes heuristiques classiques, qui sont capables de résoudre des problèmes comportant jusqu'à 10 000 variables. Le projet SPEEQ s'appuiera sur les résultats et les références du projet SAAM pour répondre à une question centrale concernant le compromis entre le nombre de qubits utilisés et le nombre d'opérations quantiques utilisées, ce qui est essentiel pour la conception de nouveaux algorithmes. Le schéma d'encodage efficace en termes de qubits proposé dans le cadre de ce projet peut présenter de nombreux avantages au-delà de la résolution des problèmes d'ordonnancement. De nouveaux algorithmes qui résolvent des problèmes d'optimisation combinatoire difficiles pourraient avoir un impact profond sur les chaînes d'approvisionnement, la logistique et d'autres industries aux opérations complexes.