Materi pengantar yang bagus tentang kelas kompleksitas komputasi kuantum

10

Saya ingin belajar lebih banyak tentang kelas kompleksitas komputasi dalam konteks komputasi kuantum.

Media tidak begitu penting; bisa berupa buku, catatan kuliah online atau sejenisnya. Yang paling penting adalah isinya.

Materi tersebut harus mencakup dasar-dasar kelas kompleksitas komputasi kuantum dan mendiskusikan persamaan, perbedaan, dan hubungan di antara mereka dan mungkin juga dengan kelas kompleksitas komputasi klasik.

Saya lebih suka perawatan yang ketat daripada yang intuitif. Gaya penulisnya tidak masalah.

Sedangkan untuk prasyarat, saya hampir tidak tahu tentang topik, jadi mungkin lebih banyak materi mandiri akan lebih baik. Yang sedang berkata, saya mungkin tidak akan membaca buku 1000 halaman kecuali itu sangat bagus, apa pun dalam kisaran 1-500 halaman mungkin berhasil.

Adapun ketersediaan, tentu saja saya lebih suka bahan yang tidak di belakang paywall semacam dan dapat ditemukan secara online, tetapi ini bukan persyaratan yang ketat.

Apa yang kamu sarankan?

complexity-theory resource-request Kiro
sumber
Secara umum, meminta rekomendasi untuk kelas atau materi lain tidak dipertimbangkan pada topik untuk situs Stack Exchange; tetapi selain masalah itu, topik posting Anda tidak benar-benar tentang subjek "komputasi kuantum". Mengajar konsep kompleksitas komputasi lebih cocok untuk situs Ilmu Komputer kami .
Robert Cartaino
@RobertCartaino Terima kasih atas umpan baliknya, izinkan saya mencoba menjawab poin Anda. Saya meminta bahan untuk belajar sendiri, dan permintaan sumber daya afaik diizinkan dalam parameter . Saya akan mencoba yang terbaik untuk mengubah pertanyaan menjadi pada topik.
Kiro
1
@MEE Kecuali Anda mengabaikan inti dari topik ini - mengajarkan dasar-dasar kompleksitas komputasi hanyalah kebetulan bagi keahlian komputasi kuantum. Saya menyebutnya masalah "minuman ringan favorit programmer" . Ini adalah masalah ilmu komputer di mana menambahkan "dalam konteks komputasi kuantum" tidak membuatnya lebih sesuai dengan topik di sini dalam contoh ini. Tidak penting; pengguna tidak memiliki pertanyaan tentang subjek ini, dan mereka hanya ingin pergi ke tempat lain untuk menemukan informasi itu. Apa pun keputusan Anda.
Robert Cartaino
@ RobertTCartaino ok, saya mengerti maksud Anda sekarang, saya salah mengerti alasan penutupan. Karena itu saya ingin menarik kembali suara saya yang terbuka sekarang, tetapi karena ini tidak mungkin saya memilih untuk menutup pertanyaan ini.
MEE - Pasang kembali Monica
1
@RobertCartaino "dasar-dasar kompleksitas komputasi hanyalah kebetulan untuk keahlian komputasi kuantum" Saya setuju bahwa 'dasar-dasar' adalah bersamaan, tetapi saya pikir pertanyaan yang saat ini ditanyakan adalah cukup pada topik yang dapat saya lihat pada catatan kuliah tentang komputasi kuantum sebagai jawaban. Saya setuju bahwa versi sebelumnya memang akan dengan kasus " minuman ringan favorit programmer ", tetapi saya pikir itu telah diselesaikan sekarang.
Kadal diskrit

Jawaban:

7

Saya pikir survei John Watrous adalah tempat yang bagus untuk memulai (Profesor Watrous merekomendasikannya kepada saya sejak lama dan saya telah terpikat sejak itu!):

J. Watrous. Kompleksitas komputasi kuantum. Ensiklopedia Kompleksitas dan Ilmu Sistem, Springer, 2009. arXiv: 0804.3401 [quant-ph]

Sepengetahuan saya, ia memiliki kelas kompleksitas tertinggi dengan rasio halaman.

Saya juga sangat suka Barbados Lecture Notes 2016 Scott Aaronson:

S. Aaronson (dengan A. Bouland dan L. Schaeffer). Kompleksitas Negara Quantum dan Transformasi: Dari Uang Quantum ke Black Holes. ECCC TR16-109

Sanketh Menda
sumber
3

Saya dapat merekomendasikan catatan Kuliah Ronald de Wolf, yang digunakan untuk kursus semester yang diajarkan olehnya tentang Quantum Computing dalam konteks program 'Mastermath' Belanda.

Bab 10 "Teori Kompleksitas Kuantum", membahas secara singkat kelas kompleksitas 'klasik', tetapi memberikan latar belakang yang cukup untuk berbicara tentang kelas kompleksitas 'kuantum' dan membandingkannya dengan klasik. Itu tidak mencakup semuanya, tetapi merujuk pada bahan lain untuk dibaca lebih lanjut.

Bab 12 "Kompleksitas Komunikasi Quantum" juga relevan dan lebih teknis, terutama karena teori kompleksitas komunikasi memiliki aplikasi yang menarik dalam perhitungan kuantum.

Kadal diskrit
sumber