Seberapa kuat penghitungan "kuantum" yang tepat jika Anda menangguhkan unitaritas?

Pertanyaan pendek.

Apa kekuatan komputasi dari sirkuit "kuantum", jika kita mengizinkan gerbang non-kesatuan (tapi masih tidak dapat dibalik), dan membutuhkan output untuk memberikan jawaban yang benar dengan pasti?

Pertanyaan ini dalam arti tentang apa yang terjadi pada kelas $\mathsf{EQP}$ ketika Anda membiarkan sirkuit menggunakan lebih dari sekadar gerbang kesatuan. (Kami masih terpaksa membatasi diri pada gerbang yang dapat dibalik di atas $\mathbb C$ jika kami ingin dapat memiliki model perhitungan yang terdefinisi dengan baik.)

(Pertanyaan ini telah mengalami beberapa revisi sehubungan dengan kebingungan saya tentang hasil yang diketahui tentang sirkuit seperti itu dalam kasus kesatuan.)

Tentang perhitungan kuantum "tepat"

Saya mendefinisikan $\mathsf{EQP}$ demi pertanyaan ini menjadi kelas masalah yang dapat tepat diselesaikan dengan sirkuit keluarga seragam kuantum, di mana koefisien masing-masing kesatuan adalah dihitung dengan polinomial-waktu-dibatasi mesin Turing (dari string masukan $1^n$ ) untuk setiap ukuran input $n$ , dan tata letak sirkuit sebagai jaringan terarah juga dapat diproduksi dalam waktu polinomial. Dengan "tepat" terpecahkan, maksud saya bahwa mengukur bit output menghasilkan $|0\rangle$ dengan kepastian bagi NO kasus, dan $|1\rangle$ dengan pasti untuk kasus YES.

Peringatan:

• Bahkan membatasi ke gerbang kesatuan, gagasan ini dari berbeda dari yang dijelaskan oleh Bernstein dan Vazirani menggunakan mesin Turing kuantum. Definisi di atas memungkinkan rangkaian keluarga { C n } pada prinsipnya memiliki gerbang tanpa batas ditetapkan - masing-masing sirkuit individu C n hanya menggunakan subset terbatas, tentu saja - karena gerbang yang berlaku dihitung dari input. (Mesin kuantum Turing dapat mensimulasikan setiap set gerbang hingga yang Anda sukai, tetapi hanya dapat mensimulasikan set gerbang hingga, karena hanya memiliki sejumlah transisi hingga.)$\mathsf{EQP}$$\{ C_n \}$$C_n$

• Model perhitungan ini meremehkan setiap masalah dalam , karena kesatuan dapat berisi gerbang tunggal yang mengkodekan solusi untuk setiap masalah dalam P (koefisiennya setelah semua ditentukan oleh perhitungan waktu-poli). Jadi kompleksitas waktu atau ruang spesifik masalah tidak selalu menarik untuk sirkuit seperti itu.$\mathsf P$$\mathsf P$

Kita dapat menambah peringatan ini pengamatan bahwa implementasi praktis komputer kuantum akan memiliki noise. Model komputasi semenarik terutama untuk alasan teoritis , sebagai salah satu peduli dengan menyusun transformasi kesatuan daripada perhitungan layak, dan juga sebagai versi yang tepat dari . Secara khusus, meskipun peringatan di atas, kita memiliki P ⊆ E Q P ⊆ B Q P .$\mathsf{BQP}$$\mathsf{P} \subseteq \mathsf{EQP} \subseteq \mathsf{BQP}$

Alasan untuk mendefinisikan dalam cara saya lakukan adalah agar DISKRIT-LOG dapat dimasukkan ke dalam E Q P . Pada [  Mosca + Zalka 2003  ], ada algoritma polinomial-waktu untuk membangun sirkuit kesatuan yang secara tepat memecahkan instance DISCRETE-LOG dengan menghasilkan versi QFT yang tepat tergantung pada modulus input. Saya percaya bahwa kita kemudian dapat menempatkan DISCRETE-LOG ke dalam E Q P , seperti yang didefinisikan di atas, dengan menyematkan elemen-elemen rangkaian-konstruksi ke dalam cara koefisien gerbang dihitung. (Jadi hasilnya DISCRETE-LOG ∈ E Q P pada dasarnya dipegang oleh fiat, tetapi mengandalkan pembangunan Mosca + Zalka.)$\mathsf{EQP}$$\mathsf{EQP}$$\mathsf{EQP}$$\in \mathsf{EQP}$

Menangguhkan unitaritas

Biarkan menjadi kelas komputasi yang kita dapatkan jika kita menangguhkan batasan yang gerbang menjadi satu, dan memungkinkan mereka untuk berkisar pada transformasi yang tidak dapat dibalik. Bisakah kita menempatkan kelas ini (atau bahkan mencirikannya) dalam istilah kelas non-deterministik tradisional C lainnya ?$\mathsf{EQP_{\mathrm{GL}}}$$\mathbf C$

Salah satu alasan saya untuk bertanya: jika adalah kelas masalah yang secara efisien dapat dipecahkan dengan kesalahan yang dibatasi , berdasarkan rangkaian keluarga rangkaian "kuantum non-kesatuan" - di mana instance YA memberikan output dari | 1 ⟩ dengan probabilitas paling sedikit 2/3, dan NO contoh dengan probabilitas paling 1/3 (setelah normalisasi negara-vector) - maka [Aaronson 2005] menunjukkan bahwa B Q P G L = P P . Yaitu: menangguhkan unitaritas dalam hal ini setara dengan membiarkan kesalahan yang tidak terikat.$\mathsf{BQP}_{\mathrm{GL}}$$|1\rangle$$\mathsf{BQP}_{\mathrm{GL}} = \mathsf{PP}$

Apakah hasil yang serupa, atau hasil yang jelas, diperoleh untuk ?$\mathsf{EQP_{\mathrm{GL}}}$

Jawaban singkat. Ternyata menangguhkan persyaratan transformasi kesatuan, dan mengharuskan setiap operasi tidak dapat dibalik, menimbulkan kelas-kelas yang dapat didefinisikan dengan pasti. Kelas-kelas tertentu yang dimaksud adalah dan 'baru' subclass L P W P P , yang keduanya duduk antara S P P dan C = P . Kelas-kelas ini memiliki definisi yang cukup teknis, yang dijelaskan secara singkat di bawah ini; meskipun definisi-definisi ini sekarang dapat diganti, pada prinsipnya, dengan definisi-definisi dalam hal algoritma "seperti-kuantum" yang non-kesatuan.$\mathsf{LWPP}$$\mathsf{LPWPP}$$\mathsf{SPP}$$\mathsf{C_=P}$

Kelas penghitungan berisi GRAF ISOMORFISME. Hal ini juga berisi seluruh kelas U P , jadi kita tidak akan mengharapkan tepat kesatuan algoritma kuantum untuk menjadi sekuat kelas non-kesatuan (seperti yang kita jika tidak bisa menunjukkan $\mathsf{SPP}$$\mathsf{UP}$ ).$\mathsf{NP \subseteq BQP}$

Jawaban yang lebih panjang.

• Dalam pertanyaan saya, saya mengusulkan mendefinisikan ulang untuk memungkinkan masalah yang dipecahkan oleh keluarga sirkuit seragam yang menggunakan gerbang yang efisien dihitung, tetapi tidak harus diambil dari gerbang-himpunan berhingga. Saya tidak lagi begitu yakin bahwa itu adalah ide yang baik untuk mendefinisikan kembali E Q P dengan cara ini, meskipun saya percaya keluarga sirkuit tersebut berharga untuk belajar. Kita dapat memanggil kelas ini sesuatu seperti U n i t a r y P C sebagai gantinya.$\mathsf{EQP}$ $\mathsf{EQP}$$\mathsf{UnitaryP_{\mathbb C}}$

  Hal ini dimungkinkan untuk menunjukkan bahwa , yang sampai saat ini adalah yang terbaik dikenal menuju E Q P . Kelas L W P P lebih atau kurang sesuai dengan masalah yang ada algoritma acak, di mana NO instance menghasilkan hasil 1 dengan probabilitas tepat 0,5, dan contoh YA menghasilkan hasil 1 dengan beberapa probabilitas yang dapat efisien dan tepat dihitung dalam bentuk rasional, yang lebih besar dari (tetapi mungkin secara eksponensial mendekati) 0,5. Definisi teknis L W $\mathsf{UnitaryP_{\mathbb C} \subseteq LWPP}$$\mathsf{EQP}$$\mathsf{LWPP}$ disajikan dalam bentuk mesin Turing nondeterministik, tetapi tidak lebih mencerahkan.$\mathsf{LWPP}$

  Jika kita mendefinisikan menjadi dibalik-gerbang setara dengan U n i t a r y P C , sehingga adalah serangkaian masalah yang persis dipecahkan oleh dibalik keluarga sirkuit dengan koefisien gerbang efisien dihitung, maka G L P C = L $\mathsf{GLP}_{\mathbb C}$$\mathsf{UnitaryP_{\mathbb C}}$ .$\mathsf{GLP_{\mathbb C} = LWPP}$

• Jika kita membatasi untuk terbatas gerbang-set, adalah mungkin untuk menunjukkan bahwa keluarga rangkaian kesatuan dapat disimulasikan dalam subset dari , yang dapat kita sebut L P W P P . (Menggunakan deskripsi L W P P di atas, berkorespondensi ini untuk algoritma acak di mana peluang mendapatkan output 1 untuk contoh YES persis m t ( x ) / 2 p ( | x | ) , untuk beberapa polinomial p , beberapa bilangan bulat $\mathsf{LWPP}$$\mathsf{LPWPP}$$\mathsf{LWPP}$$m^{t(x)} / 2^{p(|x|)}$$p$$m$, Dan beberapa efisien dihitung jumlahnya banyak .)$t$

  Jika kita mendefinisikan sebagai ekuivalen gerbang yang tidak dapat dibalik dengan E Q P seperti yang didefinisikan secara normal, kita dapat menunjukkan bahwa E Q P G L ⊆ L P W $\mathsf{EQP_{\mathrm{GL}}}$$\mathsf{EQP}$ .$\mathsf{EQP_{\mathrm{GL}} \subseteq LPWPP}$

Koreksi terkait DISCRETE LOG.

Hasil di atas bergantung pada teknik standar untuk mewakili koefisien aljabar, dengan cara yang tidak tergantung pada input (tetapi yang mungkin tergantung pada ukuran input). Dalam uraian pertanyaan awal, saya menyatakan bahwa [ Mosca + Zalka 2003 ] menunjukkan bahwa LOG DISKRET benar-benar dipecahkan oleh gerbang-set dengan koefisien yang dapat dihitung secara efisien. Kebenaran tampaknya lebih rumit. Jika seseorang peduli tentang solvabilitas yang tepat, maka saya menganggap representasi koefisien yang tepat menjadi penting: tetapi Mosca dan Zalka tidak menyediakan cara untuk melakukan ini dengan cara yang bergantung pada input. Jadi tidak jelas bahwa LOG DISKRET sebenarnya dalam atau di kelas baru U n i t a r y $\mathsf{EQP}$ .$\mathsf{UnitaryP_{\mathbb C}}$

Referensi.

• de Beaudrap, Tentang penghitungan yang tepat dan kompleksitas kuasi-kuantum , [ arXiv: 1509.07789 ].