量子演算法概述與無窮維度的量子機器學習

為了紀念自己通過博士資格考、並推廣科普幫助外界理解這個有趣的領域，於本篇文章我會分享自己對於量子演算法的理解、 然後著重於為何要用無窮維度系統做量子機器學習，我會盡可能用文字說明與類比、並且附上連結給大家參考．即使修過兩次研究所等級的量子資訊(用的是聖經本Nielsen and Chuang)和一次博士班進階量子演算法(Andrew Childs筆記)，在動筆時我仍舊會停下來思考記憶是否準確、還跑去翻書和看筆記，所以這主題很難理解很正常、獲得些感覺就行了；另外，因為自己是物理出身、所以對於演算法的嚴謹性和複雜度分析只能說是略懂，請資訊科學界和數學出身的朋友體諒了:)

在1994年量子演算法里程碑之前，也就是在Bell lab 的Peter Shor 提出Shor Algorithm 之前（真的可以把這年當作量子科技紀年的元年），物理學家已經步履蹣跚在量子物理與資訊科學的交界處做了些探索，比較著名的有Richard Feynman倡議用量子電腦做量子模擬、David Deutsch提出量子圖靈機和Deutsch–Jozsa 演算法等，這些理論研究沒有受到世人重視原因很直觀：沒有什麼應用價值．即使學術界對於量子力學的基本無非常感興趣（如研究entanglemen的貝爾定理和探索測量本質的弱測量），而是指不會看到軍方情報界、銀行創投界和科技大廠瘋狂砸錢研究深邃的物理（至少沒聽說過軍方重本資助粒子對撞機lol）：世人在科學尋求的是力量、而不是真理．
那1994年的Shor algorithm 到底是在幹嘛能觸動世界的敏感神經呢？其應用上很直接，就是破解現行的用於網路世界（包含銀行和國防的）的非對稱加密系統如RSA、 ECC，原本這些加密系統就不像是OTP 本質上被證明安全、而是大家相信很難破解而已．以RSA為例：大數分解這個困難問題等價於尋找週期的Order finding problem(這個等價沒有很難想像，當你取餘數mod時會發現其是個週期函數，長得是f(x)=f(x+t)．）即使尋找週期這件事大家知道可以用傅立葉變換，但古典世界中我們沒有辦法對於極大的向量空間做快速的傅立葉變換（由於破解難度隨位元是指數上升，即使2048 位RSA快不行了，相信4096 位RSA可以撐到被Shor破解為止XD）；不過到了量子世界當你有了量子傅立葉變換 便可以快速的提取週期資訊(也就是從公鑰推出私鑰)，此時的破解難度和位元數目成線性增加，所以我們獲得了指數加速！（整個演算法叫做Quantum phase estimation algorithm ,QPE） 基於Shor algorithm是如此強大（對加密系統極具破壞性），所以科學界如果要煽動政府機構丟錢、或在媒體上提到量子計算潛能的話，都是從其開始說起，至於需要需要成千上萬量子位元（error crorrection至少要乘10倍）就自然先略過不談…
對於專家讀者補充，Shor algorithm 只是Hidden Subgroup problem整個家族中阿貝爾群的一個特例，對於其他的演算法如Simon algorithm 可以去量子演算法動物園晃晃，另外，值得一提的是HSP 的非阿貝爾群中應用對於計算 lattice based crytography 的 Shortest vector problem 有提速作用，雖然還沒有辦法有效率的計算（那是NP-hard），不過如果晶格設計的太偷懶可能都會有問題．而HSP在量子傅立葉變換的技巧下基本上已經是最適解，在已分析的問題上不會有什麼進展、去延伸到新問題或許些機會．
接下來大家常聽到的是1996年的Grover Search algortihm，它可以有效地提升我們搜尋雜亂無章資料庫的速度，所以毫不訝異Google想用量子電腦加速其機器學習．而這演算法就有個生動的譬喻，想像我們在N個紅包袋中只選1個裝錢，那古典電腦必須平均開N/2個紅包才能找到錢，不過量子電腦只需要開約N^0.5個紅包即可，所以其是平方提速．Grover 是Quantum Walk 家族中的一員，其演算法步驟是先透過Oracle 改變正確答案正負號，再於向量空間透過量子隨機漫步、向所有可能的選項擴散，透過重複以上兩個步驟的淨效果是正確答案被發現的機率會不斷上升！Grover的加速雖然沒有Shor 那麼戲劇化，但是其背後整個Quantum Walk家族可以針對不同的問題優化，譬如搜尋圖片中有沒有三角形（某種資料結構）就會有對應的特殊演算法，Grover（無結構資料的搜尋）在此就只是個速度上限．而Grover對於量子電腦的資源要求比較小，大概只需要上百個量子位元就能做有意義的應用（不過考慮error-correction也要加上一個數量級），雖然是比Shor 容易的目標，但是仍舊需要超過十年以上醞釀…
對於專家讀者：那兩個步驟就是在向量空間的兩次反射(Wiki的示意圖畫得很好我也不用多說)，然後Grover也是unstructure data 中的最適解，平方加速是此類問題的一般來說我們能獲得的最好結果，只能去看看在特定的資料結構會不會有更好的Quantum Walk algorithm．
在進入正題之前，我們稍微來回顧一下經典量子資訊教科書的兩大支量子演算法，不論是Shor 或是Grover都需要極為大量的量子位元來做有意義的計算（而不是Proof of Concept），加上需要的量子邏輯閘數目極多故必須執行量子糾錯（quantum error correction），使得可擴展性（scalability）成為量子計算發展的瓶頸，Google 72 qubits/ IBM 50 qubits/ IonQ 11 qubits都沒有運行量子糾錯演算法，而且一直增加量子位元的努力搞不好還會被複雜系統的操作難度趕上(如果操作難度成指數上升那就沒戲唱)，那有沒有除了增加量子位元為之外的其他道路呢？

量子資訊的典範轉移: 將資訊從儲存在二能階系統轉到無窮維度的系統？

答案是當然有的，早在1999年偉大的Seth Lloyd就已經證明了連續變數/無窮維度(Continuous Variable/Inifinite Dimension)系統也可以成為Universal Quantum Computer （請注意Seth Lloyd將是文章後半的核心人物）、他也早已在1992就證明了任何的非線性邏輯閘（加上線性邏輯閘）對都足以構成圖靈機，所以如果我們能夠找出無窮維度的自由度、並讓這些自由度之間產生非線性的邏輯閘，那就可以走出一條不使用量子位元的另外一條道路．以離子為例，它除了internal state（能階外）也會有其他的自由度如震動（vibaration degree of freedom ），如果我們不是「把資訊儲存在二能接系統把CV震動態當輔助」而是將他們的角色交換「把資訊儲存在CV震動態把二維系統當輔助」（如上圖），那我們的向量空間就會大得多（理論上震動態的維度是無限大，不過實驗上的限制當然不會讓無限這種事發生）．為了建構量子電腦，除了擁有巨大的向量空間外，我們還要有非線性的交互作用，這在離子井系統中也是做得到，不過即使有了理論但實驗還在進行中（這估計會是我的博士論文）．
給專家讀者的補充，Continous Variable 是Quantum Optics 對vibration mode的觀點，在向量空間中用X,P描述量子態，而在離子井我們偏好使用Fock baisis 所以說這震動態是infinite dimension，這兩者在數學上等價只是選擇的測量方法不同罷了．
既然（理論上）有了的無窮維度的量子資訊載體、又（理論上）能夠做圖靈完備的計算，那為何不用其來做Shor 或 Grover 而是想跑去做Quantum Machine Learning 呢？ 這就說來話長了，首先Shor在有限維度的阿貝爾群中做量子傅立葉變換、Grover是在有限的選擇中跑Quantum Walk，所以無限維系統沒有辦法直接運行這兩個演算法（尷尬），有個想法是將一個無限維自由度的振動態編碼成error-corrected的量子位元，這樣的二維系統除了比天然的量子位元活更久之外也算是具有需要更少資源的效率（把物理上的量子位元轉化成邏輯容錯上的量子位元如上所述約是1換10），不過由於震動態的dechorence 更快、加上量子糾錯的演算法不同，這是一能走的條路、不過不是我們實驗室的方向(我稱之為走老路)，有興趣的人今年ETH Prof Home團隊就有一篇這方向的實驗在Nature；另外一個不走這方向（做logical qubit跑強大量子演算法）的理由和學界知道自身極限相關，曾去年開始流行的NISQ(Noisy Intermediate-Scale Quantum) 象徵著我們理解（認命）短期間無法跑量子糾錯來攻克Fault-Tolerant Quantum Computer，只能想辦法用量子位元數目不太多又具有噪音的系統來看看能玩出什麼東西…
在花了點時間說明（1:無窮維度系統與其優點(2:為何不用這麼有趣的系統做兩大支經典的量子演算法之後，我們終於能夠進入量子機器學習（QML）這個主題，QML是量子資訊過去十年來最有趣的突破，2009年Seth Lloyd 等人提出HHL演算法：能夠快速地算出線性代數中的反矩陣，具體來說他利用「把量子態算符化」加上(Shor的)QPE創造不是提取週期資訊的變種演算法，能夠快速計算反矩陣之後，整個QML子領域（和Seth Lloyd）彷彿打了雞血一樣開始狂飆，2012年Quantum Data Fitting算線性迴歸、2013年提出Quantum principal component analysis（QPCA）把高維度的資料壓縮到低維度、也於2013年提出Quantum support vector machine(QSVM)把高維度的資料分類等（更多的演算法可以參考2016年Seth Lloyd的回顧文章），總而言之，通往新世界的大門被打開了（包含量子神經網絡和量子深度學習等）．由於 QML理論研究興起在機器學習（ML）成功落地、商業化之時（我還記得2016年王南韓棋王如何敗給AlphaGO的直播），所以跟隨著這潮流QML就開始獲得大家的關注、也成為學界的潮流：有了理論就開始寫計畫要錢看如何實作了XD
給專家讀者：在量子力學中量子態（Wave Function/Density）和算符（Hermition/Unitary）原本是涇渭分明的兩種角色，在薛丁格繪景前者是被動的系統被演化、後者則是主動地給予系統演化，就像是物理定律總會有的Initial Condition和 Equation of Motion 一樣，Seth Lloyd非常有創意的發現賦予量子態類似算符的角色可以提取出矩陣資訊（上述的HHL）；另外，原本QML演算法對古典演算法有指數加速，不過去年天才博士生Ewin Tang和Seth Lloyd發現古典機器學演算法受量子演算法題點可以優化，現在提速只剩下多項式等級而已（還好Shor沒事）
最後，那和用量子位元建構的QML相比、無窮維度系統（CV）有什麼優勢呢？ 在建構QML的演算法中有個很核心的步驟叫Control-swap，在離子井系統中之前的實驗需要17個步驟，用CV只需要3個步驟，而對於無法做量子糾錯的時代步驟是愈短愈好；其次是CV-QML不需要QPE，所以繞過了在Shor/Grover中都無法輕易轉換成CV演算法的窘境，這類演算法的精神是結合「量子態算符化」 與Displacemnt Operator達到從矩陣中提取資訊的目標．我以CV-QPCA為例做個原創譬喻，要讓量子系統進入疊加態不難，但是要如何讓比較大的eignvalue有比較大的機會被測量到才是挑戰（壓縮想要的資料）：想像是有一顆六面骰子（一組疊加態），五面都是1只有一面是100，為了做資料壓縮我們只想保留最大的那個數子，但是如果這顆骰子是公平的骰子那我們就沒戲唱（觀察塌陷獲得正確答案的機會只有1/6），不過透過CV-QPCA可以讓「骰面出現的機率」和「骰面的數字」成正比（不公平骰子），也就是說摋同一面骰子獲得正確答案的機會有100/105這麼高，這基本上是QPCA/HHL 在CV系統中的精神：）
感謝大家看到這邊，您的閱讀、分享、回應與訂閱是我繼續寫文章的動力，如果看到有任何疑問（或是錯誤）可以私信我或者直接留言，要不是剛好在資格考完心情大好、比較有空，這篇文章應該永遠不會寫出來 ，也相信你現在對這個領域的概念有點認識也知道媒體底有多hype（笑．