Comment le papier BosonSampling évite-t-il les classes faciles de matrices complexes?

Dans La complexité de calcul de l'optique linéaire ( ECCC TR10-170 ), Scott Aaronson et Alex Arkhipov soutiennent que si les ordinateurs quantiques peuvent être efficacement simulés par des ordinateurs classiques, la hiérarchie polynomiale s'effondre au troisième niveau. Le problème motivant est l'échantillonnage à partir d'une distribution définie par un réseau linéaire optique; cette distribution peut être exprimée comme le permanent d'une matrice particulière. Dans le cas classique, toutes les entrées de la matrice sont non négatives et il existe donc un algorithme probabiliste à temps polynomial, comme l'ont montré Mark Jerrum, Alistair Sinclair et Eric Vigoda (JACM 2004, doi: 10.1145 / 1008731.1008738). Dans le cas quantique, les entrées sont des nombres complexes. Notez que dans le cas général (lorsque les entrées ne doivent pas nécessairement être non négatives), le permanent ne peut pas être approximé même à l'intérieur d'un facteur constant, par le résultat classique de Valiant en 1979.

L'article définit une distribution définie par une matrice , et un problème d'échantillonnage$D_A$$A$

BosonSampling
Entrée: matrice Échantillon: à partir de la distribution$A$
$D_A$

L'utilisation d'un résultat de dureté semble être une faible preuve d'une séparation entre les mondes classique et quantique, car il est possible que la classe des matrices dans la configuration quantique spécifique soit toutes de forme spéciale. Ils peuvent avoir des entrées complexes, mais peuvent encore posséder beaucoup de structure. Il pourrait donc exister une procédure d'échantillonnage efficace pour de telles matrices, même si le problème général est # P-difficile.

Comment l'utilisation de BosonSampling dans le journal évite-t-elle les cours faciles?

Le papier utilise beaucoup de fond que je n'ai pas dans la complexité quantique. Compte tenu de toutes les personnes quantiques sur ce site, j'apprécierais vraiment un pointeur dans la bonne direction. Comment les arguments tiendraient-ils si l'on découvrait que la classe de matrices à valeurs complexes vues dans une configuration expérimentale spécifique correspondait en fait à une classe de distributions facile à échantillonner? Ou y a-t-il quelque chose d'inhérent au système quantique qui garantit que cela ne peut pas se produire?

Merci pour ta question! Il existe deux réponses, selon que vous êtes intéressé par les résultats de dureté pour l' échantillonnage de boson exact ou approximatif .

Dans le cas exact, nous prouvons que, étant donné toute matrice complexe n par n A, vous pouvez construire une expérience optique qui produit une sortie particulière avec une probabilité proportionnelle à | Per (A) | ² . Cela, à son tour, implique qu'aucun algorithme classique de temps polynomial ne peut échantillonner exactement à partir de la même distribution que l'expérience optique (étant donné une description de l'expérience en entrée), sauf si P ^#P = BPP ^NP . En fait, nous pouvons renforcer cela, pour donner une seule distribution D _n (dépendant uniquement de la longueur d'entrée n) qui peut être échantillonnée en utilisant une expérience optique de taille poly (n), mais qui ne peut pas être échantillonnée classiquement en poly (n ) temps sauf si P ^#P = BPP ^NP .

Dans le cas approximatif, la situation est plus compliquée. Notre résultat principal indique que, s'il existe un algorithme classique à temps polynomial qui simule l'expérience optique même approximativement (dans le sens d'un échantillonnage à partir d'une distribution de probabilité sur les sorties qui est 1 / poly (n) -close en distance de variation), alors dans BPP ^NP , vous pouvez approximer | Per (A) | ² , avec une probabilité élevée sur une matrice n par n A de gaussiens iid de moyenne 0 et de variance 1.

Nous conjecturons que le problème ci-dessus est # P-difficile (à tout le moins, pas dans BPP ^NP ), et les pages 57-82 de notre article sont toutes sur les preuves de cette conjecture.

Bien sûr, peut-être que notre conjecture est fausse, et on peut en fait donner un algorithme poly-temps pour approximer les permanents des matrices gaussiennes iides. Ce serait un résultat phénoménal! Cependant, le but de 85% du travail que nous avons fait était de tout fonder sur une conjecture de dureté qui était aussi propre, simple et "sans quantum" que possible. En d'autres termes, au lieu de l'hypothèse

"approximer les permanents de certaines matrices spéciales étranges qui se produisent dans notre expérience est # P-difficile,"

nous montrons qu'il suffit de faire l'hypothèse

"approximer les permanents des matrices gaussiennes iid est # P-difficile."