Problèmes dans BQP mais supposés être en dehors de P

Wikipédia a énuméré quatre problèmes qui sont en mais qui sont supposés être en dehors de P : factorisation entière; Logarithme discret; Simulation de systèmes quantiques; Calcul du polynôme de Jones à certaines racines de l'unité.$BQP$$P$

Existe-t-il d'autres problèmes de ce type?

Pour avoir une liste de ces problèmes, vous pouvez consulter la liste de l'amélioration de la vitesse superpolynomiale au zoo de l'algorithme quantique (QAZ). La liste ci-dessous est basée sur cela (voir QAZ pour des définitions et des références précises. C'est une autre façon de dire que je ne prétends même pas comprendre la plupart des problèmes de cette liste!)

Problèmes algébriques et théoriques des nombres

Si je ne me trompe pas, tous les problèmes répertoriés avant le problème du sous-groupe caché abélien en sont des cas particuliers.

• Factorisation
• Logarithme discret
• L'équation de Pell . L'affacturage se réduit à l'équation de Pell.
• Idéal Idéal Problème idéal. L'équation de Pell se réduit à ce problème, qui est donc au moins aussi difficile que l'affacturage.
• Problème de groupe d'unités
• Problème de groupe de classe
• Estimation des sommes de Gauß
• Éléments matriciels des représentations de groupe
• Ordre de groupe et adhésion
• Le problème du sous-groupe caché abélien
• Quelques (mais pas tous) problèmes de sous -groupes cachés non abéliens
• Quelques problèmes (mais pas tous) formulés comme des cas spéciaux du problème de décalage caché
• Quelques (mais pas tous) problèmes de structures non linéaires cachées
• Explorer quelques graphiques (arbres soudés)
• Isomorphisme de groupe, pour les groupes abéliens et certains groupes non abéliens
• Trouvez quelques propriétés des anneaux finis et des idéaux

Approximation et simulation

• Simulation quantique. Evidemment -complet$BQP$
• Calcul de quelques noeuds invariants, dont le polynôme de HOMFLY, dont le polynôme de Jones est un cas particulier. Certains d'entre eux sont complets $BQP$
• Calcul de quelques invariants à trois variétés. Certains d'entre eux sont complets $BQP$
• Estimation de la fonction de partition thermodynamique de certains systèmes classiques
• Calcul des fonctions zêta sur des champs finis
• Un problème de réécriture de chaîne est -complet$\mathit{PromiseBQP}$
• approximation des éléments matriciels des puissances de matrices creuses exponentiellement grandes.

Algorithme que je ne comprends pas vraiment.

Ce sont principalement des algorithmes où QAZ revendique une augmentation superpolynomial, mais je ne comprends pas pourquoi le problème d' origine est censé être de . Cela dit, je parierai beaucoup de mon argent sur le fait que QAZ ait raison et moi-même sur ce point.$P$

• $>\log(n)$
• $P$$\mathrm{polylog}$
• $\mathrm{polylog}$
• Problème des énumérateurs de poids. Quelque chose lié au code et aux fonctions de partition, mais je ne comprends pas de quoi il s'agit.

$P$$BQP$$P$

$BQP$$P$

• $(\tfrac12-\tfrac{\text{constant}}{D})N$$\left(\tfrac12-\tfrac{1}{22D^{3/4}}\right)N$$(\tfrac12-\tfrac{\text{constant}}{\sqrt{D}})N$
• $m×n$$k$$m$$n$$k$$\mathrm{poly}(k)\mathrm{polylog}(mn)$algorithme quantique trouvant des échantillons des éléments inconnus de la matrice en 2016 ( papier ). En 2018, tout en essayant de prouver que cette mise à l'échelle est impossible à atteindre avec une machine classique, Ewin Tang a en fait trouvé un algorithme classique réalisant les mêmes performances dans les mêmes conditions (papier disponible ici et ici ).