Qual é o mínimo entre todas as distribuições de vetores unitários da variação do produto escalar dos vetores?

$n$$x_1,\ldots, x_n$$k$$n > k$$\max_{i\neq j} \mathrm{Var}(x_i^T x_j)$$\mathbb{E}[x_i^Tx_j]=0$

Eu tentei algumas distribuições e quase todas elas têm variação . Por exemplo, a distribuição na qual cada coordenada de cada é escolhida de maneira independente e uniforme de e a distribuição na qual cada é um vetor uniforme independente na esfera unitária dimensional tem variação .$1/k$$x_i$$\left\{-1/\sqrt{k}, 1/\sqrt{k}\right\}$$x_i$$k$$1/k$

É a variância mínima entre todas as distribuições?$1/k$

Apresentarei uma formulação equivalente, mas de aparência mais simples, do problema e mostrarei um limite inferior de ( n / k - 1) / ( n −1). Também mostro uma conexão com um problema aberto em informações quânticas. [Editar na revisão 3: em revisões anteriores, afirmei que uma caracterização exata dos casos em que o limite inferior mostrado abaixo é provavelmente difícil, porque uma pergunta análoga no caso complexo inclui um problema em aberto sobre SIC-POVMs em informação quântica. No entanto, essa conexão com os SIC-POVMs estava incorreta. Para detalhes, consulte a seção “Conexão incorreta aos SIC-POVMs em informações quânticas” abaixo.]

Formulação equivalente

Primeiro, como já foi apontado na resposta de daniello, observe que Var ( x _i ^T x _j ) = E [( x _i ^T x _j ) ² ] - E [ x _i ^T x _j ] ² = E [( x _i ^T x _j ) ² ]. Assim, no resto da resposta, nos esquecemos de variância e ao invés minimizar max _{i ≠ j} E [( x _i ^t x _j ) ² ].

A seguir, uma vez que decidimos que nosso objetivo é minimizar o máximo de _{i ≠ j} E [( x _i ^T x _j ) ² ], podemos ignorar a restrição de que E [ x _i ^T x _j ] = 0. Isso ocorre porque, se tivermos vetores unitários x ₁ ,…, x _n , então podemos negar cada um deles independentemente com probabilidade 1/2 para satisfazer E [ x _i ^T x _j ] = 0 sem alterar o valor da função objetivo max _{i ≠ j} E [( x _i ^T x _j) ² ].

Além disso, alterando a função de objectivo max _{i ≠ j} E [( x _i ^t x _j ) ² ] para (1 / ( n ( n -1))) Σ _{i ≠ j} E [( x _i ^t x _j ) ² ] não altera o valor ideal. O último é no máximo o primeiro, porque a média é no máximo o máximo. Entretanto, sempre podemos fazer os valores de E [( x _i ^T x _j ) ² ] para diferentes escolhas de ( i , j ) ( i ≠j ) igual permutando os n vetores x ₁ ,…, x _n aleatoriamente.

Portanto, para qualquer n e k , o valor ótimo do problema em questão é igual ao mínimo de (1 / ( n ( n −1))) ∑ _{i ≠ j} E [( x _i ^T x _j ) ² ] onde x ₁ ,…, x _n são variáveis ​​aleatórias que recebem vetores unitários em ^k como valores.

Entretanto, pela linearidade da expectativa, essa função objetivo é igual ao valor esperado E [(1 / ( n ( n −1))) ∑ _{i ≠ j} ( x _i ^T x _j ) ² ]. Como o mínimo é no máximo a média, não há mais a necessidade de considerar distribuições de probabilidade. Ou seja, o valor ideal do problema acima é igual ao valor ideal do seguinte:

Escolha vetores unitários x ₁ ,…, x _n ℝ ℝ ^k para minimizar (1 / ( n ( n −1))) ∑ _{i ≠ j} ( x _i ^T x _j ) ² .

Limite inferior

Usando esta formulação equivalente, provaremos que o valor ótimo é pelo menos ( n / k - 1) / ( n −1).

Para 1 ≤ i ≤ n , seja X _i = x _i x _i ^T o projetor de classificação 1 correspondente ao vetor unitário x _i . Então, sustenta que ( x _i ^T x _j ) ² = Tr ( X _i X _j ).

Vamos Y = Σ _i X _i . Então, sustenta que Tr _{i ≠ j} Tr ( X _i X _j ) = ∑ _{i , j} Tr ( X _i X _j ) - n = Tr ( Y ² ) - n .

A desigualdade de Cauchy-Schwarz implica que Tr ( Y ² ) ≥ (Tr Y ) ² / k = n ² / k e, portanto, ∑ _{i ≠ j} Tr ( X _i X _j ) = Tr ( Y ² ) - n ≥ n ² / k - n . Dividindo por n ( n −1), obtemos que o valor objetivo é pelo menos ( n / k - 1) / ( n −1).

Em particular, quando n = k +1, a resposta de daniello está dentro de um fator de 2 a partir do valor ideal.

Quando esse limite inferior é atingível?

Atingir este limite inferior ( n / k - 1) / ( N -1) é equivalente a tornar Y = ( n / k ) I . Não sei a caracterização exata quando possível, mas existem condições suficientes:

• Quando n = k +1, é possível considerar os vetores unitários k +1 que formam um k- simplex regular centrado na origem, melhorando de 2 / ( k ( k +1)) na resposta de daniello para o ideal 1 / k ² .
• Quando n é um múltiplo de k , é claramente possível através da fixação de uma base ortonormal de ℝ ^k e atribuindo a cada um dos vectores de base, para n / k de v ₁ , ..., v _n .
• De forma mais geral do que o último ponto de marcador, se for atingível com alguns escolha de k e ambos n = n ₁ e n = n ₂ , então também é possível para a mesma k e n = n ₁ + n ₂ . Em particular, é possível, se n = um k + b , onde um e b são inteiros satisfazendo um ≥ b ≥0.

Embora eu não tenha verificado os detalhes, parece que qualquer projeto esférico 2 fornece uma solução para atingir esse limite inferior.

Conexão incorreta aos SIC-POVMs em informações quânticas

Nas revisões anteriores, afirmei:

Eu suspeito que responder a isso completamente é uma pergunta difícil. A razão é que, se em vez considerar o complexo espacial vector ℂ ^k , esta questão está relacionada com um problema em aberto na informação quântica.

Mas essa relação estava incorreta. Eu vou explicar o porquê.

Mais precisamente, considere o seguinte problema:

Escolha vetores unitários x ₁ ,…, x _n ℂ ℂ ^k para minimizar (1 / ( n ( n −1))) ∑ _{i ≠ j} | x _i ^* x _j | ² .

O limite inferior acima também se aplica a esta versão complexa. Considere o caso em que n = k ² na versão complexa. Então o limite inferior é igual a 1 / ( k +1).

Até agora, estava correto.

Um conjunto de k ² vetores unitários x ₁ ,…, x _{k ²} ∈ ℂ ^k atingindo o limite inferior é chamado de SIC-POVM na dimensão k ,

Esta parte estava incorreta. Um SIC-POVM é um conjunto de k ² vetores unitários x ₁ ,…, x _n ℂ ℂ ^k para os quais | x _i ^* x _j | ² = 1 / ( k 1) para todos os i ≠ j . Observe que aqui o requisito deve ser válido para todos os pares i ≠ j , não apenas para a média de todos os pares i ≠ j . Na seção "Formulação equivalente", mostramos a equivalência entre minimizar o máximo e minimizar a média, mas isso foi possível porque x ₁,…, X _n eram variáveis ​​aleatórias tomando vetores unitários lá. Aqui x ₁ ,…, x _n são apenas vetores unitários, portanto não podemos usar o mesmo truque.

A resposta rápida e suja à pergunta é "não, a variação pode ser menor": Seja a base padrão e considere o seguinte processo aleatório: escolha um par de números inteiros distintos i, j de e defina . Para os outros vetores, (para ) atribua-os a maneira individual. Então, para cada , mantenha como está ou gire-o (para ) com probabilidade .$v_1, v_2, \ldots, v_k$$\{1,2,\ldots,k+1\}$$x_i = x_j = v_1$$x_t$$t \notin \{i,j\}$$v_2, \ldots, v_k$$t \in \{1,\ldots,k+1\}$$x_i$$-x_i$$\frac{1}{2}$

É fácil ver que - e são ortogonais ou apontam na mesma direção / oposta com probabilidade cada.x a x b $E[x_a \cdot x_b] = 0$$x_a$$x_b$$\frac{1}{2}$

Por outro lado, temos . Temos que se e somente se que acontece com a probabilidade . Caso contrário . Portanto, temos que, para todo , : ( x um ⋅ x b ) 2 = 1 { um , b } = { i , j $Var[x_a \cdot x_b] = E[(x_a \cdot x_b)^2]$$(x_a \cdot x_b)^2 = 1$$\{a,b\} = \{i,j\}$ (xa⋅xb)2=$\frac{1}{k+1 \choose 2}$$(x_a \cdot x_b)^2 = 0$$a$$b$

Minha intuição é que isso seja tão ruim (pequeno) quanto possível, mas não tenho uma prova. Mais interessante é que essa construção parece quebrar para n >> k, e também quando os precisam ser escolhidos independentemente (possivelmente de diferentes distribuições).$x_i$