Low-depth quantum symmetrization

Quantum symmetrization is the task of transforming a non-strictly increasing list of n integers into an equal superposition of all permutations of the list (or more generally, performing this operation coherently on a superposition of such lists). This task plays a key role in initial state preparation for first-quantized simulations. A weaker version of symmetrization in which the input list is \emph{strictly} increasing has been extensively studied due to its application to fermionic systems, but the general symmetrization problem with repetitions in the input list has not been solved previously. We present the first quantum algorithm for the general symmetrization problem. Our algorithm, based on (quantum) sorting networks, uses O(logn) depth and O(nlogm) ancilla qubits where m is the greatest possible value of the list, enabling efficient simulation of bosonic quantum systems in first quantization. Furthermore, our algorithm can prepare (superpositions of) Dicke states of any Hamming weight in O(logn) depth using O(nlogn) ancilla qubits. We also propose an O(log2n)-depth quantum algorithm to transform second-quantized states to first-quantized states. Using this algorithm, QFT-based quantum telescope arrays can image brighter photon sources, extending quantum interferometric imaging systems to a new regime.