Saya mencoba menemukan distribusi di atas vektor acak, katakanlah , pada -satuan dimensi ruang (di mana ) yang meminimalkan \ max_ {i \ neq j} \ mathrm {Var} (x_i ^ T x_j) tunduk pada kendala \ mathbb {E} [x_i ^ Tx_j] = 0 .E [ x T i x j ] = 0
Saya mencoba beberapa distribusi dan hampir semuanya memiliki varian . Misalnya, distribusi di mana setiap koordinat setiap dipilih secara independen dan seragam dari dan distribusi di mana masing-masing adalah vektor seragam independen pada -dimensional unit sphere memiliki varian .
Apakah varian minimum di antara semua distribusi?
Jawaban:
Saya akan menyajikan rumusan masalah yang setara tetapi terlihat lebih sederhana, dan menunjukkan batas bawah ( n / k - 1) / ( n −1).
Saya juga menunjukkan koneksi ke masalah terbuka dalam informasi kuantum.[Sunting dalam revisi 3: Dalam revisi sebelumnya, saya mengklaim bahwa karakterisasi yang tepat dari kasus-kasus di mana batas bawah yang ditunjukkan di bawah ini cenderung sulit karena pertanyaan analog dalam kasus kompleks mencakup masalah terbuka tentang SIC-POVMs di informasi kuantum. Namun, koneksi ke SIC-POVM ini salah. Untuk detailnya, lihat bagian “Koneksi yang salah ke SIC-POVMs dalam informasi kuantum” di bawah ini.]Formulasi yang setara
Pertama, seperti yang telah ditunjukkan dalam jawaban daniello, perhatikan bahwa Var ( x i T x j ) = E [( x i T x j ) 2 ] - E [ x i T x j ] 2 = E [( x i T x j ) 2 ]. Jadi dalam sisa jawabannya, kita lupa tentang varians dan bukannya meminimalkan max i ≠ j E [( x i T x j ) 2 ].
Selanjutnya, begitu kita memutuskan tujuan kita adalah untuk meminimalkan maks i ≠ j E [( x i T x j ) 2 ], kita dapat mengabaikan batasan bahwa E [ x i T x j ] = 0. Ini karena jika kita memiliki random vektor satuan x 1 , ..., x n , maka kita dapat meniadakan masing-masing secara independen dengan probabilitas 1/2 untuk memenuhi E [ x i T x j ] = 0 tanpa mengubah nilai fungsi tujuan max i ≠ j E [( x i T x j) 2 ].
Selain itu, mengubah fungsi tujuan dari maks i ≠ j E [( x i T x j ) 2 ] ke (1 / ( n ( n −1))))) i ≠ j E [( x i T x j ) 2 ] tidak mengubah nilai optimal. Yang terakhir paling banyak yang pertama karena rata-rata paling banyak maksimum. Namun, kita selalu dapat membuat nilai E [( x i T x j ) 2 ] untuk berbagai pilihan ( i , j ) ( i ≠j ) sama dengan mengubah n vektor x 1 , ..., x n secara acak.
Jadi untuk setiap n dan k , nilai optimal dari masalah yang dimaksud adalah sama dengan minimum (1 / ( n ( n −1)))) i i ≠ j E [( x i T x j ) 2 ] di mana x 1 ,…, x n adalah variabel acak yang menggunakan vektor satuan dalam ℝ k sebagai nilai.
Namun, dengan linearitas harapan, fungsi objektif ini sama dengan nilai yang diharapkan E [(1 / ( n ( n n1 ))))) i ≠ j ( x i T x j ) 2 ]. Karena minimum adalah paling banyak rata-rata, tidak perlu lagi mempertimbangkan distribusi probabilitas. Artinya, nilai optimal masalah di atas sama dengan nilai optimal berikut ini:
Batas bawah
Dengan menggunakan formulasi yang setara ini, kami akan membuktikan bahwa nilai optimal setidaknya ( n / k - 1) / ( n −1).
Untuk 1≤ i ≤ n , misalkan X i = x i x i T menjadi proyektor peringkat-1 yang sesuai dengan vektor satuan x i . Kemudian, ia berpendapat bahwa ( x i T x j ) 2 = Tr ( X i X j ).
Biarkan Y = i X i . Kemudian, ia menyatakan bahwa i i ≠ j Tr ( X i X j ) = i i , j Tr ( X i X j ) - n = Tr ( Y 2 ) - n .
Ketidaksamaan Cauchy-Schwarz menyiratkan bahwa Tr ( Y 2 ) ≥ (Tr Y ) 2 / k = n 2 / k , dan karenanya i ≠ j Tr ( X i X j ) = Tr ( Y 2 ) - n ≥ n 2 / k - n . Dengan membaginya dengan n ( n −1), kita memperoleh bahwa nilai obyektif setidaknya ( n / k - 1) / ( n )1).
Khususnya, ketika n = k +1, jawaban daniello berada dalam faktor 2 dari nilai optimal.
Kapan batas bawah ini dapat dicapai?
Mencapai ini terikat lebih rendah ( n / k - 1) / ( n -1) adalah setara dengan membuat Y = ( n / k ) saya . Saya tidak tahu karakterisasi pasti ketika itu dapat dicapai, tetapi mengikuti kondisi yang cukup ada:
Meskipun saya belum memeriksa detail, tampaknya setiap desain 2 bola memberikan solusi untuk mencapai batas bawah ini.
Koneksi yang salah ke SIC-POVMs dalam informasi kuantum
Dalam revisi sebelumnya, saya menyatakan:
Tetapi hubungan ini tidak benar. Saya akan menjelaskan alasannya.
Sejauh ini benar.
Bagian ini salah. SIC-POVM adalah seperangkat k 2 vektor unit x 1 ,…, x n ∈ ℂ k yang | x i * x j | 2 = 1 / ( k +1) untuk semua i ≠ j . Perhatikan bahwa di sini persyaratan harus berlaku untuk semua pasangan i ≠ j , bukan hanya rata-rata untuk semua pasangan i ≠ j . Di bagian "Rumusan ekivalen", kami menunjukkan kesetaraan antara meminimalkan maksimum dan meminimalkan rata-rata, tetapi ini dimungkinkan karena x 1,…, X n adalah variabel acak yang mengambil vektor satuan di sana. Di sini x 1 , ..., x n hanyalah vektor satuan, jadi kita tidak dapat menggunakan trik yang sama.
sumber
Jawaban cepat dan kotor untuk pertanyaan adalah "tidak, bisa lebih kecil": Biarkan menjadi basis standar, dan pertimbangkan proses acak berikut: pilih sepasang bilangan bulat yang berbeda i, j dari , dan set . Untuk vektor lainnya (untuk ) tetapkan untuk dengan cara satu-ke-satu. Kemudian, untuk setiap , jaga apa adanya atau balikkan (ke ) dengan probabilitas .v1,v2,…,vk {1,2,…,k+1} xi=xj=v1 xt t∉{i,j} v2,…,vk t∈{1,…,k+1} xi −xi 12
Mudah untuk melihat bahwa - baik dan adalah ortogonal atau mereka menunjuk ke arah yang sama / berlawanan dengan probabilitas masing-masing.x a x b 1E[xa⋅xb]=0 xa xb 12
Di sisi lain kita memiliki . Kami memilikinya jika dan hanya jika yang terjadi dengan probabilitas . Kalau tidak . Jadi kita memiliki itu untuk setiap , : ( x a ⋅ x b ) 2 = 1 { a , b } = { i , j }Var[xa⋅xb]=E[(xa⋅xb)2] (xa⋅xb)2=1 {a,b}={i,j} (xa⋅xb)2=0ab1(k+12) (xa⋅xb)2=0 a b
Intuisi saya adalah bahwa ini seburuk (kecil) karena mendapat tetapi saya tidak punya bukti. Lebih menarik adalah bahwa konstruksi ini tampaknya rusak untuk n >> k, dan juga ketika harus dipilih secara independen (mungkin dari distribusi yang berbeda).xi
sumber