Apakah ada algoritma kuantum yang meningkat pada SAT klasik?

29

Algoritma klasik dapat menyelesaikan 3-SAT dalam waktu (acak) atau 1,3303 n waktu (deterministik). (Referensi: Batas Atas Terbaik di SAT )1.3071n1.3303n

Sebagai perbandingan, menggunakan algoritma Grover pada komputer kuantum akan mencari dan memberikan solusi dalam , secara acak. (Ini mungkin masih memerlukan pengetahuan tentang berapa banyak solusi yang mungkin ada atau tidak, saya tidak yakin seberapa perlu batasan itu.) Ini jelas jauh lebih buruk. Apakah ada algoritma kuantum yang melakukan lebih baik daripada algoritma klasik terbaik (atau setidaknya - hampir sama baiknya?)1.414n

Tentu saja algoritma klasik dapat digunakan pada komputer kuantum dengan asumsi ruang kerja yang cukup; Saya bertanya-tanya tentang algoritma kuantum yang inheren.

Alex Meiburg
sumber

Jawaban:

21

Saya pikir seseorang dapat memperoleh batas atas non-sepele dari komputasi kuantum dengan mempercepat algoritma acak Schöning untuk 3-SAT. Algoritma dari Schöning berjalan dalam waktu dan menggunakan teknik amplitudo amplifikasi standar satu dapat memperoleh algoritma kuantum yang berjalan dalam waktu ( 2 / (4/3)nyang secara signifikan lebih cepat dari algoritma klasik.(2/3)n=1.15n

wwjohnsmith1
sumber
1.32065n1.1492n
Anda juga dapat menikmati makalah ini: digitalcommons.utep.edu/cgi/…
Martin Schwarz
30

Memang, seperti yang dikatakan wwjohnsmith1, Anda bisa mendapatkan kecepatan akar kuadrat atas algoritma Schöning untuk 3-SAT, tetapi juga lebih umum untuk algoritma Schöning untuk k-SAT. Faktanya, banyak algoritma acak untuk k-SAT dapat diimplementasikan secara kuadratik lebih cepat pada komputer kuantum.

O(T(n)poly(n))T(n)n1/T(n)O(T(n))O(T(n)poly(n))

O(T(n))1/TO(T)O(T(n)poly(n))

Robin Kothari
sumber