  Quantum walks (QWs) are of interest as examples of uniquely quantum behavior
and are applicable in a variety of quantum search and simulation models.
Implementing QWs on quantum devices is useful from both points of view. We
describe a prototype one-dimensional discrete time QW algorithm that economizes
resources required in its implementation. Our algorithm needs only a single
shift (increment) operation. It also allows complete flexibility in choosing
the shift circuit, a resource intensive part of QW implementations. We
implement the shift using the quantum Fourier transform (QFT), yielding, to
date, the most efficient and scalable, quadratic size, linear depth circuit for
the basic QW. This is desirable for Noisy Intermediate-Scale Quantum (NISQ)
devices, in which fewer computations implies faster execution and reduced
effects of noise and decoherence. As the QFT diagonalizes unitary circulant
matrices, we generalize the shift in the basic QW to introduce spatial
convolutions in the QW. We demonstrate our basic QW algorithm using the QFT
based shift by running it on publicly accessible IBM quantum computers.
