Efficient parallelization of quantum basis state shift
Lj Budinski, Ossi Niemimäki, Roberto Zamora-Zamora, Valtteri Lahtinen
Abstract
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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" overflow="scroll"> <mml:mn>15</mml:mn> <mml:mi>n</mml:mi> <mml:mo>+</mml:mo> <mml:mn>74</mml:mn> </mml:math> two-qubit CX gates in the parallel circuit, using a total of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" overflow="scroll"> <mml:mn>2</mml:mn> <mml:mi>n</mml:mi> <mml:mo>−</mml:mo> <mml:mn>2</mml:mn> </mml:math> 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.