Algoritma klasik dapat menyelesaikan 3-SAT dalam waktu (acak) atau 1,3303 n waktu (deterministik). (Referensi: Batas Atas Terbaik di SAT )
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?)
Tentu saja algoritma klasik dapat digunakan pada komputer kuantum dengan asumsi ruang kerja yang cukup; Saya bertanya-tanya tentang algoritma kuantum yang inheren.
sumber
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.
sumber