Distribution de probabilité de profondeur bornée

20

Deux questions connexes sur l'informatique en profondeur limitée:

1) Supposons que vous commenciez par n bits et que vous commenciez par le bit i peut être 0 ou 1 avec une certaine probabilité p (i), indépendamment. (Si cela rend le problème plus simple, nous pouvons supposer que tous les p (i) s sont 0,1 ou 1/2.ou même que tous sont 1/2.)

Maintenant, vous faites un nombre limité de tours de calcul. À chaque tour, vous appliquez des portes classiques réversibles sur des ensembles de bits disjoints. (Fixez votre ensemble préféré de portes réversibles classiques universelles.)

À la fin, vous obtenez une distribution de probabilité sur les chaînes sur n bits. Y a-t-il des résultats sur la restriction de telles distributions?

Je cherche quelque chose d'analogue au lemme de commutation Hastad, résultat Boppana que l'influence totale est petite ou théorème LMN.

2) La même question que 1) mais avec des circuits quantiques de profondeur bornés.

Gil Kalai
la source
4
Je peux manquer quelque chose, mais n'est pas la question 1 avec tous les égale à 1 / 2 trivial? Vous commencez avec une distribution uniforme sur { 0 , 1 } n , qui est invariante sous les bijections. p(i)1/2{0,1}n
Klaus Draeger
Les éléments suivants constituent-ils une transformation utile de votre problème? Transformez votre entrée (un vecteur ) en un vecteur de longueur 2 n représentant une distribution de probabilité sur des chaînes binaires de longueur n . Maintenant, tout calcul est une matrice stochastique carrée agissant (disons) sur la gauche pour produire une distribution de probabilité sur des chaînes de sortie de longueur n . WLOG nous pouvons supposer que toutes les entrées sont binaires. La seule question est quelle est la classe des matrices binaires stochastiques qui peuvent être produites via un nombre limité de multiplications matricielles de nos matrices de base (portes réversibles). p0,p1,2nnn
usul
Désolé, je devrais être plus précis. Par matrice de base, j'entends ici non pas une porte réversible, mais plutôt un ensemble de portes réversibles agissant en parallèle, et il ne me semble pas immédiatement évident à quoi ressembleraient de telles matrices étant donné un ensemble de portes.
usul
Les deux réponses méritent la prime, je verrai ce que je peux faire
Gil Kalai
qu'entendez-vous par "ensembles disjoints" de bits?
vzn

Réponses:

14

Il y a quelques articles relativement récents d'Emanuele Viola et al., Qui traitent de la complexité des distributions d'échantillonnage. Ils se concentrent sur un modèle restreint de calculs, comme les arbres de décision de profondeur bornés ou les circuits de profondeur bornés.

Malheureusement, ils ne discutent pas des portes réversibles. Au contraire, il y a souvent une perte de longueur de sortie. Néanmoins, ces articles peuvent être un bon point de départ.

Les circuits à profondeur limitée ne peuvent pas échantillonner de bons codes

La complexité des distributions

MassimoLauria
la source
Merci beaucoup, Massimo! cela semble très pertinent.
Gil Kalai
(Je suis également intéressé par le cas non réversible.)
Gil Kalai
12

Réponse courte.

Pour les circuits quantiques, il existe au moins un résultat de non- limitation: les circuits quantiques à profondeur limitée arbitraire sont peu susceptibles d'être simulés avec une petite erreur multiplicative dans la probabilité du résultat, même pour les circuits classiques à profondeur polynomiale .

QNC0

Détails

Nous pouvons considérer la définition des circuits quantiques à profondeur polylogique donnée par Fenner et al. (2005) :

QNCk{Cn}n0pCnnp(n)O(logk(n))

Les portes à qubit unique doivent provenir d'un ensemble fini fixe, bien que cela suffise pour simuler n'importe quelle unité fixe sur un nombre constant de qubits avec une précision fixe. Nous permettons également à tout sous-ensemble des qubits à la fin du circuit d'être utilisé pour représenter la sortie de la famille de circuits (par exemple, un seul qubit pour les fonctions booléennes).

Bremner, Jozsa et Sheppard (2010) notent (voir la section 4) que, en utilisant une adaptation de la technique de porte-téléportation due à Terhal et DiVincenzo (2004) , post-sélection sur certains des qubits dans un circuit permet de résoudre les problèmes dans . En utilisant leurs résultats sur la simulation de circuits post-sélectionnés, cela implique que le problème de l'échantillonnage classique à partir de la distribution de sortie d'un circuit arbitraire avec une sortie booléenne, avec une erreur multiplicative au plus dans la probabilité d'échantillonnage, est en impossible avec des circuits de profondeur polynomiaux aléatoires à moins que la hiérarchie polynomiale ne s'effondre partiellementQNC0PostBQP=PPQNC02PHΔ3 ).

Niel de Beaudrap
la source
1
Cher Niel, Très intéressant! Merci! Je suis particulièrement intéressé par les distributions. Pouvez-vous expliquer pourquoi "Cela, bien sûr, ne vous dit pas ..."?
Gil Kalai
1
Le résultat d'inapproximabilité à facteur constant est valable via PostQNC⁰ = PostBQP = PP . La post-sélection est utilisée ici pour "forcer le succès" d'une longue chaîne de téléportations, pour simuler une distribution quantique-poly-profondeur via une distribution quantique-constante-profondeur conditionnée à un événement de probabilité extrêmement faible mais non nulle. Tout facteur d'approximation constant serait tout aussi valable pour un circuit poly-profondeur. Mais cela ne vous dit pas, par exemple, une limite supérieure sur la quantité d'amplitude, en termes absolus (et asymptotiques), qui est concentrée (ou pourrait être projetée sur) un sous-espace particulier.
Niel de Beaudrap