量子圖靈機

量子圖靈機( QTM ) 或通用量子計算機是一種用於模擬量子計算機效應的抽象機器。它提供了一個簡單的模型，可以捕捉量子計算的所有能力——也就是說，任何量子算法都可以正式表示為特定的量子圖靈機。然而，計算等效量子電路是更常見的模型。 ^{[1] [2] :2}

量子圖靈機可以在基於轉換矩陣的框架中與經典和概率圖靈機相關聯。也就是說，可以指定一個矩陣，其與表示經典或概率機器的矩陣的乘積提供了表示量子機器的量子概率矩陣。蘭斯·福特諾（Lance Fortnow）展示過這一點。 ^[3]

非正式草圖

理解量子圖靈機 (QTM) 的一種方式是，它以量子有限自動機 (QFA) 概括確定性有限自動機(DFA) 的方式概括經典圖靈機 (TM)。本質上，經典TM的內部狀態被希爾伯特空間中的純狀態或混合狀態所取代；轉移函數被一組將希爾伯特空間映射到自身的酉矩陣所取代。 ^[4]

也就是說，經典的圖靈機由 7元組描述${\displaystyle M=\langle Q,\Gamma ,b,\Sigma ,\delta ,q_{0},F\rangle }$ 。請參閱圖靈機的正式定義，以更深入地了解此元組中的每個元素。

對於三帶量子圖靈機（一個帶保存輸入，第二個帶保存中間計算結果，第三個帶保存輸出）：

• 狀態集${\displaystyle Q}$被希爾伯特空間所取代。
• 磁帶字母符號${\displaystyle \Gamma }$同樣被希爾伯特空間（通常是與狀態集不同的希爾伯特空間）所取代。
• 空白符號${\displaystyle b\in \Gamma }$是希爾伯特空間的一個元素。
• 輸入和輸出符號${\displaystyle \Sigma }$通常被視為離散集，就像在經典系統中一樣；因此，量子機的輸入和輸出都不需要是量子系統本身。
• 過渡函數${\displaystyle \delta :\Sigma \times Q\otimes \Gamma \to \Sigma \times Q\otimes \Gamma \times \{L,R\}}$是過渡么半群的廣義，被理解為希爾伯特空間自同構的酉矩陣的集合${\displaystyle Q}$ 。
• 初始狀態${\displaystyle q_{0}\in Q}$可能是混合狀態，也可能是純狀態。
• 最終或接受狀態的集合${\displaystyle F}$是希爾伯特空間${\displaystyle Q}$的子空間 。

以上僅僅是量子圖靈機的草圖，而不是它的正式定義，因為它模糊了幾個重要的細節：例如，測量的頻率；例如，一次測量和多次測量 QFA 之間的區別。這個測量問題影響了輸出磁帶寫入的定義方式。

1980 年和 1982 年，物理學家保羅·貝尼奧夫發表文章^{[5] [6]} ，首次描述了圖靈機的量子力學模型。 1985 年，牛津大學物理學家戴維·多伊奇（David Deutsch）發表的一篇文章進一步發展了量子計算機的概念，他認為量子門的功能可以類似於傳統數字計算二進制邏輯閘。 ^[4]

Iriyama、 Ohya和 Volovich 開發了一種線性量子圖靈機(LQTM) 模型。這是具有混合狀態並允許不可逆轉換函數的經典 QTM 的概括。這些允許表示沒有經典結果的量子測量。 ^[7]

斯科特·阿倫森(Scott Aaronson) 定義了一種具有後選擇功能的量子圖靈機，他證明了這種機器上的多項式時間類 ( PostBQP ) 等於經典複雜度類PP 。 ^[8]

參見

• 量子模擬器§解決物理問題