Distributed Quantum Counting Algorithm Research

With the development of quantum computing and quantum information science, distributed quantum computing came into being. We can get considerable computing power by connecting a set of quantum computer through quantum network. Distributed quantum computing gives us a logic gate-level parallelism. Comparing with traditional parallel computing, it is a lower-level parallelism.Every problem in P belongs to NP, and every problem in NP is polynomial-time reducible to NP-complete problem. So if we can design an algorithm with lower complexity to solve NP-complete problem, all the problems in NP may be speeded up from their original algorithm with an equal factor. The counting problem is a class of NP-complete problem which is widely concerned. We will develop a distributed quantum algorithm to solve counting problem. After that, we can consider it as a universal computing scheme. When solving other NP problems (including problems in P), all we need to do is designing a suitable black box and an proper "address mapping", then plug it into the quantum counting algorithm. This will bring about a speedup of nearlyAt first, this thesis summarizes current state of distributed quantum computing, including physical environment and its application. Then, the accurate definition of NP and counting problem is given. After that, many certificates of NP-complete problem and corresponding counting problem are shown.Second, this thesis introduces basic quantum gates, including single qubit quantum gate, multi quantum gate and universality of basic quantum gate. It also describes methods transforming local quantum gate into non-local edition in detail, which plays a very important role in distributed quantum computing. At last, a series quantum circuit of some typical problem is developed.Then comes one of the most important part of this thesis, which is theoretical derivation, design and implementation of distributed quantum counting algorithm. We give a detailed proof of the algorithm’s principle first, and then design the framework, of the algorithm. We also describe the design and implementation of all parts of the algorithm, including Gro ver iteration, reducing multi qubit quantum gate and reverse quantum Fourier transform. At last, we give an example using quantum counting algorithm to solve the Set Cover problem. Finally, this thesis analyses the complexity of the algorithm, including quantum gate complexity, query complexity and communication complexity. It also discusses efficiency of qubits.