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⟩$ while supplying the kernel state $|\mathbf{b}⟩$ 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}⟩$ and $|\mathbf{b}⟩$ are supplied by upstream quantum routines, the convolution subroutine requires only the fixed uncompute ${\mathrm{PREP}}_u^{†}$, completely avoiding the need for a kernel-dependent inverse preparation ${\mathrm{PREP}}_b^{†}$. We then introduce a reversal matrix $J_n=X^{\otimes n}$ and define reflected shifts ${\tilde{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{\tilde{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.