Apa konsekuensi dari ?

Shiva Kintali baru saja mengumumkan (keren!) Menghasilkan bahwa isomorfisma grafik untuk grafik treewidth dibatasi lebar yaitu -Hard $\geq 4$ $\oplus L$ . Secara informal, pertanyaan saya adalah, "Seberapa sulit itu?"

Kita tahu bahwa yang tidak seragam , lihat jawaban untuk pertanyaan ini . Kami juga tahu bahwa tidak mungkin , lihat jawaban untuk pertanyaan ini . Betapa mengejutkannya jika ? Saya telah mendengar banyak orang mengatakan bahwa tidak akan mengejutkan seperti . $NL \subseteq \oplus L$ $\oplus L = P$ $L=\oplus L$ $L=NL$ $P=NP$

Apa konsekuensi dari ? $L=\oplus L$

Definisi: adalah sekumpulan bahasa yang dikenali oleh mesin Turing non-deterministik yang hanya dapat membedakan antara bilangan genap atau ganjil dari jalur "penerimaan" (daripada jumlah jalur penerimaan nol atau bukan nol), dan yang selanjutnya dibatasi untuk bekerja di ruang logaritmik. $\oplus L$

cc.complexity-theory complexity-classes logspace Aaron Sterling
sumber

Jawaban:

Wigderson membuktikan bahwa . Dengan argumen standar, akan menyiratkan . (Ambil mesin dalam . Ia memiliki mesin yang setara dengan dalam . Ambil bahasa pasangan instans-instan . Jika bahasa ini dalam , maka dengan hardcoding saran yang sesuai kita mendapatkan mesin setara dengan ) $NL/poly \subseteq \oplus L/poly$ $L = \oplus L$ $L/poly = NL/poly$ $M$ $NL/poly$ $M'$ $\oplus L/poly$ $\oplus L$ $S = \{(x,a)~|~M'(x,a)~\textrm{accepts}\}$ $L$ $a$ $L/poly$ $M$

Saya pikir itu akan mengejutkan: program percabangan nondeterministik akan setara dengan program percabangan deterministik (hingga faktor polinomial).

Ryan Williams
sumber

(Hasil Widgerson itu dimasukkan oleh NL / poli = UL / poli .)

Nah jika maka simulasi rangkaian stabilizer berada di , karena Aaronson dan Gottesman (Physical Review A 70, 052328) membuktikan simulasi semacam itu selesai untuk dalam pengurangan ruang log, atau lebih lemah lagi bahwa simulasi jaringan CNOT adalah di . Ekuivalen, jika simulasi sirkuit tersebut di maka . Secara pribadi, saya akan menemukan ini mengejutkan, tetapi tidak pada musim gugur dari kursi saya, saya akan menemukan mengejutkan. $L=\oplus L$ $L$ $\oplus L$ $L$ $L$ $L = \oplus L$ $P=NP$

Joe Fitzsimons
sumber

Terima kasih. Apakah ada penjelasan intuitif untuk apa yang bisa dilakukan oleh sirkuit stabilizer? Saya tidak terbiasa dengan mereka.

Aaron Sterling

@ Harunsterling: Sirkuit stabilizer adalah model terbatas dari perhitungan kuantum; mereka dihasilkan oleh gerbang CNOT (menghitung secara terbalik XOR dari dua bit input), dan dua gerbang yang tidak memiliki analog langsung dalam perhitungan klasik. Bertindak berdasarkan input "klasik" (yang disebut status dasar komputasi), atau pada input yang hanya sedikit lebih umum daripada input "klasik", input ini dapat disimulasikan secara efisien dalam hal transformasi symplectic modulo 2, meskipun memiliki rasa mekanis kuantum ( dan hanya sedikit malu kemampuan universalitas untuk perhitungan kuantum).

Niel de Beaudrap

@ AaronSterling: Mereka adalah himpunan bagian dari semua sirkuit kuantum yang mencakup CNOTS (dasarnya XOR + fanout) serta sejumlah gerbang kuantum yang dapat menciptakan superposisi yang sama (misalnya gerbang Hadamard). Jika Anda terbiasa dengan perhitungan kuantum, maka sirkuit sesuai dengan operator yang memetakan operator Pauli ke operator Pauli lainnya di bawah konjugasi, bekerja pada input klasik (atau input yang dapat diperoleh dari input klasik melalui sirkuit grup Clifford lain).

Joe Fitzsimons

Saya pikir kita perlu hierarki "kejutan", dengan 'jatuh dari kursi saya "di atas :)

Suresh Venkat