基于Hamming距離和量子搜索算法的聯(lián)想分類器設(shè)計(jì)

摘要： 針對(duì)現(xiàn)有聯(lián)想分類器不能存儲(chǔ)重復(fù)樣本的問題， 提出一種基于Hamming距離和量子搜索算法的量子聯(lián)想分類器設(shè)計(jì)方法， 并給出聯(lián)想分類器存儲(chǔ)和分類的線路圖. 該方法需提前準(zhǔn)備5組量子比特， 分別對(duì)Hamming距離、 輸入樣本、 模式樣本、 類別和序號(hào)進(jìn)行編碼. 首先， 根據(jù)樣本總體N， 計(jì)算聯(lián)想分類器所需的量子位數(shù)， 再利用量子旋轉(zhuǎn)門和Hadamard門將初態(tài)為0〉的量子位旋轉(zhuǎn)為恰好包含N個(gè)基態(tài)的均衡疊加態(tài); 其次， 根據(jù)待存儲(chǔ)樣本的類別和值， 將剩余兩組初始狀態(tài)為0〉的量子位通過可控操作轉(zhuǎn)換為相應(yīng)的量子基態(tài); 最后， 基于量子最小搜索的分類方法， 計(jì)算輸入樣本與所有存儲(chǔ)樣本之間的Hamming距離， 再使用固定相位Grover量子搜索算法搜索這些Hamming距離的最小值， 最小值對(duì)應(yīng)存儲(chǔ)樣本的類別即為輸入樣本的類別， 具體的分類結(jié)果可通過測(cè)量寄存器中的量子態(tài)得到.關(guān)鍵詞： 量子聯(lián)想分類器； 均衡疊加態(tài)； Hamming距離； 量子最小搜索

中圖分類號(hào)： TP391""文獻(xiàn)標(biāo)志碼： A""文章編號(hào)： 1671-5489（2024）06-1426-13

Design of Associative Classifier Based on HammingDistance and Quantum Search AlgorithmXIAO Hong， LIU Xintong

（School of Computer and Information Technology， Northeast Petroleum University，Daqing 163318， Heilongjiang Province， China）

Abstract： Aiming at the problem that the existing associative classifier could not store duplicate samples，

we proposed "a design method of associative classifier based on Hamming distance and quantum search algorithm， and gave a

line diagram for the storage and classification of the associative classifier.

The method required the preparation of "five sets of qubits "in advance to encode Hamming distance， input sample， pattern sample， category and sequence number respectively.

Firstly， according to the total N of the sample， the number of qubits required by the associative classifier was calculated， and then the qubits with an "initial state of "0〉

were rotated to an equilibrium superposition state containing exactly N ground states by using the quantum revolving gate and the Hadamard gate.

Secondly， according to the category and value of the sample to be stored， the remaining two sets of qubits with initial state of "0〉 were converted into the corresponding

quantum ground state through controllable operation. Finally， based on the classification method of quantum minimum search， the Hamming distance between the input sample and all the

stored samples was calculated， and then the fixed phase Grover quantum search algorithm was used to search for the minimum value of these Hamming distances. "The category of the stored

sample corresponding to the minimum value was the category of the input sample， and the specific classification results could be obtained by measuring the quantum states in the register.

Keywords： quantum associative classifier; equilibrium superposition state; Hamming distance; quantum minimum searchFeynman^［1］提出了基于量子力學(xué)原理構(gòu)建計(jì)算機(jī)以避免在經(jīng)典計(jì)算機(jī)上模擬量子力學(xué)系統(tǒng)所遇到的困難. 隨著量子計(jì)算機(jī)的發(fā)展^［2］， 各種與人工智能相關(guān)的量子計(jì)算模型層出不窮， 例如量子神經(jīng)網(wǎng)絡(luò)^［3-7］、 量子模式識(shí)別^［8］、 量子機(jī)器學(xué)習(xí)^［9-10］、 量子支持向量機(jī)^［11-13］和量子分類與決策^［14-20］等.

聯(lián)想記憶可概括為對(duì)人腦中信息的存儲(chǔ)、 聯(lián)想和檢索的研究， 對(duì)計(jì)算機(jī)科學(xué)的各領(lǐng)域都有重要指導(dǎo)意義. 隨著量子計(jì)算的興起， 量子聯(lián)想存儲(chǔ)器也得到了迅速發(fā)展^［21-24］. 量子聯(lián)想記憶的相關(guān)研究包括概率量子存儲(chǔ)^［25］和量子存儲(chǔ)模型的制備與測(cè)量^［26］. 與經(jīng)典聯(lián)想存儲(chǔ)器相比， 量子聯(lián)想存儲(chǔ)器具有指數(shù)級(jí)的存儲(chǔ)容量和指數(shù)級(jí)的加速能力. 量子計(jì)算具有線性特

性， 但如果量子態(tài)在時(shí)間演化過程中出現(xiàn)很小的非線性， 則量子計(jì)算機(jī)即可在多項(xiàng)式時(shí)間內(nèi)解決NP完全問題^［27］. 因此， Tchapet等^［28］利用非線性搜索算法提出了一種設(shè)計(jì)量子聯(lián)想存儲(chǔ)器的新方法， 該方法表明位翻轉(zhuǎn)通道不會(huì)對(duì)量子聯(lián)想存儲(chǔ)器產(chǎn)生影響， 但相位和位相翻轉(zhuǎn)的破壞性最大. 文獻(xiàn)［29-30］提出了模式存儲(chǔ)方法， 使用量子系統(tǒng)的基態(tài)對(duì)模式進(jìn)行編碼， 所有的存儲(chǔ)模式必須彼此不同， 因此該方案不適合存儲(chǔ)樣本， 且這兩種方案都沒有給出具體的量子線路實(shí)現(xiàn)存儲(chǔ)操作.

量子聯(lián)想存儲(chǔ)和檢索一般包括模式存儲(chǔ)和模式檢索兩部分. 模式存儲(chǔ)常用的方法是將標(biāo)記樣本存儲(chǔ)在均衡疊加態(tài)中， 但這些方法直接使用量子基態(tài)編碼模式信息， 并不能同時(shí)存儲(chǔ)

相同的樣本， 因此， 這些方法不提供量子線路實(shí)現(xiàn)存儲(chǔ)方案. 模式檢索首先計(jì)算輸入樣本與存儲(chǔ)樣本之間的相似度， 再使用Grover算法搜索相似度最大的存儲(chǔ)模式^［31］， 但使用原始Grover算法分類成功的概率并不理想.

為改進(jìn)模式存儲(chǔ)和分類， 本文提出一種新的模式存儲(chǔ)和分類方案. 該方案的模式存儲(chǔ)采用量子均衡疊加態(tài)， 由于本文對(duì)模式樣本的序號(hào)、 類別和內(nèi)容分別進(jìn)行了編碼， 因此

可以存儲(chǔ)相同的模式樣本. 同時(shí)， 本文也給出了特定的量子線路. 在模式分類中， 使用改進(jìn)的Grover算法， 即提出了一種改進(jìn)的固定相位（π/3或者5π/3）Grover算法， 可提高搜索的成功率.

1"量子聯(lián)想分類器的樣本存儲(chǔ)

本文提出的量子聯(lián)想分類器同樣將樣本存儲(chǔ)在均衡疊加態(tài)， 區(qū)別是本文使用3組量子比特分別對(duì)每個(gè)樣本的序號(hào)、 類別和值進(jìn)行編碼， 且樣本的數(shù)量是任意的， 不需要滿足2

的整數(shù)次冪. 為便于描述， 首先給出包含任意數(shù)量基態(tài)的量子均衡疊加態(tài)的構(gòu)造方法， 這些基態(tài)可用來編碼所有待存儲(chǔ)樣本的序號(hào).

1.1"量子均衡疊加態(tài)的構(gòu)造

本文采用文獻(xiàn)［32］的方法構(gòu)造含任意數(shù)目基態(tài)的量子均衡疊加態(tài). 假設(shè)有k個(gè)樣本需要存儲(chǔ)， 若k是偶數(shù)， 則設(shè)k=m2r， m為奇數(shù)， 根據(jù)文獻(xiàn)［32］， Uk=UmH^r. 因此， 要構(gòu)建酉算子Uk（含k個(gè)基態(tài)的均衡疊加態(tài)）， 只需先構(gòu)建酉算子Um（含m個(gè)基態(tài)的均衡疊加態(tài)）， 最后再加上r個(gè)受Hadamard門作用的單量子比特. 所以只需考慮k為奇數(shù)時(shí)的構(gòu)造方法即可.

算法1"量子均衡疊加態(tài)構(gòu)造方案.

輸入： 基態(tài)個(gè)數(shù)k（k為奇數(shù)）， 初始值t=0;

輸出： 含k個(gè)基態(tài)的均衡疊加態(tài);

步驟1） t=0， k0=k;

步驟2） While kt≠1

步驟3） ""令kt=2^rt+kt+1， 1≤kt+1≤2^rt-1;

步驟4） ""得到作用在第（rt+1）個(gè)量子位的受控門Λt（R（θkt））（其中θkt=arctan（kt+1/2^rt））

和作用在第1到第rt量子位的受控門Λt+1（H^rt）;

步驟5） ""t=t+1;

步驟6） End while.

為便于理解， 下面以k=31為例， 給出U31的具體構(gòu)造方法：

k0=k=31，"kt=2^rt+kt+1，"1≤kt+1≤2^rt-1，

t=0 31=24+15，"Λ0R（θ31），"θ31=arctan（15/24），"Λ1（H⁴），

t=1 15=23+7，"Λ1R（θ15），"θ15=arctan（7/23），"Λ2（H³），

t=2 7=22+3，"Λ2R（θ7），"θ7=arctan（3/22），"Λ3（H²），

t=3 3=21+1，"Λ3R（θ3），"θ3=arctan（1/2），"Λ4（H）.

圖1為實(shí)現(xiàn)31個(gè)基態(tài)均衡疊加的量子線路.

1.2"模式樣本的分類存儲(chǔ)方案

為解決現(xiàn)有存儲(chǔ)方案不能存儲(chǔ)相同類別樣本的問題^［31］， 即為存儲(chǔ)不同類別的樣本， 需準(zhǔn)備3個(gè)寄存器， 分別存儲(chǔ)模式樣本的序號(hào)、 類別和樣本值. 首先， 需計(jì)算3個(gè)寄存器所需的量子比特?cái)?shù)， 并將3個(gè)寄存器的初始狀態(tài)均設(shè)為0〉； 其次， 通過一些量子旋轉(zhuǎn)門和Hadamard門將序號(hào)寄存器轉(zhuǎn)換為均衡疊加態(tài); 最后， 以疊加態(tài)中的每個(gè)基態(tài)為控制條件， 將初始狀態(tài)為0〉的類別寄存器和樣本值寄存器轉(zhuǎn)換為與待存儲(chǔ)模式樣本的類別和值一致的狀態(tài).

不失一般性， 假設(shè)有N個(gè)C模式的二進(jìn)制量子比特， 則存儲(chǔ)這些樣本的均衡疊加態(tài)可表示為

M〉=1N∑N-1k=0mk〉ck〉k〉，（1）其中mk〉=mkq-1，mkq-2，…，mk0〉表示第k個(gè)樣本的值， ck〉=ck

t-1，ckt-2，…，ck0〉 （t=log2C）表示第k個(gè)樣本的類別， k〉表示第k個(gè)樣本的序號(hào).

算法2"量子聯(lián)想分類器的模式樣本存儲(chǔ)方案.

輸入： 樣本個(gè)數(shù)N， 模式個(gè)數(shù)C， 序號(hào)量子位個(gè)數(shù)q;

輸出： 1N∑N-1k=0mk〉ck〉k〉;

步驟1） 設(shè)置3種類型寄存器的量子位數(shù)量np=log2N， nc=log2C， q;

步驟2） 初始化寄存器， 0〉^{（np+nc+q）};

步驟3） 序號(hào)構(gòu)造均衡疊加態(tài)1N∑N-1k=00〉^q0〉ⁿk〉;

步驟4） 令k=0;

步驟5） While k≠N

步驟6） ""以位置基準(zhǔn)態(tài)k〉作為控制條件， 控制相應(yīng)的0〉^q0〉^nc翻轉(zhuǎn)；

步驟7） ""k=k+1；

步驟8） End while.

由算法2的方案可見： 即使存在大量的相同樣本， 也可以以疊加態(tài)存儲(chǔ). 此外， 這種方法也有利于海量數(shù)據(jù)的分類和統(tǒng)計(jì)處理.

下面以4類20個(gè)5位樣本為例說明模式樣本的存儲(chǔ)過程. 共有20個(gè)樣本， 所以序號(hào)量子位個(gè)數(shù)是5， 樣本類別個(gè)數(shù)是4， 從而只需要2個(gè)量子位存儲(chǔ)類別個(gè)數(shù). 存儲(chǔ)這些樣本共需12個(gè)

量子比特. 存儲(chǔ)這些樣本的量子線路如圖2所示， 量子疊加態(tài)的表達(dá)式為

M〉= "120（10000〉11〉00000〉+01111〉00〉00001〉+10010〉10〉00010〉+ "01100〉10〉00011〉+00001〉01〉00100〉+11100〉11〉00101〉+ "00100〉10〉00110〉+11011〉00〉00111〉

+10001〉10〉01000〉+ "01000〉01〉01001〉+01010〉00〉01010〉+10110〉11〉01011〉+ "01001〉00〉01100〉+11001〉01〉01101〉+00011〉00〉01110〉+ ""00110〉10〉01111〉+10101〉11〉10000〉+00010〉01〉10001〉+ "00100〉11〉10010〉+01101〉01〉10011〉）.（2）

2"量子聯(lián)想分類器的分類方法

本文設(shè)計(jì)一種基于量子最小值搜索的聯(lián)想分類方法. 先計(jì)算輸入樣本與所有存儲(chǔ)樣本之間的Hamming距離， 再使用Grover搜索算法搜索這些Hamming距離的最小值. 最小值所對(duì)應(yīng)存儲(chǔ)樣本的類別即為待分類輸入樣本的類別. 本文提出一種改進(jìn)的固定相位Grover算法.

2.1"改進(jìn)的固定相位Grover算法

2.1.1"固定相位Grover算法

設(shè)標(biāo)記項(xiàng)為s1〉，s2〉，…，sM〉， 未標(biāo)記項(xiàng)為t1〉，t2〉，…，tN-M〉， cos θ=（N-M）/N， sin θ=M/N， 0lt;θlt;π/2， 其中N為任意自然數(shù)， 不需要是2的整數(shù)次冪. 系統(tǒng)的初始狀態(tài)為

ψ^（0）〉=UN0〉^log2N=1N∑N-1i=0i〉=cos θN-M∑N-Mi=1ti〉+sin θM∑Mi=1si〉=sin θs〉+cos θt〉，（3）

其中s〉=1M∑Mi=1si〉為標(biāo)記態(tài)的疊加，

t〉=1N-M∑N-Mi=1ti〉為非標(biāo)記態(tài)的疊加， "UN為有N個(gè)基態(tài)的均衡疊加態(tài)的酉算子.

Grover算法中兩個(gè)相移算子的一般形式為

Is=I-（1-e^iφ）s〉〈s

，I0=I-（1-e^iφ）0〉〈0，（4）

其中s〉為標(biāo)記態(tài)， φ為相移， Is，I0為相移算子， I為單位矩陣. 迭代運(yùn)算符為

G=-UNI0U+NIs=（1-e^iφ）cos2θ-1e^iφ（1-e^iφ）sin θcos θ

（1-e^iφ）sin θcos θe^iφ（（1-e^iφ）sin2θ-1），（5）

其中UN為含N個(gè)基態(tài)的酉算子， U+N為UN的厄米算符， φ為相移， Is，I0為相移算子.

根據(jù)文獻(xiàn)［33］的結(jié)果， 經(jīng)過q次迭代后， 系統(tǒng)狀態(tài)為

ψ^（q）〉=Gqψ^（0）〉=aqs〉+bqt〉，（6）

其中aq=sin θ（e^iqφUq（y）+e^i（q-1）φUq-1（y））， bq=cos θe^i（

^q-1）φ（Uq（y）+Uq-1（y））， Gq表示G經(jīng)過q次迭代， y=cos δ=2sin

2θsin2（φ/2）-1， Uq（y）=sin（（q+1）δ）/sin δ是第二類Chebyshev多項(xiàng)式. 算法的成功概率為

Pqs=aq2=sin2θsin2δ（1-cos δcos（（2q+1）δ）+2cos φsin（（q+1）δ）sin（qδ））.（7）

在龍算法的SO（3）圖中^［34］， 每迭代一次， 算子G使相位旋轉(zhuǎn)4arcsin（sin（φ/2）sin θ）弧度， 使成功概率最大化的迭代次數(shù)為

Q=π4arcsinsinφ2MN，（8）

其中φ為相位參數(shù)， 當(dāng)φ=π時(shí)， 該算法等價(jià)于原始Grover算法. 當(dāng)φ取其他特定值時(shí)， 該算法等價(jià)于其他版本的Grover算法. 成功概率最大時(shí)的迭代次數(shù)與標(biāo)記數(shù)M有關(guān)， 若預(yù)先不知道標(biāo)記項(xiàng)數(shù)量， 則不能直接使用該算法.

2.1.2"搜索目標(biāo)個(gè)數(shù)未知時(shí)相移φ的確定

為解決標(biāo)記項(xiàng)數(shù)未知的搜索問題， 給出以下引理.

引理1"令m為正整數(shù)， q是0～（m-1）內(nèi)隨機(jī)選取的正整數(shù). 測(cè)量從初始狀態(tài)開始進(jìn)行q次迭代后寄存器的平均成功概率為

Pm=12sin2（φ/2）（1-cos δ）1+cos δcos φ-（cos δ+cos φ）sin2mδ2msin δ.

當(dāng)m≥1sin δ時(shí)， 如果φ為π3或5π3， 則14≤Pm≤2cos φsin2θ+cos2θ+24-2sin2θ（1-cos φ）.

證明： 隨機(jī)選取整數(shù)0≤q≤m-1， 當(dāng)m≥1sin δ時(shí)， "q次迭代之后的平均成功概率為

Pm= "1m∑m-1q=0Pqs12sin2φ/2（1-cos δ）1+cos δc

os φ-（cos δ+cos φ）sin（2mδ）2msin δ≥ "12sin2φ/2（1-cos δ）1+cos φ

cos δ+cos δ+cos φ2≥14sin2φ/21-cos φ2=14=Pmin，

Pm= "12sin2φ/2（1-cos δ）1+cos δcos φ-（cos δ+cos φ）sin（2mδ）2msin

δ≤ "12sin2φ/2（1-cos δ）1+cos φcos δ-cos δ+cos φ2=2cos φsin2θ+cos2θ +24-2sin2θ（1-cos φ）=Pmax，

Pmaxφ=Pmaxcos φcos φφ=-2sin2θcos

2θsin φ（4-2sin2θ（1-cos φ））2，

其中δ=arccos（2sin2θsin2（φ/2）-1）.

由于Grover算法的迭代次數(shù)不超過N， 所以m必須滿足1sin δ≤m≤N， 即sin δ≥1N，

sin δ= 1-cos2δ=2sin θ sin（φ/2）1-sin2θsin2（φ/2）.

當(dāng)0≤φ≤π/2或3π/2≤φ≤2π時(shí)，

sin δsin θ=2sin（φ/2）-4sin3（φ/2）sin2θ1-sin2（φ/2）sin2θ≥0，

此時(shí)， sin δ隨sin θ的增大而增大， 所以

sin δ≥（sin δ）min=21Nsinφ21-1Nsin2φ2.

由（sin δ）min≥1N可得cos φ≤N-1N+N-1≤12. 因此， π3

≤φ≤π2或3π2≤φ≤5π3.

由于當(dāng)π3≤φ≤π2時(shí)， Pmaxφ≤0； 當(dāng)3π2≤φ≤5π3時(shí)， Pmaxφ≥0，

因此本文將旋轉(zhuǎn)相位設(shè)為φ=π3或φ=5π3. 以N=2²⁰， M=1～3N4為例， 設(shè)φ分別為π30，2π30，…，59π30， 計(jì)算每個(gè)φ

值1sin δgt;N的個(gè)數(shù)及Pmax的最大值和最小值， 結(jié)果如圖3所示. 設(shè)置M=1～3N/4只是為使不同φ值比較結(jié)果更清晰. 在實(shí)際算法中并沒有該限制， 即1≤M≤N.

由圖3（A）可見， 當(dāng)π3≤φ≤5π3時(shí)， 1sin δ≤N； 當(dāng)φlt;π3或φgt;5π3時(shí)， 1sin δgt;N. 由圖3（B）可見， 當(dāng)π3≤φ≤5π3， 且φ=π3或φ=5π3時(shí)， Pmax的最大值為0.923 1， 這也是本文選擇這兩個(gè)相位的原因. 當(dāng)本文算法相位φ=π時(shí)， 等價(jià)于原始Grover算法. 雖然它不違反1sin δ≤N， 但成功的最大概率只有0.75. 對(duì)于標(biāo)記項(xiàng)數(shù)未知的Grover算法， 固定相位π/3或5π/3是最佳選擇.

但文獻(xiàn)［33］算法中φ=1.916 84π， 不能滿足1sin δ≤N. 因此， 對(duì)于某些標(biāo)記項(xiàng)數(shù)概率M/N， 不能保證搜索的有效實(shí)現(xiàn).

2.1.3"搜索目標(biāo)個(gè)數(shù)未知時(shí)的搜索方案

設(shè)存在T［0，1，…，N-1］， 希望找到x， 即找到一個(gè)整數(shù)0≤i≤N-1， 并且T［i］=x， 假設(shè)i存在， 但i的數(shù)量M未知. 本文采用文獻(xiàn)［35］中的方案對(duì)未知標(biāo)記項(xiàng)數(shù)進(jìn)行搜索.

算法3"搜索目標(biāo)個(gè)數(shù)未知時(shí)的搜索方案.

輸入： 含N個(gè)基態(tài)的量子均衡疊加態(tài)；

輸出： 搜索基態(tài)i；

步驟1） 初始化n=1， m=1， λ=651lt;λlt;43;

步驟2） 均勻隨機(jī)選擇小于m的非負(fù)整數(shù)j;

步驟3） 初始化ψ^（0）〉=1N∑ii〉;

步驟4） While n≤j

步驟5） ""ψ^（n）〉=1N∑ii〉;

步驟6） ""觀察寄存器： i作為輸出;

步驟7） ""If T［i］=x;

步驟8） """"問題解決， exit;

步驟9） ""Else

步驟10） """"m=min{λm，N};

步驟11） """"返回步驟2）;

步驟12） ""End if

步驟13） End while.

2.2"基于改進(jìn)固定相位Grover算法的最小值搜索

設(shè)T［0，1，…，N-1］為包含N個(gè)元素的無序列表. 最小搜索是找到最小值T［y］的索引y， 但標(biāo)記最小值T［y］的索引可能不是唯一的， 因此這是一個(gè)含有未知數(shù)量標(biāo)記項(xiàng)的搜索. 本文采用文獻(xiàn)［36］中的方

案進(jìn)行最小搜索. 搜索的基本思想是先使用固定相位（π/3或5π/3）的Grover算法查找小于當(dāng)前閾值T［y］的項(xiàng)的索引y0， 然后使用T［y0］作為新的閾值. 重復(fù)上述過程， 直到獲得最小值的概率足夠大， 算法如下.

算法4"量子最小值搜索算法.

輸入： 含N個(gè)基態(tài)的量子均衡疊加態(tài)；

輸出： 搜索目標(biāo)y；

步驟1） 令t=0

步驟2） 均勻隨機(jī)選擇閾值索引0≤y≤N-1；

步驟3） While t≤454N+710log22N;

步驟4） ""初始化內(nèi)存為∑jN^-0.5j〉y〉， 標(biāo)記T［j］lt;T［y］的每個(gè)條目j;

步驟5） ""t=t+p（N，r）log2N;

步驟6） ""使用固定相位π/3或5π/3的Grover算法;

步驟7） ""t=t+p（N，r）92Nr-1;

步驟8） ""觀察第一個(gè)寄存器， 令y′作為輸出;

步驟9） ""If T［y′］lt;T［y］;

步驟10） """"y=y′;

步驟11） ""End if

步驟12） End while

步驟13） Return y.

關(guān)于最小搜索算法的運(yùn)行時(shí)間， 有如下結(jié)果.

定理1""用算法4的搜索方案可求出最小值， 其期望總時(shí)間步數(shù)為O（N）.

證明： 設(shè)P（t，r）是當(dāng)有固定相位（π/3或5π/3）的Grover算法在t個(gè)元素中搜索時(shí)， r個(gè)元素的索引將被選擇的概率. 根據(jù)文獻(xiàn)［36］中的引理1， 如果r≤t， 則P（t，r）=1/r， 否則P（t，r）=0.

令mq=1sin δ， 使用固定相位π3或5π3的Grover算法尋找解的期望迭代次數(shù)上界為92mq. 此外， 根據(jù)文獻(xiàn)［36］中的引理2， 在T［y］

保持最小值之前的第2階段的預(yù)期時(shí)間步長(zhǎng)總數(shù)最多為∑Nr=2p（N，r）92Nr-1≤454

N， 并且在T［i］保持最小之前的第2階段的預(yù)期時(shí)間步長(zhǎng)總

數(shù)至多為∑Nr=2（p（N，r）log2N）≤710log22N. 因此， 算法4中方案預(yù)期的時(shí)間步長(zhǎng)最多為454N+710log22N=O（N）.

算法4中的方案， 運(yùn)行454N+710log22N次并不總能找到最小值. 實(shí)際上， 該方案通過反復(fù)調(diào)用算法4中的方案搜索最小值. 算法4中的方案實(shí)際上是一個(gè)試探性隨機(jī)搜索， 成功所需平均迭代次數(shù)的上界為92mq. 因此， 算法4的最小搜索方案實(shí)際上采用了不達(dá)到目標(biāo)不放棄的策略， 平均迭代次數(shù)的上界是454N+710log22N=O（N）.

2.3"計(jì)算Hamming距離的量子線路設(shè)計(jì)

量子聯(lián)想分類器的分類基于Hamming距離， 因此需設(shè)計(jì)量子線路計(jì)算兩個(gè)樣本之間的Hamming距離. 本文首先設(shè)計(jì)一個(gè)量子線路模塊實(shí)現(xiàn)加1， 如圖4所示.

對(duì)于n量子位基態(tài)， 該模塊使其以循環(huán)的方式反復(fù)加1， 即0〉→1〉→…2n-1〉→0〉→…

. 對(duì)于兩組q位二進(jìn)制樣本， Hamming距離是具有相同位置且它們之間的值不同的位的數(shù)目. 因此， 計(jì)算Hamming距離可通過逐個(gè)檢測(cè)對(duì)應(yīng)的位， 并將檢測(cè)結(jié)果累加實(shí)現(xiàn).

根據(jù)該思想設(shè)計(jì)的計(jì)算兩個(gè)樣本之間Hamming距離的量子線路如圖5所示. 其中mq-1mq-2…m0〉為存儲(chǔ)樣本， pq-1pq-2…p0〉為輸入樣本. q加1模塊依次檢測(cè)兩個(gè)采樣對(duì)應(yīng)的位. 如果它們不相同， 則Hamming距離增加1. 最終Hamming距離存儲(chǔ)在hs-1hs-2…h(huán)0〉中， 初始態(tài)為0〉^s.

2.4"基于量子聯(lián)想分類器的輸入樣本分類

設(shè)基態(tài)pq-1pq-2…p0〉為q位輸入樣本， h=0〉^s為存儲(chǔ)Hamming距離的寄存器. 它們都與存儲(chǔ)的N個(gè)q位模式樣本糾纏在一起，

用公式表示為

1N∑N-1k=0hks-1hks-2…h(huán)k0〉pq-1pq-2…p0〉mkq-1mkq-2…mk0〉ckt-1ckt-2…ck0〉k〉，（9）

其中： n=log2N; s=log2q， t=log2C， C為存儲(chǔ)樣本的類別數(shù).

量子聯(lián)想分類器的分類任務(wù)是通過尋找新輸入樣本與所有存儲(chǔ)樣本之間的Hamming距離的最小值確定新輸入樣本pq-1pq-2…p0〉的類別.

解決該問題的基本思路是利用Hamming距離模塊計(jì)算輸入樣本與所有存儲(chǔ)樣本之間的Hamming距離. 根據(jù)量子態(tài)的疊加原理， 可同時(shí)計(jì)算輸入樣本與所有存儲(chǔ)樣本之間的距離， 然后使用固定相位（π/3或5π/3）的Grover算法搜索這些距離的最小值， 最后對(duì)分類器進(jìn)

行測(cè)量. 此時(shí)， 寄存器ct-1ct-2…c0〉的測(cè)量結(jié)果為輸入樣本的類別. 用于分類的量子線路如圖6所示.

由圖6可見， Grover算法在由N個(gè)樣本的序號(hào)組成的無序數(shù)據(jù)庫中進(jìn)行搜索. 搜索過程還涉及到Hamming距離模塊與序號(hào)量子比特的糾纏， 例如確定一條記錄是否為標(biāo)記項(xiàng)等.

設(shè)有N個(gè)q位二進(jìn)制樣本， 可分為C類， 其中一個(gè)輸入二進(jìn)制樣本P=pq-1pq-2…p0. 量子聯(lián)想分類器的任務(wù)是將N個(gè)已知樣本存儲(chǔ)在內(nèi)存中， 同時(shí)確定輸入樣本的類別. 量子聯(lián)想分類器采用5個(gè)糾纏寄存器h〉p〉m〉c〉k〉， 初始態(tài)分別為0〉^s0〉^q0〉^q0〉^t0〉ⁿ， 分別存儲(chǔ)Hamming距離、 輸入樣本、 模式樣本、 類別和序號(hào). 根據(jù)上述假設(shè)， 5個(gè)寄存器中的量子比特?cái)?shù)為

s=log2q， q，q，t=log2C， n=log2N.

量子聯(lián)想分類器總線路如圖7所示. 旋轉(zhuǎn)門R（θj）用于將輸入樣本加載到分類器的寄存器pq-1pq-2…p0〉中， 其中θj=pj（π/2）， j=q-1，q-2，…，0.

圖7中， 分類器的5個(gè)寄存器在不同時(shí)刻的狀態(tài)分別為

ψ0〉=0〉^s0〉^q0〉^q0〉^t0〉ⁿ，（10）

ψ1〉=∑N-1k=00〉^s0〉^q0〉^q0〉^t

k〉，（11）

ψ2〉=∑N-1k=00〉^s|pq-1pq-2…p0〉mkq-1mkq-2…mk0〉

ckt-1ckt-2…ck0〉k〉，（12）

ψ3〉=∑N-1k=0hks-1hks-2…h(huán)k0〉pq-1pq-2…p0〉mkq-1mkq-2…mk0〉ckt-1ckt-2…ck0〉k〉，（13）

ψ4〉=ks-1ks-2…k0〉pq-1pq-2…p0〉kq-1kq-2…k0〉kt-1kt-2…k0〉

n-1n-2…0〉，（14）

其中ψ4〉不再處于疊加態(tài)， 而是處于某一基態(tài)， 寄存器

kt-1kt-2…k0〉的值為輸入二進(jìn)制樣本P=pq-1pq-2…p0的分類結(jié)果.

3"經(jīng)典計(jì)算機(jī)仿真

目前物理量子計(jì)算機(jī)還無法實(shí)現(xiàn)， 本文在經(jīng)典計(jì)算機(jī)上進(jìn)行量子聯(lián)想分類器的模擬. 在Intel（R） Core（TM） i7-4790 CPU @ 3.60 GHz， 8.00 GB RAM和64位操作系統(tǒng)的經(jīng)典計(jì)算機(jī)上進(jìn)行仿真. 仿真基于線性代數(shù)， 以復(fù)向量作為量子態(tài)， 幺正矩陣作為幺正變換， 使用MATLAB 9.3.0.713579 （R2017b）進(jìn)行計(jì)算. 在經(jīng)典計(jì)算機(jī)上， 雖然無法驗(yàn)證量子計(jì)算的并行性， 但可以驗(yàn)證算法的實(shí)驗(yàn)結(jié)果. 下面以MNIST手寫體數(shù)字?jǐn)?shù)據(jù)庫為例驗(yàn)證量子聯(lián)想分類器的可行性.

3.1"手寫數(shù)字?jǐn)?shù)據(jù)庫MNIST

手寫數(shù)字?jǐn)?shù)據(jù)庫MNIST有一個(gè)包含6萬個(gè)樣本的訓(xùn)練集和一個(gè)包含1萬個(gè)樣本的測(cè)試集（http：//yann.lecun.com/exdb/mnist/index.html）. 這些數(shù)字已被尺寸標(biāo)準(zhǔn)化， 并在固定大小的圖像中居中. 從0～9的圖像數(shù)量訓(xùn)練集分別為5 923，6 742，5 958，6 131，5 842，5 421，5 918，6 265，5 851，59 492， 測(cè)試集分別為980，1 135，1 032，1 010，982，892，958，1 028，974，1 009. 所有數(shù)字都是28×28的灰度圖像.

3.2"手寫數(shù)字圖像的預(yù)處理

由于量子聯(lián)想分類器只能接收二值向量樣本， 因此本文需將所有手寫數(shù)字圖像轉(zhuǎn)換為二值向量. 對(duì)數(shù)字圖像的二值化， 通常采用閾值分割， 如具有全局最優(yōu)效果的Otsu閾

值. 為簡(jiǎn)單， 本文先選擇基于像素灰度值直方圖的閾值. 然后將所有大于等于該閾值的灰度值設(shè)為1， 將小于該閾值的灰度值設(shè)為0. 以從每個(gè)類別的訓(xùn)練集中隨機(jī)選擇10張訓(xùn)練圖像為例， 二值化前后的圖像如圖8所示. 最后使用NEQR（nearly equal quantizer with a rounding-off procedure）模型將28×28的二值圖像用11個(gè)量子比特表示， 其中1個(gè)量子比特表示顏色， 5個(gè)量子比特表示Y方向坐標(biāo)y4〉y3〉y2〉y1〉y0〉， 5個(gè)量子比特表示X方向坐標(biāo)x4〉x3〉x2〉x1〉x0〉， "yi〉，xi〉∈{0，1}.

3.3"量子聯(lián)想分類器參數(shù)設(shè)置

對(duì)于數(shù)據(jù)庫MNIST， 訓(xùn)練集需存儲(chǔ)在內(nèi)存中. 根據(jù)訓(xùn)練集的樣本信息， 量子聯(lián)想分類器中初始狀態(tài)為h〉p〉m〉c〉k〉=0〉^s0〉^q0〉^q0〉^t0〉ⁿ的5個(gè)寄存器大小分別為s=log211=4， q=

log228+log228+1=11， t=log210=4， n=log260 000=16. 因此， 構(gòu)建該量子聯(lián)想分類器需要46個(gè)量子比特和一些用于酉變換的量子門.

3.4"量子聯(lián)想分類器的分類結(jié)果

量子聯(lián)想分類器的初始狀態(tài)為0〉⁴⁶， 存儲(chǔ)訓(xùn)練集樣本后的狀態(tài)為ψ〉=160 000∑59 999k=00〉⁴0〉¹¹mk10mk9…mk0〉ck3ck2ck1ck0〉k〉.（15）對(duì)于第j個(gè)測(cè)試樣本（1≤j≤10 000）， 首先通過一些量子旋轉(zhuǎn)門將其加載到寄存器p10p9…p0〉中， 然后使用Hamming距

離模塊并行計(jì)算Hamming距離， 并使用固定相位（π/3或5π/3）的Grover算法求出這些Hamming距離的最小值. 最后， 經(jīng)過約454N+710log22N=2 932次的搜索， 可由寄存器ct-1ct-2…c0〉的測(cè)量結(jié)果t-1t-2…0〉得到輸入樣本的模式， 由寄存器hs-1hs-2…h(huán)0〉的測(cè)量結(jié)果s-1s-2…0〉得到輸入樣本與最相似存儲(chǔ)樣本的Hamming距離， 由mq-1mq-2…m0〉和kn-1kn-2…k0〉的測(cè)量結(jié)果q-1q-2…0〉和n-1n-2…0〉分別得到與輸入樣本最相似的存儲(chǔ)樣本值和序號(hào).

通過對(duì)10 000個(gè)測(cè)試樣本的分析， 發(fā)現(xiàn)其中345個(gè)樣本與Hamming距離最小的訓(xùn)練樣本不屬于同一類. 因此， 量子聯(lián)想分類器不可能對(duì)這些樣本獲得正確結(jié)果. 此外， 在所有測(cè)試樣本中， 有59個(gè)匹配樣本. 每種方法都有多個(gè)Hamming距離最小的訓(xùn)練樣本， 但這些訓(xùn)練樣本并不都與測(cè)試樣本屬于同一類別. 對(duì)于這59個(gè)測(cè)試樣本， 量子聯(lián)想分類器并不能總得到正確結(jié)果. 實(shí)驗(yàn)結(jié)果表明， 量子聯(lián)想分類器的分類準(zhǔn)確率可達(dá)95.96%以上， 比文獻(xiàn)［31］方法的準(zhǔn)確率更高. 文獻(xiàn)［31］中提出的模式識(shí)別方法通過手動(dòng)設(shè)置Hamming距離的閾值方式進(jìn)行樣本識(shí)別， 只要存儲(chǔ)的模式樣本與待識(shí)別樣本的Hamming距離小于該閾值， 則將此待識(shí)別樣本的類別判定為與存儲(chǔ)模式樣本相同. 在這種方式中， 當(dāng)小于該閾值的存儲(chǔ)模式存在多個(gè)不同類型的樣本時(shí)， 可能會(huì)出現(xiàn)待識(shí)別樣本被錯(cuò)誤識(shí)別的情況， 從而導(dǎo)致識(shí)別率相對(duì)較低， 識(shí)別效果不理想. 而本文方法通過搜索Hamming距離的最小值， 得到最終分類結(jié)果， 使分類結(jié)果更準(zhǔn)確， 在一定程度上解決了該問題， 使本文方法的分類準(zhǔn)確率更高.

綜上所述， 針對(duì)現(xiàn)有聯(lián)想分類器不能存儲(chǔ)重復(fù)樣本的問題， 本文提出了一種新的量子聯(lián)想分類器， 并給出了實(shí)現(xiàn)模式樣本存儲(chǔ)的量子線路. 該分類器采用兩種新技術(shù)： 1） 提出了任意數(shù)量樣本的存儲(chǔ)技術(shù)， 通過將樣本序號(hào)和樣本值分開存儲(chǔ)， 可有效解決其他類似算法無法存儲(chǔ)重復(fù)樣本的問題; 2） 基于固定相位的Grover算法搜索技術(shù)， 通過將旋轉(zhuǎn)相位固定為π/3或5π/3提高搜索性能. 與經(jīng)典分類器相比， 該分類器的優(yōu)勢(shì)是對(duì)所有樣本進(jìn)行并行處理的能力. 隨著海量數(shù)據(jù)在信息處理領(lǐng)域的日益突出， 這種并行處理能力具有重要意義. 此外， 目前量子計(jì)算機(jī)尚未普及， 本文提出的聯(lián)想分類器設(shè)計(jì)方案無實(shí)用價(jià)值， 但作為一種前瞻性的理論探索， 本文結(jié)果對(duì)未來量子硬件普及后解決聯(lián)想分類問題具有一定的參考意義.

參考文獻(xiàn)

［1］"FEYNMAN R. Simulating Physics with Computers ［J］. International Journal of Theoretical Physics， 1982， 21： 467-488.

［2］"GYONGYOSI L， IMRE S. A Survey on Quantum Computing Technology ［J］. Computer Science Review， 2019， 31： 51-71.

［3］"PAQUET E， SOLEYMANU F. QuantumLeap： Hybrid Quantum Neural Network for Financi

al Predictions ［J］. Expert Systems with Applications， 2022， 195： 116583-1-116583-11.

［4］"ABBAS A， SUTTER D， ZOUFAL C， et al. The Power of Quantum Neural Networks ［J］. Nature Computational Science， 2021， 1（6）： 403-409.

［5］"TIAN J K， SUN X Y， DU Y X， et al. Recent Advances fo

r Quantum Neural Networks in Generative Learning ［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2023， 45（10）： 12321-12340.

［6］"QI J， YANG C H H， CHEN P Y. QTN-VQC： An End-to-End Learning Fram

ework for Quantum Neural Networks ［EB/OL］. （2021-10-06）［2023-01-15］. https：//arxiv.org/abs/2110.03861.

［7］"SKOLIK A， MCCLEAN J R， MOHSENI M， et al. Layerwise L

earning for Quantum Neural Networks ［J］. Quantum Machine Intelligence， 2021， 3： 1-11.

［8］"SHARMA R， KAUSHIK B， GONDHI N K， et al. Quantum Particle Swarm Optimization Based Convolutional Neural Network for Handwritten Script Recognition ［J］. Computers Materials and Continua， 2022， 71（3）： 5855-5873.

［9］"CEREZO M， VERDON G， HUANG H Y， et al. Challenges and Opportunities in Quantum

Machine Learning ［J］. Nature Computational Science， 2022， 2（9）： 567-576.

［10］"MELNIKOV A， KORDZANGANEH M， ALODJANTS A， et al. Qua

ntum Machine Learning： From Physics to Software Engineering ［J］. Advances in Physics： X， 2023， 8（1）： 2165452-1-2165452-52.

［11］"RANA A， VAIDYA P， GUPTA G. A Comparative Study of Q

uantum Support Vector Machine Algorithm for Handwritten Recognition with Support Vector Machine Algorithm ［J］. Materials Today： Proceedings， 2022， 56： 2025-2030.

［12］"KAVITHA S S， KAULGUD N. Quantum Machine Learning fo

r Support Vector Machine Classification ［J］. Evolutionary Intelligence， 2022， 17： 819-828.

［13］"SINGH G， KAUR M， SINGH M， et al. Implementation of

Quantum Support Vector Machine Algorithm Using a Benchmarking Dataset ［J］. Indian Journal of Pure amp; Applied Physics （IJPAP）， 2022， 60（5）： 407-414.

［14］"XIAO F， PEDRYCZ W. Negation of the Quantum Mass Fun

ction for Multisource Quantum Information Fusion with Its Application to Pattern Classification ［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2022， 45（2）： 2054-2070.

［15］"ISHWARYA M S， CHERUKURI A K. Quantum-Inspired Ensemble Approach to Multi-att

ributed and Multi-agent Decision-Making ［J］. Applied Soft Computing， 2021， 106： 107283-1-107283-9.

［16］"FERRO G M， KOVALENKO T， SORNETTE D. Quantum Decisio

n Theory Augments Rank-Dependent Expected Utility and Cumulative Prospect Theory ［J］. Journal of Economic Psychology， 2021， 86： 102417-1-102417-21.

［17］"KRELINA M. Quantum Technology for Military Applications ［J］. EPJ Quantum Technology， 2021， 8（1）： 24-1-24-53.

［18］"HERMAN D， GOOGIN C， LIU X， et al. Quantum Computing for Finance ［J］. Nature Reviews Physics， 2023， 5（8）： 450-465.

［19］"ZHANG J W， LI Z， HE R F， et al. Interactive Quantum Classifier Inspired by Quantum Open System Theory ［C］//2021 International Joint Conference on Neural Networks （IJCNN）. Piscataway， NJ： IEEE， 2021： 1-7.

［20］"WU Q， LIU X W， QIN J D， et al. A Linguistic Distribution Behavioral Multi-criter

ia Group Decision Making Model Integrating Extended Generalized TODIM and Quantu

m Decision Theory ［J］. Applied Soft Computing， 2021， 98： 106757-1-106757-20.

［21］"QUIROZ G， ICE L， DELGADO A， et al. Particle Track Classification Using Quant

um Associative Memory ［J］. Nuclear Instruments and Methods in Physics Research Section A： Accelerators， Spectrometers， Detectors and Associated Equipment， 2021， 1010： 165557-1-165557-12.

［22］"CHEN S， COTLER J， HUANG H Y， et al. Exponential Separations between Learning

with and without Quantum Memory ［C］//2021 IEEE 62nd Annual Symposium on Foundations of Computer Science （FOCS）. Piscataway， NJ： IEEE， 2022： 574-585.

［23］"DRMOTA P， MAIN D， NADLINGER D P， et al. Robust Quan

tum Memory in a Trapped-Ion Quantum Network Node ［J］. Physical Review Letters， 2023， 130（9）： 090803-1-090803-8.

［24］"NIMBE P， WEYORI B A， ADEKOYA A F. Models in Quantum

Computing： A Systematic Review ［J］. Quantum Information Processing， 2021， 20（2）： 80-1-80-61.

［25］"KHAN M， FAYE J P L， MENDES U C， et al. EP-PQM： Efficient Parametric Probabilistic Quantum Memory with Fewer Qubits and Gates ［J］. IEEE Transactions on Quantum Engineering， 2022， 3： 1-15.

［26］"ALIAKBARZADEH M， KITTO K. Preparation and Measureme

nt in Quantum Memory Models ［J］. Journal of Mathematical Psychology， 2018， 83： 24-34.

［27］"ABRAMS D S， LLOYD S. Nonlinear Quantum Mechanics Implies Polynomial-Time Sol

ution for NP-Complete and #P Problems ［J］. Physical Review Letters， 1998， 81（18）： 3992-1-3992-4.

［28］"TCHAPET N J P， NANA E S G. Concise Quantum Associative Memories with

Nonlinear Search Algorithm ［J］. Fortschritte der Physik， 2016， 64（2/3）： 250-268.

［29］"VENTURA D， MARTINEZ T. Initializing the Amplitude Distribution of a Quantum State ［J］. Foundations of Physics Letters， 1999， 12： 547-559.

［30］"TRUGENBERGER C A. Probabilistic Quantum Memories ［J］. Physical Review Letters， 2001， 87（6）： 067901-1-067901-4.

［31］"DE PAULA N F M， DA SILVA A J， DE OLIVEIRA W R， e

t al. Quantum Probabilistic Associative Memory Architecture ［J］. Neurocomputing， 2019， 351： 101-110.

［32］"肖紅， 劉新彤， 李盼池. 靈活的固定相位量子搜索算法 ［J］. 北京工業(yè)大學(xué)學(xué)報(bào)， 2023， 49（6）： 630-638. （XIAO H， LIU X T， LI P C. Flexible

Fixed Phase Quantum Search Algorithm ［J］. Journal of Beijing University of Technology， 2023， 49（6）： 630-638.）

［33］"YOUNES A. Fixed Phase Quantum Search Algorithm

［EB/OL］. （2007-04-12）［2023-01-10］. https：//arxiv.org/abs/0704.1585.

［34］"LONG G L. Grover Algorithm with Zero Theoretical Failure Rate ［J］. Physical Review A， 2001， 64（2）： 022307-1-022307-7.

［35］"BOYER M， BRASSARD G， HYER P， et al. Tight Bounds on Quantum Sarching ［J］. Fortschritte der Physik： Progress of Physics， 1998， 46（4/5）： 493-505.

［36］"DURR C， HOYER P. A Quantum Algorithm for Finding the Minimum "［EB/OL］.

（1996-07-18） ［2023-02-01］. https：//arxiv.org/abs/quant-ph/9607014.

（責(zé)任編輯： 韓"嘯）