量子電腦硬體
從排列沒有規則的 100 萬筆資料中尋找符合條件的 1 筆時，Grover 演算法所需的查詢（呼叫預言機）次數的數量級，最接近下列何者？
- A約 20 次
- B約 1,000 次
- C約 50 萬次
查看答案與解析
正確答案：B. 約 1,000 次
以古典電腦一筆一筆檢查，平均需要一半的約 50 萬次，最差需要 100 萬次。Grover 演算法藉由逐步放大正確答案的振幅，約經過 √N 次、精確來說 (π/4)√N ≈ 785 次的反覆後，就能以高機率得到正確答案，數量級為 √(100 萬) = 1,000 次左右。加速只有平方的程度，不像 Shor 演算法那樣有指數性的差異。對於對稱式加密，金鑰窮舉搜尋的次數從 2ⁿ 降為約 2^(n/2)，因此一般認為把金鑰長度加倍（從 AES-128 改為 AES-256）就能應對。
- A. log₂(100 萬) ≈ 20，這是對已排序資料進行二分搜尋的次數，無法用於沒有規則的資料。
- B. 正確。數量級為 √(100 萬) = 1,000。
- C. 這是以古典電腦逐筆檢查時的平均次數。