通用賽道：題目1

選手不應(yīng)在文檔的任何地方直接或間接透露隊名、成員和單位信息

摘要：

（摘要中，選手應(yīng)以至少包括以下幾個內(nèi)容：1. 所選作答內(nèi)容的場景介紹（尤其是對于更開放的題目） 2. 主要算法思路，包括經(jīng)典和量子部分，重點(diǎn)講解創(chuàng)新點(diǎn)和獨(dú)特之處 3. 結(jié)果概述，包括在所給的例題和自創(chuàng)數(shù)據(jù)上的表現(xiàn) ）

破解RSA加密的有效量子算法之一是Shor量子算法，將大數(shù)分解問題轉(zhuǎn)化為量子計算機(jī)可以并行處理的函數(shù)周期求解問題。我們基于Shor量子算法原理和本源量子給出的代碼示例，用Python語言實(shí)現(xiàn)經(jīng)典計算部分和量子計算部分的程序，創(chuàng)新點(diǎn)是優(yōu)化了代碼中底數(shù)a的選取。結(jié)果是在16GB內(nèi)存上實(shí)現(xiàn)5位二進(jìn)制數(shù)的因數(shù)分解（5n+2=27量子比特），若要實(shí)現(xiàn)題目要求的分解57，需要32量子比特的量子虛擬機(jī)，這在16GB內(nèi)存上無法實(shí)現(xiàn)；另一種方法是選取”2n+2”規(guī)模的量子算法，我們由于技術(shù)能力限制未能實(shí)現(xiàn)，用作前景展望。

場景介紹：

（選手應(yīng)根據(jù)所選題目的情況，對題目的應(yīng)用場景、經(jīng)濟(jì)價值等進(jìn)行一定綜述。對于題目給定場景明確的，可以具體舉例或者對題目所給場景進(jìn)行擴(kuò)展；對于題目未給定詳細(xì)場景的，應(yīng)詳細(xì)敘述自己所選場景，包括場景概述、場景應(yīng)用價值、場景和數(shù)據(jù)來源等。）

?

量子計算相較于經(jīng)典計算，以指數(shù)級的優(yōu)勢解決特定問題。Shor量子算法是破解RSA加密系統(tǒng)的經(jīng)典算法，其對大數(shù)分解問題的構(gòu)建了計算模型，將大數(shù)分解問題轉(zhuǎn)化為求函數(shù)周期問題。Shor算法的提出使得基于大數(shù)分解難題的RSA算法在足夠多量子比特的量子計算機(jī)面前不再安全。

?

在具體的量子計算機(jī)上（或者量子虛擬機(jī)）實(shí)現(xiàn)Shor算法，已經(jīng)有不少的研究。其中本源量子封裝好的shor分解算法，在16GB的內(nèi)存上實(shí)現(xiàn)最多5位二進(jìn)制數(shù)的分解。

算法原理思路：

（選手應(yīng)在本環(huán)節(jié)詳細(xì)描述解題所用的算法思路。具體可參考以下幾個部分。

1.?數(shù)學(xué)模型：對于僅給出應(yīng)用場景的，選手應(yīng)首先將場景中的數(shù)學(xué)模型抽象出來

2.?預(yù)處理：選手應(yīng)詳細(xì)介紹如何題目所給條件進(jìn)行經(jīng)典處理，變?yōu)榱孔铀惴梢越邮艿男问?/p>

3.?量子算法（含經(jīng)典-量子混合算法）：選手應(yīng)詳細(xì)介紹所選的量子算法模型、原理以及選擇原因。這一環(huán)節(jié)應(yīng)為最重要部分，包括整體性的說明，以及選手進(jìn)行的創(chuàng)新性改進(jìn)（如有）的說明等。

4.?后處理：選手應(yīng)在此處敘述如何將量子測量結(jié)果轉(zhuǎn)化為問題答案。

5.?其他：如選手可以在此處進(jìn)行理論的復(fù)雜度（線路深度、寬度）分析等

此處以原理展示為主，可以使用文字、公式、圖表、少量核心代碼、偽代碼、流程圖等幫助說明，不應(yīng)粘貼大段代碼。具體代碼分析應(yīng)放在后面。）

1.?數(shù)學(xué)模型：

?

;

證明：是一個周期函數(shù)，周期為，故有；

因此有，?；

我們?nèi)『?，即為所求?/p>

總之，Shor算法實(shí)現(xiàn)了難解的大數(shù)分解問題轉(zhuǎn)化為求函數(shù)周期問題，求出函數(shù)的周期r即可求出N的因子，這里涉及到a的選取問題，我們在預(yù)處理部分再講述。

2.?預(yù)處理：輸入待分解的數(shù)N和底數(shù)a。（1）若N為素數(shù)，拋出異常（2）a取整數(shù)，且與N互質(zhì)（3）若a大于N舍棄（4）a為完全平方數(shù)時求出的周期r必為奇數(shù) 【2015 對Shor算法破解RSA的探討_凃玲英】，實(shí)現(xiàn)過濾優(yōu)化。

3.?量子算法：Shor量子算法主要由三個部分組成，即量子傅里葉變換模塊、模指線路模塊、逆量子傅里葉模塊。（1）由于初態(tài)為|0>態(tài)，因此第一部分的量子傅里葉變換模塊等價于Hadamard門，輸出疊加態(tài)。（2）模指模塊由疊加態(tài)控制的若干模乘模塊構(gòu)成，模乘模塊相應(yīng)的由模加模塊連同一系列加法器組成，這里省略模指、模乘、模加的數(shù)學(xué)推導(dǎo)。（3）逆量子傅里葉模塊選出預(yù)測周期值，對這部分測量得出量子測量值。

4.?后處理：量子測量程序輸出是，若干測量值(用k來表示）和相應(yīng)命中次數(shù)，這些測量值往往比較大，不是最終的結(jié)果。令Q=22n，其中n為待分解數(shù)N的比特數(shù)。求出（k/Q=s/r）的分母，我們要對k/Q使用“連分?jǐn)?shù)逼近”法，求出最終的分母r，這個r就是Shor算法中需要求階的r。

5.?復(fù)雜度分析：經(jīng)典Shor算法需要的是2n+3n+2個量子比特數(shù)，即“5n+2”的規(guī)模。例如，求解57這個數(shù)，n=6，需要5*6+2即32個量子比特的計算設(shè)備才能求解。由于16GB內(nèi)存最多可以模擬30個量子比特，因此在16GB內(nèi)存上無法運(yùn)行“5n+2”規(guī)模的Shor算法求解57乃至更大的數(shù)。

6.?前景展望：為了實(shí)現(xiàn)16GB內(nèi)存上求解57（n=6）上至119（n=7)，可以采用較低量子比特規(guī)模的算法，比如“2n+2”規(guī)模的算法【2017 Factoring using 2n+2 qubits with Toffoli based modular multiplication-Thomas H?ner, Martin Roetteler, Krysta M. Svore】 。該算法不使用傅里葉變換的模式，有模乘和模加模塊。使用O(nlogn)規(guī)模的加法器，不需要n位的清潔位而是1位臟位實(shí)現(xiàn)。為了實(shí)現(xiàn)2n+2規(guī)模的總量子位規(guī)模，模乘線路如下：

?

結(jié)果展示和結(jié)論：

（選手應(yīng)在此處詳細(xì)展示根據(jù)題目要求運(yùn)行算法的結(jié)果，包括對每一個具體問題搭建量子線路的量子比特數(shù)、線路深度分析，若采用迭代算法，也要包括量子線路的運(yùn)行次數(shù)等。若需要展示線路運(yùn)行時間（根據(jù)題目而定），應(yīng)同時附上所用經(jīng)典計算機(jī)的配置情況。最后，選手應(yīng)對整體文檔進(jìn)行一個總結(jié)。）

（1）shor算法分解樣例9：

（2）shor算法分解樣例15：

?

（3）總結(jié)：

總體任務(wù)是基于本院量子的知識，復(fù)現(xiàn)了shor算法。在本機(jī)物理內(nèi)存16GB的情況下，實(shí)際環(huán)境中空余的可以分給量子虛擬機(jī)的大概只有4GB左右，在這種情況下可以跑出n=4，即15及以內(nèi)的結(jié)果。完成了初賽的簡答題:) 結(jié)合前面的分析，在內(nèi)存充足的情況下可以滿足題目條件。

（4）待改進(jìn)之處：

我們有一個疑惑，對于底數(shù)為2時，可能不一定找得到相應(yīng)的周期r，所以造成程序卡住了。后續(xù)需要設(shè)置代碼中底數(shù)選取部分的“超時跳過”機(jī)制。

代碼分析：

（與算法原理思路不同，選手在此處應(yīng)對代碼進(jìn)行詳盡說明，包括所使用的第三方包、環(huán)境；解釋具有重要意義的自定義函數(shù)、變量、過程的作用和含義；標(biāo)注函數(shù)的輸入、輸出格式；解釋一些特殊技巧等等?？梢耘浜洗a注釋一起進(jìn)行說明。選手應(yīng)確保根據(jù)文檔，閱卷人可以正確編譯、運(yùn)行其提供的代碼。）

都在提交的代碼中做了備注，描述函數(shù)的功能、輸入和輸出【1】【2】。比如下面的代碼，參考了本源量子的C++代碼邏輯，我們轉(zhuǎn)成了Python版本使用。

?

參考內(nèi)容：

（選手應(yīng)在此處全部列舉非原創(chuàng)部分所采用的參考文獻(xiàn)、代碼，且引用之處應(yīng)在文檔中予以對應(yīng)標(biāo)注。對于不如實(shí)標(biāo)注被發(fā)現(xiàn)的，予以作弊處理，根據(jù)情節(jié)嚴(yán)重進(jìn)行扣分到取消資格的懲罰。）

【1】shor算法量子計算部分參考：本源量子系列《量子計算與編程入門》（郭國平 陳昭昀 郭光燦 著）p205-p250

【2】經(jīng)典計算部分參考：https://github.com/OriginQ/QPanda-2/blob/master/QAlg/Shor/Shor.cpp（本源量子shor.cpp)

【3】底數(shù)a選取的優(yōu)化參考：2015 《對Shor算法破解RSA的探討》凃玲英

【4】量子線路優(yōu)化至2n+2規(guī)模的參考：2017《 Factoring using 2n+2 qubits with Toffoli based modular multiplication》Thomas H?ner, Martin Roetteler, Krysta M. Svore

?