基于FPGA的量子Fourier變換模擬器的設計與實現

◆張 磊 牛云波

?

基于FPGA的量子Fourier變換模擬器的設計與實現

◆張 磊1牛云波2

（1.中國電子科技集團第三十研究所 四川 610041；2.中國人民解放軍96901部隊 北京 100000）

量子Fourier變換是次序查找、相位估計和素因數分解等量子算法中的核心運算，作用極其重要。目前針對量子Fourier變換的研究大多都是基于軟件模擬進行的，但是軟件模擬不能有效地模擬和發揮實現量子算法的并行運算的特點和優勢。為解決該問題，本文提出了一種基于FPGA設計和實現了量子Fourier變換的硬件模擬器。該設計充分利用FPGA硬件并行處理的特點，采用模塊化的設計思想，并能夠推廣至多量子位的量子Fourier變換的模擬設計。

量子Founer變換；量子算法；量子電路；量子模擬

0 引言

量子Fourier變換(Quantum Fourier Transform, QFT)對于一些重要的量子算法如次序查找[1]、素因數分解[2]、特征選擇[3]等至關重要，也是量子計算機中的量子態的線性變換的重要運算單元。量子Fourier變換可以應用于破解RSA密碼的密鑰[4]，發現蛋白質和核酸等大分子的能量譜[5]。

目前，一般使用軟件模擬來驗證基于QFT的量子算法，但是軟件模擬是按順序執行[6]，無法有效地模擬量子系統固有的并行的特點和優勢，此外，軟件模擬的復雜度隨量子位的數量的增加呈指數級增長[7]。然而，基于FPGA的硬件模擬可以很好地解決上述問題，因為FPGA硬件平臺具有并發處理和可重構特點[8]，非常適用于根據待解決的問題來調整QFT的量子位和運算速度。

本文論述了一種基于FPGA的QFT硬件模擬器的設計與實現。由于QFT硬件模擬設計結構易于多量子位可重構的優勢，可以用于量子計算、量子信息、量子通信、量子模擬、量子密碼和量子測量等研究領域。本文的內容安排如下：第一部分介紹了量子計算的理論；第二部分闡述QFT算法和體系結構；第三部分詳細論述了QFT硬件模擬器的設計部分；第四部分給出了 FPGA設計的綜合結果；第五部分中總結和展望今后的工作。

1 量子信息和量子計算

1.1 量子信息的表達

1.2 量子門和量子電路

如同經典計算采用邏輯門構建電路一樣，量子計算也采用量子門組成量子電路。量子門在數學上表達成unitary矩陣，實際上，任何一個unitary矩陣都是一個有效的量子門。

與經典邏輯門不同的是，量子門是可逆的，這意味著，只要知道輸出qubit的值，就有可能知道輸入qubit的值。因此，輸入和輸出的qubit的位數必須相同。量子Fourier變換所使用的一些量子門描述如下:

2 量子Fourier變換的分析

2.1 量子Fourier變換的數學分析

量子Fourier變換是一個unitary變換，在數學上，從式(6)可以得到如下式(7):

2.2 量子Fourier變換的優勢和挑戰

盡管上述的量子Fourier變換目前還不能實現，但是QFT模擬在下述的算法中發揮重要作用，因此QFT模擬器的設計和實現將變得很有意義。

（1）相位估計算法:該算法在量子化學的研究中具有重要作用，可以加速分子軌道能量的計算。

（2）Shor素因數分解算法:該算法能夠以指數級速度快速查找一個非常大的n位整數的素數因子。

（3）Shor離散對數算法:該算法是密碼學的基礎，特別適合解決如下問題，當表達式b=as中a和b已知時，求解s。

（4）特征選擇算法:該算法模式識別和圖像識別，處理特征選擇任務的速度比經典算法要快。

3 量子Fourier變換的硬件模擬器的設計

圖1 Block diagram of QFT circuit architecture

如圖1所示的電路圖為QFT硬件模擬電路的通用架構，qubit的位數和pipeline的深度，都被設置為parameter類型，用戶可以根據需要修改。該電路架構包括QFT量子運算單元，輸入端的寄存器組reg[n:1]，輸出端的多路復用器MUX和測試用的計數器counter。

量子Fourier變換電路中的量子門，基于硬件設計時會用到基本的運算模塊，如加法器、減法器和乘法器，實現Hadamard門需要4個加法器和4個乘法器；而受控相移門需要2個加法器和4個乘法器。

4 量子Fourier變換硬件模擬器的結果

本文應用Verilog HDL語言設計量子Fourier變換硬件模擬器，并在Xilinx Kintex-7系列的型號為XC7K410TFFG900的FPGA芯片上進行了綜合編譯。量子Fourier變換硬件設計充分使用FPGA內部集成的IP核，主要是使用18-bits DSP塊和分布式存儲器。例如，如果受控相移量子門的一部分映射到復數乘法器，那么每個受控相移量子門需要的DSP塊的數量就從6減少至4。

表1總結了量子位qubits從2位到16位的pipeline架構P和without pipeline架構WP的FPGA設計的綜合結果，包括所用的LUTs、寄存器和DSP塊的資源和電路可達的最大頻率。

表1 FPGA synthesis summary

5 結束語

本文研究了量子Fourier變換硬件模擬設計的通用架構，并且在Xilinx FPGA芯片上綜合編譯和驗證。該硬件模擬的通用架構可以很容易擴展增加待處理qubits的數量，非常適合基于QFT的新型量子算法的研究與開發。未來的工作是采用分組量子門來硬件模擬量子疊加態和糾纏態的量子Fourier變換。

[1]王平平, 陸正福, 楊春堯.整數分解量子算法[J].通信技術, 2017.

[2]張英俏.基于光纖連接的腔系統實現兩比特離散量子傅立葉變換[J].延邊大學學報, 2012.

[3]楊帆. 量子傅里葉在圖像處理中的應用研究[D].武漢理工大學, 2013.

[4]張洪濤, 熊紅梅, 凃玲英.量子Fourier變換在實現Deutsch-Jozsa算法中的應用[J].華僑大學學報, 2016.

[5]唐小川.分布式量子計數算法研究[D].東北大學, 2012.

[6]Song Jun.Joint Wavelet-Fractional Fourier Transform[J]. Chinese Physics Letters,2016.

[7]王保松, 張丙云. 量子力學中的傅立葉變換算符[J].吉林師范大學學報,2016.

[8]Olalla, Carlos, Leyva, et al.Digital QFT robust control of DC-DC current-mode converters[J].Electrical Engineering, 2013.