  Unitary Coined Discrete-Time Quantum Walks (UC-DTQW) constitute a universal
model of quantum computation, meaning that any computation done by a general
purpose quantum computer can either be done using the UC-DTQW framework. In the
last decade,s great progress has been done 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
UC-DTQW, which is composed at the time of two unitary operators: the shift and
coin operators. We conceive the shift operator of the system as the unitary
matrix form of the adjacency matrix associated to the graph on which the
UC-DTQW 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 or
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 to a quantum circuit, and any quantum circuit acting on a bipartite
system will be always associated to a 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 multigraph on which the quantum
walk takes place, and provide a description of how this can be implemented in
circuit form.
