以基於格羅弗演算法的量子線路解決精確覆蓋問題;Quantum Circuit Based on Grover′s Algorithm to Solve Exact Cover Problem

NCU Institutional Repository > 資訊電機學院 > 資訊工程研究所 > 博碩士論文 > Item 987654321/93236

jsp.display-item.identifier=請使用永久網址來引用或連結此文件: http://ir.lib.ncu.edu.tw/handle/987654321/93236

题名:	以基於格羅弗演算法的量子線路解決精確覆蓋問題;Quantum Circuit Based on Grover′s Algorithm to Solve Exact Cover Problem
作者:	王昱傑;Wang, Yu-Jie
贡献者:	資訊工程學系
关键词:	量子計算;量子線路;精確覆蓋;格羅弗演算法;量子計數;量子模擬器;量子電腦;Quantum computing;Quantum circuit;Exact Cover;Grover’s algorithm;Quantum counting;Quantum simulator;Quantum computer
日期:	2023-07-25
上传时间:	2024-09-19 16:50:00 (UTC+8)
出版者:	國立中央大學
摘要:	近年來，量子計算(quantum computing)由於強大的計算能力在學術界和工業界都引起了廣泛的關注和研究。學術界的研究推動了理論和技術的發展，而工業界的參與加速了量子計算技術的實際應用和商業化進程。巨擘科技如IBM、Google、Microsoft，都已經投入了大量資源和人力進行量子計算的研究和開發，推出了自己的量子計算平台或套件，並開放給研究機構和開發者使用，以促進量子計算技術的應用和驗證。本論文聚焦於在 IBM 提供的量子電腦(quantum computer)及量子模擬器(quantum simulator)上，以格羅弗演算法(Grover’s algorithm)解決屬於 NPC 問題的精確覆蓋(exact cover)問題。其中使用 IBM Qiskit 套件建構量子線路(quantum circuit)，所提方法以受控量子計數器實現精確覆蓋問題的神諭(oracle)，計算宇集內的元素被集合收集(collection of sets)覆蓋的次數，及使用相位回擊(phase kickback)之機制反轉給定問題中可行解的相位，並藉由擴散器(diffuser)放大可行解的機率振幅。最後，以 IBM 公司提供的量子模擬器 ibmq_qasm_simulator 及量子電腦 ibmq_kolkata 執行量子線路並進行測量以得到問題解答，並與現存解決精確覆蓋的古典演算法進行比較。本文所提出之用於解決精確覆蓋問題之量子線路與古典電腦中的窮舉搜索法相比具有平方量級的加速，意即，古典電腦需以O(2^\|S\|)的時間複雜度計算，而所提出方法的量子線路僅需O(sqrt(2^\|S\|)) 即可解決相同的問題，其中 \|S\| 為精確覆蓋中集合收集 S 的大小。;In recent years, quantum computing has gained widespread attention and research in both the academic and industrial sectors. Academic research has driven the development of theories and technologies, while industrial involvement has accelerated the practical applications and commercialization of quantum computing. Big Tech such as IBM, Google, and Microsoft have invested significant resources and manpower into quantum computing research and development. They have introduced their own quantum computing platforms or packages and made them available to research institutions and developers to promote the application and validation of quantum computing technology.This article focuses on solving the Exact Cover problem using Grover′s algorithm on the quantum computer and quantum simulator provided by IBM. The approach utilizes the IBM Qiskit package to construct a quantum circuit. The proposed method employs a controlled quantum counter as an implicit oracle to calculate the number of times elements in a universal set are covered by a collection of sets. It utilizes the mechanism of phase kickback to flip the phase of feasible solutions in the given problem and amplifies the phase amplitudes of feasible solutions through a diffuser. Finally, measurements are performed using IBM′s quantum simulator, ibmq_qasm_simulator, and quantum computer, ibmq_kolkata, and compared with existing classical algorithms for Exact Cover.The quantum circuit proposed in this article for solving the Exact Cover problem is compared to the exhaustive search method in classical computers and demonstrates a quadratic speedup. In other words, while classical computers require a time complexity of O(2^\|S\|) for solving Exact Cover problem, the proposed method can solve the same problem in just O(sqrt(2^\|S\|)) time, where \|S\| represents the size of the collection of sets S in the Exact Cover problem.
显示于类别:	[資訊工程研究所] 博碩士論文

文件中的档案:

档案	描述	大小	格式	浏览次数
index.html		0Kb	HTML	8	检视/开启

在NCUIR中所有的数据项都受到原著作权保护.

社群 sharing

数据加载中.....