  The aim of this paper is to build quantum circuits that implement
discrete-time quantum walks having an arbitrary position-dependent coin
operator. The position of the walker is encoded in base 2: with $n$ wires, each
corresponding to one qubit, we encode $2^n$ position states. The data necessary
to define an arbitrary position-dependent coin operator is therefore
exponential in $n$.
  We first propose a circuit implementing the position-dependent coin operator,
that is naive, in the sense that it has exponential depth and implements
sequentially all appropriate position-dependent coin operators. We then propose
a circuit that "transfers" all the depth into ancillae, yielding a final depth
that is linear in $n$ at the cost of an exponential number of ancillae. The
main idea of this linear-depth circuit is to implement in parallel all coin
operators at the different positions.
  Finally, we extend the result of Ref. [2] from position-dependent unitaries
which are diagonal in the position basis to position-dependent $2 \times
2$-block-diagonal unitaries: indeed, we show that for a position dependence of
the coin operator (the block-diagonal unitary) which is smooth enough, one can
find an efficient quantum-circuit implementation approximating the coin
operator up to an error $\epsilon$ (in terms of the spectral norm), the depth
and size of which scale as $O(1/\epsilon)$.
  A typical application of the efficient implementation would be the quantum
simulation of a relativistic spin-1/2 particle on a lattice, coupled to a
smooth external gauge field; notice that recently, quantum spatial-search
schemes have been developed which use gauge fields as the oracle, to mark the
vertex to be found [3, 4]. A typical application of the linear-depth circuit
would be when there is spatial noise on the coin operator (and hence a
non-smooth dependence in the position).
