요약일 실시예에 따른 그래프 다중 채색 문제 수행 장치는 노드 및 간선으로 구성된 그래프 다중 채색 문제를 획득하는 동작; 각 노드 i(i는 노드의 식별 정보)에 채색 가능한 색상의 경우의 수 j(j는 경우의 수의 식별 정보)를 조합한 식별 정보 i, j 각각에 큐비트를 할당하는 동작; 동일한 노드의 식별 정보를 갖는 모든 큐비트 간에 W-State 게이트를 연결하는 동작; 서로 인접한 노드의 식별 정보를 갖는 서로 다른 두가지 큐비트 간에 Cost Function Hamiltonian 게이트를 연결하는 동작; 동일한 노드의 식별 정보를 갖는 서로 다른 두가지 큐비트 간에 XY Hamiltonian 게이트를 연결하는 동작; 및 상기 W-state, Cost Function Hamiltonian, XY Hamiltonian 게이트가 연결된 양자 회로를 동작시켜 상기 큐비트로부터 상기 그래프 다중 채색 문제의 해답을 도출하는 동작을 수행할 수 있다.
