A Survey on How to Solve Combinatorial Optimization Problems Using Real Quantum Machines
- Alternative Title
- 실제 양자 기계를 이용한 조합 최적화 문제 해결 방법에 대한 조사
- Abstract
- 조합 최적화 문제(COP)는 유한한 집합의 해 중에서 최적의 값을 찾는 문제이다. 가능한 해의 집합이 커질수록 문제의 복잡성이 증가하며, 현재의 고전적인 컴퓨터 기술로는 합리적인 시간 내에 해결하기 어렵다. 양자 어닐링 (QA)은 고전적인 시뮬레이션 어닐링(SA) 방법으로 해결할 수 없는 문제에 대한 대안이 될 수 있다. 따라서 QA 방식을 적용한 특수 목적의 양자 어닐러를 이용하여 이러한 문제를 해결하려는 다양한 시도가 이루어져 왔다. 본 설문조사에서는 양자 어닐러를 활용하여 실제 규모의 COP를 해결한 최근 연구들을 분석한다. 이를 통해, 기존 양자 어닐러의 하드웨어 한계를 극복하기 위해 COP의 크기를 어떻게 줄일 수 있을지 논의한다. 또한, 각 연구에서 고전적 모의 어닐링과 양자 어닐링 방법의 결과를 비교하고 분석하여 양자 어닐러가 실제 규모의 COP 에 적용 가능함을 입증하였다.|A combinatorial optimization problem (COP) is the problem of finding the optimal solution in a finite set. When the size of the feasible solution set is large, the complexity of the problem increases, and it is not easy to solve in a reasonable time with the current classical computer technology. Quantum annealing (QA) is a method that replaces classical simulated annealing (SA) methods that do not solve these cases. Therefore, several attempts have been made to solve this problem using a special-purpose quantum annealer to which the QA method is applied. In this survey, we analyze recent studies that solve real-scale COPs using quantum annealers. Through this, we discuss how to reduce the size of the COP to be input to overcome the hardware limitations of the existing quantum annealer. Additionally, we demonstrated the applicability of quantum annealer to COP on a practical scale by comparing and analyzing the results of the classical simulated annealing and quantum annealing methods from each study.
- Issued Date
- 2025
- Awarded Date
- 2025-02
- Type
- Dissertation
- Publisher
- 국립부경대학교 대학원
- Alternative Author(s)
- HENG SOVANMONYNUTH
- Affiliation
- 국립부경대학교 대학원
- Department
- 대학원 인공지능융합학과
- Advisor
- Youngsun Han
- Table Of Contents
- I. Introduction 1
1. Motivation 1
2. Contribution 2
3. Thesis Outline 2
II. Background 4
1. Combinatorial Optimization Problem 4
2. Quantum Annealing 5
3. Real Quantum Annealing Machines 6
3.1. CMOS Annealer 7
3.2. Digital Annealer 7
3.3. D-Wave Annealer 8
4. Decomposition 10
III. Problem Categorization 11
1. Graph Partitioning and Clustering Problems 11
1.1. Graph Partitioning 11
1.2. Community Detection 12
1.3. Detecting Multiple Communities 12
1.4. Maximum Clique Problem 13
1.5. Core-Periphery Partitioning 13
2. Factorization Problems 14
2.1. Prime Factorization 14
2.2. Matrix Factorization 14
3. Prediction Problem 15
3.1. Finite-Set Model Predictive Control 15
3.2. Feature Selection 15
4. Other Well-Known Problems 16
4.1. Support Vector Machine 16
4.2. Nurse Scheduling Problem 17
4.3. Traffic Flow Optimization 17
IV. Methodology 18
1. Graph Partitioning and Clustering Problems 18
1.1. Graph Partitioning 18
1.2. Community Detection 19
1.3. Detecting Multiple Communities 20
1.4. Maximum Clique Problem 21
1.5. Core-Periphery Partitioning 24
2. Factorization Problems 24
2.1. Prime Factorization 24
2.2. Matrix Factorization 25
3. Prediction Problems 25
3.1. Finite-Set Model Predictive Control 26
3.2. Feature Selection 27
4. Other Well-Known Problems 28
4.1. Support Vector Machine 28
4.2. Nurse Scheduling Problem 28
4.3. Traffic Flow Optimization 30
V. Performance Evaluation 32
1. Optimization Formulation 32
1.1. K-concurrent Approach 32
1.2. Qbsolv Algorithms 33
1.3. Reverse Annealing 33
2. Performance Comparison 34
VI. Conclusion & Discussion 37
Bibliography 39
Acknowledgement 48
Publication 49
- Degree
- Master
- Files in This Item:
-
-
Download
A Survey on How to Solve Combinatorial Optimization Problems Using Real Quantum Machines.pdf
기타 데이터 / 4.07 MB / Adobe PDF
-
Items in Repository are protected by copyright, with all rights reserved, unless otherwise indicated.