Pengurangan ruang log dari sirkuit Parity-L ke CNOT?

Pertanyaan.

Dalam makalah mereka Peningkatan simulasi sirkuit stabilizer , Aaronson dan Gottesman mengklaim bahwa mensimulasikan sirkuit CNOT adalah ⊕L -complete (di bawah pengurangan ruang log). Jelas bahwa itu terkandung dalam ⊕L ; bagaimana hasil kekerasan berlangsung?

Secara ekuivalen: apakah ada pengurangan ruang log dari produk matriks berulang modulo 2, menjadi produk berulang dari matriks elementer (matriks yang dapat dibalik yang mewujudkan transformasi baris) mod 2?

Detail

Operasi dikendalikan-TIDAK (atau CNOT ) adalah operasi boolean yang dapat dibalik, dari bentuk

$$\mathsf{CNOT}_{\!h,j} (x_1\,, \;\ldots\;, x_h\,,\; \ldots\;, x_j\,, \;\ldots\;, x_n) \;\;=\;\; (x_1\,, \;\ldots\;, x_h\,,\; \ldots\;, x_j \oplus x_h\,, \;\ldots\;, x_n)$$ di mana hanyaj^thbit berubah, dan bit yang diubah dengan menambahkan$x_h$ modulo 2, untuk setiap posisi yang berbedahdanj. Tidak sulit untuk melihat, jika kita menafsirkan sebagai vektor lebih dari ℤ / 2ℤ, yang ini sesuai dengan modulo transformasi baris 2, yang dapat kita wakili dengan matriks dengan 1s pada posisi diagonal dan posisi off-diagonal tunggal. SebuahCNOT sirkuitkemudian produk matriks yang terdiri dari produk dari beberapa matriks elementer jenis ini.$\mathbf x = (x_1\,, \;\ldots\;, x_n)$

Makalah oleh Aaronson dan Gottesman yang disebutkan di atas (yang, sangat kebetulan untuk pertanyaan ini, adalah tentang kelas sirkuit kuantum yang dapat disimulasikan dalam ⊕L ) memiliki bagian tentang kompleksitas komputasi. Menjelang awal bagian ini, mereka menggambarkan ⊕L sebagai berikut:

⊕L adalah kelas dari semua masalah yang dapat dipecahkan oleh mesin Turing ruang logaritmik nondeterministik, yang menerima jika dan hanya jika jumlah total jalur penerimaan adalah ganjil. Tetapi ada definisi alternatif yang mungkin lebih intuitif untuk ilmuwan non-komputer. Ini adalah bahwa ⊕L adalah kelas masalah yang mengurangi untuk mensimulasikan sirkuit CNOT ukuran polinomial, yaitu  sirkuit yang seluruhnya terdiri dari gerbang NOT dan CNOT, yang bekerja pada keadaan awal | 0 ... 0⟩. (Mudah untuk menunjukkan bahwa kedua definisi itu setara, tetapi ini akan mengharuskan kita untuk menjelaskan apa arti definisi yang biasa!)

Target audiens artikel termasuk sejumlah besar ilmuwan non-komputer, sehingga keinginan untuk menghindari itu tidak masuk akal; Saya berharap seseorang dapat menjelaskan bagaimana kesetaraan ini berlaku.

Jelas, simulasi produk dari matriks tersebut dapat dilakukan dalam ⊕L sebagai kasus khusus dari evaluasi koefisien produk matriks iterasi (mod 2), yang merupakan masalah lengkap (di bawah pengurangan logspace) untuk ⊕L . Lebih lanjut, karena matriks CNOT hanya melakukan operasi baris elementer, setiap matriks yang dapat dibalik dapat didekomposisi sebagai produk dari matriks CNOT. Namun: tidak jelas bagaimana cara saya menguraikan bahkan sebuah mod 2 matriks yang dapat dibalik menjadi produk dari matriks CNOT oleh pengurangan ruang log . (Memang, seperti dicatat oleh Emil Jeřábek dalam komentar, eliminasi Gaussian cukup untuk menghitung determinan mod 2, yang merupakan masalah ⊕L -lengkap : jadi serangan langsung dengan mendekomposisi mis. matriks yang dapat dibalik sebagai produk dari matriks dasar tampaknya tidak layak dalam ruang log kecuali L  =  ⊕L .) Untuk mengatakan tidak ada produk matriks yang tidak dapat dibalik. Jadi beberapa pengurangan yang cerdas tampaknya diperlukan.

Saya harap seseorang dapat memberikan sketsa pengurangan ini, atau referensi ( misalnya  teks yang merupakan latihan ini, jika sederhana).

Mari kita mulai dengan masalah -complete untuk menghitung mod 2 jumlah lintasan panjang n dari simpul s ke simpul t dalam grafik berarah G = ( V , E ) . Kami menerapkan beberapa pengurangan logspace sebagai berikut.$\oplus L$$2$$n$$s$$t$$G=(V,E)$

Misalkan menjadi grafik sedemikian rupa sehingga V ′ = V × { 0 , … , n } dan E ′ = { ( ( u , i ) , ( v , i + 1 ) : i < n , ( u , v ) ∈ E } ∪ { $G'=(V',E')$$V'=V\times\{0,\dots,n\}$ (yaitu, kita mengambil n + 1 salinan G ‘simpul s, tepi make pergi dari saya th copy ke ( i + 1 ) th copy sesuai dengan G tepi 's, dan tambahkan semua loop otomatis). Maka masalah aslinya setara dengan menghitung jalur panjang n dari s ′ = ( s , 0 ) ke t ′ = ( t , n $E'=\{((u,i),(v,i+1):i<n,(u,v)\in E\}\cup\{(w,w):w\in V'\}$$n+1$$G$$i$$(i+1)$$G$$n$$s'=(s,0)$$t'=(t,n)$dalam .$G'$

Selain itu, adalah asiklik, dan kita secara eksplisit dapat menentukan penghitungan V ' = { w k : k ≤ m } sehingga semua tepi di G ' terpisah dari diri-loop pergi dari w k ke w l untuk beberapa k < l . Tanpa kehilangan sifat umum, w 0 = s ′ dan w m = t ′ . Biarkan M menjadi matriks kedekatan G $G'$$V'=\{w_k:k\le m\}$$G'$$w_k$$w_l$$k<l$$w_0=s'$$w_m=t'$$M$$G'$WR enumerasi yang diberikan. Kemudian adalah matriks integer segitiga atas dengan 1 pada diagonal, dan jumlah lintasan panjang n dari s ′ ke t ′ sama dengan elemen kanan atas M n .$M$$1$$n$$s'$$t'$$M^n$

Mudah untuk melihat bahwa mana E i , j ( a ) adalah matriks elementer yang satu-satunya entri nondiagonal adalah a dalam baris i dan kolom j . Dengan cara ini, kami mengurangi masalah awal untuk menghitung elemen kanan atas dari produk matriks elementer. Di dalam ⊕

$$M=\prod_{j=m}^1\prod_{i=0}^{j-1}E_{i,j}(M_{i,j}),$$ $E_{i,j}(a)$$a$$i$$j$$\oplus L$kasus, perhitungannya adalah modulo , yaitu, kami mempertimbangkan matriks lebih dari F 2 . (Dalam hal ini, matriks-matriks dasar hanya bisa menjadi E i , j ( 0 ) = I , yang dapat kita abaikan, dan E i , j ( 1 ) , yang dapat disimulasikan oleh gerbang CNOT tunggal, seperti yang disebutkan dalam pertanyaan .) Jika kita menganggapnya sebagai matriks bilangan bulat, kita mendapatkan masalah # L -complete, dan jika kita menganggapnya modulo k , kita mendapatkan masalah M o d k L -complete.$2$$\mathbb F_2$$E_{i,j}(0)=I$$E_{i,j}(1)$$\#L$$k$$\mathrm{Mod}_kL$