Apa model komputasi kuantum?

32

Saya kadang-kadang mendengar orang berbicara tentang algoritma kuantum dan tentang status dan kemampuan untuk mempertimbangkan berbagai kemungkinan sekaligus, tetapi saya tidak pernah berhasil membuat seseorang menjelaskan model komputasi di balik ini. Untuk lebih jelasnya, saya tidak bertanya tentang bagaimana komputer kuantum dibangun secara fisik, tetapi bagaimana cara melihatnya dari sudut pandang komputasi.

Casebash
sumber
8
Harap perbaiki ejaan dalam judul pertanyaan.
Shane
Beberapa sejarah dan referensi ada di sini en.wikipedia.org/wiki/Universal_quantum_simulator
Radu GRIGore
Catatan mod: menggabungkan pertanyaan duplikat persis tertutup dengan pertanyaan ini dan menghapus komentar dari duplikat yang tidak relevan lagi.
Kaveh

Jawaban:

24

Saya akan menggemakan rekomendasi Martin Schwartz tentang Nielsen & Chaung sebagai referensi standar; ada banyak lainnya juga.

Penelitian di lapangan lebih suka untuk mempertimbangkan keluarga seragam dari sirkuit kuantum, yang (ironisnya) diarahkan jaringan asiklik yang menggambarkan bagaimana keadaan satu atau lebih register berubah dengan waktu, dengan cara yang mirip dengan sirkuit boolean klasik. Jika Anda ingin mempelajari lebih lanjut, saya sarankan belajar dalam hal model ini.

Saya ingin memberikan beberapa jawaban kualitatif untuk melengkapi tanggapan Martin.

  1. Perhitungan kuantum sebenarnya tidak mempertimbangkan "kemungkinan ganda sekaligus" --- atau lebih tepatnya, apakah Anda menganggapnya mempertimbangkan beberapa kemungkinan sekaligus adalah masalah pilihan interpretasi mekanika kuantum Anda , yaitu pilihan filosofis yang tidak memiliki bergantung pada kemampuan atau prediksi model komputasi. ("Mempertimbangkan berbagai kemungkinan sekaligus" sesuai dengan "banyak interpretasi dunia" dari QM.)

    Paling tidak, dapat dikatakan bahwa komputer kuantum mempertimbangkan banyak kemungkinan sekaligus hanya sejauh komputasi acak menggunakan koin- membalik mempertimbangkan beberapa kemungkinan sekaligus. Hal ini karena:

  2. Keadaan kuantum adalah generalisasi dari distribusi probabilitas "yang biasa" --- dengan beberapa perbedaan sederhana namun penting. Distribusi probabilitas dapat direpresentasikan sebagai vektor nyata non-negatif yang entri-entrinya berjumlah 1: yaitu, vektor satuan dalam norma ℓ 1 . Komputasi probabilistik harus memetakan ℓ 1- vektor satuan ke vektor lain yang demikian, dan semuanya dijelaskan oleh peta stokastik. Seseorang dapat menggambarkan perhitungan kuantum dengan cara yang sama, kecuali menggunakan ℓ 2 -unit vektor lebih dari ℂ (tidak terbatas menjadi nyata atau non-negatif); transformasi dilakukan oleh peta-peta yang mempertahankan orm 2 -norm, yaitu operasi kesatuan.

    Perbedaan ini tidak sepele, tentu saja, juga tidak menjelaskan namun apa koefisien dari vektor keadaan kuantum berarti . Tetapi mungkin membantu menjelaskan apa yang sedang terjadi dengan ruang Hilbert dan produk tensor dalam perhitungan kuantum: untuk menjelaskan, hal-hal yang persis sama seperti yang terjadi dalam perhitungan probabilistik. Ruang konfigurasi bit acak adalah vektor dalam ℝ + 2 (di mana ℝ + adalah real non-negatif); tetapi karena bit acak dapat dikorelasikan, kami menggabungkan ruang konfigurasi dari satu atau lebih bit acak dengan mengambil produk tensor. Jadi ruang konfigurasi dari dua bit acak adalah ℝ + 2  ⊗ ℝ + 2  ≅ ℝ + 4 , atau ruang distribusi probabilitas sepenuhnya-umum atas empat string dua-bit yang berbeda. Operasi A pada bit acak pertama yang tidak bekerja pada bit kedua diwakili oleh operator A  ⊗  I 2  . Dan seterusnya. Konstruksi yang sama berlaku untuk bit kuantum; dan kita dapat mempertimbangkan register kuantum di atas set elemen yang dapat dibedakan dengan cara yang sama kita mempertimbangkan distribusi probabilitas atas set tersebut, lagi-lagi menggunakan ℓ 2 -norm vektor lebih dari ℂ.

    Deskripsi ini sebenarnya menggambarkan keadaan kuantum "murni" --- yang pada prinsipnya Anda dapat mentransformasikannya dalam cara penyimpanan informasi menjadi distribusi delta melalui bit-string 00 ... 0 (atau lebih tepatnya, ke nyatakan secara arbitrer dekat dengan ini dalam norma ℓ 2 ). Di atas quantum-randomness (yang saya belum sebutkan secara eksplisit), Anda dapat mempertimbangkan vanilla-convexity-randomness yang sesuai dengan campuran probabilistik status quantum: ini diwakili oleh operator densitas , yang dapat diwakili oleh matriks pasti positif. dengan jejak 1 (lagi-lagi menggeneralisasi distribusi probabilitas "klasik", yang dapat diwakili oleh kasus khusus dari matriks diagonal positif dengan jejak 1).

    Yang penting tentang ini adalah bahwa, sementara keadaan kuantum sering digambarkan sebagai "besar secara eksponensial", ini karena mereka biasanya digambarkan menggunakan struktur matematika yang sama dengan distribusi probabilitas; mengapa distribusi probabilitas tidak digambarkan sebagai "besar secara eksponensial" dengan cara yang sama tidak jelas (tetapi pada akhirnya tidak penting). Kesulitan simulasi negara kuantum datang dari kenyataan ini, bersama-sama dengan fakta bahwa koefisien kompleks ℓ ini 2 -distributions (atau kompleks off-diagonal segi operator kepadatan, jika Anda suka) dapat membatalkan dengan cara yang probabilitas tidak bisa , membuat estimasi mereka lebih sulit.

  3. Keterikatan hanyalah bentuk lain dari korelasi. Untuk perhitungan probabilistik pada mis. String boolean, satu-satunya keadaan "murni" (yang dapat dipetakan oleh transformasi pengawet informasi ke distribusi puncak-delta pada 000 ... 0) adalah "dasar standar" dari distribusi puncak-delta pada string boolean yang berbeda. Jadi, dasar of + 2 n inidibedakan. Tetapi tidak ada dasar yang dibedakan dalam mekanika kuantum, sejauh yang dapat kami katakan --- ini adalah yang paling jelas untuk bit kuantum (lihat putaran 1/2 partikel, jika Anda ingin tahu mengapa). Sebagai konsekuensinya, ada lebih banyak transformasi pengawet informasi dari sekedar permutasi: kelompok kontinyu, pada kenyataannya. Ini memungkinkan calon komputer kuantum untuk mengubah keadaan dengan cara yang tidak mungkin untuk komputer probabilistik, mungkin mendapatkan keuntungan asimptotik daripada mereka.

    Tapi bagaimana dengan keterjeratan, yang banyak orang temukan misterius, dan mengklaim sebagai penyebab percepatan komputer kuantum di atas klasik? "Keterikatan" di sini benar-benar hanya suatu bentuk korelasi: sama seperti dua variabel acak dikorelasikan jika distribusinya merupakan kombinasi cembung lebih dari satu distribusi produk (dengan marjinal yang berbeda pada setiap variabel), dua "variabel kuantum" dilibatkan jika distribusi adalah kombinasi linear (dengan unit ℓ 2-norm) dari dua distribusi produk yang valid; itu adalah konsep yang sama di bawah norma yang berbeda, dan memainkan peran yang sama dalam tugas komunikasi. (Misalnya: "teleportasi kuantum" dalam komunikasi kuantum berhubungan dengan penyandian dan pendekodean pesan menggunakan pad sekali waktu secara klasik.) Ini adalah bentuk korelasi yang lebih umum daripada hanya bit berkorelasi klasik; tetapi satu-satunya cara untuk menunjukkan ini adalah bahwa korelasi yang dikodekan dalam keadaan terjerat berlaku untuk lebih dari satu dasar istimewa . Dalam cara berbicara, keterikatan adalah konsekuensi dari tidak adanya dasar yang istimewa.

    Orang-orang suka menyebut keterjeratan sebagai elemen kunci perhitungan kuantum, tetapi ini sepertinya tidak menahan air: ada hasil yang menunjukkan bahwaketerjeratan tidak penting secara kuantitatif untuk algoritma Shor untuk faktor bilangan bulat besar, dan bahwa memang sistem kuantum dapat memiliki terlalu banyak keterjeratan untuk berguna untuk perhitungan. Bahkan, di mana pun saya menyadari bahwa keterikatan memainkan peran penting dalam protokol kuantum pada dasarnya adalah komunikasi (di mana korelasi diharapkan memainkan peran penting untuk protokol klasik).

Pada titik ini, saya mulai mengarungi ranah pendapat pribadi, jadi saya akan berhenti di sini. Tapi mudah-mudahan, pernyataan ini dapat menghilangkan misteri dari apa yang tidak jelas tentang perhitungan kuantum dan bagaimana itu dijelaskan.

Niel de Beaudrap
sumber
1
Saya harus mengakui, saya tidak setuju dengan Anda tentang pertanyaan keterikatan. Operasi pada kondisi produk murni dapat disimulasikan secara efisien. Makalah "terlalu terjerat untuk menghitung" agak menyesatkan. Makalah ini benar-benar tentang sumber daya untuk perhitungan berbasis pengukuran, dan MBQC adalah semua tentang peringkat schmidt, bukan keterjeratan per se.
Joe Fitzsimons
1
Anda tentu saja benar bahwa jika suatu komputasi tetap berada dalam bermacam-macam status produk murni, itu (secara efisien) dapat disimulasikan secara klasik; tetapi apakah itu berarti bahwa keterikatan membuat komputer kuantum "lebih cepat" (mengakui lintasan komputasi yang lebih pendek), dibandingkan dengan hanya "sulit untuk diikuti" (memiliki lintasan komputasi yang 'dikaburkan' komputasi)? Posisi saya adalah bahwa jika ada percepatan kuantum, maka belitan adalah bulu buangan, bukan bahan bakar roket.
Niel de Beaudrap
Keterjeratan itu lucu, karena itu tergantung pada dimensi sistem lokal Anda. Saya pikir kekuatan sebenarnya hanya berasal dari keberadaan superposisi, dan karenanya amplitudo kompleks. Keterikatan tampaknya merupakan konsekuensi dari ini. Ada pengkodean yang bagus yang memungkinkan untuk melakukan perhitungan kuantum universal dengan amplitudo murni nyata, yang saya pikir berjalan menuju karakterisasi ini. Algoritma saat ini semuanya memanfaatkan beberapa bentuk efek interferensi.
Joe Fitzsimons
Saya sebagian setuju dengan Joe pada titik interferensi, namun masalah untuk berbicara secara ketat tentang titik ini adalah apa yang ada (intervensi yang cukup) langkah-langkah interferensi yang ada di pasar ? Apakah Anda tahu karya-karya dalam arah ini? Satu-satunya contoh yang muncul di benak saya adalah yang satu ini (namun saya belum membacanya secara mendetail).
Juan Bermejo Vega
@JuanBermejoVega: gangguan tampaknya hanya menjadi akibat dari kenyataan bahwa ada transformasi pengawet informasi yang tidak mempertahankan status dasar standar. Satu-satunya alternatif nyata untuk gangguan adalah kehilangan informasi, seperti dalam probabilitas klasik. Maka yang kita miliki hanyalah transformasi yang dapat dibalik yang tidak mempertahankan basis standar; narasi gangguan, seproduktif ketika berbicara tentang propagasi di ruang angkasa, hanyalah sebuah cara untuk menggambarkan seperti apa rasanya jika Anda terus mencoba mengurai non-pelestarian ini dalam hal basis standar.
Niel de Beaudrap
12

Lance Fortnow menulis sebuah artikel yang menjelaskan komputasi kuantum tanpa menggunakan mekanika kuantum. Pada dasarnya ia menyajikannya dengan cara yang sama dengan yang dilakukan komputasi probabilistik. Saya menduga ini mungkin titik awal yang lebih cepat daripada sesuatu seperti Nielson dan Chuang (meskipun saya setuju bahwa jika Anda ingin benar-benar masuk ke ini maka Nielson dan Chung pasti harus ada dalam daftar bacaan Anda).

L. Fortnow. Pandangan satu kompleksitas teori tentang komputasi kuantum. Theoretical Computer Science, 292 (3): 597-610, 2003. Edisi khusus makalah disajikan pada lokakarya kedua tentang Algoritma dalam Pemrosesan Informasi Quantum.

Joshua Grochow
sumber
11

Nah, teks standar yang digunakan adalah Quantum Computation dan Quantum Information oleh Nielsen dan Chuang. Ini mencakup berbagai aspek pada tingkat yang wajar. Hampir setiap orang yang bekerja di ladang memiliki salinannya di rak mereka. Buku Kaye, Laflamme dan Mosca juga bagus, tetapi mencakup lebih sedikit (meskipun ada sedikit lebih fokus pada algoritma).

Meskipun sangat mungkin untuk menjelaskan komputasi kuantum tanpa masuk ke banyak mekanika kuantum, saya tidak berpikir bahwa ini selalu merupakan cara yang baik untuk mendekati pembelajaran komputasi kuantum. Ada cukup banyak intuisi yang dapat diperoleh dengan memiliki rasa untuk teori fisik, karena banyak model yang lebih baru dari perhitungan kuantum (yaitu model adiabatik, topologi dan berbasis pengukuran) lebih termotivasi secara fisik daripada mesin Turing kuantum atau model rangkaian.

Yang mengatakan, mekanika kuantum yang diperlukan untuk memahami perhitungan kuantum cukup sederhana, dan tercakup dengan cukup baik di Nielsen dan Chuang. Sungguh, Anda bisa merasakannya dengan baik membaca bab yang relevan dan mencoba latihan. Ini adalah jenis hal yang bisa Anda pahami dengan beberapa hari kerja. Saran saya, bagaimanapun, adalah jangan menggunakan teks intro standar ke mekanika kuantum. Pendekatan yang diambil untuk memodelkan atom, molekul, dan material menggunakan sistem dimensi tak terbatas, dan membutuhkan banyak usaha lebih banyak untuk mencapai puncaknya. Untuk informasi kuantum itu adalah awal yang jauh lebih baik untuk melihat sistem dimensi yang terbatas. Juga, secara tradisional, masalah yang dipelajari oleh fisikawan cenderung berputar di sekitar menemukan keadaan dasar dan perilaku kondisi mapan, dan inilah yang akan dibahas oleh sebagian besar teks pengantar (dimulai dengan persamaan gelombang Schroedinger yang tidak tergantung waktu). Untuk komputasi kuantum, kita cenderung lebih tertarik pada evolusi waktu sistem, dan ini ditangani dengan jauh lebih ringkas dalam teks-teks komputasi kuantum daripada dalam teks intro mekanika kuantum umum (yang menurut definisi lebih umum).

Joe Fitzsimons
sumber
8

BQP

|ϕH2H2...H2|ψUsqkamuSebuahre

Untuk pengantar yang lebih mendalam, silakan lihat buku teks standar Nielsen dan Chuang.

Martin Schwarz
sumber
Seperti halnya model yang disebutkan Martin, ada beberapa yang lain: komputasi kuantum berbasis adiabatik, dan topologi.
Joe Fitzsimons
5

Anda dapat memiliki pengantar yang bagus dalam artikel "Pengantar Komputasi Quantum untuk Non-Fisikawan" oleh Eleanor Rieffel dan Wolfgang Polak. Ini mungkin agak tua, namun masih merupakan pengantar yang bagus, singkat, dan lengkap tentang topik ini: http://arxiv.org/abs/quant-ph/9809016

Artikel lain, yang jauh lebih diringkas adalah "Perhitungan Kuantum yang dijelaskan oleh Pablo Arrighi kepada Ibu saya" di http://arxiv.org/abs/quant-ph/0305045

Alejandro DC
sumber
1
Rieffel dan Polak tampaknya telah menghasilkan sebuah buku juga: Quantum Computing: A Gentle Introduction
Logan Mayfield
4

Anda mungkin sudah mengetahui hal ini, tetapi di blognya , Scott Aaronson memiliki tautan ke sejumlah kuliahnya tentang komputasi kuantum, serta tautan ke QC primer oleh orang lain (cukup gulir ke bawah bilah sisi kanan untuk menemukan ini) .

Jika Anda ingin pengantar sepanjang buku, tetapi sesuatu yang lebih lembut daripada teks seperti Nielsen dan Chuang, saya akan merekomendasikan Quantum Computing for Computer Scientists oleh Yanofsky dan Mannucci. Mereka menghabiskan cukup banyak waktu meninjau prasyarat matematika sebelum menyelam ke QC itu sendiri. Jika Anda memiliki latar belakang matematika yang kuat, buku ini mungkin tampak terlalu mendasar, tetapi menurut saya itu cukup berguna.

Kurt
sumber
4

Secara umum, saya akan menyarankan saran Joe. Tetapi untuk intro cepat, saya akan menempatkan teks Lance Fortnow dan Stephen Fenner di daftar bacaan ilmuwan komputer menjadi kuantum.

Martin Schwarz
sumber
3

Jika Anda cukup maju, Anda mungkin mulai dengan survei de Wolf-Drucker tentang metode kuantum untuk masalah klasik. Ini adalah cara yang baik untuk memahami teknik kuantum sebelum Anda sampai ke masalah kuantum .

Suresh Venkat
sumber
2

Saya tidak berpikir Anda perlu belajar mekanika kuantum. Namun itu tergantung pada bidang apa yang ingin Anda kerjakan. Ada bidang-bidang yang benar-benar membutuhkan pengetahuan tentang mekanika kuantum, namun sebagai contoh bidang yang saya kerjakan, teori jenis dan kalkulus lambda, saya tidak membutuhkannya, saya bisa melakukannya hanya dengan mengetahui beberapa model komputasi untuknya.

Alejandro DC
sumber
2

Selain teks standarnya dengan Chuang, Michael Nielsen memiliki serangkaian kuliah video di Youtube yang disebut Quantum Computing for the Determined yang sejauh ini memberikan tinjauan umum tentang model komputasi. Video-videonya sangat ditonton oleh siapa pun yang sedikit memahami ilmu komputer dan aljabar linier.

Maks
sumber