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

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|۴).

graph's edge coloring, quantum computing, net of qubit, superposition and entanglement, Qiskit language