量子圖靈機 Quantum Turing Machine, QTM

量子圖靈機（Quantum Turing Machine, QTM）是經典圖靈機（Turing Machine, TM）在量子計算框架下的推廣，它利用量子力學原理（如疊加態、糾纏和幺正演化）擴展了計算能力。下面對量子圖靈機進行解析。

1. 定義與基本結構

定義

量子圖靈機由以下幾個核心組件構成，

量子態空間（Hilbert Space）：
經典圖靈機的配置（狀態、磁帶內容、讀寫頭位置）被推廣為量子態，允許疊加形式：

? ? ? ? ? ? ? $|\psi\rangle = \sum_i \alpha_i |q_i, \text{tape}_i, \text{head}_i\rangle$
其中?? $\alpha_i$ ? 為復數概率幅，滿足?? $\sum |\alpha_i|^2 = 1$ ?。

有限狀態集 $Q$ ：
包含初始狀態 $q_0$ ? 和接受/拒絕狀態（測量時坍縮到這些狀態）。

字母表 $\Gamma$ ：
磁帶符號（含空白符號 $\#$ ），支持量子疊加的符號寫入。

量子轉移函數 $\delta$ ：

? ? ? ? ? $\delta: Q \times \Gamma \to \mathbb{C}^{Q \times \Gamma \times \{L, R\}}$
對每個 $(q, \gamma)$ ，輸出一組可能的 $(q', \gamma', D)$ ?及其概率幅，需滿足幺正性（即整體演化算符 $U$ ?是幺正的： $U^\dagger U = I$ ?。

? ? ?在量子圖靈機（QTM）的轉移函數定義中，符號 $\mathbb{C}^{Q \times \Gamma \times \{L, R\}}$ ? 的數學含義和物理意義接下來分開說明。

1.1.? $\mathbb{C}$ ?的含義

? ?? $\mathbb{C}$ ?表示復數集合。量子計算中，概率幅（probability amplitudes）是復數，而非經典概率中的實數。
量子態的演化由復數系數（如 $\alpha + i\beta$ ）描述，其模平方?? $|\alpha + i\beta|^2 = \alpha^2 + \beta^2$ ? 表示測量時坍縮到該狀態的概率。

1.2. 轉移函數的完整解釋

轉移函數的形式：

? ? ? ?? $\delta: Q \times \Gamma \to \mathbb{C}^{Q \times \Gamma \times \{L, R\}}$
輸入：當前狀態 $q \in Q$ ?和讀到的磁帶符號 $\gamma \in \Gamma$ 。

? ? 輸出：一個復數賦值的映射，覆蓋所有可能的：新狀態 $q' \in Q$ ?，寫入的符號 $\gamma' \in \Gamma$ ，讀寫頭移動方向 $D \in \{L, R\}$ （左/右）。

需要強調的是，對每個 $(q, \gamma)$ ， $\delta$ ?輸出一組形如? ? $\delta(q, \gamma) = \sum_{(q', \gamma', D)} c_{q', \gamma', D} \cdot (q', \gamma', D)$

其中?? $c_{q', \gamma', D} \in \mathbb{C}$ ? 是轉移到配置?? $(q', \gamma', D)$ ? 的概率幅。

1.3. 為什么需要復數 $\mathbb{C}$

量子疊加與干涉

? ? ?復數相位（如 $e^{i\theta}$ ?）允許量子態之間發生相長/相消干涉，這是量子并行性的核心（例如Deutsch-Jozsa算法中的相位反轉）。經典概率（實數）無法描述干涉現象。

幺正性（Unitarity）

? ? 量子演化必須保持概率守恒（即幺正性 $U^\dagger U = I$ ?），復數系數是滿足此性質的數學必需。

? ? 例如，Hadamard門的變換矩陣包含 $\pm \frac{1}{\sqrt{2}}$ ?，其平方和為1。

1.4. 量子圖靈機跳轉示例

? ? 量子圖靈機的狀態轉移由量子疊加和幺正演化決定，相比經典圖靈機，它可以同時處理多個計算路徑。以下是幾個具體示例，從簡單到復雜?

?1.4.1.?簡單示例：單步確定性轉移

問題：設計一個量子圖靈機，初始狀態為? $|q_0\rangle$ ，讀取符號?0?時轉移到? $|q_1\rangle$ ，讀取?1?時轉移到? $|q_2\rangle$ 。

? ? 定義：

? ? ? ? 狀態集? $Q = \{ |q_0\rangle, |q_1\rangle, |q_2\rangle \}$

? ? ? ? 紙帶字母? $\Sigma = \{0, 1\}$

? ? ? ? 初始頭位置在?0。

? ? ? ? 轉移規則：

? ? ? ? ?? ? ? ? ? $\delta(|q_0\rangle, 0) = |q_1\rangle, \quad \delta(|q_0\rangle, 1) = |q_2\rangle$

? ? ? ? ? ? ? ? （這里假設轉移是確定性的，即沒有疊加態。）

? ? 運行示例：

? ? ? ? 輸入紙帶：0
? ? ? ? ? ? ? ? 初始狀態： $|q_0\rangle$
? ? ? ? ? ? ? ? 讀取?0?→ 轉移到? $|q_1\rangle$
? ? ? ? ? ? ? ? 最終狀態： $|q_1\rangle$

? ? ? ? 輸入紙帶：1
? ? ? ? ? ? ? ? 初始狀態： $|q_0\rangle$
? ? ? ? ? ? ? ? 讀取?1?→ 轉移到? $|q_2\rangle$
? ? ? ? ? ? ? ? 最終狀態： $|q_2\rangle$

特點：
這個例子和經典圖靈機完全一致，沒有量子特性。真正的量子圖靈機需要疊加態和干涉。

1.4.2. 簡單量子疊加態轉移

問題：設計一個量子圖靈機，初始狀態為? $|q_0\rangle$ ，讀取?0?時進入疊加態? $\frac{1}{\sqrt{2}}(|q_1\rangle + |q_2\rangle)$ ，讀取?1?時進入? $|q_2\rangle$ 。

定義：

? ? ? ? 狀態集? $Q = \{ |q_0\rangle, |q_1\rangle, |q_2\rangle \}$ 。

? ? ? ? 轉移規則：

? ? ? ? ? ? ? ? ? ?? $\delta(|q_0\rangle, 0) = \frac{1}{\sqrt{2}} |q_1\rangle + \frac{1}{\sqrt{2}} |q_2\rangle\\ \\ \delta(|q_0\rangle, 1) = |q_2\rangle$

? ? ? ? 運行示例：

? ? ? ? ? ? ? ? 輸入紙帶：0
初始狀態： $|q_0\rangle$
讀取?0?→ 進入疊加態? $\frac{1}{\sqrt{2}}(|q_1\rangle + |q_2\rangle)$ ?
最終狀態： $\frac{1}{\sqrt{2}} |q_1\rangle + \frac{1}{\sqrt{2}} |q_2\rangle$

? ? ? ? ? ? ? ? 輸入紙帶：1
初始狀態： $|q_0\rangle$
讀取?1?→ 進入? $|q_2\rangle$
最終狀態： $|q_2\rangle$

? ? ? ? 特點：
這里首次引入量子疊加態，使得機器可以同時進入兩個狀態? $|q_1\rangle$ ?和? $|q_2\rangle$ ，概率各 50%。

1.4.3.??多步量子計算（Deutsch-Jozsa 問題）

問題：判斷一個函數? $f: \{0,1\} \rightarrow \{0,1\}$ ?是恒定（constant）還是平衡（balanced）。
（? 恒定： $f(0)=f(1)$ ，平衡： $f(0) \neq f(1)$ ? ）

量子圖靈機實現：

初始狀態： $|q_0\rangle |0\rangle$ （初始狀態 + 紙帶?0）。
第一步（疊加態構造）：
- 應用 Hadamard 門（量子并行性）：
  $|q_0\rangle |0\rangle \rightarrow \frac{1}{\sqrt{2}}(|q_0\rangle |0\rangle + |q_0\rangle |1\rangle)$
第二步（查詢函數?ff）：
- 量子預言機（Oracle）計算? $|x\rangle \rightarrow (-1)^{f(x)} |x\rangle$ ?：
  - 如果? $f$ ?恒定，相位不變
  - 如果? $f$ ?平衡， $|0\rangle$ ?和? $|1\rangle$ ?相位相反
第三步（干涉測量）：
- 再次應用 Hadamard 門：
  - 若? $f$ ?恒定，測量結果為? $|0\rangle$
  - 若? $f$ ?平衡，測量結果為? $|1\rangle$

? ? 特點：

? ? ? ? 經典計算需要 2 次查詢，量子計算僅需 1 次（量子加速）。

? ? ? ? 量子圖靈機通過疊加態 + 干涉實現高效計算。

1.4.4. 復雜示例：Shor 算法的量子部分（因數分解）

問題：找到一個大數? $N$ ?的非平凡因數。

量子圖靈機步驟：

初始狀態： $|q_0\rangle |0\cdots0\rangle$ （所有量子比特置零）。
第一步（疊加態構造）：
- 應用 Hadamard 門生成所有可能的? $x$ ：
  $|q_0\rangle |0\rangle \rightarrow \frac{1}{\sqrt{2^n}} \sum_{x=0}^{2^n-1} |q_0\rangle |x\rangle$
第二步（模冪計算）：
- 計算? $f(x) = a^x \mod N$ （ $a$ ?是隨機選擇的數）：
  $\sum_x |x\rangle |0\rangle \rightarrow \sum_x |x\rangle |f(x)\rangle$
第三步（量子傅里葉變換 QFT）：
- 對? $|x\rangle$ ?進行 QFT，提取周期? $r$ （使得? $a^r \equiv 1 \mod N$ ）
測量與經典后處理：
- 測量得到? $r$ ，再用經典算法求? $\gcd(a^{r/2} \pm 1, N)$

? ? 特點：

? ? ? ? 經典算法需要指數時間，量子算法僅需多項式時間;

? ? ? ? 量子圖靈機通過并行計算 + 干涉高效提取周期。?

1.5. 與經典圖靈機的對比

? ? 經典確定性TM：
$\delta$ ? 輸出唯一的下一個配置（如? $(q', \gamma', D)$ ?），無復數系數。

? ? 經典概率TM：
輸出是概率分布（實數且非負，如 $p(q', \gamma', D) \in [0,1]$ ?），但無復數相位。

? ? 量子TM：
復數概率幅允許干涉和糾纏，這是量子加速（如Shor算法）的根源。

1.6. 數學驗證：幺正性條件

? ? 為確保量子演化的合法性， $\delta$ ?必須滿足：

? ? ? ?? ? ? ??? $\sum_{q', \gamma', D} |\delta(q, \gamma, q', \gamma', D)|^2 = 1 \quad \forall (q, \gamma)$ .
即每個輸入的轉移概率幅模平方和為1（類比經典概率的歸一化）。

1.7 分析總結

? ?? $\mathbb{C}^{Q \times \Gamma \times \{L, R\}}$ ? ?表示，量子圖靈機的每一步演化由復數概率幅控制，支持疊加態和干涉。復數 $\mathbb{C}$ ?是量子計算超越經典計算的關鍵數學結構，使得量子并行性和相位操作成為可能。這一形式化定義是量子計算理論的基礎，與物理實現（如量子門操作）直接對應。

2. 核心性質

2.1.? 量子并行性

? ? ? ??QTM 可同時處理多個計算路徑（疊加態），例如：
輸入 $n$ ?比特時，QTM 可同時計算?? $2^n$ ? 個狀態（指數級并行性）。

2.2. 幺正演化

? ? ? ??每一步操作必須保持概率守恒，即轉移矩陣 $U$ ?是幺正矩陣。

? ? ? ??經典TM的不可逆操作（如刪除信息）在QTM中需通過輔助比特實現可逆性。【注，從非相對論獨立量子系統的角度，沒有什么是會消失的】

2.3. 測量與概率輸出

? ? ? ??計算結束時，對量子態進行測量，得到接受/拒絕結果的概率由?? $| \alpha_{\text{accept}} |^2$ ? 和 $| \alpha_{\text{reject}} |^2$ ? 決定。

? ? ? ??輸出是概率性的（類似BQP復雜度類）。

2.4. 與經典TM的關系

? ? ? ??經典TM是QTM的特例：當所有概率幅為0或1時，QTM退化為確定性TM。

? ? ? ??嚴格更強未確定：目前已知QTM可高效解決某些經典難解問題（如Shor算法），但尚未證明 $BQP \neq P$ ?。

3. 示例：Deutsch-Jozsa問題的QTM實現

? ? 問題：

? ? ? ??判斷函數 $f: \{0,1\}^n \to \{0,1\}$ ?是常函數（全0或全1）還是平衡函數（一半0、一半1）。
QTM步驟：

? ? ? ??初始化磁帶為 $|{0^n} \rangle |{1}\rangle$ ，應用?Hadamard?門生成疊加態：

? ? ? ??? ? ? ?? $\frac{1}{\sqrt{2^n}} \sum_{x \in \{0,1\}^n} |{x}\rangle |{-}\rangle$

通過量子轉移函數 $\delta$ ?實現 Oracle 查詢（相位反轉）：

? ? ? ??? ? ? ?? $|{x}\rangle |{-}\rangle \to (-1)^{f(x)} |{x}\rangle |{-}\rangle$

再次應用?Hadamard?門并測量：若結果為 $|{0^n}\rangle$ ，則 $f$ ?為常函數；否則為平衡函數。
優勢：QTM僅需1次查詢，經典TM最壞需?? $2^{n-1}+1$ ?次。

4. 與量子線路模型的等價性

? ? ? ??量子圖靈機（QTM）與量子線路模型（Quantum Circuit Model）在計算能力上是等價的：

? ? ? ??? ? ? ??QTM → 量子線路：QTM的每一步幺正操作可分解為量子門序列

? ? ? ??? ? ? ??量子線路 → QTM：量子線路可通過QTM模擬，磁帶存儲量子門操作的歷史

? ? ? ??但量子線路更實用，因其直接對應現代量子計算機的物理實現（如超導量子比特）。

5. 復雜度與開放問題

復雜度類
BQP（Bounded-Error Quantum Polynomial Time）：
QTM在多項式時間內以高概率（≥2/3）解決的問題類（如整數分解、離散對數）。

? ? ? ? 已知關系： $\text{P} \subseteq \text{BQP} \subseteq \text{PSPACE}$ ?。

? ? ? ? 未解決問題： $\text{BQP} \subsetneq \text{NP}$ ?是否成立？

開放問題
量子優勢的極限：是否存在 BQP-complete 問題（類似NP-complete）？

? ? ? ? 物理實現：如何構建可擴展、容錯的QTM硬件？

? ? ? ? 與經典計算的關系：是否所有P問題都可被QTM高效解決（即 P = BQP）？

6. 量子圖靈機小結

量子圖靈機是理論模型，結合了圖靈機的框架與量子疊加/糾纏特性。

? ? 優勢：潛在指數級加速（如Shor算法）、并行性、解決經典難解問題。

? ? 挑戰：物理實現困難（退相干、糾錯）、數學基礎未完全明確（如BQP與NP的關系）。

? ? 意義：為理解量子計算的極限提供了理論基礎，推動算法設計（如Grover搜索、HHL線性方程求解）。

? ? 量子圖靈機不僅是抽象工具，更是探索“計算本質”的橋梁——它揭示了一個可能性：在某些問題上，宇宙允許我們比經典計算機走得更快，但可能依然不是最快的可能方式。

7.附錄：量子力學和量子計算的酉正變換

? ? ? ? 從非相對論獨立量子系統的角度出發，量子演化遵循幺正性（unitarity），這意味著信息不會消失，量子態始終以確定性的方式演化。這一觀點與經典物理中的信息守恒和量子力學的基本原理密切相關。

7.1. 幺正演化的核心思想

? ? 在量子力學中，一個封閉（孤立）量子系統的演化由幺正算符 $U$ ?描述：

? ? ? ? ? ? ? $|\psi(t)\rangle = U(t) |\psi(0)\rangle$
其中 $U$ ?滿足 $U^\dagger U = I$ ，即：可逆性：任何量子操作均可通過 $U^\dagger$ ? 逆轉。

? ? 信息守恒：量子態的內積（即概率幅）在演化中保持不變。

? ? 推論：量子信息不會被銷毀，只會被轉移或重新編碼。

7.2. 量子圖靈機中的幺正性

? ? ? ? 量子圖靈機（QTM）的轉移函數 $\delta$ ?必須生成幺正演化，每個配置的轉移概率幅需滿足歸一化條件：

? ? ? ?? $\sum_{q', \gamma', D} |\delta(q, \gamma, q', \gamma', D)|^2 = 1$

（全局確定性）即使單個路徑的概率幅可能干涉相消，但所有可能的演化路徑總概率保持守恒。

示例：
若QTM在某步將狀態?? $|q\rangle$ ? 分裂為?? $\alpha|q_1\rangle + \beta|q_2\rangle$ ?，則未來可通過逆操作重新組合為原狀態（假設無測量）。

7.3. "沒有什么是會消失"的物理表現

（1）量子態的非定域性
量子信息可能分散到多個自由度（如糾纏態），但絕不會完全消失。
例如：一個量子比特 $\alpha|0\rangle + \beta|1\rangle$ ?被編碼到多個輔助比特中，信息仍存在于聯合系統中。

（2）量子糾錯與相干性
即使環境導致退相干（decoherence），信息實際上轉移到了環境自由度中（整體系統仍幺正演化）。
量子糾錯碼通過主動修復，將"丟失"的信息從環境中重新提取。

（3）No-Cloning定理的互補性
量子不可克隆定理（No-Cloning）禁止完美復制未知量子態，但同時也意味著量子信息不能被完全擦除（否則可逆性被破壞）。

7.4. 與經典計算的對比?

性質	經典圖靈機	量子圖靈機
信息處理	可擦除信息（如覆蓋磁帶符號）	信息必須守恒（幺正演化）
操作	允許不可逆操作（如AND門）	所有操作必須可逆（如Toffoli門）
"消失"的含義	信息可被刪除（熱力學熵增）	信息僅被隱藏或分散（整體系統保持幺正）