-tidak memelihara mesin Turing

Membaca beberapa utas baru-baru ini tentang komputasi kuantum (di sini , di sini , dan di sini ), membuat saya ingat pertanyaan menarik tentang kekuatan beberapa jenis mesin pelestarian .$\ell_p$

Bagi orang yang bekerja dalam teori kompleksitas menuju kompleksitas kuantum, teks pengantar yang bagus adalah makalah Fortnow yang tautannya diposting oleh Joshua Grochow di sini . Dalam makalah itu, mesin Turing kuantum disajikan sebagai mesin Turing probabilistik umum. Pada dasarnya, mesin probabilistik memiliki keadaan dinormalisasi bawah -norm, yaitu . Evolusi waktu dari mesin diberikan oleh aplikasi dari matriks stokastik sehingga , yaitu mempertahankan -norm. Jadi negara pada waktu adalahℓ 1 ∥ s ∥ 1 = 1 P ∥ P s ∥ 1 = 1 P ℓ 1 t P t$s$$\ell_1$$\parallel s\parallel_1=1$$P$$\parallel Ps\parallel_1=1$$P$$\ell_1$$t$$P^ts$(notasi mungkin tidak tepat karena multiplikasi kiri atau kanan tergantung pada apakah adalah vektor baris atau kolom atau baris atau kolom adalah subruang yang mempertahankan norma). Jadi dalam hal ini mesin Turing yang probabilistik adalah mesin pengawet yang dilambangkan dengan .s P ℓ 1 M ℓ $P$$s$$P$$\ell_1$$M^{\ell_1}$

Kemudian mesin Turing kuantum dapat dilihat memiliki keadaan dengan dan matriks kesatuan (yang mempertahankan -norms) sehingga adalah keadaan pada waktu mana . Ini adalah mesin pengawet dilambangkan dengan .∥ s ∥ 2 = $s$$\parallel s\parallel_2=1$ℓ 2 P t s t ∥ P t s ∥ 2 = 1 ℓ 2 M ℓ $P$$\ell_2$$P^ts$$t$$\parallel P^ts\parallel_2=1$$\ell_2$$M^{\ell_2}$

Biarkan secara umum mesin pengawet -norm ditandai dengan .M ℓ $\ell_p$$M^{\ell_p}$

Jadi pertanyaan saya adalah:

(1) Apa kekuatan -norm mesin pengawet untuk hingga ? Secara lebih formal, dapatkah kita membuktikan bahwa untuk setiap dan diberikan , jika maka ada bahasa dan mesin sehingga efisien menentukan dan tidak ada mesin yang efisien memutuskan . Misalnya, ini bisa menjadi generalisasi dari pertanyaan, apakah ? p p q q > p L M ℓ q M ℓ q L M ℓ p L N P ⊆ B Q $\ell_p$$p$$p$$q$$q>p$$L$$M^{\ell_q}$$M^{\ell_q}$$L$$M^{\ell_p}$$L$$NP \subseteq BQP$

(2) Bagaimana dengan ? Di sini nilai maksimum komponen vektor keadaan adalah 1.$p=\infty$

(3) Pertanyaan-pertanyaan ini melampaui unitaritas sehingga tidak diharapkan untuk setuju dengan mekanika kuantum. Secara umum, apa yang terjadi dengan perhitungan jika Anda mengendurkan pembatasan unitaritas pada operasi? Ada pekerjaan tentang mengizinkan operator non-linear (lihat Aaronson 2005 ).

(4) Mungkin yang paling penting, apakah itu universal? Saya pikir ini jelas, karena untuk kasus-kasus tertentu itu universal. Tetapi apa yang terjadi dengan universalitas ketika ?$p=\infty$

Ini bukan jawaban yang lengkap untuk pertanyaan, tetapi terlalu panjang untuk ditulis sebagai komentar. Itu memperluas komentar saya sebelumnya.

Pertanyaan "Apa yang terjadi pada perhitungan jika aksioma mekanika kuantum sedikit dimodifikasi?" Dibahas secara sangat rinci oleh sebuah makalah menyenangkan [Aar04] oleh Scott Aaronson. Saya percaya bahwa pertanyaan Anda pada dasarnya dijawab di paruh pertama Bagian 2 dari [Aar04].

Aaronson menunjukkan bahwa jika p> 0 dan p ≠ 2, maka sebuah matriks yang mempertahankan norma-p untuk semua vektor harus merupakan matriks permutasi umum (produk dari matriks permutasi dan matriks diagonal). Dia menyatakan bahwa hal yang sama berlaku dalam kasus p = ∞. Semua ini berlaku untuk lebih dari ℝ dan lebih ℂ. Perhatikan bahwa ini termasuk kasus p = 1: matriks stokastik mempertahankan 1-norma untuk vektor tidak negatif tetapi tidak untuk semua vektor pada umumnya.

Saya kira mesin Turing probabilistik yang digeneralisasi seperti pada [For00] memiliki matriks permutasi umum sebagai matriks transisi globalnya hanya jika itu adalah mesin Turing deterministik, tetapi saya tidak memiliki bukti yang ada.

Aaronson juga membahas beberapa modifikasi lain dari aksioma mekanika kuantum dalam makalah ini. Sebagai contoh, jika kita mengubah aturan pengukuran (bukan set gerbang yang diizinkan) sehingga hasil x terjadi dengan probabilitas | α _x | ^p / ∑ _y | α _y | ^p , di mana α _y adalah amplitudo | y⟩, maka "komputer kuantum" ini dapat menyelesaikan masalah dalam PP (termasuk masalah NP-complete) dalam waktu polinomial kecuali p = 2 (Proposisi 5).

Referensi

[Aar04] Scott Aaronson. Apakah mekanika kuantum pulau dalam ruang teori? Dalam Prosiding Konferensi Växjö “Teori Kuantum: Peninjauan Kembali Yayasan,” 2004. arXiv: quant-ph / 0401062 v2.

[For00] Lance Fortnow. Pandangan satu kompleksitas teori tentang komputasi kuantum. Dalam Komputasi: Simposium Teori Australasia (CATS 2000), hlm. 58–72, Januari 2000. http://dx.doi.org/10.1016/S1571-0661(05)80330-5

$p \not\in \{1,2\}$$\ell_p$$\left| \psi_i \right|^p$

$\ell_p$$\ell_1$$\ell_2$$\Omega(N^{1/p})$$\ell_\infty$$\ell_p$$\ell_q$$1/p+1/q=1$$\ell_p$$p$