量子比特(qubit)是計算觀點對量子力學的基礎貢獻之一. 一般而言, 對于可區分
維量子系統的量子态, 我們可以用
上的一個機關矢量來描述它. 最簡單而有趣的情形即是
, 這樣的系統就叫量子比特(qubit). 考慮對态矢量
的測量, 為了保證得到結果
的機率是
, 并且得到結果
, 那麼
必須是機關矢量. 如此說來, 任何一個線性動力系統都是可能的備選方案, 隻要能夠保證态矢量的模長不變. 換句話說, 這樣的演化把态矢量從
映射到
, 這裡的
是酉矩陣(unitary), 即它能夠保證态矢量的模長不變. 在數學上, 這等價于
, 即對于每個矩陣元有
. 這個解釋的美妙之處, 在于它是與實作系統無關的, 這樣的系統可能是光子的極化, 也可能是原子中某個電子的能級, 還可能是原子核的自旋, 亦或是超導線圈中的電流方向. 是以, 量子比特是一種裝置無關的量子資訊描述方式. 它就像是經典資訊中的比特一樣, 我們能夠從中推理出資訊, 卻不必知道它究竟是編碼在何處, 不管是在RAM(Random-Access Memory, 随機通路存儲器)上, 在硬碟上, 還是在算盤上.
于實體實驗而言, 單量子比特的情形已經足夠有趣了. 但從計算觀點來看,
量子比特情形下發生的事情更吸引我們. 此時, 一個量子态
就是
中的一個機關矢量. 那麼, 對于矢量空間機關正交基中的每個元素, 我們都用一個
比特字元串标記. 大多數
量子比特的量子态是糾纏的, 這意味着它們的振幅在某種意義上, 對
比特串的各處都是關聯的. 酉矩陣給出了這樣的系統的動力學描述, 它們由一系列兩比特量子門構成. 為了表示作用在具體的量子比特上的量子門, 比如第
個或者第
個量子比特, 我們考慮一個矩陣元
非零當且僅當
比特字元串中
和
等于
或者
的酉矩陣
. 進一步地,
的值應該隻取決于四個比特, 即
.
這樣的線性代數形式看起來似乎很抽象, 但它還可以被用于描述經典的确定性計算和随機計算. 對于經典的确定性計算, 雖然有些浪費, 但确實用
比特字元串來表示. 譬如說對于長度為
的矢量, 其中隻有一個分量為
, 其餘均為
的情形. 那麼考慮一個
矩陣
, 且其中每列隻有一個
, 這樣的動力學描述即表示了從
到
的映射. 事實上, 随機計算(譯者注: 指的就是 Markov 過程)也是類似的. 隻不過此時的狀态矢量的各個分量均為非負實數, 且它們的和為
. 對于任何僅有非負矩陣元, 且每一列矩陣元和為
的矩陣
,
都是有效的狀态轉移. 在一般意義上, 這樣的圖象忽視了一個事實: 一些
比特的變換比另一些更容易. 那麼為了表示單個操作, 即兩比特操作, 我們也需要用一個矩陣
. 它滿足對于所有未作用比特
, 有
, 即
的值僅僅取決于其對應的比特
是否被作用. 這啟示我們, 如果我們不對一個比特作用, 那麼它不應該發生變化.
是以, 說到随機計算和量子計算最關鍵的不同, 它“僅僅”是把實數換成了複數(甚至允許負實數), 以及用于度量态矢量模長的範數從
換成了
. 也就是說, 于量子态而言, 其态矢量各分量的機率幅平方和等于
; 而機率矢量的分量的和為
, 且并沒有平方. 然而, 在計算中, 可以用不同的相位作為不同分支這一事實, 意味着當我們重新組合它們的機率幅的時候, 機率幅可能得到增強(即相長幹涉)或者削弱(即相消幹涉). 如果“0”用矢量
表示, 而“1”用矢量
表示, 那麼非(NOT)操作能夠表示(不論量子或經典情形)為
. 論及它的幾何意義, 這是一個角度為
的旋轉. 然而, 隻有量子計算機才能作用“非門的平方根”, 這樣的量子門即
旋轉:
如果我們從量子态“0”開始, 然後作用一個
門, 那麼我們會得到态
. 要是我們測量這個态, 那麼得到結果
的機率都是
. 然而, 如果我們對初态“0”作用兩次
門, 那麼我們得到的結果是“1”. 這展示了量子疊加和經典随機性之間的核心差異: 将一個量子态進行疊加, 那麼它不會有任何不可逆的資訊丢失. 當我們有
個量子比特的時候, 疊加和幹涉使得我們能得到更大的計算優勢. 一個著名的例子就是 Grover 算法: 給定一個
比特二進制函數
, 我們要找到一個滿足
的輸入
, 這裡僅僅需要計算
大約
次, 即平方級加速. 正是機率是機率幅的平方這一事實, 使得 Grover 算法得以可行. 是以, 在
個基矢量上的均勻疊加的量子态, 對應着每個基矢量的機率幅都是
. 更進一步地, 我們能夠示範計算
造成的影響, 并且這樣的影響是可比較的: 每個目标量子态
(即
)的機率幅大緻以
的速度增長, 而這樣的破壞僅僅出現在總機率幅非常大的時候. 是以, 總影響(漸進時間複雜度)的階是
; 或者更一般地, 對于
個解有
.
而用于分解整數的 Shor 算法的加速, 于經典計算而言更為戲劇性. Shor 算法有更為本質的經典部分, 即把素因子分解(Factoring)問題轉化為更抽象的尋階問題(Period-finding). 這個問題輸入是一個在集合
上函數
, 滿足性質
當且僅當
能夠整除某些隐含周期
. 它的目标是尋找合适的
. 既然
相對于
來說可以指數大, 如果我們把
視作一個黑盒, 那麼經典計算機用于尋找它的時間自然是指數的.
然而, 量子計算機卻能夠機率幅近似表示為一系列
的量子态的疊加,即考慮每個
是某個随機選擇的
. 迄今為止, 這很像一個機率算法, 選擇随機的
用于計算
. 此外, 根據對
的, 選擇考慮
的分布. 但算法的下一步是量子的, 并且應用了一類稱為量子 Fourier 變換(Quantum Fourier Transform, QFT)的酉矩陣. 這個矩陣中的矩陣元為
. 為了有效的執行算法, 我們需要經典快速 Fourier 變換(Fast Fourier Transform, FFT)的量子版本. 但是它們的相異之處同樣是戲劇性的: 因為它是對量子态的機率幅進行變換, 而不是像經典的 FFT 一樣作用在一串數上. 在這種情形下應用 QFT, 得到的疊加态中
的機率幅約為
. 如果
能夠近似地被
整除, 那麼它的和會非常大; 反之, 如果
并不能近似地整除
, 它會涉及到很多不同相位的複數, 不難驗證, 此時它們傾向于互相抵消. 是以, 測量
會傳回一個接近
的倍數的答案. 最終, 通過經典連分數展開算法, 我們重新得到了
一旦我們開發出了新的公鑰密碼系統來抵抗量子計算機的攻擊, 量子模拟就在實踐上逐漸變得更加重要. 而 Shor 算法所展示的量子計算的力量, 甚至遠不能用令人驚訝來形容, 因為這一問題的解決和量子力學并沒有明顯的聯系. 在 Shor 算法之後, 人們越來越難以相信量子力學能夠被經典計算機有效模拟. 在此之前, 很多科學家們寄希望于基于量子力學的模型, 希望它能夠控制那些反直覺特征, 比如指數大的态矢量空間, 并且要保持它們與我們的觀測相容. 但是現在, 我們知道這些模型并不能簡化量子力學自身(或者說, 至少并不容易模拟), 除非素因子分解問題(Factoring)和尋階問題(Period-finding)在經典計算機上有更快的算法. 這樣的情形就像是 NP 完全性(NP-Completeness)的發展, 即昭示了不同領域在求解 NP-Complete 問題的努力, 在實際上是等價的.
Shor 算法和 Grover 算法是最著名的量子算法, 但并不是唯一的兩個. 比如最近提出的一個量子算法, 即用于求解大的線性方程組的 HHL 算法[1]: 給定一個矩陣
和一個矢量
, 找到滿足
的
. 然而, 不像這一問題的經典算法, 量子版本的
都是量子态(因而我們可以隻用
個量子比特表示
維的矢量). 更進一步地,
必須是稀疏的, 并且對于給定的隐含表示滿足給定任意行名額
, 能夠有效的找到所有的非零
. 這一限制使得它能夠在理論上在多項式時間裡解決指數大小的方程組. 然而, 需要說明的是: 算法的運作時間還取決矩陣
的條件數的大小, 條件數是一個關系到經典計算機上求解線性方程組的數值穩定性的參數. 找一個能夠使用這一算法的自然的情形, 是一個引人注目的未解決問題(Open Problem).
另一個最近的算法上的進展是 Metropolis 采樣算法(Metropolis sampling)的量子對應[2]. 對于經典情形, Metropolis 法是是一種在指數大小的狀态空間上, 從難于分析的分布中采樣的方法. 事實上, 這是一個通過使用随機性來得到指數級加速的例子, 而刻畫對計算模型的改變會使得它變得多麼強大也并不令人着迷. 它應用範圍很是出乎意料, 包括統計推斷和關于非負矩陣的排列(the permanent of a nonnegative matrix)的近似算法[3], 但是它最初的發展, 是對系統的熱力學分布采樣所引起的. 如果一個狀态
有能量
在溫度
下的熱力學分布與
成比例, 是以更低的溫度會使得系統更難以轉化到低能态情形. 類似地, 量子 Metropolis 算法也從熱力學分布中産生量子态. 就像它的經典版本一樣, 量子 Metropolis 算法花費更多時間去産生低溫态, 正如其往往解決更困難的優化問題一樣. 但是除了少數情形, 證明其運作時間的嚴格的界(bound), 在一般意義上是困難的. 盡管沒有形式化的證明, 我們仍然能夠運作經典 Metropolis 算法, 并且經驗地觀察到它在很多情形下執行的很快. 而對于量子 Metropolis 算法的經驗觀察, 當然需要等到第一台真正的大規模量子計算機出現. 但是我們已經知道了足夠的工具, 如果我們能夠指出如何組合它們, 以此使用量子 Metropolis 算法作為子過程設計新的量子算法, 就像非負矩陣的排列算法使用經典 Metropolis 算法一樣.
人們仍然在不斷地提出着使用量子計算機的新想法, 而一個令人興奮地進展是, 我們找到了越來越多的隻需要
或稍多些量子比特的應用. 量子比特的數量足夠小, 意味着它能夠很容易被經典計算機有效模拟, 特别是當我們并不能展示量子比特間足夠大的互相作用之前. 這樣的量子計算裝置能夠被用于提高量子測量的精度(比如原子鐘, 或者測量引力波), 在網絡中作為“量子中繼器(quantu repeater)”分發用于密碼學協定的糾纏, 或者甚至用于建構能夠組成任意尺寸孔徑的望遠鏡陣列. 正如經典計算機使用, 遠遠超過了作為計算模型的 Turing 機看起來的那樣, 量子計算裝置的使用也會變得比我們現在的想象更加廣泛.
原文釋出時間為：2017.02.01
本文作者：Climber.pI
本文來源：
知乎，如需轉載請聯系原作者。