Limites pour l'approximation dans la distance de variation totale par des circuits quantiques

Il a été récemment montré que pour des notions raisonnables d'approximation d'états et de fonctions par des circuits quantiques, presque tous les états et fonctions sont exponentiellement difficiles à approximer Knill 1995. Les limites obtenues sont asymptotiquement serrées, sauf pour celle basée sur la distance de variation totale (DVT). La DVT est la métrique la plus pertinente pour la performance d'un circuit quantique. Dans cet article, nous obtenons des limites asymptotiquement serrées pour la DVT. Nous montrons que dans un sens naturel, presque tous les états sont difficiles à approximer à une DVT de 2/e-ε même pour ε exponentiellement petit. La quantité 2/e est asymptotiquement la distance moyenne à la distribution uniforme. Presque tous les états avec des amplitudes de probabilité concentrées dans une petite fraction de l'espace sont difficiles à approximer à une DVT de 2-ε. Ces résultats impliquent que la complexité des circuits quantiques non uniformes est non triviale dans tout modèle raisonnable. Ils renforcent également la notion que la distance d'information relative entre les états (qui est basée sur la difficulté de transformer un état en un autre) reflète pleinement la dimensionalité de l'espace des qubits, et non le nombre de qubits.