Unitary coined discrete-time quantum walks (UCDTQW) constitute a universal model of computation, meaning that any computation done by a general purpose quantum computer can either be done using the UCDTQW framework. In the last decades, great progress has been made in this field by developing quantum walk-based algorithms that can outperform classical ones. However, current quantum computers work based on the quantum circuit model of computation, and the general mapping from one model to the other is still an open problem. In this work, we provide a matrix analysis of the unitary evolution operator of UCDTQW, which is composed at a time of a shift and a coin operators. We conceive the shift operator of the system as the unitary matrix form of the adjacency matrix associated with the graph on which the UCDTQW takes place, and provide a set of equations to transform the latter into the former and vice versa. However, this mapping modifies the structure of the original graph into a directed multigraph, by splitting single edges and arcs of the original graph into multiple arcs. Thus, the fact that any unitary operator has a quantum circuit representation means that any adjacency matrix that complies with the transformation equations will be automatically associated with a quantum circuit, and any quantum circuit acting on a bipartite system will be always associated with a directed multigraph. Finally, we extend the definition of the coin operator to a superposition of coins in such a way that each coin acts on different vertices of the directed multigraph on which the UCDTQW takes place, and provide a description of how this can be implemented in circuit form.
