Apa kelas kompleksitas untuk subrutin kuantum yang menggunakan status kuantum arbitrer sebagai input?

Kelas kompleksitas BQP sesuai dengan subrutin kuantum waktu polinomial mengambil input klasik dan mengeluarkan output klasik probabilistik. Saran kuantum memodifikasi bahwa untuk memasukkan salinan beberapa status saran kuantum yang telah ditentukan tetapi dengan input klasik seperti biasa. Apa kelas kompleksitas untuk subrutin kuantum waktu polinomial yang mengambil status kuantum arbitrer sebagai input, dengan satu salinan hanya karena tidak ada kloning, dan mengeluarkan status kuantum sebagai output?

Saya pikir apa yang ingin Anda ketahui adalah analog kuantum dari kelas masalah fungsi. (Terima kasih kepada Peter Shor karena menunjukkan deskripsi singkat ini dalam komentar.)

Proses abstrak yang mengambil keadaan kuantum ukuran tetap sebagai input dan menghasilkan keadaan kuantum ukuran tetap sebagai output disebut saluran kuantum . Dalam situasi Anda, kami tidak ingin memperbaiki ukuran input atau ukuran output, dan oleh karena itu kami secara alami menganggap keluarga saluran kuantum sebagai analog kuantum fungsi dari string klasik ke string klasik.

Jelaslah mungkin untuk mendefinisikan kelas keluarga saluran kuantum yang dapat diimplementasikan / diperkirakan oleh keluarga sirkuit kuantum yang efisien (dengan gagasan efisiensi, keseragaman, dan perkiraan yang sesuai). Saya tidak tahu apakah kelas ini memiliki nama standar (tetapi lihat komentar Peter Shor untuk saran).

Dalam spekulasi saya, kelas saluran kuantum tidak sering dipelajari karena salah satu alasan untuk mempertimbangkan kelas kompleksitas adalah untuk membandingkan kekuatan model komputasi yang berbeda, dan kelas saluran kuantum tidak dapat digunakan untuk membandingkan model komputasi klasik dan kuantum. Namun, sangat baik untuk mendefinisikan dan berbicara tentang kelas-kelas tersebut jika ada hal menarik yang dapat dibuktikan tentang mereka.

Sesuatu yang Anda mungkin tertarik adalah gagasan oracle kuantum yang diperkenalkan oleh Aaronson dan Kuperberg di arXiv: quant-ph / 0604056 . Mengutip dari kertas mereka:

Seperti halnya oracle klasik memodelkan subrutin yang algoritmanya memiliki akses kotak hitam, demikian pula oracle kuantum memodelkan subrutin kuantum, yang dapat mengambil input kuantum dan menghasilkan output kuantum.

Ini tidak secara langsung menjawab pertanyaan Anda tentang definisi kelas kompleksitas yang mewakili model yang Anda gambarkan. Namun, gagasan oracle kuantum memiliki relevansi dalam teori kompleksitas: dalam makalah mereka Aaronson dan Kuperberg menggunakan oracle kuantum untuk memberikan pemisahan antara QMA dan QCMA .

Saya pikir kelas kompleksitas untuk masalah keputusan , mengambil status kuantum sebagai input cenderung memiliki definisi yang rapuh. Untuk masalah janji, baik definisi akan peka terhadap pilihan numerik, atau pada dasarnya akan memecahkan masalah keputusan / janji klasik yang dikodekan dalam beberapa basis negara kuantum yang dapat didekodekan secara efisien.

Jawaban Tsuyoshi menggambarkan apa yang saya anggap generalisasi masalah fungsi yang benar. Jika yang Anda inginkan adalah generalisasi masalah keputusan, Anda dapat mengkhususkan diri pada keluarga saluran darin$\Phi_n: \mathrm L(\mathcal H_2^{\otimes n}) \to \mathrm L(\mathcal H_2)$Status -qubit ke status qubit tunggal. Tentu saja, sirkuit kuantum adalah saluran yang sangat baik; jika kita akan berbicara tentang melakukan saluran tertentu yang dibatasi secara komputasi, kita mungkin juga hanya berbicara tentang rangkaian keluarga kuantum yang seragam (atau dalam hal ini, setiap cara yang seragam untuk menerapkan peta CPTP). Untuk ukuran yang baik, rangkaian harus diakhiri dengan pengukuran basis standar, jika kita ingin mempertahankan semantik dalam memutuskan sesuatu dengan probabilitas terbatas.

$\mathcal L$$\rho'$$\rho \in \mathcal L$$\rho$$\rho'$$\mathcal L$

Selain itu, tampaknya - karena teorema tanpa kloning mencegah Anda membuat salinan dari kondisi input Anda - bahwa Anda tidak dapat memperbesar probabilitas keberhasilan. Jadi setiap definisi QBQP yang melibatkan beberapa probabilitas keberhasilan konstan yang dibatasi dari 1/2 mungkin akan sangat tergantung pada apa probabilitas itu. Untuk menghindari hal ini, seperti halnya dengan kelas fungsi FBPP dan FBQP , kita dalam praktiknya mungkin mendefinisikan QBQP$\mathcal L$$\mathcal L$(1), yaitu probabilitas yang mendekati kepastian seiring ukuran input tumbuh - dan juga, probabilitas penolakan negara mana pun yang dapat ditolak oleh rutinitas keputusan juga harus menyatu menjadi nol.

Masalah kuantum-janji yang dapat dibedakan oleh sirkuit QBQP (untuk input berukuran n )

• $\mathcal H_2^{\otimes n}$
• Untuk NO instance, campuran keadaan murni yang ortogonal dengan subruang itu (atau setidaknya, semua negara ortokomplementer diizinkan oleh janji).

Di atas kelas-kelas negara bagian ini mungkin merupakan racun negara bagian terdekat yang diizinkan oleh janji, dan sangat dekat dengan negara bagian dari salah satu dari dua kelas di atas; tetapi asimtotik, kelas-kelas negara bagian yang puas dengan janji itu akan bertemu dengan dua kelas ini saat n tumbuh. Sirkuit yang terlibat dalam prosedur pengambilan keputusan pada dasarnya akan sesuai dengan sirkuit yang memetakan beberapa dasar keadaan murni di$\mathcal L$$\mathcal L^\bot$ keputusan atau masalah janji, dikodekan dalam keadaan kuantum, dengan kesalahan konvergen ke nol.

Perbaiki saya jika saya salah, tetapi bagi saya sepertinya Anda tertarik dengan kelas BQP / qpoly . Definisi dari Complexity Zoo: "Kelas masalah yang dapat dipecahkan oleh mesin BQP yang menerima keadaan kuantum ψn sebagai saran, yang hanya bergantung pada panjang input n."

Jika itu salah satunya, di situs web Anda dapat menemukan hubungan kelas ini dengan kelas kompleksitas lainnya. Jika tidak, situs web ini juga berisi informasi tentang apa yang terjadi pada BQP ketika Anda menggunakan berbagai jenis saran.

Ada juga karya yang relatif baru tentang " karakterisasi saran kuantum " di mana Anda dapat menemukan hierarki berikut:

Saya tidak tahu berapa banyak info ini sudah ada di Complexity Zoo. Jika Anda tertarik pada makalah, penulis juga telah memberikan ceramah tentang hal itu.

Sunting Saya ingin tahu apakah dengan "arbitrer" yang Anda maksud adalah keadaan yang dihasilkan oleh proses kuantum yang lebih umum yang 'evolusi kesatuan bertindak atas dasar komputasi' seperti evolusi disipatif. Dalam kasus terakhir khusus ini Anda tidak memiliki kekuatan komputasi lebih dari BQP seperti yang ditunjukkan dalam artikel ini .

Berikut adalah beberapa referensi tentang bahasa kuantum, yaitu, masalah keputusan dengan input kuantum. Mungkin masih banyak lagi.

1. NP Quantum dan Hierarki Quantum- Tomoyuki Yamakami
2. Tentang Kompleksitas Bahasa Quantum- Elham Kashefi, Carolina Moura Alves
3. Tes yang efisien untuk status produk, dengan aplikasi untuk permainan kuantum Merlin-Arthur -Aram Harrow, Ashley Montanaro, DOI: 10.1109 / FOCS.2010.66, Abstrak: arxiv.org/abs/1001.0017v3