Efficient parallelization of quantum basis state shift

Abstract

Basis state shift is central to many quantum algorithms, most notably the quantum walk. Efficient implementations are of major importance for achieving a quantum speedup for computational applications. We optimize the state shift algorithm by incorporating the shift in different directions in parallel. This provides a significant reduction in the depth of the quantum circuit in comparison to the currently known methods, giving a linear scaling in the number of gates versus working qubits in contrast to the quadratic scaling of the state-of-the-art method based on the quantum Fourier transform. For a one-dimensional array of size $2^n$ for $n>4$, we derive the total number of $15n+74$ two-qubit $CX$ gates in the parallel circuit, using a total of $2n-2$ qubits including an ancilla register for the decomposition of multi-controlled gates. We focus on the one-dimensional and periodic shift, but note that the method can be extended to more complex cases.

References in corpus (1)

• Universal computation by quantum walk

Cited by in corpus (7)

• Efficient Quantum Lattice Gas Automata
• Opportunities and challenges of quantum computing for climate modelling
• A multiple-circuit approach to quantum resource reduction with application to the quantum lattice Boltzmann method
• Float Lattice Gas Automata: A connection between Molecular Dynamics and Lattice Boltzmann Method for quantum computers
• Adaptive Lattice Gas Algorithm: Classical and Quantum implementations
• Vortex Detection from Quantum Data
• Fully Quantum Lattice Gas Automata Building Blocks for Computational Basis State Encodings