基于FPGA的量子Fourier變換模擬器的設(shè)計(jì)與實(shí)現(xiàn)

◆張 磊 牛云波

?

基于FPGA的量子Fourier變換模擬器的設(shè)計(jì)與實(shí)現(xiàn)

◆張 磊1牛云波2

（1.中國(guó)電子科技集團(tuán)第三十研究所 四川 610041；2.中國(guó)人民解放軍96901部隊(duì) 北京 100000）

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

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

0 引言

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

目前，一般使用軟件模擬來驗(yàn)證基于QFT的量子算法，但是軟件模擬是按順序執(zhí)行[6]，無法有效地模擬量子系統(tǒng)固有的并行的特點(diǎn)和優(yōu)勢(shì)，此外，軟件模擬的復(fù)雜度隨量子位的數(shù)量的增加呈指數(shù)級(jí)增長(zhǎng)[7]。然而，基于FPGA的硬件模擬可以很好地解決上述問題，因?yàn)镕PGA硬件平臺(tái)具有并發(fā)處理和可重構(gòu)特點(diǎn)[8]，非常適用于根據(jù)待解決的問題來調(diào)整QFT的量子位和運(yùn)算速度。

本文論述了一種基于FPGA的QFT硬件模擬器的設(shè)計(jì)與實(shí)現(xiàn)。由于QFT硬件模擬設(shè)計(jì)結(jié)構(gòu)易于多量子位可重構(gòu)的優(yōu)勢(shì)，可以用于量子計(jì)算、量子信息、量子通信、量子模擬、量子密碼和量子測(cè)量等研究領(lǐng)域。本文的內(nèi)容安排如下：第一部分介紹了量子計(jì)算的理論；第二部分闡述QFT算法和體系結(jié)構(gòu)；第三部分詳細(xì)論述了QFT硬件模擬器的設(shè)計(jì)部分；第四部分給出了 FPGA設(shè)計(jì)的綜合結(jié)果；第五部分中總結(jié)和展望今后的工作。

1 量子信息和量子計(jì)算

1.1 量子信息的表達(dá)

1.2 量子門和量子電路

如同經(jīng)典計(jì)算采用邏輯門構(gòu)建電路一樣，量子計(jì)算也采用量子門組成量子電路。量子門在數(shù)學(xué)上表達(dá)成unitary矩陣，實(shí)際上，任何一個(gè)unitary矩陣都是一個(gè)有效的量子門。

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

2 量子Fourier變換的分析

2.1 量子Fourier變換的數(shù)學(xué)分析

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

2.2 量子Fourier變換的優(yōu)勢(shì)和挑戰(zhàn)

盡管上述的量子Fourier變換目前還不能實(shí)現(xiàn)，但是QFT模擬在下述的算法中發(fā)揮重要作用，因此QFT模擬器的設(shè)計(jì)和實(shí)現(xiàn)將變得很有意義。

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

（2）Shor素因數(shù)分解算法:該算法能夠以指數(shù)級(jí)速度快速查找一個(gè)非常大的n位整數(shù)的素?cái)?shù)因子。

（3）Shor離散對(duì)數(shù)算法:該算法是密碼學(xué)的基礎(chǔ)，特別適合解決如下問題，當(dāng)表達(dá)式b=as中a和b已知時(shí)，求解s。

（4）特征選擇算法:該算法模式識(shí)別和圖像識(shí)別，處理特征選擇任務(wù)的速度比經(jīng)典算法要快。

3 量子Fourier變換的硬件模擬器的設(shè)計(jì)

圖1 Block diagram of QFT circuit architecture

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

量子Fourier變換電路中的量子門，基于硬件設(shè)計(jì)時(shí)會(huì)用到基本的運(yùn)算模塊，如加法器、減法器和乘法器，實(shí)現(xiàn)Hadamard門需要4個(gè)加法器和4個(gè)乘法器；而受控相移門需要2個(gè)加法器和4個(gè)乘法器。

4 量子Fourier變換硬件模擬器的結(jié)果

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

表1總結(jié)了量子位qubits從2位到16位的pipeline架構(gòu)P和without pipeline架構(gòu)WP的FPGA設(shè)計(jì)的綜合結(jié)果，包括所用的LUTs、寄存器和DSP塊的資源和電路可達(dá)的最大頻率。

表1 FPGA synthesis summary

5 結(jié)束語(yǔ)

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

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

[2]張英俏.基于光纖連接的腔系統(tǒng)實(shí)現(xiàn)兩比特離散量子傅立葉變換[J].延邊大學(xué)學(xué)報(bào), 2012.

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

[4]張洪濤, 熊紅梅, 凃玲英.量子Fourier變換在實(shí)現(xiàn)Deutsch-Jozsa算法中的應(yīng)用[J].華僑大學(xué)學(xué)報(bào), 2016.

[5]唐小川.分布式量子計(jì)數(shù)算法研究[D].東北大學(xué), 2012.

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

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

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