Quantum circuits for discrete-time quantum walks with position-dependent coin operator

Abstract: 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 i m e s 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

e p s i l o n

(in terms of the spectral norm), the depth and size of which scale as

O (1 / e p s i l o n)

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

Recommendations

Cites work

Cited in

(6)

This page was built for publication: Quantum circuits for discrete-time quantum walks with position-dependent coin operator

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6107780)