本文選題：分布式量子計算　切入點：量子計數(shù)算法　出處：《東北大學》2012年碩士論文

【摘要】：隨著量子計算和量子信息技術(shù)的發(fā)展,分布式量子計算應(yīng)運而生。通過量子網(wǎng)絡(luò)將量子計算機連接起來能獲得更強的計算能力。分布式量子計算具有邏輯門級并行能力,與傳統(tǒng)的并行計算相比,這是更底層的并行。所有的P問題都屬于NP問題,而所有NP問題又可多項式規(guī)約到NP完全問題,因此如果能設(shè)計出一個復(fù)雜度更低的求解NP完全問題的算法,那么所有NP問題都可以在原有算法基礎(chǔ)上的獲得同樣的加速。計數(shù)問題是一類受到廣泛關(guān)注的NP完全問題,本文提出一個解決計數(shù)問題的分布式量子算法,將這個算法作為通用的計算模式,在解決其他NP問題(當然也包括P問題)時,只需設(shè)計相應(yīng)的黑箱,研究適當?shù)牡刂酚成浞桨?就能在原有的算法上獲得將近。O的加速。本文首先總結(jié)分布式量子計算的發(fā)展現(xiàn)狀,包括物理環(huán)境和應(yīng)用,然后給出NP問題和計數(shù)問題的精確定義,NP完全問題的證書以及相應(yīng)的計數(shù)問題描述。 接下來介紹基本量子門,包括單比特量子門、多比特量子門、基本量子門的通用性。然后詳細描述量子門的非本地化方法,這是分布式量子計算的關(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ù)雜度,還討論了量子比特利用率。
[Abstract]:With the development of quantum computing and quantum information technology, distributed quantum computing emerges as the times require.A quantum computer can be connected to a quantum network to achieve greater computing power.Distributed quantum computing has the parallel capability of logic gate, which is lower level than traditional parallel computing.All P problems belong to NP problems, and all NP problems can be reduced to NP complete problems by polynomials. Therefore, if we can design a lower complexity algorithm for solving NP complete problems,Then all NP problems can be obtained the same acceleration on the basis of the original algorithm.The enumeration problem is a kind of NP-complete problem, which is widely concerned. In this paper, a distributed quantum algorithm is proposed to solve the counting problem, which is regarded as a general computing model, and is used to solve other NP problems (including P problem, of course).By designing the corresponding black box and studying the appropriate address mapping scheme, we can obtain the acceleration of nearly. O on the original algorithm.This paper first summarizes the development of distributed quantum computing, including the physical environment and applications, then gives the exact definition of NP problem and enumeration problem and the certificate of NP-complete problem and the corresponding description of counting problem.Then we introduce the generality of basic quantum gates, including single-bit quantum gates, multi-bit quantum gates, and basic quantum gates.Then the non-localization method of quantum gate is described in detail, which is the key of distributed quantum computing.Then we design some typical quantum circuits.Then, the theoretical derivation, design and implementation of the distributed quantum counting algorithm are described in detail.The principle of quantum counting algorithm is deduced theoretically, then the overall structure of the algorithm is designed. Then, the design and implementation of each part of the algorithm are described in detail, including Grover iteration, simplification of multi-quantum bit gates and quantum inverse Fourier transform.Finally, an example of quantum counting algorithm for solving set covering problem is given.Finally, the complexity of distributed quantum algorithms, including quantum gate complexity, query complexity and communication complexity, is analyzed. Quantum bit utilization is also discussed.
【學位授予單位】：東北大學
【學位級別】：碩士
【學位授予年份】：2012
【分類號】：TP38;O413

【參考文獻】

相關(guān)期刊論文 前1條

1 夏培肅;量子計算[J];計算機研究與發(fā)展;2001年10期

，

本文編號：1703972