第5章 量子演算法入門#

章前言#

工具齊備之後，本章開始回答本書的核心問題：量子演算法到底為什麼快？

5.1 節先建立正確的直覺：加速不是「平行計算」，而是把問題包裝成黑箱查詢模型，再用干涉讓錯誤答案的振幅相消；我們介紹 query 複雜度與 oracle 的形式化。5.2 節以最簡單的 Deutsch–Jozsa 演算法為例，完整走一遍「疊加 → 一次黑箱查詢 → 干涉 → 測量讀出」的流程：對 \(n\) 位元輸入，古典方法最壞需要 \(2^{n-1}+1\) 次查詢才能判斷函式是常數還是平衡，量子方法只要 1 次。5.3 節介紹 Bernstein–Vazirani 演算法，用同樣的架構一次讀出隱藏的字串 \(a\) （古典需 \(n\) 次查詢），並用我們第 3 章的模擬器實際執行。

這兩個演算法實用價值不高，但它們是理解 Grover 與 Shor 的教科書級範例——干涉的威力第一次以「指數對多項式」的形式現身。

學習目標

1. 會形式化黑箱（oracle）查詢模型並定義 query 複雜度。
2. 完整推導 Deutsch–Jozsa 演算法的每一步振幅。
3. 實作並驗證 Bernstein–Vazirani 演算法，理解相位 kickback 技巧。