分布式量子計數(shù)算法研究.pdf

1、隨著量子計算和量子信息技術(shù)的發(fā)展，分布式量子計算應(yīng)運而生。通過量子網(wǎng)絡(luò)將量子計算機連接起來能獲得更強的計算能力。分布式量子計算具有邏輯門級并行能力，與傳統(tǒng)的并行計算相比，這是更底層的并行。
　　所有的P問題都屬于NP問題，而所有NP問題又可多項式規(guī)約到NP完全問題，因此如果能設(shè)計出一個復(fù)雜度更低的求解NP完全問題的算法，那么所有NP問題都可以在原有算法基礎(chǔ)上的獲得同樣的加速。計數(shù)問題是一類受到廣泛關(guān)注的NP完全問題，本文提出一個解

2、決計數(shù)問題的分布式量子算法，將這個算法作為通用的計算模式，在解決其他NP問題（當(dāng)然也包括P問題）時，只需設(shè)計相應(yīng)的黑箱，研究適當(dāng)?shù)牡刂酚成浞桨福湍茉谠械乃惴ㄉ汐@得將近O(1/m√N/M)的加速。
　　本文首先總結(jié)分布式量子計算的發(fā)展現(xiàn)狀，包括物理環(huán)境和應(yīng)用，然后給出NP問題和計數(shù)問題的精確定義，NP完全問題的證書以及相應(yīng)的計數(shù)問題描述。
　　接下來介紹基本量子門，包括單比特量子門、多比特量子門、基本量子門的通用性。然后詳

3、細描述量子門的非本地化方法，這是分布式量子計算的關(guān)鍵。再設(shè)計一些典型問題的量子線路。
　　然后，詳細描述分布式量子計數(shù)算法的理論推導(dǎo)和設(shè)計與實現(xiàn)。先從理論上推導(dǎo)量子計數(shù)算法的原理，再設(shè)計算法的總體結(jié)構(gòu)，接著詳細描述了算法各個部分的設(shè)計與實現(xiàn)，包括Grover迭代、化簡多量子比特門和量子逆傅立葉變換，最后給出量子計數(shù)算法求解集合覆蓋問題的實例。
　　文章最后分析分布式量子算法的復(fù)雜度，包括量子門復(fù)雜度、查詢復(fù)雜度和通信復(fù)雜度，