تقرير
Quantum Speedup for the Maximum Cut Problem
| العنوان: | Quantum Speedup for the Maximum Cut Problem |
|---|---|
| المؤلفون: | Chang, Weng-Long, Wong, Renata, Chung, Wen-Yu, Chen, Yu-Hao, Chen, Ju-Chin, Vasilakos, Athanasios V. |
| سنة النشر: | 2023 |
| المجموعة: | Quantum Physics |
| مصطلحات موضوعية: | Quantum Physics |
| الوصف: | Given an undirected, unweighted graph with $n$ vertices and $m$ edges, the maximum cut problem is to find a partition of the $n$ vertices into disjoint subsets $V_1$ and $V_2$ such that the number of edges between them is as large as possible. Classically, it is an NP-complete problem, which has potential applications ranging from circuit layout design, statistical physics, computer vision, machine learning and network science to clustering. In this paper, we propose a quantum algorithm to solve the maximum cut problem for any graph $G$ with a quadratic speedup over its classical counterparts, where the temporal and spatial complexities are reduced to, respectively, $O(\sqrt{2^n/r})$ and $O(m^2)$. With respect to oracle-related quantum algorithms for NP-complete problems, we identify our algorithm as optimal. Furthermore, to justify the feasibility of the proposed algorithm, we successfully solve a typical maximum cut problem for a graph with three vertices and two edges by carrying out experiments on IBM's quantum computer. Comment: 4 pages, 6 figures, The 28th Workshop on Compiler Techniques and System Software for High-Performance and Embedded Computing (CTHPC 2023), May 25-26 2023, National Cheng Kung University, Tainan, Taiwan. v2: indicated corresponding authors, included a link to the GitHub repository in Section "Code availability" |
| نوع الوثيقة: | Working Paper |
| الوصول الحر: | http://arxiv.org/abs/2305.16644Test |
| رقم الانضمام: | edsarx.2305.16644 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |