Quantum Merlin Arthur

Le Quantum Merlin Arthur, couramment abrégé en QMA, est une classe de complexité mathématique et algorithmique de la théorie de l’information qui représente l’analogue quantique de la classe classique NP, ou non-déterministe en temps polynomial. Dans ce modèle de calcul théorique, un prouveur doté d’une puissance infinie, Merlin, fournit une preuve sous la forme d’un état quantique, appelé certificat ou témoin quantique, à un vérificateur doté d’un ordinateur quantique polynomial, Arthur. L’objectif d’Arthur est de vérifier de manière probabiliste et efficace la validité de la preuve fournie. Le problème emblématique appartenant à la classe QMA est la détermination de l’énergie de l’état fondamental d’un hamiltonien local, une tâche fondamentale de la physique quantique de la matière condensée.