Asymmetric Linear-Combination-of-Unitaries Realization of Quantum Convolution via Modular Adders

Abstract

Discrete circular convolution over $\mathbb{Z}/N\mathbb{Z}$ is a linear operator and can be implemented on quantum hardware within the linear-combination-of-unitaries (LCU) framework. In this work, we make this connection explicit through an asymmetric-LCU formulation: circular convolution is the postselected block of a circuit whose controlled-shift unitary is modular addition on computational-basis states. The asymmetry is essential: fixing the postselection state to the uniform state $|u\rangle$ while supplying the kernel state $|\mathbf{b}\rangle$ as the input ancilla naturally preserves the complex coefficients $b_i$ within the block, whereas a symmetric overlap would yield $|b_i|^2$ weights and erase their phases. Accordingly, when $|\mathbf{a}\rangle$ and $|\mathbf{b}\rangle$ are supplied by upstream quantum routines, the convolution subroutine requires only the fixed uncompute $\mathrm{PREP}_u^\dagger$, completely avoiding the need for a kernel-dependent inverse preparation $\mathrm{PREP}_b^\dagger$. We then introduce a reversal matrix $J_n=X^{\otimes n}$ and define reflected shifts $\widetilde{L}_{i,n}=L_{i,n}J_n$. This symmetrization yields a recursive operator algebra for convolution that is natively compatible with LCU/block-encoding workflows. The resulting symmetrized operator differs from circular convolution only by one known input-side $J_n$ layer. Crucially, for real-valued kernels, the resulting operator $H_n(\mathbf{b})=\sum_i b_i\widetilde{L}_{i,n}$ is Hermitian, providing a direct Hermitian interface for quantum singular value transformation (QSVT) and related spectral transformations. Based on this framework, we present a transparent recursive construction, paired with an exactly equivalent optimized bitwise compilation of the same $\mathrm{SELECT}$ block. Finally, we evaluate implementation trade-offs and resource scaling under explicit cost-model conventions.