Dari mana datangnya keunggulan kuantum?
Mengambil langkah mundur, kita dapat bertanya mengapa mengubah masalah optimasi menjadi masalah decoding seharusnya bermanfaat? Dengan memahami hal ini lebih dalam, kita dapat berharap mendapatkan intuisi untuk memandu pencarian masalah optimasi tambahan yang dapat dimanfaatkan oleh komputer kuantum.
Baik masalah optimasi yang kita mulai maupun masalah decoding yang kita konversi menjadi sesuatu yang disebut Masalah NP-sulit. Hal ini menunjukkan bahwa tidak mungkin menemukan solusi pasti secara efisien untuk semua permasalahan ini, bahkan dengan bantuan komputer kuantum. Dengan menggunakan efek kuantum, DQI telah mengubah satu masalah sulit menjadi masalah sulit lainnya. Bagaimana cara ini mencapai sesuatu? Kuncinya adalah kekerasan NP menunjukkan kesulitannya contoh yang sangat sulit dari suatu masalah yang diberikan. Jika contoh masalah dibatasi untuk memiliki beberapa struktur tambahan, ini bisa membuat mereka lebih mudah. Janji dari DQI adalah bahwa jenis struktur tertentu dapat membuat masalah decoding menjadi lebih mudah, tanpa membuat masalah optimasi lebih mudah diselesaikan dengan menggunakan komputer konvensional.
Dalam soal OPI, kisi-kisi yang muncul terstruktur secara aljabar; komponen-komponen vektor basis, bukannya sewenang-wenang, diperoleh dengan menaikkan suatu bilangan ke pangkat yang lebih tinggi secara berturut-turut. Struktur aljabar ini tercermin dalam masalah optimasi asli (OPI) dan masalah penguraian kode yang dapat diubah oleh komputer kuantum (dekode Reed-Solomon). Struktur ini membuat masalah decoding lebih mudah, namun sejauh yang kami tahu tidak membuat masalah optimasi lebih mudah untuk komputer konvensional. Dalam keadaan ini, kemampuan untuk mengubah masalah optimasi menjadi masalah decoding, menggunakan kekuatan komputasi kuantum, memberikan keuntungan.
