A quantum method for graph edge coloring problem
سال انتشار: 1400
نوع سند: مقاله کنفرانسی
زبان: انگلیسی
مشاهده: 214
فایل این مقاله در 9 صفحه با فرمت PDF قابل دریافت می باشد
- صدور گواهی نمایه سازی
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
COMCONF08_055
تاریخ نمایه سازی: 8 آبان 1400
چکیده مقاله:
This paper demonstrates attack to the graph edge coloring problem by exploiting quantum computationscapabilities. We expect by exploiting quantum advantages be able to tackle space and time complexity of this problem.The graph edge coloring problem is coloring graph's edges with possible least number of colors (edge chromaticnumber) such that no two adjacent edges have the same color. It is an NP complete problem, means it's decisionversion can be verified in polynomial time. However, the time taken to obtain a solution for it is not polynomial.Quantum computers can potentially solve problems that are computationally intractable on a classical computer inpolynomial time using quantum-mechanical effects such as superposition and entanglement.In this research we try to combine capabilities of quantum computing with activities need for solving thisproblem. By mapping graph structure to a net of qubits we will be able to attack this problem to solve it by using ofquantum computations advantages as speedup/parallelism. We will propose a method step by step from ۲_edgecoloring, ۳_edge coloring gradually to χ′(G)_edge(edge chromatic number) coloring. At last we present the sourcecode for χ′(G)_edge coloring in quantum IBM Qiskit language that simulate the solving quantum circuit. We will showcomplexity of our method is O(|E|۲) & it's quantum circuit depth is Θ(|E|۴).
کلیدواژه ها:
نویسندگان
Hossein Abdolmaleki
Department of Engineering Science, College of Engineering, University of Tehran, Tehran, Iran
Nayereh Majd
Department of Engineering Science, College of Engineering, University of Tehran, Tehran, Iran