Decomposition of Sparse Amplitude Permutation Gates with Application to Preparation of Sparse Clustered Quantum States

In this work we consider a novel heuristic decomposition algorithm for $n$-qubit gates that implement specified amplitude permutations on sparse states with $m$ non-zero amplitudes. These gates can be useful as an algorithmic primitive for higher-order algorithms. We demonstrate this by showing how it can be used as a building block for a novel sparse state preparation algorithm, Cluster Swaps, which is able to significantly reduce CX gate count compared to alternative methods of state preparation considered in this paper when the target states are clustered, i.e. such that there are many pairs of non-zero amplitude basis states whose Hamming distance is 1. Cluster Swaps can be useful for amplitude encoding of sparse data vectors in quantum machine learning applications.