arXiv:2610.02172
Robust exponential lower bounds for fermionic and bosonic Gaussian ranks
Fuchuan Wei, Kong-Wing Wu, Zhengwei Liu, Zi-Wen Liu
Abstract
The power and limitations of classical simulation are central to understanding quantum computational advantages. A leading simulation paradigm is based on coherent decomposition into classically tractable free states where the decomposition rank determines the simulation complexity. Proving strong lower bounds on this number is a notoriously difficult and mathematically rich problem, as exemplified by the qubit stabilizer rank problem. Here, we study the Gaussian version of this problem in both bosonic and fermionic systems and establish robust exponential lower bounds on Gaussian rank. In particular, we prove that for every pure non-Gaussian state on finitely many modes, with definite parity in the fermionic case, the approximate border Gaussian rank of its tensor powers grows at least exponentially at any fixed norm error below one. Our proofs combine reduction to four modes with Majorana spectral bounds for fermions, and Gaussian postselection with an entropy-based rank bound for bosons. As concrete examples, we derive explicit exponential lower bounds for the four-mode fermionic GHZ state and the bosonic single-photon state. The bosonic results require no assumption on the energy of the target state. Our results show that non-Gaussianity universally entails exponential Gaussian decomposition complexity, setting fundamental limitations on decomposition-based classical simulation of bosonic and fermionic systems.
AI Summary
The paper asks whether tensor powers of non-Gaussian pure states necessarily require exponentially many terms in coherent Gaussian decompositions, a simulation framework analogous to stabilizer decompositions. It treats fermionic states of definite parity and bosonic states on finitely many modes, allowing Gaussian summands entangled across copies. For every fixed normalized non-Gaussian pure state $|\psi\rangle$, it proves that some $c_\psi>0$ satisfies $\bar\chi_G^{(\delta)}(|\psi\rangle^{\otimes k})\ge e^{c_\psi k}$ for sufficiently large $k$, at every fixed norm error $0\le\delta<1$. Here approximate border Gaussian rank permits limits of decompositions whose coefficients can diverge and cancel. The rate can be chosen independently of $\delta$, and the bosonic theorem assumes no energy bound. For the four-mode fermionic state $|M\rangle=(|0000\rangle+|1111\rangle)/\sqrt2$, the bound is $c(1-\delta^2)(343/243)^k$. Single-photon tensor powers have eventual lower bound $(11/10)^k$ at fixed error and border rank greater than $(5/4)^k$ at zero error. The fermionic proof reduces general resources to four modes by Gaussian postselection, then compares Majorana-generated matrix ranks and spectra. The bosonic proof postselects states near nonvacuum number states and compares photon-truncated Schmidt-rank bounds for Gaussian terms with environment Rényi entropy. Typical measurement records transfer the bounds back without exponentially amplifying approximation error. The optimal exponential rates remain undetermined, including whether they depend on approximation error. The Gaussian constraints used do not directly extend to stabilizer rank; the results constrain Gaussian-decomposition simulation rather than establish hardness for arbitrary classical simulation.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.