一種求倒數(shù)近似值的量子算法及其量子電路

朱家良，葉 賓，季 雯

(中國礦業(yè)大學(xué) 信息與控制工程學(xué)院，江蘇 徐州 221116)

0 引 言

量子計算以其獨(dú)特的并行計算特性，在機(jī)器學(xué)習(xí)、高維數(shù)據(jù)挖掘、大數(shù)據(jù)處理、圖像處理等領(lǐng)域有著巨大優(yōu)勢[1-4]。和傳統(tǒng)的數(shù)字計算相比較，量子計算顯著減少了執(zhí)行時間和能耗[5]。量子計算機(jī)的基本存儲單元是量子比特，一個量子比特可表示量子態(tài)|0〉和|1〉的疊加，因此一次運(yùn)算就可同時處理兩個基態(tài)。處理2n狀態(tài)的信息，n個量子比特僅需一次操作，遠(yuǎn)快于2n個經(jīng)典比特所需的2n次操作[6]。正因如此，量子計算能夠指數(shù)級加速傳統(tǒng)算法，被認(rèn)為是解決算力不足的有效方法之一。

求取一個無符號數(shù)的倒數(shù)在求解量子線性系統(tǒng)、量子相位估計、量子支持向量機(jī)等領(lǐng)域有著廣泛的應(yīng)用。在傳統(tǒng)算法中常用牛頓迭代法、割線法等求取倒數(shù)的近似值，但是需要多次的迭代計算。量子計算的特性可以顯著降低牛頓迭代計算的問題規(guī)模。Cao[7]于2007年首次提出了一種基于牛頓迭代法近似求取正整數(shù)倒數(shù)的量子線路，但其耗費(fèi)輔助量子比特較多，線路結(jié)構(gòu)復(fù)雜。該文提出一種更簡潔的近似求取無符號數(shù)倒數(shù)的量子算法，此算法以基本的量子全加器[8-9]和量子乘法器[10-11]為基礎(chǔ)模塊，通過少量輔助寄存器進(jìn)行連接，經(jīng)過移位操作等搭建出量子電路。經(jīng)過分析，其時間復(fù)雜度為O(n3)，空間復(fù)雜度為O(2n3)，具有量子代價小、結(jié)構(gòu)簡單等特點(diǎn)，有利于降低構(gòu)造量子電路的成本及物理實(shí)現(xiàn)難度。

1 量子邏輯門基礎(chǔ)

量子計算中的基本單位量子比特(qubit)與經(jīng)典計算機(jī)中的比特(bit)相對應(yīng)，單量子比特的狀態(tài)為2個基態(tài)相疊加的形式[12]:|φ〉=α|0〉+β|1〉，其中α和β均為復(fù)數(shù)，滿足|α|2+|β|2=1。

與經(jīng)典計算機(jī)中的邏輯門類似，量子計算中的計算單元由量子邏輯門組成，它們在數(shù)學(xué)上是一個幺正變換和酉變換，并且這個變換是可逆的，在此介紹幾種常用的量子邏輯門：

非(NOT)門，是一個單量子門，量子電路符號如圖1(a)所示，它的作用是實(shí)現(xiàn)量子態(tài)從|0〉向|1〉的翻轉(zhuǎn)。

受控非(CNOT)門[13]，是一個雙量子邏輯門，由控制位和目標(biāo)位組成。如圖1(c)所示，它的作用是若控制位的量子態(tài)為|0〉，則目標(biāo)位上的量子態(tài)不發(fā)生翻轉(zhuǎn)；反之，若控制位量子態(tài)為|1〉，目標(biāo)位上的量子態(tài)發(fā)生翻轉(zhuǎn)。

Toffoli門[14]，是一個三量子比特門，由兩個控制位和一個目標(biāo)位組成。如圖1(d)所示，僅當(dāng)控制位|a〉和|b〉都為|1〉時，目標(biāo)位|c〉中的狀態(tài)發(fā)生翻轉(zhuǎn)，否則不發(fā)生變化。

圖1 量子邏輯門

測量門，將量子比特投影到經(jīng)典比特中，實(shí)現(xiàn)觀測。如圖1(e)所示輸入為處于疊加態(tài)的量子位，輸出投影到|0〉和|1〉下的概率幅度。

2 量子乘法器的實(shí)現(xiàn)

2.1 量子半加器

n位的量子全加器是由n個半加器組成的，該文設(shè)計的半加器包括1個Toffoli門和2個CNOT門，如圖2所示。其中|a〉和|b〉是輸入的二進(jìn)制數(shù)，|0〉是輔助量子位，結(jié)果存儲在|sum〉中，|cout〉是進(jìn)位。

半加器的過程如下：

|a〉|b〉|0〉|0〉→|a〉|b〉|sum〉|cout〉

(1)

輔助量子位輸出：

|0〉|0〉→|sum〉|cout〉

(2)

|sum〉=|a⊕(b⊕0)〉

(3)

|cout〉=|ab⊕0〉

(4)

圖2 量子半加器

2.2 n位量子全加器

量子全加器是量子乘法器實(shí)現(xiàn)的基礎(chǔ)。2002年，Cheng Kai-Wen[8]首次完善了量子全加器和量子全減器的電路圖。常麗等人[9]于2019年采用了超前進(jìn)位方式，簡化了量子全加器的結(jié)構(gòu)。在此基礎(chǔ)上，該文根據(jù)全加器的邏輯表達(dá)式設(shè)計出單比特的量子全加器電路圖，如圖3(a)所示(圖3(b)為其簡化圖)。然后將多個單比特的量子全加器組合，得到n比特量子全加器，如圖3(c)所示。

|si〉=|ai⊕bi⊕ci-1〉

(5)

|ci〉=|aibi⊕(ai⊕bi)ci-1〉

(6)

其中，|ai〉是一個二進(jìn)制數(shù)a的第i位，|bi〉是另一個二進(jìn)制數(shù)b的第i位，|c〉是進(jìn)位c的第i位，|si〉是a與b之和的第i位。

(a)單比特量子全加器電路圖

(b)圖(a)的簡化圖

(c)n比特量子全加器電路圖

2.3 量子乘法器

目前大多數(shù)的量子乘法器是在一個n量子比特的寄存器中輸入|a〉1=|an-1〉1?|an-2〉1?…?|a0〉1來表示整數(shù)a=2n-1an-1+2n-2an-2+…+20a0;在另一個n量子比特的寄存器中輸入|b〉2=|bm-1〉2?|bm-2〉2?…?|b0〉2來表示整數(shù)b=2m-1bm-1+2m-2bm-2+…+20b0;第三個l量子比特的寄存器用來存放前兩個寄存器中的數(shù)相乘的結(jié)果，其狀態(tài)為|c〉3=|cl-1〉3? |cl-2〉3?…?|c0〉3，其中c=2l-1cl-1+ 2l-2cl-2+…+20c0。經(jīng)過量子乘法器運(yùn)算后各寄存器中的數(shù)值改變?nèi)缦拢?/p>

|a〉1|b〉2|c〉3→|a〉1|b〉2|c+abmod2l〉3

(7)

最后通過測量第三個量子寄存器，將其讀數(shù)寫入經(jīng)典寄存器來得到兩數(shù)相乘的結(jié)果[15-17]。

2.4 量子乘法器的移位實(shí)現(xiàn)

在實(shí)現(xiàn)量子乘法運(yùn)算的過程中，最重要的一步就是對乘數(shù)進(jìn)行移位相加，例如實(shí)現(xiàn)110和111的乘積，其實(shí)現(xiàn)步驟見圖4(a)。由其規(guī)律可知，部分積之間的相加要實(shí)現(xiàn)左移操作，即在量子計算機(jī)上實(shí)現(xiàn)移位寄存器。文獻(xiàn)[10]中設(shè)計的量子乘法器完善了移位寄存器的功能，算法整體的時間復(fù)雜度為o(n2)，空間復(fù)雜度為o(n2)。Suzuki[11]在2020年提出的量子乘法器的時間復(fù)雜度和空間復(fù)雜度都較低，但是結(jié)構(gòu)復(fù)雜。該文運(yùn)用對寄存器低位置零的操作達(dá)到移位寄存器的效果，擁有結(jié)構(gòu)簡單、復(fù)雜度低等優(yōu)點(diǎn)。具體步驟如下：

(8)

如圖4(b)所示，將圖4(a)中部分積的低位置零，再與高位相加，即可實(shí)現(xiàn)與移位同樣的效果，110與111相乘的部分積低位置零后表示為：

(9)

分析可知，此方法耗費(fèi)寄存器的空間復(fù)雜度僅為O(2n-1)(n為兩個乘數(shù)中位數(shù)較大的二進(jìn)制數(shù)的位數(shù))。

圖4 置零乘法的實(shí)現(xiàn)步驟

2.5 量子乘法器的實(shí)現(xiàn)

下面按照圖3(b)中所示的乘法計算過程，將輸入寄存器、置零寄存器、全加器，以及輸出寄存器(包含量子寄存器和經(jīng)典寄存器)合并以設(shè)計出完整的量子乘法器。

如圖5所示，輸入寄存器中的n位二進(jìn)制數(shù)|a〉1=|a〉1?|a〉2?…?|a〉n和m位二進(jìn)制數(shù)|b〉2=|b〉1?|b〉2?…?|b〉m相乘，將部分積 |a0bt〉，|a1bt〉…|anbt〉，(t=0,1,…,m-1)的結(jié)果分別存放在置零寄存器:

|0〉0=|0〉0?…?|0〉t0?…?|0〉m-1(t0=0),

|0〉1=|0〉0?…?|0〉t1?…?|0〉m-1(t1=1)

?

|0〉l=|0〉0?…?|0〉tl?…?|0〉m-1(tl=n,l=2×max(n,m))上(第s個置零寄存器從第ts位開始存放，s=0,1,…,n)；再將置零寄存器與全加器相連，依次求出部分積|0〉0，|0〉1，…，|0〉l的和(此過程中可以通過對|0〉s寄存器逐個清零來減少寄存器的使用，大大降低空間復(fù)雜度)，并將結(jié)果存放在寄存器|c〉3=|c0〉3?…?|cl〉3中(l=2×max(n,m))；最后通過測量將量子寄存器上的信息轉(zhuǎn)化至經(jīng)典寄存器c上，實(shí)現(xiàn)結(jié)果的觀測。

圖5 量子乘法器電路圖

2.6 量子乘法器復(fù)雜度分析

為了驗(yàn)證算法的有效性，該文用通用量子門作為時間單元，輔助量子比特作為空間單元，分析基于牛頓迭代法的量子倒數(shù)器的時間復(fù)雜度以及空間復(fù)雜度。

首先是時間復(fù)雜度的分析。對于n位二進(jìn)制數(shù)乘以m位二進(jìn)制數(shù)，該文改進(jìn)的量子乘法器線路如圖5所示。在量子乘法器中，首先是用Toffoli門進(jìn)行各位二進(jìn)制數(shù)的相乘操作，需要mn個Toffoli門。隨后將輔助量子寄存器中的數(shù)進(jìn)行相加，由圖3(a)可知，一個比特的量子全加器由2個Toffoli和5個CNOT門組成，因此n比特的量子全加器需要7n個通用量子門。進(jìn)行m次加法操作，因此需要用7mn個通用量子門。因此整個乘法器需要用到8mn個通用量子門，時間復(fù)雜度為O(mn)。若計算的二進(jìn)制數(shù)都是n位，則時間復(fù)雜度為O(n2)。

其次是空間復(fù)雜度的分析。由圖5所知，對于n位二進(jìn)制數(shù)乘以m位二進(jìn)制數(shù)(m>n)，需要m+n個輸入寄存器來儲存輸入的二進(jìn)制數(shù)。一個輔助量子寄存器需要m個量子比特，m個輔助量子寄存器一共需要2m2量子比特。所以量子乘法器一共需要2m2+m+n個量子比特，時間復(fù)雜度為O(m2)。若計算的二進(jìn)制數(shù)都是n位，則時間復(fù)雜度為O(n2)

該量子乘法器需要用到8mn個通用量子門，時間復(fù)雜度為O(n2)(m=n時)。所需量子寄存器的數(shù)量是2m2+m+n，空間復(fù)雜度為O(n2)(m=n時)。

3 求倒數(shù)近似值的量子算法及其量子電路

3.1 牛頓迭代法

根據(jù)牛頓迭代公式：

(10)

若求取已知數(shù)λ的倒數(shù)，則令函數(shù)f(x)為：

(11)

對f(x)求導(dǎo)得：

f(x)'=-x-2

(12)

聯(lián)立式(6)～式(8)可得：

(13)

其中,λ為所求倒數(shù)的原數(shù)，要求滿足λ>1；x0為滿足x0>0且與λ-1相近的二進(jìn)制數(shù)。圖6為牛頓迭代法的電路圖。

圖6 利用牛頓迭代法求倒數(shù)的電路圖

3.2 求倒數(shù)近似值的量子算法及其量子電路實(shí)現(xiàn)步驟

按照式(9)與圖6的系統(tǒng)圖，利用3個量子乘法器和2個量子全加器可設(shè)計出單步牛頓迭代法對應(yīng)的量子電路，然后將每一步的迭代電路相連實(shí)現(xiàn)整個迭代過程。詳細(xì)的迭代步驟如下：

(1)進(jìn)行第一次迭代，將2和x0分別轉(zhuǎn)化為二進(jìn)制數(shù)，輸入量子寄存器|a〉=|an-1〉?|an-2〉?…?|a0〉和|b〉=|bm-1〉? |bm-2〉?…|b0〉中，把|2x0〉0的結(jié)果放入輔助寄存器|qcarry_sum0〉2n(n代表兩個乘數(shù)中位數(shù)較多的二進(jìn)制數(shù)的位數(shù))；

(3)通過測量將量子寄存器|qborrow〉上的信息轉(zhuǎn)化至經(jīng)典寄存器上，實(shí)現(xiàn)第一次迭代結(jié)果的觀測。量子電路圖如圖7(a)所示；

(a)一次迭代的倒數(shù)近似器電路

(b)n次迭代的倒數(shù)近似器電路

4 量子倒數(shù)器代價分析

4.1 時間復(fù)雜度

4.2 空間復(fù)雜度

由圖7所示，λ與x0都為n位二進(jìn)制數(shù)的時候，用以存放λ與x0的寄存器數(shù)量為2n，輔助寄存器|qcarry_1〉1至|qcarry_n〉2n-1的數(shù)量為2n2-n，寄存器|qcarry_sum0〉和|qcarry_sum1〉的數(shù)量一共為4n，寄存器|qbarrow〉的數(shù)量為2n-1，因此一共所需的寄存器為2n2+7n-1。最終一次迭代的倒數(shù)計算器的空間復(fù)雜度為O(n2)。用n個倒數(shù)器進(jìn)行疊加相連，空間復(fù)雜度為O(n3)。

5 結(jié)束語

該文設(shè)計的基于牛頓迭代法的量子倒數(shù)計算器實(shí)現(xiàn)了求取n位二進(jìn)制數(shù)的倒數(shù)，并且改進(jìn)了量子乘法器，用低位置零操作代替移位操作。該設(shè)計大大降低了系統(tǒng)的空間復(fù)雜性。時間復(fù)雜性分析進(jìn)一步表明，所設(shè)計的量子倒數(shù)器的時間復(fù)雜度并未遠(yuǎn)大于單獨(dú)的乘法器，且結(jié)構(gòu)簡單，易于優(yōu)化，迭代次數(shù)可根據(jù)具體精度需要任意選擇。