Complexité de l'optimisation sur un groupe unitaire

Quelle est la complexité de calcul de l'optimisation de diverses fonctions sur le groupe unitaire ? $\mathcal{U}(n)$

Une tâche typique, résultant souvent en théorie quantique de l' information, on maximiser le nombre de types (ou des polynômes d'ordre supérieur en ) sur l' ensemble des matrices unitaires . Ce type d'optimisation est-il calculable de manière efficace (peut-être approximativement) ou est-il difficile pour NP? (c'est peut-être bien connu, mais je n'ai pas pu trouver de références générales) $\mathrm{Tr}AUBU^{\dagger}$ $U$ $U$

cc.complexity-theory reference-request optimization quantum-information Marcin Kotowski
la source

êtes-vous d'accord pour restreindre "diverses fonctions" aux "polynômes sur les unitaires"?

Artem Kaznatcheev

Je ne sais pas trop comment ces problèmes surviennent, mais quel serait l'analogue classique naturel de ce problème? Connaissez-vous la complexité de ce problème?

Robin Kothari

Il y a un très bon article de Roger Brockett de 1991 qui montre comment exprimer le tri et la programmation linéaire essentiellement sous la forme que vous décrivez, mais sur les matrices orthogonales. Aucune mention de complexité cependant, mais le fait que deux problèmes très différents puissent être exprimés de la même manière signifie que vous devrez connaître quelque chose sur la structure du problème pour déterminer la complexité: eecs.berkeley.edu/~sburden/research/ jonathan / Brockett1991.pdf

Suresh Venkat

@Artem: oui, dans la pratique, les polynômes de faibles degrés sont les plus pertinents, je pense.

Marcin Kotowski

Cela se résume aux décompositions propres de

dans l'exemple de degré 2 que vous donnez. Pour

hermitiens

, le

unitaire peut être utilisé pour maximiser la trace en alignant les espaces propres de

avec ceux de

; il suffit alors de maximiser le produit scalaire des séquences de leurs valeurs propres, ce qui est trivial si

sont semi-définis positifs (et un cas auquel on peut réduire en ajoutant des multiples de l'identité pour redimensionner les valeurs propres). Ou êtes-vous intéressé par des cas beaucoup plus généraux, pas nécessairement motivés par la mécanique quantique sur des systèmes de petite dimension?

A

$A$

B

$B$

A

$A$

B

$B$

U

$U$

U B U^{†}

$U B U^\dagger$

A

$A$

A

$A$

B

$B$

Niel de Beaudrap

Réponses:

Veillez excuser mon retard! Dans la théorie de l'informatique quantique, il existe de nombreux exemples de problèmes d'optimisation sur le groupe unitaire qui, étonnamment (du moins pour moi), peuvent être résolus dans le temps polynomial (classique) par réduction à une programmation semi-définie.

Voici un premier exemple: résoudre un de mes problèmes de 2000, en 2003 Barnum, Saks et Szegedy a montré que Q (f), la complexité de requête quantique d'une fonction booléenne f: {0,1} ⁿ → {0,1 }, peut être calculé en polynôme temporel en 2 ⁿ (c'est-à-dire la taille de la table de vérité de f). J'y avais pensé, mais je ne voyais pas comment le faire, car il fallait optimiser la probabilité de réussite sur tous les algorithmes de requête quantique possibles, chacun avec son propre ensemble de matrices unitaires (éventuellement 2 ⁿ ). Barnum et al. réduit au SDP en exploitant une "dualité" entre matrices unitaires et matrices semi-définies positives, l' isomorphisme dit de Choi-Jamiolkowski. Pour un SDP plus récent et plus simple caractérisant Q (f), voir l'article de Reichardt 2010 montrant que la méthode de l'adversaire à poids négatif est optimale.

Un autre cas important où cette astuce a été exploitée est celui des systèmes de preuve interactifs quantiques. Bien que cela ne soit pas intuitivement évident, en 2000, Kitaev et Watrous ont prouvé que QIP ⊆ EXP. en réduisant le problème de l'optimisation sur les matrices unitaires de taille exponentielle qui se posent dans un système de preuve interactif quantique à 3 tours, à la résolution d'un SDP de taille exponentielle unique (encore une fois, je pense, en utilisant l'isomorphisme de Choi-Jamiolkowski entre les états mixtes et matrices unitaires). La récente percée QIP = PSPACE est venue de montrer que ce SDP particulier pouvait être approximativement résolu encore mieux, en NC (c'est-à-dire par des circuits de profondeur de log).

Donc, quel que soit votre problème d'optimisation spécifique impliquant le groupe unitaire, je suppose qu'il peut être résolu plus rapidement que vous ne le pensez - si ce n'est d'une manière encore plus simple, puis par réduction en SDP!

Scott Aaronson
la source

Cher Scott! Barnum, Saks et Szegedy ne mentionnent pas explicitement l'isomorphisme Choi-Jamiolkowski, et je ne comprends pas comment cela est lié à leur construction. Peux tu développer ta pensée à ce propos? Je demande parce que j'essaie de comprendre si un résultat similaire est possible dans le cas d'oracles défectueux.

Joris

-3

Déterminer si deux matrices Hadamard sont équivalentes est un problème complet d'isomorphisme graphique (GI). Brendon McKay a un document sur ce sujet. Voir BD McKay, Hadamard equivalence via graph isomorphism, Discrete Mathematics, 27 (1979) 213-216.

Dursun
la source

\pm 1

$\pm 1$