Explicit Block Encoding of Difference-of-Gaussian Operators on a Periodic Grid

1. Problem Statement

The Difference-of-Gaussian (DoG) operator is a fundamental tool in image processing (feature/edge detection), quantum machine learning, and finite-difference methods for approximating the Laplacian-of-Gaussian. However, implementing DoG on quantum computers faces significant challenges:

• Dimensional Bottleneck: Representing high-resolution, multi-dimensional systems classically scales as $O(N^D)$, making them intractable.
• Inefficiency of Existing Quantum Methods:
  • Basis-state encodings (e.g., NEQR): Rely on quantum arithmetic circuits where depth and gate counts scale with image size and pixel bit-depth, treating filter coefficients as generic data without exploiting their structure.
  • Standard Block Encoding: Typically relies on black-box oracles like Quantum Random Access Memory (QRAM) or unary iteration to load matrix entries. These methods incur high gate costs (often intractable for modest sizes) and lack structure-specific optimization.
• Goal: Develop an explicit, efficient quantum circuit for the DoG operator that exploits its mathematical structure to avoid black-box oracles and achieve a constant subnormalization factor independent of grid size or dimension.

2. Methodology

The authors propose a novel block-encoding construction based on the Linear Combination of Unitaries (LCU) framework, leveraging the natural probabilistic decomposition of the DoG operator.

Core Mathematical Insight

The discrete DoG operator $A_h$ is defined as a weighted sum of cyclic shift operators $S_t$:
$$A_h = \sum_{t \in T} (p_t - q_t) S_t$$
where:

• $T$ is a finite set of spatial offsets (stencil).
• $p_t$ and $q_t$ are two normalized discrete Gaussian probability distributions (with variances $\sigma_p^2 < \sigma_q^2$).
• The coefficients are the difference of these distributions: $c_t = p_t - q_t$.

Circuit Construction

Instead of loading signed amplitudes directly (which is expensive), the authors encode the sign difference using a single auxiliary qubit:

1. Registers:
   • Indicator Register ($H_{ind}$): 1 qubit to branch between the two Gaussian components.
   • Shift-Label Register ($H_{shift}$): Encodes the shift index $t$.
   • Data Register ($H_{data}$): Encodes the grid state $|j\rangle$.
2. State Preparation ($P$):
   • A Hadamard gate creates a superposition on the indicator qubit.
   • Controlled Gaussian loaders ($G_p$ and $G_q$) prepare the magnitude states $\sum \sqrt{p_t}|t\rangle$ and $\sum \sqrt{q_t}|t\rangle$ on the shift register.
   • This creates a state: $\frac{1}{\sqrt{2}}(|0\rangle \sum \sqrt{p_t}|t\rangle + |1\rangle \sum \sqrt{q_t}|t\rangle)$.
3. Phase Encoding:
   • A Pauli-Z gate is applied to the indicator qubit. This flips the phase of the $|1\rangle$ branch, effectively converting the sum of the two branches into their difference: $|0\rangle \sum \sqrt{p_t}|t\rangle - |1\rangle \sum \sqrt{q_t}|t\rangle$.
4. Selection ($SEL$):
   • A controlled-shift operator applies $S_t$ to the data register based on the shift register state.
5. Uncomputation:
   • The inverse preparation $P^\dagger$ is applied, and the indicator/shift registers are projected onto $|0\rangle$.
   • The resulting operation on the data register is $\frac{1}{2} A_h$.

3. Key Contributions

1. Explicit Block Encoding with Constant Subnormalization:

   • The method achieves a subnormalization factor $\lambda = 2$, which is constant and independent of the grid size $N$, spatial dimension $D$, or stencil width $|T|$.
   • It avoids QRAM and signed amplitude loading, relying instead on efficient Gaussian state preparation circuits and controlled shifts.
   • The non-Clifford cost is dominated by the Gaussian loaders and controlled shifts, with T-gate complexity scaling efficiently ($O(s^2)$ or $O(2^s)$ depending on the loader method used).

2. Spectral Characterization:

   • The authors prove that the DoG operator is diagonalized by the discrete Fourier basis.
   • The eigenvalues are given by the difference of the Fourier transforms of the two Gaussian kernels: $\mu(\omega) = \hat{p}(\omega) - \hat{q}(\omega)$.
   • Under symmetric kernels, the operator is Hermitian, allowing direct application of quantum signal processing (QSP) and qubitization without requiring Hermitian dilation.

3. Success Probability Analysis:

   • Exact Formula: Derived a closed-form expression for the success probability: $P_{success} = \frac{1}{4} \sum_\omega |\mu(\omega)|^2 |\hat{v}_h(\omega)|^2$. This shows success depends on the input signal's power spectrum overlapping with the DoG passband.
   • Asymptotic Scaling: For smooth functions on a refining grid ($h \to 0$), the success probability scales as $O(h^4)$.
   • Comparison: While this matches the $O(h^4)$ scaling of explicit Laplacian encodings, the DoG method maintains a constant $\lambda=2$. In contrast, standard Laplacian encodings often have $\lambda \propto 1/h^2$, which compresses the spectrum and complicates downstream eigenvalue transformations.

4. Results

• Numerical Validation: A 1D example ($N=16$, $D=1$) confirmed the bandpass nature of the transfer function (zero response at DC, peak at intermediate frequencies, suppression at high frequencies).
• Scaling Verification: Numerical experiments showed that the success probability for a sinusoidal input follows the theoretical $O(h^4)$ scaling as grid resolution increases, with the ratio of exact to asymptotic probability converging to 1.
• Resource Efficiency: The circuit requires only three single-qubit Clifford gates (Hadamard, Pauli-Z) plus the Gaussian loaders and controlled shifts. The 1-norm of the coefficient vector is bounded by 2, ensuring the theoretical subnormalization holds.

5. Significance

• Efficiency for Quantum Image Processing: This method provides a tunable, wide-stencil bandpass filter that can be integrated directly into quantum linear algebra primitives (like QSVT) without the overhead of arithmetic circuits or QRAM.
• Optimized for Downstream Tasks: The constant subnormalization ($\lambda=2$) is a critical advantage for Hamiltonian simulation and eigenvalue transformations. Because the eigenvalues do not shrink with grid refinement (unlike methods where $\lambda$ grows), the effective simulation time and polynomial degrees required for spectral transformations remain independent of the grid spacing $h$.
• Generalizability: The approach is not limited to Gaussians; it applies to any operator expressible as a signed linear combination of normalized distributions over unitary shifts, suggesting potential extensions to other differential operators or filters.

In summary, the paper presents a mathematically rigorous and resource-efficient quantum circuit for the DoG operator, bridging the gap between classical signal processing concepts and practical quantum algorithm implementation by exploiting the operator's inherent probabilistic structure.