Model Komputasi Kuantum

Komputasi kuantum menggantikan bit klasik dengan keadaan kuantum yang dapat disuperposisikan dan dijerat, mendefinisikan model seperti sirkuit kuantum dan kelas kompleksitas BQP yang tampaknya memecahkan beberapa masalah lebih cepat daripada metode klasik apa pun.

Definition

Model komputasi kuantum memproses informasi yang disimpan dalam qubit yang keadaannya adalah vektor satuan dalam ruang kompleks; komputasi menerapkan gerbang kuantum reversibel untuk menciptakan superposisi dan keterikatan (entanglement), dan pengukuran akhir menghasilkan hasil klasik dengan probabilitas yang ditetapkan oleh keadaan kuantum.

Scope

Topik ini mencakup qubit dan gerbang kuantum, model sirkuit kuantum dan kesetaraannya dengan mesin Turing kuantum, kelas kompleksitas BQP dari komputasi kuantum yang efisien dan hubungannya dengan kelas klasik, algoritma fundamental seperti faktorisasi Shor dan pencarian Grover, serta peran pengukuran dan dekoherensi dalam mendefinisikan model.

Core questions

• Bagaimana superposisi dan keterikatan mengubah kemampuan komputasi?
• Apa hubungan antara kelas kuantum efisien BQP dan kelas klasik?
• Untuk masalah apa algoritma kuantum menawarkan percepatan yang terbukti atau tampak?
• Bagaimana pengukuran dan prinsip non-kloning membatasi komputasi kuantum?

Key theories

Model sirkuit kuantum dan BQP

Komputasi kuantum yang efisien ditangkap oleh sirkuit kuantum berukuran polinomial di atas set gerbang universal, mendefinisikan kelas BQP, yang berisi P dan diyakini memperluasnya sementara masih berada dalam PSPACE.

Percepatan kuantum

Algoritma Shor memfaktorkan bilangan bulat dalam waktu polinomial dan algoritma Grover mencari ruang tidak terstruktur dengan percepatan kuadratik, menunjukkan keuntungan konkret dari model kuantum untuk tugas-tugas tertentu.

Clinical relevance

Model kuantum memandu desain perangkat keras dan algoritma kuantum; algoritma faktorisasi Shor mengancam sistem kriptografi kunci publik yang keamanannya bergantung pada kesulitan faktorisasi, memotivasi pengembangan kriptografi pasca-kuantum, sementara simulasi kuantum menjanjikan kemajuan dalam kimia dan ilmu material.

History

Feynman mengusulkan penggunaan sistem kuantum untuk mensimulasikan fisika pada tahun 1982, dan Deutsch memformalkan mesin Turing kuantum pada tahun 1985. Algoritma faktorisasi Shor tahun 1994 dan algoritma pencarian Grover tahun 1996 menunjukkan percepatan yang konkret, mengubah komputasi kuantum menjadi cabang utama teori kompleksitas dan pendorong upaya eksperimental.

Debates

Seberapa besar keuntungan kuantum, dan apakah itu dapat direalisasikan secara fisik dalam skala besar?

Komputer kuantum menghitung fungsi yang sama dengan komputer klasik, jadi pertanyaannya adalah efisiensi. Hubungan yang tepat antara BQP dan kelas klasik belum terpecahkan, dan apakah komputer kuantum toleran-kesalahan yang besar dapat dibangun meskipun ada dekoherensi tetap menjadi pertanyaan ilmiah dan rekayasa yang terbuka.

Key figures

• Richard Feynman
• David Deutsch
• Peter Shor
• Lov Grover

Seminal works

• nielsenChuang2010
• aroraBarak2009

Frequently asked questions

Apakah komputer kuantum menghitung hal-hal yang tidak bisa dilakukan komputer klasik?

Tidak. Komputer kuantum memecahkan kelas masalah yang sama persis dengan komputer klasik; perbedaannya adalah kecepatan. Untuk masalah tertentu, seperti memfaktorkan bilangan besar, model kuantum tampaknya jauh lebih cepat, tetapi tidak memperluas batas apa yang dapat dihitung secara prinsip.

Mengapa komputasi kuantum penting untuk kriptografi?

Algoritma Shor akan memungkinkan komputer kuantum besar memfaktorkan bilangan bulat besar dan menghitung logaritma diskrit secara efisien, memecahkan sistem kunci publik yang mengamankan sebagian besar komunikasi saat ini. Prospek ini telah mendorong pencarian skema pasca-kuantum berdasarkan masalah yang dianggap sulit bahkan untuk mesin kuantum.