Une preuve assistée par l'IA résout une question de longue date sur les accélérations quantiques

Note de la rédaction

• Une preuve de la conjecture d'Aaronson-Ambainis établit que les avantages quantiques exponentiels dans les lectures d'entrées nécessitent une structure lorsqu'il s'agit de répondre à des questions par oui ou par non sur la plupart des entrées générées aléatoirement.
• PSI a déclaré que son système de recherche a utilisé un modèle Anthropic non public pour trouver la preuve, qui a été vérifiée dans l'assistant de preuve Lean et examinée par des chercheurs.
• Le théorème limite les lectures de données plutôt que le temps de calcul total, laissant de la place pour des avantages quantiques pratiques et des travaux supplémentaires pour renforcer ses limites mathématiques.

Une preuve mathématique a résolu une conjecture ouverte depuis 2008 sur le moment où les ordinateurs quantiques peuvent obtenir des avantages énormes par rapport aux machines conventionnelles, établissant une limite à leur capacité à surpasser les algorithmes classiques sur des entrées non structurées.

Le résultat prouve la conjecture d'Aaronson-Ambainis, qui relie une question sur les fonctions mathématiques au fait de savoir si des accélérations spectaculaires nécessitent une structure spéciale dans les problèmes à résoudre, une question centrale de l'informatique quantique, à savoir.