基于奇異值分解的矩陣低秩近似量子算法*

王芙蓉 楊帆 張亞 李世中 王鶴峰

1) (中北大學機電工程學院, 太原 030051)

2) (清華大學物理系, 北京 100084)

3) (西安交通大學理學院, 西安 710049)

在大數據時代, 高效的數據處理至關重要, 量子計算具有平行計算能力, 為方便處理數據提供了新的解決途徑.本文提出了一個基于奇異值分解的矩陣低秩近似量子算法, 復雜度為 O [log(pq)].在核磁共振量子計算系統完成了算法的原理演示, 選擇一個 8 ×8 維的圖像矩陣, 實現共振躍遷算法的哈密頓量 H 的時間演化,用量子態層析法分別讀出密度矩陣的不同成分, 對密度矩陣進行重構, 保真度為99.84%, 在誤差范圍內驗證了本文提出的矩陣低秩近似量子算法的正確性.而通過奇異值分解計算低秩矩陣的經典算法的復雜度是O[poly(pq)], 量子算法與經典算法相比, 實現了指數加速.

1 引 言

隨著互聯網的技術不斷提高, 大數據時代正在到來.矩陣作為處理大數據的基本工具之一, 常被用于解決許多實際問題.大多數情況下, 矩陣表示在空間和時間復雜度上會隨著數據的規模呈二次方增長, 這導致數據處理困難.因此, 去除冗雜信息, 只保留有用的信息, 構造低秩矩陣, 快速高效地近似一個目標矩陣, 可提高機器學習和數據管理的效果.目前, 低秩矩陣已被廣泛用于模式識別[1]、圖像壓縮和檢測[2,3]、圖像處理[4,5]、人臉識別[6]等應用領域.

矩陣的低秩近似是一種稀疏表示形式, 可以在保持原矩陣的諸多性質同時, 減少冗余和噪聲, 降低了數據的存儲空間和……