Algoritma sederhana untuk secara intuitif menunjukkan kecepatan kuantum?

8

Apa algoritma paling sederhana (seperti algoritma Deutsch dan Algoritma Grover ) untuk secara intuitif menunjukkan kecepatan kuantum? Dan dapatkah algoritma ini dijelaskan secara intuitif?

Idealnya ini juga akan menggambarkan dengan jelas bagaimana interferensi kuantum digunakan, dan mengapa tidak mungkin atau berguna hanya menggunakan interferensi gelombang klasik .

Steven Sagona
sumber
seperti apa percepatan (polinomial vs eksponensial), dan keuntungan apa (tanpa syarat vs orkular)?
glS
Tidak masalah, asal jelas. Percepatan eksponensial mungkin menyenangkan untuk dilihat.
Steven Sagona
Contoh paling sederhana juga akan bekerja dengan gelombang klasik. Faktanya, semua contoh, kecuali bahwa gelombang klasik dapat (dan harus) mengambil banyak jalur secara eksponensial dalam jumlah qubit yang terlibat.
Norbert Schuch

Jawaban:

6

Saya ingin menyarankan bahwa penemuan periode (sebuah subrutin, jika Anda suka, dari algoritma Shor yang terkenal) menunjukkan kecepatan-eksponensial yang sangat intuitif: harus jelas secara intuitif bahwa ada sesuatu dalam urutan (akar kuadrat dari ketidakpastian). Δhal ) dari periode hal dari evaluasi fungsi diperlukan secara klasik untuk menemukan periode hal tidak diketahui dari suatu fungsi yang dijamin secara periodik dalam nilai input integernya. Aku sudah sengaja menempatkan tanda kurung sehingga konten mereka akan intuitif untuk orang-orang yang telah tertanam paradoks ulang tahun lagi, untuk menunjukkan percepatan superpolynomial, itu sudah cukup untuk secara intuitif memahami bahwa itu adalah suatu tempat di dekat Δhal , jawaban yang benarΔhal , atau polinomialnya dan bukan sesuatu seperti jumlah digithal,HAI(catatanhal).

Algoritma kuantum untuk penemuan periode, seperti yang digunakan oleh algoritma Shor, hanya mengambil transformasi kuantum Fourier dari fungsi periodik yang diterapkan pada superposisi yang sama dari semua keadaan. Secara alami, hanya kelipatan bilangan bulat periode yang kemudian dapat memiliki amplitudo probabilitas nol, sehingga melakukan ini (biasanya) dua kali akan memungkinkan Anda untuk dengan cepat mengekstrak faktor umum sebagai penyebut umum terbesar. Tetapi transformasi Fourier Fourum secara sepele dapat diterapkan dengan rotasi terkontrol HAI(catatanhal) (satu per setiap bit input).

Speedup intuitif terbesar jelas terjadi jika Anda membuat evaluasi fungsi sangat mahal: Algoritma kuantum hanya memerlukan evaluasi (tunggal) yang konstan! Tetapi bahkan jika Anda mendapatkan gain karena Anda memiliki algoritma yang berjalan, dengan asumsi evaluasi fungsi adalah waktu yang konstan, dalam HAI(catatanhal) daripada di HAI(Δhal)yang, jika Anda tidak tahu periode yang benarhalpada dasarnya adalahHAI(hal).

piramida
sumber
4

Kesulitan dengan pertanyaan adalah kata intuitif . Intuisi pada dasarnya mencerminkan pemahaman kita tentang dunia di sekitar kita, yang digambarkan oleh fisika klasik. Mekanika kuantum adalah rezim di mana intuisi kita rusak karena fungsinya sangat berbeda dari dunia pengalaman kita sehari-hari. Seperti yang dikatakan Terry Pratchett:

Sangat sulit untuk berbicara kuantum menggunakan bahasa yang awalnya dirancang untuk memberi tahu monyet lain di mana buah matang.

Perbedaan itulah yang kami gunakan untuk mendapatkan kecepatan komputasi.

Ada urutan algoritma standar yang sebagian besar teks komputasi kuantum maju melalui: algoritma Deutsch , Deutsch-Jozsa , Simon's / Bernstein-Vazirani. Ini dipilih karena mereka yang paling mudah dimengerti. Mereka semua secara luas memiliki struktur yang sama, tetapi meningkatkan kompleksitas, dengan keuntungan yang sesuai dalam kecepatan komputasi (dengan Simon memberikan kecepatan eksponensial). Anda tidak akan memahaminya secara intuitif. Anda harus mengerjakan matematika. Saya pikir yang paling dekat yang akan Anda datang adalah melalui penjelasan berikut dari algoritma Deutsch:

f(x)f(0)=f(1)f(0)f(1)f(0)f(1)

DaftWullie
sumber
2
"Kesulitan dengan pertanyaan adalah kata intuitif. Intuisi pada dasarnya mencerminkan pemahaman kita tentang dunia di sekitar kita, yang dijelaskan oleh fisika klasik." Kata ini biasa digunakan dalam matematika, dan seringkali tidak berarti "analog dengan fisika klasik. " Yang saya maksud (dan sering dimaksudkan) dengan intuisi adalah memiliki / memahami / tentang suatu mekanisme dalam suatu kerangka kerja. Sangat mudah untuk mengajarkan seseorang untuk memasukkan formula untuk mendapatkan jawaban, tetapi membuat mereka untuk secara mendasar / memahami / kerangka kerja dan logika adalah tentang definisi intuisi standar ini.
Steven Sagona
1
@StevenSagona "memiliki pemahaman tentang mekanisme dalam suatu kerangka kerja". Ya saya setuju. Jika Anda mengetahui beberapa mekanisme dalam suatu kerangka kerja, Anda dapat memahami yang baru tanpa menyelesaikan semua detail karena Anda memiliki konteks, yang disediakan oleh pengetahuan yang ada. Dan jika Anda memahami sesuatu, Anda harus bisa, dengan beberapa pekerjaan, untuk merekonstruksi detail matematika. Tetapi Anda tidak dapat memahami mekanisme pertama dalam kerangka kerja yang sama sekali baru secara intuitif. Banyak orang yang tertarik tetapi tidak berpengalaman mencoba melakukan ini, misalnya melalui analog klasik, dan mereka gagal, tetapi mungkin percaya mereka berhasil.
DaftWullie
2

Ada contoh yang bagus dalam kuliah Microsoft . Misalkan Anda memiliki kotak hitam klasik dengan 1 input dan 1 output. Berapa banyak pertanyaan yang Anda butuhkan untuk menentukan apakah outputnya konstan atau variabel? Jelas Anda membutuhkan 2 pertanyaan; pertama Anda memasukkan 0, kedua Anda memasukkan 1; jika kedua output identik Anda memiliki konstanta, jika tidak variabel. Ternyata setelah Anda mengonversi kotak hitam klasik menjadi kotak hitam kuantum, Anda dapat membangun sirkuit yang hanya membutuhkan satu permintaan (kuliah menjelaskan bagaimana melakukannya).

kludg
sumber
3
Atau dikenal sebagai algoritma Deutsch.
DaftWullie
1
Jika Anda tertarik untuk mempelajari lebih lanjut tentang masalah Deutsch-Jozsa, saya akan merekomendasikan untuk melihat Quantum Katas . Kata Deutsch – Jozsa membahas konsep-konsep yang diperlukan sebagai serangkaian latihan mandiri, dan dapat menjadi cara yang rapi untuk belajar.
Chris Granade
Perhatikan bahwa ini hanya memberikan percepatan kuantum jika Anda menginginkan jawaban dengan pasti. Jika Anda ingin jawabannya dengan pasti, diperlukan sejumlah pertanyaan konstan, bahkan jika ukuran masalahnya meningkat (seperti halnya dengan Deutsch-Jozsa)
nippon