Asymptotic optimality of Grover-Radhakrishnan-Korepin algorithm

Grover 演算法以 $\mathcal{O}(\sqrt{N})$ 的查詢複雜度奠定了量子搜尋的基礎，但若只需找出目標項目所在的「區塊」，Grover-Radhakrishnan-Korepin（GRK）演算法能以更少步驟完成局部搜尋。多年來，GRK 的「全域-局部-全域」操作結構被廣泛猜測為最佳解，卻始終缺乏嚴格證明。最新發表於 arXiv 的研究首度將此問題轉化為時間最佳化控制模型，在龐大資料庫極限下，從數學上證實了 GRK 演算法的漸進最佳性。

Grover演算法的O(√N)極限與局部搜尋任務

Grover 演算法能在非結構化資料庫中帶來二次方加速，且其 $\mathcal{O}(\sqrt{N})$ 查詢複雜度在嚴格意義上已是不可被超越的最佳極限。如果想要獲得比標準 Grover 搜尋更快的速度，必須放寬任務的精確度要求。這催生了「局部搜尋（Partial Search）」問題：假設資料庫大小為 $N=2^n$，被劃分為 $K$ 個大小為 $b=2^m$ 的區塊，演算法的目的不再是找出單一目標，而是鎖定目標所在的特定區塊。

為了解決這個放寬條件的任務，研究人員在傳統的全域演算法（Global Grover）之外，引入了僅在單一區塊內獨立運作的局部演算法（Local Grover）。GRK 演算法精巧地結合了這兩種算子，展現出超越傳統 Grover 演算法的速度優勢。然而，自 GRK 演算法提出以來，其核心的「全域-局部-全域」三階段操作順序，是否為同等查詢次數下的唯一最佳解，一直是量子計算領域未解的難題。

懸而未決的GRK全域與局部交替操作之謎

在 GRK 演算法的標準流程中，系統會先執行 $k_1$ 次全域算子，接著執行 $k_2$ 次局部算子，最後再補上一次全域算子。當資料庫與區塊數量趨於極大值時，達到完全成功率的最佳化參數會分別趨近於 $k_1 = \frac{\pi}{4}\sqrt{N} - \frac{\sqrt{3b}}{2}$ 以及 $k_2 = \frac{\pi}{6}\sqrt{b}$。

隨著系統規模擴大，全域與局部算子之間的可能排列組合呈現指數級增長。儘管先前的數值模擬強烈暗示 GRK 就是最佳排法，但現有解析結果僅能覆蓋少數受限的序列類別。這引出了一個根本性的結構問題：為什麼「全域-局部-全域」會是在數百萬種可能序列中，最省時、最有效率的量子局部搜尋路徑？

將離散量子搜尋轉化為三維連續時間控制模型

為了解決龐大組合帶來的數學障礙，研究團隊將離散的演算法步驟映射到三維的連續狀態空間中。他們將系統劃分為三個不變子空間：目標狀態 $|t\rangle$、目標區塊內的非目標狀態 $|ntt\rangle$，以及非目標區塊的總和 $|u\rangle$。局部搜尋的終極目標，就是讓 $|u\rangle$ 的振幅降為零。

在漸進極限（$N \to \infty$ 與 $b \to \infty$）下，單次 Grover 迭代的作用角度極小，可將離散的全局與局部矩陣操作，視為李代數（Lie algebra）$\mathfrak{so}(3)$ 中的連續無限小生成元 $X$ 與 $Y$。透過這層數學轉換，原本複雜的量子查詢次數最佳化問題，被完美等價為一個三維空間中的時間最佳化控制模型，其目標是花費最短的控制時間讓初始狀態到達特定的終端平面。

導入龐特里亞金最大化原理分析切換函數

面對這種雙生成元的連續控制系統，研究團隊引入了龐特里亞金最大化原理（Pontryagin Maximum Principle，一種尋找動態系統最佳控制策略的數學工具）。這套理論透過建立哈密頓函數來評估每一步的操作成本，並定義了一個關鍵純量——切換函數 $\Phi(t)$。

切換函數的正負號直接決定了當下該使用全域生成元 $X$ 還是局部生成元 $Y$。若 $\Phi(t) > 0$，系統應選擇 $X$；若 $\Phi(t) < 0$，則應選擇 $Y$。因此，演算法操作順序的轉換必定只發生在 $\Phi(t) = 0$ 的時刻。研究團隊定義了一組對應切換函數及其導數的降維變數（$\phi_1, \phi_2, \phi_3$），憑藉李代數在交換子運算下的封閉性，證實這些變數在算子啟動時會形成一個獨立的三維線性系統，精準捕捉了切換節點的動態變化。

數學實證確立全域-局部-全域的最短路徑

藉由切換函數的諧波振盪特性，團隊證實了最佳控制策略必定具有 Bang-bang 控制結構（控制變數在極值之間切換，不含中介狀態），徹底排除了停留在 $\Phi(t) = 0$ 的奇異軌跡（Singular arcs）可能性。

模型分析進一步揭示了關鍵的「通用切換映射」法則：無論是經歷最短的全域軌跡還是局部軌跡，當切換函數歸零時，橫向切換速度的符號必定發生反轉。利用這項傳播特徵與路徑壓縮技術，數學模型嚴格排除了所有非最佳的切換模式。推演至終點，唯一倖存的常規極值結構，正是由兩次切換點所切割出來的「全域-局部-全域」三段式路徑。這項工作為 GRK 演算法的漸進最佳性提供了無懈可擊的嚴密證明。

將離散的量子查詢複雜度轉化為連續空間的控制模型，不僅確認了 GRK 的數學地位，也揭示了動態控制理論在解析量子演算法結構上的巨大潛力。