Resource-Efficient Synthesis of Sparse Quantum States

Preparing a quantum circuit that implements a given sparse state is an important building block that is necessary for many different quantum algorithms. In the context of fault-tolerant quantum computing, the so-called non-Clifford gates are much more expensive to perform than the Clifford ones. We hence provide an algorithm for synthesizing sparse quantum states with a special care for quantum resources. The circuit depth, ancilla count, and crucially non-Clifford count of the circuit produced by the algorithm are all linear in the sparsity when access to arbitrary-angled rotations is given. When compiled down to the standard Clifford+T gate set, several constructions can be given for increasingly better T-count and depth at the expense of a larger number of ancillae. The most optimised construction for T-count reaches O (s+ 2(1/ε)) T gates for error ε. The constructions are broken into two parts, one that synthesises a generalized W-state, well studied in the literature; and the second which is a classical reversible circuit implementing a permutation that maps the basis states of the W-state to those of the target sparse quantum state. We reduce this problem to the diagonalization of a binary matrix, using a specific set of elementary matrix operations corresponding to the classical reversible gates. We then solve this problem using a new version of Gauss-Jordan elimination, that minimizes the circuit complexities including circuit depth using parallel elimination steps. When the circuit is applied in one direction, we notice that all occurrences of (the expensive) Toffoli gates can all be replaced by adaptive Clifford circuits, leading to a better non-Clifford count.