Apa kompleksitas komputasi untuk mengoptimalkan berbagai fungsi di atas grup kesatuan ?
Sebuah tugas yang khas, yang timbul sering dalam teori informasi kuantum, akan memaksimalkan kuantitas tipe (atau perintah polinomial lebih tinggi di U ) atas semua kesatuan matriks U . Apakah jenis pengoptimalan ini secara efisien (mungkin kira-kira) dapat dihitung, atau apakah ini NP-hard? (mungkin ini sudah diketahui, tetapi saya belum dapat menemukan referensi umum)
cc.complexity-theory
reference-request
optimization
quantum-information
Marcin Kotowski
sumber
sumber
Jawaban:
Maaf saya terlambat! Dalam teori komputasi kuantum, ada banyak contoh masalah optimisasi atas kelompok kesatuan yang, secara mengejutkan (setidaknya bagi saya), dapat dipecahkan dalam waktu polinomial (klasik) dengan mengurangi pemrograman semidefinite.
Berikut adalah contoh awal: menyelesaikan masalah tambang dari tahun 2000, pada tahun 2003 Barnum, Saks, dan Szegedy menunjukkan bahwa Q (f), kompleksitas kueri kuantum dari fungsi Boolean f: {0,1} n → {0,1 }, dapat dihitung dalam polinomial waktu dalam 2 n (yaitu, ukuran tabel kebenaran f). Saya telah memikirkan hal ini tetapi tidak dapat melihat bagaimana melakukannya, karena kita perlu mengoptimalkan probabilitas keberhasilan atas semua algoritma kueri kuantum yang mungkin, masing-masing dengan set sendiri (mungkin 2 n- ukuran) matriks kesatuan. Barnum et al. direduksi menjadi SDP dengan mengeksploitasi "dualitas" antara matriks kesatuan dan matriks semidefinit positif, yang disebut isomorfisma Choi-Jamiolkowski. Untuk karakterisasi SDP yang lebih baru dan lebih sederhana Q (f), lihat makalah Reichardt 2010 yang menunjukkan bahwa metode musuh berbobot negatif adalah optimal.
Kasus penting lain di mana trik ini telah dieksploitasi adalah dalam sistem bukti interaktif kuantum. Meskipun tidak jelas secara intuitif, pada tahun 2000 Kitaev dan Watrous membuktikan bahwa QIP ⊆ EXP. dengan mengurangi masalah optimisasi atas matriks kesatuan ukuran eksponensial yang muncul dalam sistem bukti interaktif kuantum 3 putaran, untuk memecahkan SDP berukuran eksponensial tunggal (sekali lagi, saya pikir, menggunakan isomorfisma Choi-Jamiolkowski antara keadaan campuran dan matriks kesatuan). Terobosan QIP = PSPACE baru-baru ini datang dari menunjukkan bahwa SDP tertentu dapat kira-kira diselesaikan lebih baik, di NC (yaitu, dengan sirkuit log-depth).
Jadi, apa pun masalah pengoptimalan spesifik Anda yang melibatkan grup kesatuan, tebakan saya adalah bahwa itu dapat diselesaikan lebih cepat dari yang Anda kira - jika tidak dengan cara yang bahkan lebih sederhana, maka dengan mereduksi ke SDP!
sumber
Menentukan apakah dua matriks Hadamard adalah setara adalah masalah lengkap Graph Isomorphism (GI). Brendon McKay memiliki makalah tentang topik ini. Lihat BD McKay, kesetaraan Hadamard melalui grafik isomorphism, Discrete Mathematics, 27 (1979) 213-216.
sumber