Jakie jest minimum we wszystkich rozkładach wektorów jednostkowych wariancji iloczynu wektorów?

Usiłuję znaleźć rozkład na losowych wektorów, powiedzmy , na sferze jednowymiarowej (gdzie ), która minimalizuje zastrzeżeniem ograniczenia \ mathbb {E} [x_i ^ Tx_j] = 0 .$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$

Próbowałem niektórych dystrybucji i prawie wszystkie mają wariancję . Na przykład zarówno rozkład, w którym każda współrzędna każdego jest niezależnie i równomiernie wybierana spośród a także rozkład, w którym każdy jest niezależnym jednorodnym wektorem w sferze jednostkowej wymiarowej ma wariancję .$1/k$$x_i$$\left\{-1/\sqrt{k}, 1/\sqrt{k}\right\}$$x_i$$k$$1/k$

Czy to minimalna wariancja między wszystkimi rozkładami?$1/k$

Przedstawię równoważne, ale prostsze sformułowanie problemu i pokażę dolną granicę ( n / k - 1) / ( n −1). Pokazuję również związek z otwartym problemem w informacji kwantowej. [Edytuj w wersji 3: We wcześniejszych wersjach twierdziłem, że dokładna charakterystyka przypadków, w których osiągnięto dolną granicę pokazaną poniżej, może być trudna, ponieważ analogiczne pytanie w złożonej sprawie obejmuje otwarty problem dotyczący SIC-POVM w informacja kwantowa. Jednak to połączenie z SIC-POVM było nieprawidłowe. Aby uzyskać szczegółowe informacje, zobacz sekcję „Nieprawidłowe połączenie z SIC-POVM w informacjach kwantowych” poniżej.]

Równoważne sformułowanie

Po pierwsze, jak już wskazano w odpowiedzi Daniello, zauważ, że Var ( x _i ^T x _j ) = E [( x _i ^T x _j ) ² ] - E [ x _i ^T x _j ] ² = E [( x _i ^T x _j ) ² ]. Tak więc w pozostałej części odpowiedzi zapominamy o wariancji i zamiast tego minimalizujemy max _{i ≠ j} E [( x _i ^T x _j ) ² ].

Następnie, gdy zdecydujemy, że naszym celem jest zminimalizowanie max _{i ≠ j} E [( x _i ^T x _j ) ² ], możemy zignorować ograniczenie, że E [ x _i ^T x _j ] = 0. Jest tak, ponieważ jeśli mamy losowe wektory jednostkowe x ₁ ,…, x _n , wówczas możemy negować każdy z nich niezależnie z prawdopodobieństwem 1/2, aby spełnić E [ x _i ^T x _j ] = 0 bez zmiany wartości funkcji celu max _{i ≠ j} E [( x _i ^T x _j) ² ].

Ponadto, zmiana funkcji celu z max _{i ≠ j} E [( x _i ^T x _j ) ² ] na (1 / ( n ( n −1))) ∑ _{i ≠ j} E [( x _i ^T x _j ) ² ] nie zmienia optymalnej wartości. Ta ostatnia jest co najwyżej pierwsza, ponieważ średnia jest co najwyżej maksymalna. Jednak zawsze możemy dokonać wartości E [( x _i ^T x _j ) ² ] dla różnych wyborów ( i , j ) ( i ≠j ) równe przez permutację n wektorów x ₁ ,…, x _n losowo.

Zatem dla dowolnego n i k optymalna wartość danego problemu jest równa minimum (1 / ( n ( n- 1))) ∑ _{i ≠ j} E [( x _i ^T x _j ) ² ] gdzie x ₁ , ..., x _n są zmiennymi losowymi, które przyjmują wektor jednostkowy w ℝ ^k jako wartości.

Jednak zgodnie z liniowością oczekiwań ta funkcja celu jest równa wartości oczekiwanej E [(1 / ( n ( n- 1))) ∑ _{i ≠ j} ( x _i ^T x _j ) ² ]. Ponieważ minimum jest co najwyżej średnią, nie ma już potrzeby rozważania rozkładów prawdopodobieństwa. Oznacza to, że optymalna wartość powyższego problemu jest równa optymalnej wartości:

Wybierz wektory jednostkowe x ₁ ,…, x _n ∈ ℝ ^k, aby zminimalizować (1 / ( n ( n- 1))) ∑ _{i ≠ j} ( x _i ^T x _j ) ² .

Dolna granica

Korzystając z tego równoważnego sformułowania, udowodnimy, że optymalna wartość wynosi co najmniej ( n / k - 1) / ( n −1).

Dla 1 ≤ i ≤ n , niech X _i = x _i x _i ^T będzie projektorem rangi 1 odpowiadającym wektorowi jednostkowemu x _i . Następnie utrzymuje, że ( x _i ^T x _j ) ² = Tr ( X _i X _j ).

Niech Y = ∑ _i X _i . Następnie utrzymuje, że ∑ _{i ≠ j} Tr ( X _i X _j ) = ∑ _{i , j} Tr ( X _i X _j ) - n = Tr ( Y ² ) - n .

Nierówność Cauchy'ego-Schwarza oznacza, że ​​Tr ( Y ² ) ≥ (Tr Y ) ² / k = n ² / k , a zatem ∑ _{i ≠ j} Tr ( X _i X _j ) = Tr ( Y ² ) - n ≥ n ² / k - n . Dzieląc przez n ( n- 1), otrzymujemy, że wartość celu wynosi co najmniej ( n / k - 1) / ( n- 1).

W szczególności, gdy n = k +1, odpowiedź Daniello mieści się w współczynniku 2 od wartości optymalnej.

Kiedy można osiągnąć tę dolną granicę?

Osiągnięcie tego dolna granica ( n / k - 1) / ( n -1), co jest równoważne Y = ( n / k ) I . Nie znam dokładnej charakterystyki, kiedy jest osiągalna, ale istnieją następujące wystarczające warunki:

• Gdy n = k +1, można to osiągnąć, biorąc pod uwagę wektory jednostkowe k +1, które tworzą regularny k -simplex wyśrodkowany na początku, poprawiając się z 2 / ( k ( k +1)) w odpowiedzi Daniello na optymalną 1 / k ² .
• Gdy n jest wielokrotnością k , to wyraźnie osiągalne poprzez ustalenie Baza Ortonormalna z ℝ ^k i przypisanie każdego z wektorów bazowych do n / k o v ₁ , ..., v _n .
• Bardziej ogólnie niż ostatni punkt, jeśli jest to osiągalne przy pewnym wyborze k i zarówno n = n _{1, jak} i n = n ₂ , to jest również osiągalne dla tego samego k i n = n ₁ + n ₂ . W szczególności można to osiągnąć, jeśli n = a k + b, gdzie a i b są liczbami całkowitymi spełniającymi a ≥ b ≥0.

Chociaż nie sprawdziłem szczegółów, wydaje się, że każdy sferyczny projekt 2 daje rozwiązanie osiągające tę dolną granicę.

Niepoprawne połączenie z SIC-POVM w informacji kwantowej

We wcześniejszych wersjach stwierdziłem:

Podejrzewam, że odpowiedź na to pytanie jest trudna. Powodem jest to, że jeśli zamiast rozważyć kompleksową przestrzeni wektorowej ℂ ^k , to pytanie jest związane z otwartym problemem w informacji kwantowej.

Ale ta relacja była niepoprawna. Wyjaśnię dlaczego.

Dokładniej, rozważ następujący problem:

Wybierz wektory jednostkowe x ₁ ,…, x _n ∈ ℂ ^k, aby zminimalizować (1 / ( n ( n −1))) ∑ _{i ≠ j} | x _i ^* x _j | ² .

Dolna granica powyżej również obowiązuje w tej złożonej wersji. Rozważ przypadek, w którym n = k ² w wersji złożonej. Wtedy dolna granica jest równa 1 / ( k +1).

Jak dotąd było to poprawne.

Zestaw wektorów jednostkowych k ² x ₁ ,…, x _{k ²} ∈ ℂ ^k osiągających dolną granicę nazywa się SIC-POVM w wymiarze k ,

Ta część była niepoprawna. SIC-POVM to zbiór wektorów jednostkowych k ² x ₁ ,…, x _n ∈ ℂ ^k, dla których | x _i ^* x _j | ² = 1 / ( k +1) dla wszystkich i ≠ j . Zauważ, że tutaj wymóg musi posiadać dla wszystkich par i ≠ j , nie tylko średnią z wszystkich par i ≠ j . W sekcji „Formułowanie ekwiwalentne” wykazaliśmy równoważność między minimalizowaniem maksimum a minimalizowaniem średniej, ale było to możliwe, ponieważ x ₁,…, X _n były zmiennymi losowymi przyjmującymi wektory jednostkowe. Tutaj x ₁ ,…, x _n są tylko wektorami jednostkowymi, więc nie możemy użyć tej samej sztuczki.

$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}$

$E[x_a \cdot x_b] = 0$$x_a$$x_b$$\frac{1}{2}$

$Var[x_a \cdot x_b] = E[(x_a \cdot x_b)^2]$$(x_a \cdot x_b)^2 = 1$$\{a,b\} = \{i,j\}$$\frac{1}{k+1 \choose 2}$$(x_a \cdot x_b)^2 = 0$. Zatem mamy to dla każdego , : $a$$b$

Moją intuicją jest to, że jest tak źle (jak to tylko możliwe), ale nie mam dowodu. Bardziej interesujące jest to, że ta konstrukcja wydaje się załamać dla n >> k, a także wtedy, gdy muszą być wybrane niezależnie (być może z różnych rozkładów).$x_i$