基于Hamming距離和量子搜索算法的聯想分類器設計
2024-01-01 00:00:00肖紅劉新彤
吉林大學學報(理學版) 2024年6期
摘要： 針對現有聯想分類器不能存儲重復樣本的問題， 提出一種基于Hamming距離和量子搜索算法的量子聯想分類器設計方法， 并給出聯想分類器存儲和分類的線路圖. 該方法需提前準備5組量子比特， 分別對Hamming距離、 輸入樣本、 模式樣本、 類別和序號進行編碼. 首先， 根據樣本總體N， 計算聯想分類器所需的量子位數， 再利用量子旋轉門和Hadamard門將初態為0〉的量子位旋轉為恰好包含N個基態的均衡疊加態; 其次， 根據待存儲樣本的類別和值， 將剩余兩組初始狀態為0〉的量子位通過可控操作轉換為相應的量子基態; 最后， 基于量子最小搜索的分類方法， 計算輸入樣本與所有存儲樣本之間的Hamming距離， 再使用固定相位Grover量子搜索算法搜索這些Hamming距離的最小值， 最小值對應存儲樣本的類別即為輸入樣本的類別， 具體的分類結果可通過測量寄存器中的量子態得到.關鍵詞： 量子聯想分類器； 均衡疊加態； Hamming距離； 量子最小搜索
中圖分類號： TP391""文獻標志碼： A""文章編號： 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］提出了基于量子力學原理構建計算機以避免在經典計算機上模擬量子力學系統所遇到的困難. 隨著量子計算機的發展［2］， 各種與人工智能相關的量子計算模型層出不窮， 例如量子神經網絡［3-7］、 量子模式識別［8］、 量子機器學習［9-10］、 量子支持向量機［11-13］和量子分類與決策［14-20］等.
聯想記憶可概括為對人腦中信息的存儲、 聯想和檢索的研究， 對計算機科學的各領域都有重要指導意義. 隨著量子計算的興起， 量子聯想存儲器也得到了迅速發展［21-24］. 量子聯想記憶的相關研究包括概率量子存儲［25］和量子存儲模型的制備與測量［26］. 與經典聯想存儲器相比， 量子聯想存儲器具有指數級的存儲容量和指數級的加速能力. 量子計算具有線性特
性， 但如果量子態在時間演化過程中出現很小的非線性， 則量子計算機即可在多項式時間內解決NP完全問題［27］. 因此， Tchapet等［28］利用非線性搜索算法提出了一種設計量子聯想存儲器的新方法， 該方法表明位翻轉通道不會對量子聯想存儲器產生影響， 但相位和位相翻轉的破壞性最大. 文獻［29-30］提出了模式存儲方法， 使用量子系統的基態對模式進行編碼， 所有的存儲模式必須彼此不同， 因此該方案不適合存儲樣本， 且這兩種方案都沒有給出具體的量子線路實現存儲操作.
量子聯想存儲和檢索一般包括模式存儲和模式檢索兩部分. 模式存儲常用的方法是將標記樣本存儲在均衡疊加態中， 但這些方法直接使用量子基態編碼模式信息， 并不能同時存儲
相同的樣本， 因此， 這些方法不提供量子線路實現存儲方案. 模式檢索首先計算輸入樣本與存儲樣本之間的相似度， 再使用Grover算法搜索相似度最大的存儲模式［31］， 但使用原始Grover算法分類成功的概率并不理想.
為改進模式存儲和分類， 本文提出一種新的模式存儲和分類方案. 該方案的模式存儲采用量子均衡疊加態， 由于本文對模式樣本的序號、 類別和內容分別進行了編碼， 因此
可以存儲相同的模式樣本. 同時， 本文也給出了特定的量子線路. 在模式分類中， 使用改進的Grover算法， 即提出了一種改進的固定相位（π/3或者5π/3）Grover算法， 可提高搜索的成功率.
1"量子聯想分類器的樣本存儲
本文提出的量子聯想分類器同樣將樣本存儲在均衡疊加態， 區別是本文使用3組量子比特分別對每個樣本的序號、 類別和值進行編碼， 且樣本的數量是任意的， 不需要滿足2
的整數次冪. 為便于描述， 首先給出包含任意數量基態的量子均衡疊加態的構造方法， 這些基態可用來編碼所有待存儲樣本的序號.
1.1"量子均衡疊加態的構造
本文采用文獻［32］的方法構造含任意數目基態的量子均衡疊加態. 假設有k個樣本需要存儲， 若k是偶數， 則設k=m2r， m為奇數， 根據文獻［32］， Uk=UmHr. 因此， 要構建酉算子Uk（含k個基態的均衡疊加態）， 只需先構建酉算子Um（含m個基態的均衡疊加態）， 最后再加上r個受Hadamard門作用的單量子比特. 所以只需考慮k為奇數時的構造方法即可.
算法1"量子均衡疊加態構造方案.
輸入： 基態個數k（k為奇數）， 初始值t=0;
輸出： 含k個基態的均衡疊加態;
步驟1） t=0， k0=k;
步驟2） While kt≠1
步驟3） ""令kt=2rt+kt+1， 1≤kt+1≤2rt-1;
步驟4） ""得到作用在第（rt+1）個量子位的受控門Λt（R（θkt））（其中θkt=arctan（kt+1/2rt））
和作用在第1到第rt量子位的受控門Λt+1（Hrt）;
步驟5） ""t=t+1;
步驟6） End while.
為便于理解， 下面以k=31為例， 給出U31的具體構造方法：
k0=k=31，"kt=2rt+kt+1，"1≤kt+1≤2rt-1，
t=0 31=24+15，"Λ0R（θ31），"θ31=arctan（15/24），"Λ1（H4），
t=1 15=23+7，"Λ1R（θ15），"θ15=arctan（7/23），"Λ2（H3），
t=2 7=22+3，"Λ2R（θ7），"θ7=arctan（3/22），"Λ3（H2），
t=3 3=21+1，"Λ3R（θ3），"θ3=arctan（1/2），"Λ4（H）.
圖1為實現31個基態均衡疊加的量子線路.
1.2"模式樣本的分類存儲方案
為解決現有存儲方案不能存儲相同類別樣本的問題［31］， 即為存儲不同類別的樣本， 需準備3個寄存器， 分別存儲模式樣本的序號、 類別和樣本值. 首先， 需計算3個寄存器所需的量子比特數， 并將3個寄存器的初始狀態均設為0〉； 其次， 通過一些量子旋轉門和Hadamard門將序號寄存器轉換為均衡疊加態; 最后， 以疊加態中的每個基態為控制條件， 將初始狀態為0〉的類別寄存器和樣本值寄存器轉換為與待存儲模式樣本的類別和值一致的狀態.
不失一般性， 假設有N個C模式的二進制量子比特， 則存儲這些樣本的均衡疊加態可表示為
M〉=1N∑N-1k=0mk〉ck〉k〉，（1）其中mk〉=mkq-1，mkq-2，…，mk0〉表示第k個樣本的值， ck〉=ck
t-1，ckt-2，…，ck0〉 （t=log2C）表示第k個樣本的類別， k〉表示第k個樣本的序號.
算法2"量子聯想分類器的模式樣本存儲方案.
輸入： 樣本個數N， 模式個數C， 序號量子位個數q;
輸出： 1N∑N-1k=0mk〉ck〉k〉;
步驟1） 設置3種類型寄存器的量子位數量np=log2N， nc=log2C， q;
步驟2） 初始化寄存器， 0〉（np+nc+q）;
步驟3） 序號構造均衡疊加態1N∑N-1k=00〉q0〉nk〉;
步驟4） 令k=0;
步驟5） While k≠N
步驟6） ""以位置基準態k〉作為控制條件， 控制相應的0〉q0〉nc翻轉；
步驟7） ""k=k+1；
步驟8） End while.
由算法2的方案可見： 即使存在大量的相同樣本， 也可以以疊加態存儲. 此外， 這種方法也有利于海量數據的分類和統計處理.
下面以4類20個5位樣本為例說明模式樣本的存儲過程. 共有20個樣本， 所以序號量子位個數是5， 樣本類別個數是4， 從而只需要2個量子位存儲類別個數. 存儲這些樣本共需12個
量子比特. 存儲這些樣本的量子線路如圖2所示， 量子疊加態的表達式為
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"量子聯想分類器的分類方法
本文設計一種基于量子最小值搜索的聯想分類方法. 先計算輸入樣本與所有存儲樣本之間的Hamming距離， 再使用Grover搜索算法搜索這些Hamming距離的最小值. 最小值所對應存儲樣本的類別即為待分類輸入樣本的類別. 本文提出一種改進的固定相位Grover算法.
2.1"改進的固定相位Grover算法
2.1.1"固定相位Grover算法
設標記項為s1〉，s2〉，…，sM〉， 未標記項為t1〉，t2〉，…，tN-M〉， cos θ=（N-M）/N， sin θ=M/N， 0lt;θlt;π/2， 其中N為任意自然數， 不需要是2的整數次冪. 系統的初始狀態為
ψ（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〉為標記態的疊加，
t〉=1N-M∑N-Mi=1ti〉為非標記態的疊加， "UN為有N個基態的均衡疊加態的酉算子.
Grover算法中兩個相移算子的一般形式為
Is=I-（1-eiφ）s〉〈s
，I0=I-（1-eiφ）0〉〈0，（4）
其中s〉為標記態， φ為相移， Is，I0為相移算子， I為單位矩陣. 迭代運算符為
G=-UNI0U+NIs=（1-eiφ）cos2θ-1eiφ（1-eiφ）sin θcos θ
（1-eiφ）sin θcos θeiφ（（1-eiφ）sin2θ-1），（5）
其中UN為含N個基態的酉算子， U+N為UN的厄米算符， φ為相移， Is，I0為相移算子.
根據文獻［33］的結果， 經過q次迭代后， 系統狀態為
ψ（q）〉=Gqψ（0）〉=aqs〉+bqt〉，（6）
其中aq=sin θ（eiqφUq（y）+ei（q-1）φUq-1（y））， bq=cos θei（
q-1）φ（Uq（y）+Uq-1（y））， Gq表示G經過q次迭代， y=cos δ=2sin
2θsin2（φ/2）-1， Uq（y）=sin（（q+1）δ）/sin δ是第二類Chebyshev多項式. 算法的成功概率為
Pqs=aq2=sin2θsin2δ（1-cos δcos（（2q+1）δ）+2cos φsin（（q+1）δ）sin（qδ））.（7）
在龍算法的SO（3）圖中［34］， 每迭代一次， 算子G使相位旋轉4arcsin（sin（φ/2）sin θ）弧度， 使成功概率最大化的迭代次數為
Q=π4arcsinsinφ2MN，（8）
其中φ為相位參數， 當φ=π時， 該算法等價于原始Grover算法. 當φ取其他特定值時， 該算法等價于其他版本的Grover算法. 成功概率最大時的迭代次數與標記數M有關， 若預先不知道標記項數量， 則不能直接使用該算法.
2.1.2"搜索目標個數未知時相移φ的確定
為解決標記項數未知的搜索問題， 給出以下引理.
引理1"令m為正整數， q是0～（m-1）內隨機選取的正整數. 測量從初始狀態開始進行q次迭代后寄存器的平均成功概率為
Pm=12sin2（φ/2）（1-cos δ）1+cos δcos φ-（cos δ+cos φ）sin2mδ2msin δ.
當m≥1sin δ時， 如果φ為π3或5π3， 則14≤Pm≤2cos φsin2θ+cos2θ+24-2sin2θ（1-cos φ）.
證明： 隨機選取整數0≤q≤m-1， 當m≥1sin δ時， "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算法的迭代次數不超過N， 所以m必須滿足1sin δ≤m≤N， 即sin δ≥1N，
sin δ= 1-cos2δ=2sin θ sin（φ/2）1-sin2θsin2（φ/2）.
當0≤φ≤π/2或3π/2≤φ≤2π時，
sin δsin θ=2sin（φ/2）-4sin3（φ/2）sin2θ1-sin2（φ/2）sin2θ≥0，
此時， sin δ隨sin θ的增大而增大， 所以
sin δ≥（sin δ）min=21Nsinφ21-1Nsin2φ2.
由（sin δ）min≥1N可得cos φ≤N-1N+N-1≤12. 因此， π3
≤φ≤π2或3π2≤φ≤5π3.
由于當π3≤φ≤π2時， Pmaxφ≤0； 當3π2≤φ≤5π3時， Pmaxφ≥0，
因此本文將旋轉相位設為φ=π3或φ=5π3. 以N=220， M=1～3N4為例， 設φ分別為π30，2π30，…，59π30， 計算每個φ
值1sin δgt;N的個數及Pmax的最大值和最小值， 結果如圖3所示. 設置M=1～3N/4只是為使不同φ值比較結果更清晰. 在實際算法中并沒有該限制， 即1≤M≤N.
由圖3（A）可見， 當π3≤φ≤5π3時， 1sin δ≤N； 當φlt;π3或φgt;5π3時， 1sin δgt;N. 由圖3（B）可見， 當π3≤φ≤5π3， 且φ=π3或φ=5π3時， Pmax的最大值為0.923 1， 這也是本文選擇這兩個相位的原因. 當本文算法相位φ=π時， 等價于原始Grover算法. 雖然它不違反1sin δ≤N， 但成功的最大概率只有0.75. 對于標記項數未知的Grover算法， 固定相位π/3或5π/3是最佳選擇.
但文獻［33］算法中φ=1.916 84π， 不能滿足1sin δ≤N. 因此， 對于某些標記項數概率M/N， 不能保證搜索的有效實現.
2.1.3"搜索目標個數未知時的搜索方案
設存在T［0，1，…，N-1］， 希望找到x， 即找到一個整數0≤i≤N-1， 并且T［i］=x， 假設i存在， 但i的數量M未知. 本文采用文獻［35］中的方案對未知標記項數進行搜索.
算法3"搜索目標個數未知時的搜索方案.
輸入： 含N個基態的量子均衡疊加態；
輸出： 搜索基態i；
步驟1） 初始化n=1， m=1， λ=651lt;λlt;43;
步驟2） 均勻隨機選擇小于m的非負整數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"基于改進固定相位Grover算法的最小值搜索
設T［0，1，…，N-1］為包含N個元素的無序列表. 最小搜索是找到最小值T［y］的索引y， 但標記最小值T［y］的索引可能不是唯一的， 因此這是一個含有未知數量標記項的搜索. 本文采用文獻［36］中的方
案進行最小搜索. 搜索的基本思想是先使用固定相位（π/3或5π/3）的Grover算法查找小于當前閾值T［y］的項的索引y0， 然后使用T［y0］作為新的閾值. 重復上述過程， 直到獲得最小值的概率足夠大， 算法如下.
算法4"量子最小值搜索算法.
輸入： 含N個基態的量子均衡疊加態；
輸出： 搜索目標y；
步驟1） 令t=0
步驟2） 均勻隨機選擇閾值索引0≤y≤N-1；
步驟3） While t≤454N+710log22N;
步驟4） ""初始化內存為∑jN-0.5j〉y〉， 標記T［j］lt;T［y］的每個條目j;
步驟5） ""t=t+p（N，r）log2N;
步驟6） ""使用固定相位π/3或5π/3的Grover算法;
步驟7） ""t=t+p（N，r）92Nr-1;
步驟8） ""觀察第一個寄存器， 令y′作為輸出;
步驟9） ""If T［y′］lt;T［y］;
步驟10） """"y=y′;
步驟11） ""End if
步驟12） End while
步驟13） Return y.
關于最小搜索算法的運行時間， 有如下結果.
定理1""用算法4的搜索方案可求出最小值， 其期望總時間步數為O（N）.
證明： 設P（t，r）是當有固定相位（π/3或5π/3）的Grover算法在t個元素中搜索時， r個元素的索引將被選擇的概率. 根據文獻［36］中的引理1， 如果r≤t， 則P（t，r）=1/r， 否則P（t，r）=0.
令mq=1sin δ， 使用固定相位π3或5π3的Grover算法尋找解的期望迭代次數上界為92mq. 此外， 根據文獻［36］中的引理2， 在T［y］
保持最小值之前的第2階段的預期時間步長總數最多為∑Nr=2p（N，r）92Nr-1≤454
N， 并且在T［i］保持最小之前的第2階段的預期時間步長總
數至多為∑Nr=2（p（N，r）log2N）≤710log22N. 因此， 算法4中方案預期的時間步長最多為454N+710log22N=O（N）.
算法4中的方案， 運行454N+710log22N次并不總能找到最小值. 實際上， 該方案通過反復調用算法4中的方案搜索最小值. 算法4中的方案實際上是一個試探性隨機搜索， 成功所需平均迭代次數的上界為92mq. 因此， 算法4的最小搜索方案實際上采用了不達到目標不放棄的策略， 平均迭代次數的上界是454N+710log22N=O（N）.
2.3"計算Hamming距離的量子線路設計
量子聯想分類器的分類基于Hamming距離， 因此需設計量子線路計算兩個樣本之間的Hamming距離. 本文首先設計一個量子線路模塊實現加1， 如圖4所示.
對于n量子位基態， 該模塊使其以循環的方式反復加1， 即0〉→1〉→…2n-1〉→0〉→…
. 對于兩組q位二進制樣本， Hamming距離是具有相同位置且它們之間的值不同的位的數目. 因此， 計算Hamming距離可通過逐個檢測對應的位， 并將檢測結果累加實現.
根據該思想設計的計算兩個樣本之間Hamming距離的量子線路如圖5所示. 其中mq-1mq-2…m0〉為存儲樣本， pq-1pq-2…p0〉為輸入樣本. q加1模塊依次檢測兩個采樣對應的位. 如果它們不相同， 則Hamming距離增加1. 最終Hamming距離存儲在hs-1hs-2…h0〉中， 初始態為0〉s.
2.4"基于量子聯想分類器的輸入樣本分類
設基態pq-1pq-2…p0〉為q位輸入樣本， h=0〉s為存儲Hamming距離的寄存器. 它們都與存儲的N個q位模式樣本糾纏在一起，
用公式表示為
1N∑N-1k=0hks-1hks-2…hk0〉pq-1pq-2…p0〉mkq-1mkq-2…mk0〉ckt-1ckt-2…ck0〉k〉，（9）
其中： n=log2N; s=log2q， t=log2C， C為存儲樣本的類別數.
量子聯想分類器的分類任務是通過尋找新輸入樣本與所有存儲樣本之間的Hamming距離的最小值確定新輸入樣本pq-1pq-2…p0〉的類別.
解決該問題的基本思路是利用Hamming距離模塊計算輸入樣本與所有存儲樣本之間的Hamming距離. 根據量子態的疊加原理， 可同時計算輸入樣本與所有存儲樣本之間的距離， 然后使用固定相位（π/3或5π/3）的Grover算法搜索這些距離的最小值， 最后對分類器進
行測量. 此時， 寄存器ct-1ct-2…c0〉的測量結果為輸入樣本的類別. 用于分類的量子線路如圖6所示.
由圖6可見， Grover算法在由N個樣本的序號組成的無序數據庫中進行搜索. 搜索過程還涉及到Hamming距離模塊與序號量子比特的糾纏， 例如確定一條記錄是否為標記項等.
設有N個q位二進制樣本， 可分為C類， 其中一個輸入二進制樣本P=pq-1pq-2…p0. 量子聯想分類器的任務是將N個已知樣本存儲在內存中， 同時確定輸入樣本的類別. 量子聯想分類器采用5個糾纏寄存器h〉p〉m〉c〉k〉， 初始態分別為0〉s0〉q0〉q0〉t0〉n， 分別存儲Hamming距離、 輸入樣本、 模式樣本、 類別和序號. 根據上述假設， 5個寄存器中的量子比特數為
s=log2q， q，q，t=log2C， n=log2N.
量子聯想分類器總線路如圖7所示. 旋轉門R（θj）用于將輸入樣本加載到分類器的寄存器pq-1pq-2…p0〉中， 其中θj=pj（π/2）， j=q-1，q-2，…，0.
圖7中， 分類器的5個寄存器在不同時刻的狀態分別為
ψ0〉=0〉s0〉q0〉q0〉t0〉n，（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…hk0〉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〉不再處于疊加態， 而是處于某一基態， 寄存器
kt-1kt-2…k0〉的值為輸入二進制樣本P=pq-1pq-2…p0的分類結果.
3"經典計算機仿真
目前物理量子計算機還無法實現， 本文在經典計算機上進行量子聯想分類器的模擬. 在Intel（R） Core（TM） i7-4790 CPU @ 3.60 GHz， 8.00 GB RAM和64位操作系統的經典計算機上進行仿真. 仿真基于線性代數， 以復向量作為量子態， 幺正矩陣作為幺正變換， 使用MATLAB 9.3.0.713579 （R2017b）進行計算. 在經典計算機上， 雖然無法驗證量子計算的并行性， 但可以驗證算法的實驗結果. 下面以MNIST手寫體數字數據庫為例驗證量子聯想分類器的可行性.
3.1"手寫數字數據庫MNIST
手寫數字數據庫MNIST有一個包含6萬個樣本的訓練集和一個包含1萬個樣本的測試集（http：//yann.lecun.com/exdb/mnist/index.html）. 這些數字已被尺寸標準化， 并在固定大小的圖像中居中. 從0～9的圖像數量訓練集分別為5 923，6 742，5 958，6 131，5 842，5 421，5 918，6 265，5 851，59 492， 測試集分別為980，1 135，1 032，1 010，982，892，958，1 028，974，1 009. 所有數字都是28×28的灰度圖像.
3.2"手寫數字圖像的預處理
由于量子聯想分類器只能接收二值向量樣本， 因此本文需將所有手寫數字圖像轉換為二值向量. 對數字圖像的二值化， 通常采用閾值分割， 如具有全局最優效果的Otsu閾
值. 為簡單， 本文先選擇基于像素灰度值直方圖的閾值. 然后將所有大于等于該閾值的灰度值設為1， 將小于該閾值的灰度值設為0. 以從每個類別的訓練集中隨機選擇10張訓練圖像為例， 二值化前后的圖像如圖8所示. 最后使用NEQR（nearly equal quantizer with a rounding-off procedure）模型將28×28的二值圖像用11個量子比特表示， 其中1個量子比特表示顏色， 5個量子比特表示Y方向坐標y4〉y3〉y2〉y1〉y0〉， 5個量子比特表示X方向坐標x4〉x3〉x2〉x1〉x0〉， "yi〉，xi〉∈{0，1}.
3.3"量子聯想分類器參數設置
對于數據庫MNIST， 訓練集需存儲在內存中. 根據訓練集的樣本信息， 量子聯想分類器中初始狀態為h〉p〉m〉c〉k〉=0〉s0〉q0〉q0〉t0〉n的5個寄存器大小分別為s=log211=4， q=
log228+log228+1=11， t=log210=4， n=log260 000=16. 因此， 構建該量子聯想分類器需要46個量子比特和一些用于酉變換的量子門.
3.4"量子聯想分類器的分類結果
量子聯想分類器的初始狀態為0〉46， 存儲訓練集樣本后的狀態為ψ〉=160 000∑59 999k=00〉40〉11mk10mk9…mk0〉ck3ck2ck1ck0〉k〉.（15）對于第j個測試樣本（1≤j≤10 000）， 首先通過一些量子旋轉門將其加載到寄存器p10p9…p0〉中， 然后使用Hamming距
離模塊并行計算Hamming距離， 并使用固定相位（π/3或5π/3）的Grover算法求出這些Hamming距離的最小值. 最后， 經過約454N+710log22N=2 932次的搜索， 可由寄存器ct-1ct-2…c0〉的測量結果t-1t-2…0〉得到輸入樣本的模式， 由寄存器hs-1hs-2…h0〉的測量結果s-1s-2…0〉得到輸入樣本與最相似存儲樣本的Hamming距離， 由mq-1mq-2…m0〉和kn-1kn-2…k0〉的測量結果q-1q-2…0〉和n-1n-2…0〉分別得到與輸入樣本最相似的存儲樣本值和序號.
通過對10 000個測試樣本的分析， 發現其中345個樣本與Hamming距離最小的訓練樣本不屬于同一類. 因此， 量子聯想分類器不可能對這些樣本獲得正確結果. 此外， 在所有測試樣本中， 有59個匹配樣本. 每種方法都有多個Hamming距離最小的訓練樣本， 但這些訓練樣本并不都與測試樣本屬于同一類別. 對于這59個測試樣本， 量子聯想分類器并不能總得到正確結果. 實驗結果表明， 量子聯想分類器的分類準確率可達95.96%以上， 比文獻［31］方法的準確率更高. 文獻［31］中提出的模式識別方法通過手動設置Hamming距離的閾值方式進行樣本識別， 只要存儲的模式樣本與待識別樣本的Hamming距離小于該閾值， 則將此待識別樣本的類別判定為與存儲模式樣本相同. 在這種方式中， 當小于該閾值的存儲模式存在多個不同類型的樣本時， 可能會出現待識別樣本被錯誤識別的情況， 從而導致識別率相對較低， 識別效果不理想. 而本文方法通過搜索Hamming距離的最小值， 得到最終分類結果， 使分類結果更準確， 在一定程度上解決了該問題， 使本文方法的分類準確率更高.
綜上所述， 針對現有聯想分類器不能存儲重復樣本的問題， 本文提出了一種新的量子聯想分類器， 并給出了實現模式樣本存儲的量子線路. 該分類器采用兩種新技術： 1） 提出了任意數量樣本的存儲技術， 通過將樣本序號和樣本值分開存儲， 可有效解決其他類似算法無法存儲重復樣本的問題; 2） 基于固定相位的Grover算法搜索技術， 通過將旋轉相位固定為π/3或5π/3提高搜索性能. 與經典分類器相比， 該分類器的優勢是對所有樣本進行并行處理的能力. 隨著海量數據在信息處理領域的日益突出， 這種并行處理能力具有重要意義. 此外， 目前量子計算機尚未普及， 本文提出的聯想分類器設計方案無實用價值， 但作為一種前瞻性的理論探索， 本文結果對未來量子硬件普及后解決聯想分類問題具有一定的參考意義.
參考文獻
［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］. 北京工業大學學報， 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.
（責任編輯： 韓"嘯）
