Complex-Valued-Matrix Permanents: SPA-based Approximations and Double-Cover Analysis

Technical Summary: Complex-Valued-Matrix Permanents: SPA-based Approximations and Double-Cover Analysis

Problem Statement
The permanent of a complex-valued matrix is a fundamental quantity in fields such as Boson sampling (a candidate for demonstrating quantum supremacy) and probabilistic inference. Unlike the permanent of non-negative-real-valued matrices, which is already computationally intractable for large dimensions, the complex-valued case presents additional challenges due to "constructive and destructive interferences" between the real and imaginary parts of the terms in the permanent's summation. While the Sum-Product Algorithm (SPA) and Bethe approximations have been successfully applied to non-negative-real-valued matrices via Normal Factor Graphs (NFGs), extending these methods to complex-valued matrices remains an open problem. Specifically, it is unclear how SPA fixed points behave when transitioning from real to complex ensembles and whether established analytical relationships, such as those involving graph covers, hold in the complex domain.

Methodology
The authors extend factor-graph-based approximation techniques to complex-valued matrices using the following approach:

1. Double-Edge Normal Factor Graphs (DE-NFGs): Instead of applying SPA directly to a standard NFG for the complex permanent, the authors utilize DE-NFGs. They construct a specific DE-NFG, denoted $N_{DE}(\theta)$, designed such that its partition sum equals $|\text{perm}(\theta)|^2$. This formulation replaces binary variables with variables taking values in $\{0, 1\}^2$, allowing the representation of the squared modulus of the permanent.
2. Sum-Product Algorithm (SPA) Analysis: The authors investigate the behavior of the SPA on $N_{DE}(\theta)$. They employ a flooding schedule with midpoint damping to ensure convergence. The study focuses on ensembles of matrices where entries are i.i.d. complex random variables parameterized by an angle $\alpha \in [0, \pi]$, defining the support sector of the distribution.
3. Graph Cover Analysis: To analytically understand the Bethe approximation, the authors employ the theory of graph covers. They specifically analyze degree-2 covers (double covers) of the DE-NFG. This involves decomposing the double cover of the DE-NFG into disjoint unions of standard NFG covers and utilizing combinatorial counting techniques involving the cycle index of the symmetric group.
4. Asymptotic and Combinatorial Derivation: The paper derives exact expressions and asymptotic behaviors for the ratio of the true partition sum to the degree-2 Bethe approximation ($Z/Z_{B,2}$) for two specific cases: the all-one matrix and random complex matrices with zero-mean entries.

Key Contributions and Results

• Algorithmic Behavior and Degeneracy: Numerical experiments reveal two distinct regimes of SPA behavior based on the parameter $\alpha$:
  • Low $\alpha$ (Near Real-Valued): When $\alpha$ is below a certain threshold, SPA fixed-point messages degenerate into rank-1 matrices. In this regime, the approximation ratio behaves similarly to the square of the ratio observed in non-negative-real-valued matrices.
  • High $\alpha$ (Complex Gaussian): When $\alpha$ approaches $\pi$ (corresponding to standard complex Gaussian distributions), the SPA fixed-point messages and beliefs degenerate into diagonal matrices. In this regime, the Bethe approximation effectively approximates $\text{perm}(|\theta|^2)$ rather than $|\text{perm}(\theta)|^2$. The distribution of the approximation ratio becomes significantly more spread out, indicating a degradation in performance.
• Analytical Results via Double Covers:
  • The authors prove that the degree-2 Bethe partition sum for the DE-NFG, $Z_{B,2}(N_{DE}(\theta))$, can be expressed as the expected value of the squared modulus of the partition sum of a standard NFG cover: $\mathbb{E}[|Z(\tilde{N}(\theta))|^2]$.
  • For the all-one matrix, they derive an exact expression for $Z_{B,2}$ and show that the ratio $Z/Z_{B,2}$ scales asymptotically as $\sqrt{\pi n / e}$.
  • For zero-mean complex matrices (satisfying specific moment conditions), they derive exact expressions for the second moments of both the true partition sum and the degree-2 Bethe approximation. The asymptotic ratio is shown to scale as $\sqrt{(n + 1 + C)/e}$, where $C$ depends on the moments of the distribution.
• Validation of the "Square Law" Hypothesis: The paper investigates the relationship $Z(N)/Z_B(N) \approx (Z(N)/Z_{B,2}(N))^2$. The results indicate that this relationship holds when the argument of the matrix entries is confined within a certain threshold (near the real-valued case). However, the relationship fails when the distribution of $\theta$ tends toward the standard complex Gaussian distribution, where the SPA-based approximation loses its efficacy in capturing the interference effects of the complex permanent.

Significance
The paper provides a combined algorithmic and analytical perspective on approximating complex-valued matrix permanents. By utilizing DE-NFGs and graph cover analysis, the authors clarify the structural limitations of Bethe approximations in complex-valued settings. The work demonstrates that while SPA-based methods are robust for near-real-valued matrices, they undergo a qualitative change in behavior for highly complex (e.g., Gaussian) ensembles, where the approximation effectively shifts target from the squared modulus of the permanent to the permanent of the squared modulus. This insight helps define the boundaries of when such approximations remain meaningful for problems like Boson sampling and probabilistic inference involving complex amplitudes.