李綠周，量子計算研究要“軟硬兼施”，《中國科學報》 (2020-05-07 第3版 信息技術)
http://news.sciencenet.cn/sbhtmlnews/2020/5/354996.shtm
注：引用請注明以上出處，全文如下：
近年來，量子計算受到了極大關注，根本原因在于其具有強大的并行性，可以在有效時間內解決一些經典計算機不能有效解決的問題。
然而，量子計算的并行性并非直接可以利用，而是需要根據所解決的問題經過巧妙的算法設計才可能。即便量子計算機硬件研制成功，如果沒有相應的量子算法，量子計算的潛能還是得不到實質性發揮。因此，要想利用量子計算解決實際問題，能否設計出快速的量子算法是關鍵。當然，量子算法需要運行在量子計算硬件平臺上才能起作用。
因此，量子計算研究要“軟硬兼施”。
量子算法的歷史階段
量子算法的第一階段（1985-1994），我們稱之為初始階段，其特點是為量子而問題，即為了展示量子計算優勢而構造了一些數學問題并為之設計量子算法，這些問題在當時可能并沒有多少實用價值。
最早的量子算法可以追溯到1985年的Deutsch算法。1985年David Deutsch在其關于量子圖靈機的開創性論文中給出了一個簡單問題，并為之設計了一個量子計算過程，通過利用量子疊加和干涉現象展現出了量子計算可能超越經典計算的優勢，這為后續量子算法設計埋下了思想的種子。
雖然今天看來，Deutsch算法非常簡單，甚至會覺得一切都是理所當然的，但是在那前無古人的年代把第一個量子算法雛形設計出來是非常需要洞察力和創造力的。后來的Deutsch-Jozsa算法、Simon算法等進一步考慮更復雜的問題并在某種意義下展現出了量子計算相對于經典計算的指數加速優勢。
Simon算法可能是一個有點被外界忽略的量子算法。事實上該算法的意義至少有以下兩方面：一方面Simon算法直接啟發了著名的Shor算法的發現，這一點無論是在Shor算法的原文還是在一些知名學者寫的量子計算方面的書里都有非常明確地指出來；另一方面Simon算法近年在密碼破譯方面得到直接應用。
量子算法的第二階段（1994-2009），我們稱之為質變階段，其特點是為問題而量子，即針對具有重要應用價值的問題而設計量子算法。1994年，Shor算法展示了大數分解問題可以被量子計算機在多項式時間內解決，而該問題在經典計算機下的難解性是RSA公鑰密碼系統安全性的理論基礎。隨后，1996年Grover發現了無序數據庫搜索的平方加速量子算法，使得在無序數據庫中“大海撈針”成為可能。
由于這些算法所解決的問題具有廣泛的應用價值，因而備受關注，從而也大大推動了整個量子計算領域的發展。后續不少研究就是聚焦于如何把以上兩個算法映射到更多具有實際價值的問題。另外，此階段提出的量子游走也是一類進行量子算法設計的重要工具。
量子算法的第三個階段（2009-至今），我們稱之為新的發展階段，其特點是面向大數據環境。2009年解線性方程組量子算法（HHL算法）的提出標志著量子算法進入了第三階段。或許HHL算法并不能與Shor算法或Grover算法媲美，但是在大家苦苦等待新的量子算法出現達10多年之久，HHL算法不失為量子算法設計提供了一條新路徑，它或許是把量子模擬應用于數據處理的范例。
由于人工智能與大數據領域的諸多方法和技術都與解線性方程組有關，因此HHL算法的提出大力推動了量子計算進入機器學習與大數據處理等領域。量子計算與AI的結合近幾年成為熱點話題，圖靈獎得主姚期智先生也多次在報告中提及，這方面的交叉研究值得進行深入探索。
量子算法的問題思考
HHL算法并未把方程組的解以經典可讀取的方式呈現出來，而是把其編碼在量子態中，需要經過后續的算法設計來提取我們想要的信息。近年來出現的不少有關量子機器學習的研究主要就是基于HHL算法做后續算法設計。
目前一些量子機器學習方面的研究需要提供更嚴肅的理論分析。量子機器學習如果要面對實際數據處理問題，有待突破輸入/輸出瓶頸。所謂輸入/輸出瓶頸是指，大部分量子機器學習算法或者需要把大規模數據集編碼為量子態，或者只是把問題的解生成在量子態中，因此輸入階段的前處理和信息提取階段的后處理將耗費大量時間，乃至抵消量子算法所節省的時間。
近期，華裔學生Ewin Tang受量子推薦算法的啟發設計出了一個經典算法，它能以和量子算法相近的速度解決推薦問題，從而使得受量子啟發的經典算法設計或者說量子算法的經典化進入了更多學者的視野。如果量子算法思維能促進經典算法的發展，這也將是量子計算研究意義的另一種體現。
筆者梳理了有關量子算法的兩個常見問題和回答，以供參考。
問：量子計算機還沒造出來，現在有必要研究量子算法嗎？
答：首先，從經典計算領域來看，算法的研究遠遠早于計算機的出現。歐幾里德算法出現在古希臘時代，而第一臺電子計算機是1946年生產的。另外，圖靈機的提出正是為了嚴格地刻畫“算法”。
其次，沒有算法支持的量子計算機還能稱為計算機嗎？量子算法是量子計算機的必要軟件支撐，同時量子算法的研究也是推動量子計算向前發展的強大動力，從Shor算法的歷史地位可見一斑。所以研究量子算法也是研制量子計算機的重要環節之一。
問：沒有量子計算機，怎么研究量子算法？怎么評價算法的好壞？
答：抽象層次的算法設計從來不依賴于具體硬件平臺，在經典計算領域就是如此。算法本質上是解決問題的一種方法，量子算法是遵循量子力學規律的一種方法。硬件平臺只是實現這種方法的一個工具。當然，軟硬件之間的互動與交流對于設計更符合實際情況的算法非常必要。
從算法與復雜性研究的角度來看，算法的好壞由復雜度衡量，這依賴于嚴格的數學證明，而不是在具體硬件平臺上的測試。目前量子算法主流的研究是如此。
隨著量子計算實驗技術的發展，有越來越多的量子算法得以在真實量子平臺上進行原理性驗證。可能有時研究者會在經典計算機上對量子算法進行一定模擬以加深理解，但那并非在經典計算機實現了量子算法。
千里之行始于足下
量子計算相對與經典計算在哪些方面有優勢？有多大程度的優勢？這些問題目前遠未搞清楚，這意味著量子算法的研究有非常大的空間。大家都期待量子計算領域有更多具有創新性的算法出現，每一位量子算法研究者也都希望設計出一個代表性算法。
然而，羅馬不是一天建成的，千里之行始于足下。我們不應只記住Shor算法的巧妙，而忘記前人的努力。事實上，Shor算法是站在Simon算法的肩上，而Simon算法源于那些看似沒用的Deutsch-Jozsa算法和Deutsch算法。
這個過程正好體現了科學研究的魅力：或許很多研究成果會被大浪淘沙，但正是那些一點一滴的看似無用的研究，一步一步孕育著一個新的發現。
10131
0
2020-11-04
