Logarithmic-depth quantum circuits for Hamming weight projections
Soorya Rethinasamy, Margarite L. LaBorde, Mark M. Wilde · Physical Review A · 2024
A pure state of fixed Hamming weight is a superposition of computational basis states such that each bitstring in the superposition has the same number of ones. Given a Hilbert space of the form $\mathcal{H}={({\mathbb{C}}_{2})}^{\ensuremath{\bigotimes}n}$, or an $n$-qubit system, the identity operator can be decomposed as a sum of projectors onto subspaces of fixed Hamming weight. In this work, we propose several quantum algorithms that realize a coherent Hamming weight projective measurement on an input pure state, meaning that the post-measurement state of the algorithm is the projection of the input state onto the corresponding subspace of fixed Hamming weight. We analyze a depth-width tradeoff for the corresponding quantum circuits, allowing for a depth reduction of the circuits at the cost of more control qubits. For an $n$-qubit input, the depth-optimal algorithm uses $\mathcal{O}(n)$ control qubits and the corresponding circuit has depth $\mathcal{O}(log(n))$, assuming that we have the ability to perform qubit resets. Furthermore, the proposed algorithm construction uses only one- and two-qubit gates.