Complexidade de otimização em grupo unitário

Qual é a complexidade computacional da otimização de várias funções sobre o grupo unitário ? $\mathcal{U}(n)$

Uma tarefa típica, surgindo muitas vezes em teoria da informação quântica, seria maximizar a quantidade do tipo (ou polinômios de ordem superior em ) sobre todo unitário matrizes . Esse tipo de otimização é eficiente (talvez aproximadamente) computável ou é difícil para o NP? (talvez isso seja bem conhecido, mas não consegui encontrar nenhuma referência geral) $\mathrm{Tr}AUBU^{\dagger}$ $U$ $U$

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

você concorda em restringir "várias funções" a "polinômios sobre os unitaristas"?

Artem Kaznatcheev

Não sei muito bem como esses problemas surgem, mas qual seria o análogo clássico natural desse problema? Você conhece a complexidade desse problema?

Robin Kothari

Há um artigo muito bom de Roger Brockett, de 1991, que mostra como expressar a classificação e a programação linear essencialmente na forma que você descreve, mas sobre as matrizes ortogonais. Porém, nenhuma menção à complexidade, mas o fato de que dois problemas muito diferentes podem ser expressos da mesma maneira significa que você precisará saber algo sobre a estrutura do problema para determinar a complexidade: eecs.berkeley.edu/~sburden/research/ jonathan / Brockett1991.pdf

Suresh Venkat

@ Artigo: sim, na prática polinômios de baixos graus são os mais relevantes, eu acho.

Marcin Kotowski

Tudo se resume às decomposições de

no exemplo de grau 2 que você fornece. Para o eremita

, o

unitário pode ser usado para maximizar o traço fazendo com que os espaços próprios de

estejam alinhados com os de

; basta então maximizar o produto escalar das seqüências de seus autovalores, o que é trivial se

forem semidefinidos positivos (e um caso ao qual podemos reduzir adicionando múltiplos da identidade para redimensionar autovalores). Ou você está interessado em casos muito mais gerais, não necessariamente motivados pela mecânica quântica em sistemas de pequenas dimensões?

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 17/10/12

Respostas:

Desculpe estou atrasado! Na teoria da computação quântica, existem muitos exemplos de problemas de otimização no grupo unitário que, surpreendentemente (pelo menos para mim), são solucionáveis no tempo polinomial (clássico) por redução à programação semidefinida.

Aqui estava um exemplo inicial: resolver um problema meu de 2000, em 2003 , Barnum, Saks e Szegedy mostrou que Q (f), a complexidade quântica de consultas de uma função booleana f: {0,1} ⁿ → {0,1 }, pode ser calculado no polinômio do tempo em 2 ⁿ (ou seja, o tamanho da tabela verdade de f). Eu tinha pensado nisso, mas não conseguia ver como fazê-lo, pois é preciso otimizar a probabilidade de sucesso em todos os algoritmos de consulta quântica possíveis, cada um com seu próprio conjunto de matrizes unitárias (possivelmente com 2 ⁿ ). Barnum et al. reduzido a SDP explorando uma "dualidade" entre matrizes unitárias e matrizes semidefinidas positivas, o chamado isomorfismo de Choi-Jamiolkowski. Para um SDP mais recente e mais simples que caracteriza Q (f), consulte o artigo de Reichardt de 2010, mostrando que o método adversário de peso negativo é ideal.

Outro caso importante em que esse truque foi explorado está nos sistemas quânticos de prova interativa. Embora não seja intuitivamente óbvio, em 2000, Kitaev e Watrous provaram o QIP ⊆ EXP. reduzindo o problema de otimizar as matrizes unitárias de tamanho exponencial que surgem em um sistema de prova interativa quântica de três rodadas, para resolver um SDP de tamanho único exponencial (novamente, eu acho, usando o isomorfismo de Choi-Jamiolkowski entre estados mistos e matrizes unitárias). A recente inovação de QIP = PSPACE veio de mostrar que esse SDP em particular poderia ser resolvido aproximadamente melhor ainda, em NC (ou seja, por circuitos de profundidade de registro).

Portanto, qualquer que seja o seu problema específico de otimização que envolva o grupo unitário, meu palpite é que ele pode ser resolvido mais rapidamente do que você pensa - se não de uma maneira ainda mais simples, por redução ao SDP!

Scott Aaronson
fonte

Caro Scott! Barnum, Saks e Szegedy não mencionam explicitamente o isomorfismo de Choi-Jamiolkowski, e eu não entendo como isso está relacionado à sua construção. Você poderia, por favor, elaborar isso? Estou perguntando, porque estou tentando entender se um resultado semelhante é possível no caso de oráculos defeituosos.

Joris

-3

Determinar se duas matrizes Hadamard são equivalentes é um problema completo de Isomorfismo de Gráfico (IG). Brendon McKay tem um artigo sobre este tópico. Ver BD McKay, equivalência de Hadamard via isomorfismo gráfico, Discrete Mathematics, 27 (1979) 213-216.

Dursun
fonte

\pm 1

$\pm 1$