Algoritma Grover dan hubungannya dengan kelas kompleksitas?

12

Saya bingung tentang algoritma Grover dan hubungannya dengan kelas kompleksitas.

Algoritma Grover menemukan dan elemen dalam database N = 2 n (sedemikian sehingga f ( k ) = 1 ) elemen dengan kN=2nf(k)=1 panggilan ke oracle.

N=2n/2

Jadi kami memiliki masalah berikut:

Masalah: Temukan dalam basis data sehingga f ( k ) = 1kf(k)=1

Sekarang saya sadar bahwa ini bukan masalah keputusan dan dengan demikian definisi normal kita tentang kompleksitas kelas , NP dll tidak benar-benar berlaku. Tapi saya ingin tahu bagaimana kita akan mendefinisikan kelas kompleksitas dalam kasus seperti itu - dan cuaca itu dilakukan sehubungan dengan N atau n ?PNPNn

Selanjutnya algoritma Grover dapat digunakan sebagai subrutin. Saya telah membaca di beberapa tempat bahwa algoritma Grover tidak mengubah kelas kompleksitas masalah - apakah ada cara heuristik untuk melihat ini.

Spagettifikasi kuantum
sumber
Pertimbangkan \text{}untuk menulis nama-nama kelas kompleksitas. Misalnya \text{NP}atau\text{BQP}
Sanchayan Dutta
1
Saya tidak yakin apa yang Anda tanyakan di sini. Algoritma tidak dapat menjadi anggota kelas kompleksitas, karena kelas kompleksitas mengandung masalah komputasi. Apakah Anda bertanya apakah masalah yang dinyatakan dalam pertanyaan tersebut terkandung dalam kelas kompleksitas 'diketahui' atau lengkap untuknya? Apakah Anda bertanya apakah 'penemuan' algoritma Grover mengarah ke teorema tentang hubungan antara kelas kompleksitas yang diketahui? Mohon klarifikasi.
Kadal diskrit

Jawaban:

6

Ringkasan

  • Ada teori kompleksitas masalah pencarian (juga dikenal sebagai masalah hubungan). Teori ini mencakup kelas yang disebut FP , FNP , dan FBQP yang secara efektif menyelesaikan masalah pencarian dengan berbagai jenis sumber daya.
  • Dari masalah pencarian, Anda juga dapat menentukan masalah keputusan, yang memungkinkan Anda untuk menghubungkan masalah pencarian ke kelas P , NP , dan BQP yang biasa .
  • Apakah Anda mempertimbangkan versi pencarian dari versi keputusan dari masalah, cara Anda mempertimbangkan input untuk masalah Pencarian Tidak Terstruktur akan menentukan batas atas yang dapat Anda tambahkan pada kompleksitasnya.

Kompleksitas masalah hubungan

Seperti yang Anda perhatikan, masalah Grover memecahkan masalah pencarian , yang dalam literatur kompleksitas kadang-kadang juga dikenal sebagai masalah hubungan . Yaitu, itu adalah masalah dari jenis berikut:

Struktur masalah pencarian umum.
Diberikan input dan hubungan biner R , temukan y sedemikian rupa sehingga R ( x , y ) dipegang.xRyR(x,y)

Kelas kompleksitas FP dan FNP didefinisikan dalam hal masalah tersebut, di mana khususnya tertarik pada kasus di mana memiliki panjang paling banyak fungsi polinomial dari panjang x , dan di mana hubungan R ( x , y ) dapat dengan sendirinya dihitung dalam jumlah waktu yang dibatasi oleh beberapa polinomial dengan panjang ( x , y ) .yxR(x,y)(x,y)

Secara khusus: contoh masalah 'pencarian basis data' yang biasanya diterapkan oleh Pencarian Grover dapat dijelaskan sebagai berikut.

Pencarian Tidak Terstruktur.
Diberikan input oracle sedemikian rupa sehingga O | a | b = | a | b f ( a ) untuk beberapa fungsi f : { 0 , 1 } m{ 0 , 1 } , temukan y sedemikian rupa sehingga O | y | 0 = | y | 1O:H2m+1H2m+1O|a|b=|a|bf(a)f:{0,1}m{0,1}y .O|y|0=|y|1

Di sini, oracle itu sendiri adalah input untuk masalah: ia memainkan peran , dan hubungan yang kita hitung adalah R ( O , y )x

R(O,y)[O|y|0=|y|1][f(y)=1].

Misalkan, alih-alih sebuah oracle, kita diberi input spesifik yang menggambarkan bagaimana fungsi f dikomputasi, kita dapat mempertimbangkan kelas kompleksitas mana dari masalah ini. Seperti yang ditunjukkan , kelas kompleksitas yang sesuai yang kita peroleh tergantung pada bagaimana input diberikan.xfpyramids

  • Misalkan fungsi input disediakan sebagai basis data (karena masalahnya kadang-kadang dijelaskan), di mana setiap entri ke basis data memiliki panjang . Jika n adalah panjang dari string x yang digunakan untuk menggambarkan seluruh database , maka database memiliki entri N = n / . Maka dimungkinkan untuk mencari seluruh database dengan meminta setiap entri N secara berurutan, dan berhenti jika kita menemukan entri y sedemikian rupa sehingga f ( y ) = 1 . Andaikata setiap query ke database membutuhkan sesuatu seperti O (nxN=n/Nyf(y)=1 waktu, prosedur ini menghentikan waktu O ( N log N ) O ( n log n ) , sehingga masalahnya ada diFP.O(logN)O(logn)O(NlogN)O(nlogn)

    Dengan asumsi bahwa pencarian database dapat dilakukan dalam superposisi yang koheren, algoritma Grover memungkinkan masalah ini ada di FBQP . Namun, seperti FP  ⊆  FBQP , pencarian lengkap klasik juga membuktikan bahwa masalah ini ada di FBQP . Semua yang kami peroleh (hingga faktor log) adalah percepatan kuadratik karena penghematan jumlah kueri basis data.

  • Misalkan fungsi input dijelaskan secara ringkas, oleh algoritma waktu polinomial yang mengambil spesifikasi dan argumen y { 0 , 1 } m dan menghitung O : H m + 1 2x{0,1}ny{0,1}mO:H2m+1H2m+1berdasarkan standar negara , di mana m mungkin jauh lebih besar dari Ω ( log n ) . Contohnya adalah di mana x menentukan bentuk CNF dari beberapa fungsi boolean f : { 0 , 1 } m{ 0 , 1 } untuk m O ( n ) , dalam hal ini kita dapat mengevaluasi f ( y ) pada input secara efisien y |y|bmΩ(logn)xf:{0,1}m{0,1}mO(n)f(y) dan dengan demikian secara efisien mengevaluasi O pada status dasar standar. Ini menempatkan masalah diFNP.y{0,1}mO

    Diberikan prosedur untuk mengevaluasi dari ( x , y ) dalam waktu O ( p ( n ) ) untuk n = | x | Algoritma Grover memecahkan masalah Pencarian Tidak Terstruktur untuk O dalam waktu O ( p ( n ) f(y)(x,y)O(p(n))n=|x|OO(p(n)O(p(n)2m) . Ini bukan polinomial dalamn, dan karenanya tidak cukup untuk menempatkan masalah ini diFBQP: kami hanya mendapatkan percepatan kuadrat - meskipun ini masih berpotensi besar penghematan waktu perhitungan, dengan asumsi bahwa keuntungan yang diberikan oleh algoritma Grover tidak kalah dari overhead yang diperlukan untuk perhitungan kuantum toleran-kesalahan.O(p(n)2n)n

Dalam kedua kasus, kompleksitas ditentukan dalam hal panjang dari string x * yang menentukan bagaimana untuk menghitung oracle O . Dalam kasus x mewakili tabel pencarian, kita memiliki N = n / , dalam hal ini kinerja sebagai fungsi N mirip dengan kinerja sebagai fungsi n ; tetapi dalam kasus x secara ringkas menentukan O , dan N O ( 2 n / 2 ) , pesan gambar besar yang Grover's memecahkan masalah dalam OnxOxN=n/NnxONO(2n/2)kueri mengaburkan pesan yang lebih halus bahwa algoritma ini masih waktu eksponensial untuk komputer kuantum.O(N)

Kompleksitas keputusan dari masalah hubungan

Ada cara mudah untuk mendapatkan masalah keputusan dari masalah hubungan, yang terkenal dari teori masalah NP- lengkap : untuk mengubah masalah pencarian ke pertanyaan tentang keberadaan solusi yang valid.

Versi keputusan masalah pencarian umum.
Diberikan input dan relasi biner R , tentukan apakah y : R ( x , y ) berlaku.xRy:R(x,y)

Kompleksitas NP kelas pada dasarnya dapat didefinisikan dalam hal masalah seperti itu, ketika hubungan efisien dihitung: masalah NP- lengkap paling terkenal (CNF-SAT, HAMCYCLE, 3-COLORING) adalah tentang keberadaan solusi yang valid untuk masalah hubungan yang dapat diverifikasi secara efisien. Peralihan dari memproduksi solusi ke sekadar menegaskan keberadaan solusi ini juga memungkinkan kami untuk menggambarkan versi factoration integer yang ada di BQP (dengan menanyakan apakah ada faktor non-sepele, daripada meminta nilai-nilai faktor non-sepele) .R

xx solusi untuk Pencarian Tidak Terstruktur yang melakukannya tanpa benar-benar menemukan solusi, meskipun secara umum tidak jelas bagaimana melakukannya dengan cara yang akan memberikan keuntungan daripada benar-benar menemukan solusi.

Kompleksitas Oracle

OxO

OnOnx

O
x=111n

  • y{0,1}n

  • y{0,1}n

O|y|0=|y|1

NPOFNPOBQPOFBQPO

O

Seperti yang dapat kita lihat dari kasus terakhir, jika kita memperlakukan input hanya sebagai ramalan, situasinya terlihat agak tidak intuitif, dan tentu saja tidak memungkinkan untuk berbicara tentang cara-cara "database" dapat direalisasikan. Tetapi satu kebajikan dari mempertimbangkan versi relativised masalah, dengan ramalan yang sebenarnya, adalah bahwa kita dapat membuktikan hal-hal yang kalau tidak kita tidak tahu bagaimana membuktikannya. Jika kita dapat membuktikan bahwa versi keputusan dari masalah pencarian tidak terstruktur yang ringkas ada di BQP , maka kita akan mampu mewujudkan terobosan besar dalam perhitungan praktis; dan jika kita dapat membuktikan bahwa masalah keputusan sebenarnya tidak ada dalam BQP , maka kita akan menunjukkan bahwa P ≠ PSPACEOONPOBQPO

Niel de Beaudrap
sumber
2

nmn

m2n/2m2n1

Namun, para fisikawan suka mengajukan pendapat bahwa ini masih merupakan percepatan eksponensial yang tidak memiliki padanan klasik yang diketahui (atau memang mudah dipahami). Ini paling jelas dalam contoh basis data di mana fungsi oracle adalah pencarian basis data dan algoritma Grover dapat menyebabkan seseorang membutuhkan pencarian jauh lebih sedikit daripada ada data dalam basis data. Dalam hal ini, masih ada keuntungan yang signifikan, meskipun itu benar-benar hilang dalam gambaran kelas kompleksitas.

piramida
sumber
" Fisikawan suka mengajukan pendapat bahwa ini masih merupakan percepatan eksponensial tanpa diketahui " ... apakah Anda bermaksud menulis " masih percepatan polinomial "?
glS
Tidak, ini memang mempercepat eksponensial (tidak cukup untuk mengubah runtime eksponensial menjadi noneksponensial).
piramida
2

n

NP

f(x)x{0,1}nxf(x)=1pxmpoly(n)g(x,px)=1f(x)=1g(x,px)poly(n)

Izinkan saya memberikan beberapa contoh (mungkin ini yang Anda tanyakan di sini ?):

  • f(x)xxf(x)g(x,px)=f(x)

  • f(x)xx=72px=(8,9)g(x,p)x

  • G1G2xf(x)pxG1G2g(x,px)pxG1G2

  • xf(x)pxg(x,px)

NPPP

PNPNPPPNP

NPxpxm=poly(n)g(x,px)=1O(2mpoly(m))g(x,px)=1pxO(2m/2poly(m)). Ini secara besar-besaran lebih cepat, tetapi tidak mengubah penilaian apakah waktu tayang polinomial atau sesuatu yang lebih buruk; itu belum menjadi algoritma waktu polinomial. Sebagai contoh, grafik isomorfisme harus mencari semua permutasi yang mungkin. Minesweeper harus mencari semua kemungkinan penugasan ranjau di kotak terbuka.

Tentu saja, kadang-kadang, struktur tambahan dalam masalah memungkinkan solusi yang berbeda yang tidak memerlukan pencarian semua bukti yang mungkin. Di sana, pencarian Grover kurang dari, atau bahkan tidak, digunakan untuk kita, tetapi mungkin kita bisa membuat algoritma waktu polinomial dengan cara lain. Sebagai contoh, kasus pengujian komposit: klasik, menemukan faktor-faktor dari bilangan tampaknya sulit: kita tidak bisa melakukan lebih baik daripada menguji semua faktor yang mungkin, jadi menggunakan bentuk bukti itu tidak banyak membantu, tetapi , seperti yang telah disebutkan, pertanyaan dapat diselesaikan secara efisien melalui rute lain, pengujian primitif AKS.

DaftWullie
sumber
Kelas P dan NP biasanya didefinisikan sebagai kelas bahasa atau masalah keputusan, seperti dalam jawaban untuk pertanyaan ini . Walaupun ini dapat 'dikodekan' sebagai fungsi dengan keluaran biner seperti yang Anda lakukan di sini, ini agak tidak standar dalam teori kompleksitas.
Kadal diskrit
f(x)
Anda dapat mendefinisikan hal-hal seperti yang Anda inginkan, tetapi saya pikir sangat berguna untuk menyebutkan bahwa ini bukan standar ketika misalnya pembaca memeriksa sumber lain. Karena itulah komentar.
Kadal diskrit
-1

Lupakan basis data. Algoritma Grover memecahkan Boolean Satisfiability Problem , yaitu:

n10

Masalahnya dikenal sebagai NP-complete.

kludg
sumber
3
Ada unsur kebenaran dalam apa yang Anda katakan --- bahwa orang harus selalu menganggap oracle sebagai mengevaluasi fungsi daripada pencarian basis data; dan bahwa jika fungsi itu dapat dievaluasi dalam waktu polinomial, maka itu secara efektif adalah turunan dari SAT, yang memang NP-lengkap. Tetapi mengingat bahwa speedup dari Grover paling banyak kuadrat, tidak jelas bahwa NP-kelengkapan SAT relevan dengan apa yang sebenarnya dilakukan algoritma Grover.
Niel de Beaudrap
2
Karena downvoting bodoh atau trolling saya tidak akan berkontribusi forum ini lagi.
kludg
@kludg Saya akui bahwa salah satu suara yang turun adalah milik saya jadi izinkan saya menjelaskannya; Jawaban Anda tanpa konteks atau penjelasan lebih lanjut tidak menjawab pertanyaan yang saya ajukan di OP. Itu membuat poin yang menarik tetapi sejauh ini mengatakan ini tidak relevan dengan pertanyaan spesifik saya. Sekarang saya bisa salah tentang hal ini dan Anda menjawab sebenarnya adalah menjawab beberapa pertanyaan saya - jika ini masalahnya saya tidak percaya mereka dijawab dengan cara eksplisit.
Spagetifikasi kuantum