چکیده مقاله
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 2_edgecoloring, 3_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 2 & it's quantum circuit depth is Θ E 4
کلیدواژهها
نویسندگان
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
شیوه ارجاع
Abdolmaleki, Hossein and Majd, Nayereh,1400,A quantum method for graph edge coloring problem,8th National Congress of Electrical and Computer Engineering of Iran,Tehran
ارائهشده در
مجموعه مقالات هشتمین کنگره ملی تازه های مهندسی برق و کامپیوتر ایران28 بهمن 1400 · تهران