近日，我國科學家同時實現了機器學習和通信複雜度的量子優越性。南京大學物理學院、固體微結構物理國家重點實驗室、人工微結構科學與技術協同創新中心尹華磊、陳增兵課題組，首次實驗證明了量子技術可以為機器學習提供具有量子優勢的學習算法，並設計出量子版本的盲盒遊戲，驗證了量子優惠券理論的潛在應用價值。

相關成果發表在美國《科學》(Science)雜誌首個合作期刊《Research》。

圖片來自《Research》

機器學習可以從數據中提取有用的信息與知識，從而對基礎理論、先進技術和社會生產力等方面產生重大影響。精確調控量子態技術在通信安全、計算速度和測量精度等方面已展現出超越經典技術的量子優勢。通過利用量子技術來改進機器學習或實現量子機器學習是近年來研究熱點，已有大量研究工作開展了創新性探索。

然而，此前的嘗試大多為啟發式的，並未從理論上證明量子機器學習比經典機器學習表現出更好的性能或擁有更短的訓練時間。“可能近似正確”(PAC)學習理論量化了一個學習算法能夠有效學習一個任務所需的最小樣本數。因此，利用此理論研究量子機器學習，可為探索機器學習中的量子優勢奠定理論基礎。

2020年，荷蘭阿姆斯特丹大學研究團隊和美國IBM公司研究團隊共同提出量子優惠券收集問題，並用PAC學習理論首次嚴格證明了該問題存在具有量子優勢的學習算法。具體來說，所有希望學習到的目標函數所構成的集合稱為“概念類”，並給定一個學習算法，它所考慮的所有可能映射的集合稱為“假設空間”。若在PAC學習中，假設空間和概念類完全相同，即為恰PAC可學習(properly PAC learnable)，否則為不恰PAC可學習(improperly PAC learnable)。

一般來說，經典恰和不恰PAC可學習的樣本複雜度是不一樣的。然而，對於優惠券收集問題來說，恰和不恰PAC可學習所需的樣本複雜度在量子算法下是可以相同的。因此，量子優惠券收集算法是首個依據PAC學習理論展現經典和量子機器學習之間存在根本性不同的算法。

優惠券收集問題，圖片來自vcubingx

原始的量子優惠券算法的實驗演示需要用到高度複雜的單光子量子指紋態，以及遠超當前實驗技術的高度非線性測量裝置，以實現超高維的半正定算子測量(POVM)。

此次，尹華磊、陳增兵課題組提出相干態量子優惠券協議，巧妙地將單光子量子指紋態轉換為等效的相干態張量積形式，將單光子在維數上的振幅信息轉換為相干態在時間箱上的相位信息，藉此成功使用線性光學量子技術實驗演示了量子優惠券收集任務，利用PAC學習理論，首次實驗證明了量子技術可以為機器學習提供具有量子優勢的學習算法。

團隊從理論證明了相干態量子優惠券與原始量子優惠券在機器學習量子優勢方面的等價性，從而實現了利用當前廣泛使用的光量子通信技術（激光器、線性光學元器件和單光子探測器）來演示量子優惠券收集任務。

實驗中需要最大限度地降低量子態干涉測量的噪聲，包括：利用薩格納克(Sagnac)干涉儀實現穩定的時間和相位對準；利用高精度的相位調製技術實現高速相位精確製備；利用高對稱的保偏分數器實現偏振和強度對準；利用高效率和超低暗計數的超導納米線單光子探測器實現近似完美測量。基於這些實驗技術，團隊最終清晰地演示了機器學習的量子優越性。

量子優惠券實驗結果圖，圖片來自南京大學物理學院

為了進一步展示量子優惠券理論的潛在應用價值，團隊針對年輕人喜愛的盲盒遊戲，設計了其量子版本並成功進行了實驗演示，充分展示了量子優惠券理論的潛在應用價值和量子技術在通信複雜度上的優勢。

在盲盒遊戲中，商家將不同圖案的小球分別裝進不同盒子裡形成盲盒，並從中挑選幾乎全部盒子作為盲盒套裝，並製作了相同配置的多套盲盒套裝。顧客只能在每套盲盒套裝中抽取一個盲盒，來確認整套盲盒套裝中所有小球的圖案。顧客每消耗一套盲盒套裝就需要支付一定數額費用，若顧客猜對，商家就會獎勵給顧客獎金，獎金的數額為經典策略下所消耗盲盒套裝費用的期望值。

使用量子資源對盲盒進行編碼，顧客就可以通過設計量子編碼和量子測量來降低自己的成本，從而在遊戲中獲得更多回報。量子優惠券實驗結果表明，量子協議可以有效地減少學習具有多達14000個元素的優惠券所需的樣本數量。量子盲盒遊戲實驗結果表明，針對不同類型的盲盒套裝，顧客總可以通過選擇合適的光強（發光強度）來降低成本以獲得更多的回報，這說明量子優惠券協議在這種遊戲中消耗的資源少於最優經典策略。

量子盲盒遊戲實驗結果，圖片來自南京大學物理學院

前述實驗結果有力證明了即使沒有使用多粒子糾纏態和量子門操控，僅僅利用線性光學的量子技術，就可以在機器學習和通信複雜度方面，實現相對於經典技術的量子優越性。

論文共同第一作者為南京大學物理學院研究生周民罡、曹嘯宇和陸玉碩，通信作者為南京大學副教授尹華磊和教授陳增兵。前述工作獲得國家自然科學基金、江蘇省自然科學基金、中央高校基本科研業務費、南京江北新區重點研發計劃等支持。