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

2022-04-02 05:27:20朱家良

計算機技術與發展 2022年3期

朱家良，葉賓，季雯

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

0 引言

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

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

1 量子邏輯門基礎

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

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

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

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

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

圖1 量子邏輯門

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

2 量子乘法器的實現

2.1 量子半加器

半加器的過程如下：

|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位量子全加器

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

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

(5)

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

(6)

其中，|ai〉是一個二進制數a的第i位，|bi〉是另一個二進制數b的第i位，|c〉是進位c的第i位，|si〉是a與b之和的第i位。

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

(b)圖(a)的簡化圖

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

2.3 量子乘法器

目前大多數的量子乘法器是在一個n量子比特的寄存器中輸入|a〉1=|an-1〉1?|an-2〉1?…?|a0〉1來表示整數a=2n-1an-1+2n-2an-2+…+20a0;在另一個n量子比特的寄存器中輸入|b〉2=|bm-1〉2?|bm-2〉2?…?|b0〉2來表示整數b=2m-1bm-1+2m-2bm-2+…+20b0;第三個l量子比特的寄存器用來存放前兩個寄存器中的數相乘的結果，其狀態為|c〉3=|cl-1〉3? |cl-2〉3?…?|c0〉3，其中c=2l-1cl-1+ 2l-2cl-2+…+20c0。經過量子乘法器運算后各寄存器中的數值改變如下：

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

(7)

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

2.4 量子乘法器的移位實現

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

(8)

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

(9)

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

圖4 置零乘法的實現步驟

2.5 量子乘法器的實現

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

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

|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寄存器逐個清零來減少寄存器的使用，大大降低空間復雜度)，并將結果存放在寄存器|c〉3=|c0〉3?…?|cl〉3中(l=2×max(n,m))；最后通過測量將量子寄存器上的信息轉化至經典寄存器c上，實現結果的觀測。

圖5 量子乘法器電路圖

2.6 量子乘法器復雜度分析

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

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

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

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