Bagaimana saya menerapkan oracle kuantum dalam algoritma Deutsch?

Saya mencoba mensimulasikan algoritma Deutsch (kasus dasar dari algoritma Deutsch-Josza), dan saya tidak sepenuhnya yakin bagaimana saya akan menerapkan oracle kuantum yang diperlukan agar algoritma berfungsi, tanpa mengalahkan tujuan algoritma dan "mencari". apa fungsi yang diinput, dengan mengevaluasi fungsi.

Ada dua pertanyaan di sini. Yang pertama bertanya bagaimana Anda mungkin benar-benar menerapkan ini dalam kode, dan yang kedua bertanya apa gunanya jika Anda tahu oracle yang Anda lewati.

Penerapan

Mungkin cara terbaik adalah membuat fungsi IsBlackBoxConstantyang mengambil oracle sebagai input, kemudian menjalankan program Deutsch Oracle untuk menentukan apakah itu konstan. Anda dapat memilih oracle secara acak, jika Anda mau. Ini dia, diimplementasikan dalam Q #:

operation IsBlackBoxConstant(blackBox: ((Qubit, Qubit) => ())) : (Bool)
{
    body
    {
        mutable inputResult = Zero;
        mutable outputResult = Zero;

        // Allocate two qbits
        using (qbits = Qubit[2])
        {
            // Label qbits as inputs and outputs
            let input = qbits[0];
            let output = qbits[1];

            // Pre-processing
            X(input);
            X(output);
            H(input);
            H(output);

            // Send qbits into black box
            blackBox(input, output);

            // Post-processing
            H(input);
            H(output);

            // Measure both qbits
            set inputResult = M(input);
            set outputResult = M(output);

            // Clear qbits before release
            ResetAll(qbits);
        }

        // If input qbit is 1, then black box is constant; if 0, is variable
        return One == inputResult;
    }
}

Apa gunanya?

Kompleksitas kueri

Kompleksitas komputasi adalah bidang yang berkaitan dengan pengelompokan algoritma berdasarkan kuantitas sumber daya yang mereka konsumsi sebagai fungsi dari ukuran input. Sumber daya ini termasuk waktu (diukur dalam langkah / instruksi), memori, dan juga sesuatu yang disebut kompleksitas kueri . Kompleksitas kueri berkaitan dengan berapa kali suatu algoritma harus query fungsi oracle kotak hitam.

$n$$2^{n-1}$

$2^{n-1}$

Aplikasi di dunia nyata

Jika Anda bukan teoretikus kompleksitas, Anda mungkin tidak terlalu peduli tentang kompleksitas kueri dan malah ingin tahu mengapa masalah oracle Deutsch penting di dunia "tidak ada aturan" di mana Anda diizinkan untuk melihat ke dalam kotak hitam. Mencoba menganalisis masalah oracle sebagai masalah non-oracle penuh dengan kesulitan, dan saya tidak percaya ada yang memecahkan pertanyaan tentang algoritma klasik terbaik untuk masalah oracle Deutsch ketika Anda diizinkan untuk menganalisis sirkuit oracle. Anda mungkin berpikir - apa yang bisa dianalisis? Hanya ada empat kemungkinan sirkuit! Bahkan, ini jauh lebih rumit.

Jika kita melihat representasi paling sederhana dari Deutsch Oracle satu-bit, konstruksi gerbang adalah sebagai berikut:

$C_{1,0}$

$X_0C_{1,0}$

$\mathbb{I}_4$

$X_0$

Namun, ini bukan satu-satunya cara untuk menerapkan nubuat. Semua ini dapat ditulis ulang menggunakan ratusan, ribuan, bahkan jutaan gerbang logika! Yang penting adalah efek kumulatif gerbang logika ini setara dengan konstruksi sederhana di atas. Pertimbangkan penerapan alternatif Constant-1 berikut:

$H_0Z_0H_0$

Ternyata, untuk input apa pun yang pernah Anda berikan:

$H_0Z_0H_0|\psi\rangle = X_0|\psi\rangle$

$H_0Z_0H_0$$X_0$

$H_0Z_0H_0 = \begin{bmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & \frac{-1}{\sqrt{2}} \end{bmatrix} \begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix} \begin{bmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & \frac{-1}{\sqrt{2}} \end{bmatrix} = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} = X_0$

Jadi kita punya:

$(H_0(Z_0(H_0|\psi\rangle))) = (((H_0Z_0)H_0)|\psi\rangle) = X_0|\psi\rangle$

$H_0Z_0H_0$$X_0$

Penting untuk alasan historis & pedagogis

Terutama, masalah Oracle Deutsch penting karena alasan historis dan pedagogis. Ini adalah algoritma pertama yang diajarkan kepada siswa karena ini adalah yang paling sederhana, dan tampaknya menunjukkan peningkatan kuantum selama Anda tidak mengajukan terlalu banyak pertanyaan. Ini juga berfungsi sebagai titik peluncuran yang baik untuk mempelajari Masalah Periodisitas Simon dan kemudian Algoritma Shor.

Tidak ada cara untuk membangun oracle dengan cara yang tidak akan mengalahkan titik algoritma Deutsch - itu sebabnya itu adalah algoritma berbasis oracle.

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

$f(x)$$1 \leq x \leq N$$f(x)$$y$$f(x+y)=f(x)$$f(x)$

Jadi intinya adalah bahwa algoritma berbasis oracle membuktikan bahwa Anda bisa mendapatkan percepatan jika Anda memiliki masalah dengan struktur itu (yaitu di mana Anda hanya ingin mempelajari beberapa properti spesifik dari suatu fungsi), tetapi tidak memberi tahu Anda jika masalah seperti itu ada.

Jadi, jika Anda ingin menerapkan Deutsch, cara apa pun untuk melakukan oracle baik-baik saja - itu adalah algoritma "bukti-prinsip" dan tidak menghasilkan percepatan aktual pada masalah nyata (setidaknya tidak ada yang kita ketahui).

Anda memiliki dua contoh di halaman Pengalaman Q IBM tentang algoritme . Mereka menunjukkan contoh fungsi. Saya harap ini bisa menginspirasi Anda untuk simulasi Anda.

Saya tidak punya contoh untuk algoritme Deutsch, tetapi di sini dan di sini ada dua tutorial yang memandu Anda dalam mengimplementasikan algoritma Deutsch-Jozsa dan nubuat-nubuat yang digunakannya di Q #.

Gagasan untuk kedua algoritma ini adalah sama: Anda harus menyediakan oracle untuk algoritma sebagai operasi yang diterapkan di tempat lain. Dengan cara ini algoritma tidak tahu oracle mana yang diberikan dan tidak memiliki cara untuk "melihat" oracle selain dengan menyebutnya. Tutorial ini juga memiliki harness yang menghitung berapa kali oracle dipanggil, sehingga jika solusi Anda menyebutnya lebih dari sekali, ia gagal dalam tes.

Harus diakui, ini masih memiliki masalah yang sering dimiliki oleh algoritma oracle: manusia dapat melihat implementasi tes dan oracle yang diteruskan dan mencari tahu jawabannya dengan mencari tahu oracle mana yang diimplementasikan. Ini dapat dilawan dengan mengacak pilihan oracle, seperti yang disarankan DaftWullie.

Saya pikir ahelwerjawaban itu menyentuh beberapa cara yang kita pikirkan tentang kompleksitas algoritma. Namun - karena kita tidak benar-benar memiliki "ramalan" di dunia nyata yang ingin kita tanyakan, Anda mungkin bertanya-tanya mengapa kita akan khawatir tentang kerumitan permintaan, atau gagasan tentang ramalan sama sekali. Saya akan mencoba memberikan beberapa perspektif tentang ini, dan khususnya untuk menggambarkan bagaimana Anda mungkin mencoba memikirkan cara untuk membangun "oracle Deutsch – Josza" dengan cara yang Anda tidak merasa seolah-olah Anda selingkuh.

(Sebagai Norbert Schuch ditunjukkan, untuk masalah Deutsch yang merupakan kasus dasar dari Deutsch-Josza, tidak ada banyak ruang untuk wawasan, tapi saya berharap pertanyaan Anda tentang nubuat berlaku lebih umum juga. Itulah yang akan saya bicarakan di sini.)

Intuisi tentang nubuat

Konsep oracle adalah cara untuk memungkinkan diri kita menyederhanakan cara kita berbicara tentang masalah komputasi.

Aplikasi asli dari konsep oracle adalah mempertimbangkan secara hipotetis apa yang bisa kita lakukan jika kita bisa menyelesaikan masalah yang sulit, bahkan masalah yang mustahil, tanpa berkomitmen bagaimana kita bisa melakukannya bahkan secara prinsip. Tetapi dalam kompleksitas komputasi akhir-akhir ini - khususnya dalam perhitungan kuantum, misalnya  dalam kasus Deutsch-Josza, Bernstein-Vazirani, dan masalah oracle lainnya - situasinya berbeda: oracle menggambarkan fungsi yang merupakan dasar dari masalah. Fakta bahwa itu adalah 'oracle' adalah cara untuk menyusun bagaimana kita menggambarkan fungsi yang menjadi pusat masalah: bukan berarti kita tidak boleh merenungkan bagaimana fungsi dihitung, tetapi informasi ini tidak disediakan sebagai bagian masalah, dan bahwa kami tidak peduli dengan waktu atau kompleksitas lain yang terkait dengan fungsi itu.

Ketika kita mengambil pendekatan ini, kita sebenarnya dapat memperoleh jawaban yang terkait dengan pertanyaan yang sangat sulit dalam perhitungan. Misalnya, Anda mungkin tahu bahwa kita tidak tahu bagaimana untuk membuktikan baik P  ≠  NP atau P  =  NP , tetapi bahwa kita dapat menunjukkan bahwa ada nubuat Sebuah sehingga kita dapat menunjukkan bahwa P ^A  ≠  NP ^A . Apa yang dilakukan oracle A di sini adalah tidak membantu komputer (lebih tepatnya, mesin Turing deterministik atau mesin Turing nondeterministik) untuk menyelesaikan masalah - itu mewakili masalah yang harus dipecahkan oleh komputer. Fakta bahwa kita dapat menunjukkan dalam beberapa kasus bahwa P ^A ≠  NP ^A , tidak berarti bahwa P benar - benar berbeda dari NP : itu hanya berarti bahwa hanya menggunakan nondeterminisme benar-benar sumber daya yang signifikan untuk dimiliki model komputasi - ini memungkinkan Anda untuk menyelesaikan beberapa masalah secara efisien, dan tidak ada cara secara umum untuk mensimulasikan nondeterminisme secara efisien pada komputer deterministik. Jadi jika Anda ingin memecahkan masalah terkait dengan apa A melakukan komputasi, Anda benar-benar akan membutuhkan beberapa informasi tentang struktur fungsi apapun yang bisa efisien menghitung A .

Ini adalah salah satu hal utama tentang nubuat: mereka memungkinkan Anda untuk berbicara tentang cara model komputasi dapat atau tidak bisa menyelesaikan masalah, ketika Anda diberikan informasi terbatas tentang masalah tersebut.

Menggunakan algoritma oracle untuk menyelesaikan masalah non-oracle

Algoritme Deutsch-Josza, atau algoritma Bernstein-Vazirani, pada prinsipnya bukan algoritma yang dilakukan seseorang untuk kepentingan mereka sendiri. (Yah, tidak benar - benar - lihat Bagian berikutnya.) Mereka berdiri untuk cara yang Anda dapat memecahkan masalah . Masalah apa yang mereka pecahkan? Mereka memungkinkan Anda untuk menemukan fitur tertentu dari fungsi yang Anda minati - apakah itu konstan / seimbang, atau vektor apa yang terkait dalam beberapa fungsi linear skalar-dihargai pada vektor.

Fungsi apa yang Anda jalankan? - Anda menjalankannya pada fungsi apa pun yang Anda minati jawabannya.

Penjelasan tentang ini sebagai algoritma berbasis oracle tidak penting. Masalah oracle pada dasarnya memungkinkan Anda untuk mengetahui bahwa, dengan komputer kuantum yang ideal, Anda dapat menyelesaikan masalah bahkan jika Anda tahu sedikit tentang fungsi tersebut , asalkan Anda benar-benar dapat mengevaluasi fungsi secara efisien dalam praktek. Untuk benar-benar mengevaluasi fungsi seperti itu, tentu saja Anda akan memerlukan beberapa deskripsi tentang bagaimana melakukannya, sehingga Anda memiliki lebih banyak informasi daripada di pengaturan oracle; tapi itu tidak mencegah Anda menggunakan algoritma yang sama.

Apa yang terjadi ketika Anda memiliki lebih banyak informasi daripada di pengaturan oracle, adalah bahwa tiba-tiba ada cara lain yang mungkin dapat Anda selesaikan. Secara khusus, mungkin menjadi mungkin untuk menyelesaikan masalah secara efisien secara klasik . (Ini adalah pengamatan yang sama dengan P ^A  ≠  NP ^A : ini membuktikan bahwa ada masalah yang ada di NP , yang mana algoritma deterministik efisien setidaknya akan memerlukan informasi struktural aktual untuk dapat menyelesaikan - sehingga ketika Anda memberikan deskripsi dari fungsi yang dapat dihitung secara efisien daripada 'oracle', ada kemungkinan bahwa masalahnya akan munculP. ) Ini berarti bahwa algoritma kuantum mungkin tidak memiliki keunggulan yang sama atas algoritma klasik dalam memecahkan masalah tertentu yang Anda sajikan - dan pada kenyataannya mungkin bahwa pendekatan klasik lebih baik (terutama dengan perangkat yang kami miliki saat ini).

Pada akhirnya, hanya karena Anda memiliki algoritma kuantum untuk menyelesaikan sesuatu, tidak berarti bahwa itu selalu cara terbaik untuk menyelesaikan sesuatu. Ini tentu saja benar untuk algoritma Deutsch-Josza: bahkan dalam pengaturan oracle, menggunakan keacakan hampir sama baiknya, dan itu jauh lebih baik mengingat bahwa kita belum memiliki komputer kuantum besar yang dapat diandalkan! Tapi sekali lagi ...

"Menerapkan" oracle

Tujuan penerapan algoritma Deutsch-Josza sama dengan menerapkan " Hello, World! " - bukan untuk memecahkan masalah yang belum terpecahkan, tetapi untuk berlatih menggunakan alat yang Anda harapkan akan berguna untuk melakukan hal-hal lain.

Untuk mempraktikkan pengkodean, Anda harus merasa benar-benar santai dan nyaman dengan gagasan menerapkan oracle, dan dengan gagasan komputer yang mengevaluasi oracle. Pada prinsipnya, inilah yang ingin Anda lakukan. Bahkan jika Anda menggunakan emulator klasik, di mana komputer klasik sebenarnya mengevaluasi semua cabang superposisi dan secara eksplisit menemukan jawaban untuk masalah untuk berpura-pura bahwa itu adalah komputer kuantum yang bertindak dengan cara yang sedikit lebih bundaran, jadi baik itu - Anda sedang berlatih bagaimana menggunakan alat yang mungkin berguna untuk hal-hal lain, dan yang suatu hari tidak akan berjalan di komputer klasik.

Jadi bagaimana Anda sebaiknya menerapkan oracle Anda?

(i) Jika Anda benar-benar berkomitmen pada gagasan bahwa Anda baru saja berlatih, Anda tidak perlu berpura-pura melakukan sesuatu yang ajaib. Datang dengan cara apa pun untuk menerapkan fungsi oracle, bahkan jika itu jelas bagi pengamat kasual apakah hasilnya konstan atau seimbang. Anda hanya mencoba berlatih mewujudkan suatu algoritma - jangan khawatir bahwa seseorang akan menuduh Anda sebagai penipu, bahwa Anda berpura-pura menyembuhkan kanker tetapi sebenarnya bermain dengan Lego. Anda tidak pernah yang berpura-pura untuk menyembuhkan kanker, dan Anda sedang bermain dengan Lego oleh pilihan yang disengaja. Rangkul itu dan lakukan saja.

$f(x) = g(x,r)$$r$$g(x,r)$$x$$r$, dan di mana tidak jelas bagaimana menyelesaikannya secara klasik, tidak sepele.

• $g(x,r) = x \cdot r$$x,r \in \{0,1\}^n$$g(x,r)$$f(x)$$f(x)$$r \ne 0$

• Dapat dibayangkan bahwa konstruksi di atas dapat dielaborasi / dikaburkan sedikit, untuk mendapatkan konstruksi yang dijamin untuk mengevaluasi baik fungsi konstan atau fungsi seimbang, dan di mana mana dari dua ini terjadi tidak jelas atau bahkan sulit - tetapi saya bisa ' t pikirkan bagaimana, saat ini.

Ingatlah bahwa ini sebenarnya sangat sulit dilakukan - tetapi jika Anda dapat melihat cara untuk melakukannya, itu bisa sangat berharga: Bravyi, Gossett, dan Koening melakukan sesuatu seperti ini untuk masalah Bernstein-Vazirani, dan itu memungkinkan mereka untuk menunjukkan pemisahan kecil tapi tanpa syarat antara kompleksitas kuantum dan klasik, yang merupakan salah satu hal yang lebih menarik terjadi dalam kompleksitas kuantum dalam beberapa tahun terakhir.

TL; DR

• Jangan memusingkan fakta bahwa Anda sedang 'mengevaluasi' oracle.

• Jika Anda memikirkan sesuatu, hanya khawatir bahwa deskripsi aktual dari fungsi tersebut memungkinkan untuk menyelesaikan masalah yang sama dengan mudah tanpa komputer kuantum.

• Jika motivasi Anda hanya untuk berlatih dengan pemrograman kuantum, jangan khawatir tentang itu. Simpan kekhawatiran Anda untuk masalah yang lebih berharga, seperti pemanasan global. Sementara itu, nikmati bermain dengan Lego saat Anda membangun sesuatu yang lebih.