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

1. Problem Statement

The paper addresses the challenge of implementing discrete circular convolution on quantum hardware.

• Physical Constraints: A direct bilinear multiplication of quantum amplitudes (the naive definition of convolution) is physically impossible as a unitary operation (Lomont's no-go argument).
• Existing Approaches: Previous work (e.g., Zhou & Wang; Castelazo et al.) established that convolution can be viewed as a linear operator acting on basis-indexed vectors, implementable via the Linear-Combination-of-Unitaries (LCU) framework. However, these approaches often treat the kernel preparation symmetrically or rely on Fourier-domain methods that require specific oracle access.
• Key Limitation: Standard symmetric LCU implementations (using the same state preparation $PREP_b$ on both sides of the circuit) result in weights proportional to $|b_i|^2$, which destroys the complex phase information of the kernel coefficients $b_i$. This is fatal for convolution, which relies on the complex coefficients themselves.

2. Methodology

The authors propose a novel framework based on Asymmetric LCU and Modular Addition to realize quantum convolution.

A. Asymmetric LCU Formulation

The core insight is that circular convolution over $\mathbb{Z}/N\mathbb{Z}$ can be realized as an asymmetric post-selected block:

• Kernel State ($|b\rangle$): Supplied as an input ancilla state (prepared by $PREP_b$).
• Post-selection State ($|u\rangle$): A fixed, uniform superposition state $|u\rangle = \frac{1}{\sqrt{N}}\sum |i\rangle$.
• Mechanism: The circuit applies a controlled-shift unitary conditioned on the kernel index. By projecting the ancilla onto the uniform state $|u\rangle$ (rather than the kernel state $|b\rangle$), the resulting operation preserves the complex coefficients $b_i$ directly, rather than their squared magnitudes.
• Efficiency: If the kernel state $|b\rangle$ is already available from an upstream quantum routine, the convolution subroutine requires only the fixed uncompute operation $PREP_u^\dagger$, eliminating the need for a kernel-dependent inverse preparation $PREP_b^\dagger$.

B. Modular Adder as the SELECT Operator

The authors establish a direct equivalence between the SELECT operator in the LCU framework and Modular Addition:

• The group action of the cyclic group $\mathbb{Z}/N\mathbb{Z}$ corresponds to modular addition in the computational basis: $|i\rangle|k\rangle \to |i\rangle|k+i \pmod N\rangle$.
• Therefore, any standard quantum modular adder (e.g., Ripple-Carry or QFT-based) can serve as the $SELECT_L$ block.

C. $J_n$-Symmetrization and Hermiticity

To facilitate advanced spectral processing (like QSVT), the authors introduce a Reversal Matrix $J_n = X^{\otimes n}$ (bitwise NOT).

• Reflected Shifts: They define a symmetrized shift operator $\tilde{L}_{i,n} = L_{i,n} J_n$.
• Hermitian Operator: The symmetrized convolution operator is defined as $H_n(b) = \sum b_i \tilde{L}_{i,n}$.
• Key Property: For real-valued kernels, $H_n(b)$ is strictly Hermitian. This is a crucial distinction from standard convolution operators, which are generally non-Hermitian even for real kernels.
• Relation: Standard convolution $C_n(b)$ is related to the symmetrized version by a single input layer: $C_n(b) = H_n(b)J_n$.

D. Recursive Construction and Compilation

The paper provides two implementations for the reflected shift block:

1. Structural Recursion: A direct recursive definition of the reflected generator $U_n$ that exposes the operator algebra. This is structurally transparent but not gate-optimal ($O(n^4)$ CNOTs).
2. Optimized Bitwise Compilation: An exactly equivalent, gate-optimized carry-propagation implementation. This reduces the complexity to $O(n^3)$ CNOTs (or $O(n^2)$ macro blocks), matching the efficiency of standard ripple-carry adders.

3. Key Contributions

1. Explicit Asymmetric-LCU Bridge: The paper formally bridges circulant-matrix implementations and group-convolution frameworks by explicitly stating the asymmetric post-selection condition ($|u\rangle$ vs $|b\rangle$) required to preserve complex phases.
2. Hermitian Pipeline for Real Kernels: The introduction of the $J_n$-symmetrized operator $H_n(b)$ provides a native Hermitian interface for real-valued kernels. This allows the direct application of Quantum Singular Value Transformation (QSVT) without needing auxiliary Hermitian dilations or normal equations (which would square the condition number).
3. Recursive Normal Form: A structurally transparent recursive construction for the reflected shift family, paired with an optimized bitwise compilation that proves exact equivalence to standard modular adders.
4. Resource Analysis: A detailed complexity analysis comparing the new method against classical FFT, Fourier-domain quantum approaches, and standard LCU methods under different input models (coherent quantum states vs. classical vectors).

4. Results and Complexity

• Circuit Complexity:
  • Direct Recursive: $O(\log^3 N)$ macro blocks, $O(\log^4 N)$ primitive CNOTs.
  • Optimized Bitwise: $O(\log^2 N)$ macro blocks, $O(\log^3 N)$ primitive CNOTs.
  • Standard Adders: Ripple-carry adders offer $O(\log N)$ primitive gate complexity; QFT adders offer $O(\log^2 N)$.
• Success Probability: The success probability of the post-selection is $p_{succ} = \frac{\|C_n(b)a\|^2}{N \|a\|^2 \|b\|^2}$. Amplitude amplification can be used to boost this, adding a factor of $1/\sqrt{p_{succ}}$ to the runtime.
• Input Models:
  • Coherent Input: If $|a\rangle$ and $|b\rangle$ are already quantum states, the cost is dominated by the convolution block ($O(\text{polylog } N)$).
  • Classical Input: If inputs are classical vectors, the dominant cost is state preparation/loading ($T_{load}(N)$), which typically overwhelms the convolution circuit cost.
• Deconvolution: For deconvolution (inverse filtering), the Hermitian nature of $H_n(b)$ allows QSVT to approximate the inverse with a polynomial degree scaling linearly with the condition number $\kappa$, avoiding the $\kappa^2$ scaling associated with normal-equation approaches.

5. Significance

• Theoretical Unification: The work unifies disparate views of quantum convolution (circulant matrices, group theory, and modular arithmetic) under a single asymmetric LCU statement.
• Practical Efficiency: It clarifies that for coherent quantum inputs (a common scenario in quantum signal processing pipelines), the convolution block is highly efficient and avoids the overhead of re-preparing the kernel.
• Enabling QSVT: By providing a native Hermitian formulation for real kernels, the paper removes a significant barrier to applying powerful spectral transformation tools (QSVT) to convolution problems, specifically for tasks like deblurring or inverse filtering.
• Modularity: The framework treats the modular adder as a black box, allowing hardware architects to swap in the most efficient adder (ripple-carry, QFT, or carry-lookahead) without altering the high-level convolution logic.

In summary, this paper provides a rigorous, optimized, and Hermitian-friendly framework for implementing quantum convolution, resolving phase preservation issues in LCU and enabling direct spectral processing for real-valued kernels.