A leading simulation paradigm centres around coherent decomposition into classically tractable free states where the decomposition rank determines simulation complexity. Establishing key lower bounds on this number presents a notably difficult and mathematically rich problem, such as demonstrated by the qubit stabiliser rank problem.

The Gaussian version of this problem has been studied in both bosonic and fermionic systems, yielding strong exponential lower bounds on Gaussian rank. Specifically, it has been proven that for every pure non-Gaussian state on finitely many modes, with definite parity in the fermionic case, the approximate border Gaussian rank is at least proportional to the number of modes minus one.

## Exponential Scaling of Tensor Network Complexity Confirms Simulation Barriers Scientists at Tsinghua University and collaborating institutions have demonstrated that approximate border Gaussian rank, a measure of classical simulation cost, of tensor powers now grows exponentially with system size, improving upon previous nearly quadratic bounds. This breakthrough surpasses a critical threshold previously hindering definitive proof of exponential complexity for simulating quantum states using decomposition into simpler, classically manageable components.

Earlier methods failed to reach conjectured limits. The team’s findings apply universally to both fermionic and bosonic systems, establishing fundamental limitations on how efficiently these complex quantum behaviours can be modelled by conventional computers.

Explicit examples include exponential lower bounds derived from analysing the four-mode fermionic GHZ state and the single-photon bosonic state without assumptions about energy levels. These results demonstrate that non-Gaussianity universally entails exponential Gaussian decomposition complexity however current bounds do not yet reveal practical limits or indicate scalability towards realistically sized problems. Analysis establishes that the approximate border Gaussian rank of tensor powers grows at least exponentially for any fixed norm error below one.

Their proofs combine reduction to four modes with Majorana spectral bounds for fermions, and Gaussian postselection with an entropy-based rank bound for bosons. Understanding and characterising quantum advantage over classical computation is central to quantum information science; this motivates extensive study of classically simulating quantum systems and dynamics because more efficient general classical simulation methods leave less room for potential quantum speedups. A standard framework relies on decomposing states or operations into combinations of tractable components whose properties are computed efficiently, then combining their contributions to achieve overall simulation.

In this formalism, the free decomposition rank, the minimum number of free components needed in the decomposition, is a key parameter governing simulation cost. The longstanding stabilizer rank problem provides a prominent example concerning how the minimum number of stabilizer states grows in a coherent decomposition of T-state tensor powers, controlling the cost of stabilizer-decomposition-based universal quantum circuit simulation. Subexponential growth would enable subexponential-time classical simulation and thereby rule out exponential quantum speedup.

Fermionic linear optics with Gaussian inputs and occupation number measurements admits efficient classical simulation as do bosonic Gaussian circuits with Gaussian inputs, homodyne or heterodyne detection, and adaptive feed-forward. Non-Gaussian resources extend these models to universal computation: pure non-Gaussian parity eigenstates enable matchgate computation while cubic-phase resources supply nonlinearity for continuous variable universality; this motivates study of Gaussian rank and related measures of non-Gaussianity which underlie decomposition based algorithms in both settings.

They resolve the exponential lower bound problem for Gaussian rank in fermionic and bosonic systems proving unconditional bounds on approximate Gaussian rank of tensor powers of the standard four-mode fermionic GHZ state and the single photon state, more generally every fixed pure non-Gaussian state on finitely many modes.

The Gaussian setting entails subtleties absent from the stabilizer setting; unlike stabilizer states, Gaussian states form continuous families meaning a sequence of superpositions can converge to a target with no exact decomposition. Therefore, they consider border Gaussian rank given by smallest number needed for arbitrarily accurate approximation. Their bounds allow these limits and any constant norm error below one without input energy assumptions in the bosonic case.

This section formally defines Gaussian ranks, its border and approximate variants, and summarizes main results; logarithms are natural while entropies measured in nats. For state |ψ⟩, the Gaussian rank χG(|ψ⟩) is the minimum number of pure Gaussian states needed to express it as a linear combination allowing either parity Gaussian states in fermionic cases.

The border Gaussian rank χG(|ψ⟩) is the smallest r for which |ψ⟩ can be approximated arbitrarily closely by vectors of at most rank r; if no finite value suffices then corresponding rank is +∞. Single-photon state |1⟩ illustrates difference between exact and border ranks because coherent state converges on norm toward |1⟩as real ε→0 meaning single photon has border rank two but infinite exact one, Appendix A proves this statement giving separation for both.

To establish this, analysis reduces the problem to four modes establishing a lower bound then transferring back with controlled error; these are the smallest supporting definite parity pure non-Gaussian states. That proposition shows every 0 ≤δ Full argument including approximation control given appendix B. For t This work addresses a longstanding challenge: accurately quantifying how quickly simulation costs escalate as systems become more complex, previous attempts struggled to definitively prove this scaling behaviour beyond nearly quadratic increases.

Still, acknowledging that determining precise scaling exponents remains formidable these results represent significant progress nonetheless. Any quantum state differing slightly from easily simulated “Gaussian” states, those resembling simple harmonic motion, requires resources growing exponentially with system size for classical computers to mimic it; this finding clarifies why certain algorithms promise speedups because they inherently use non-Gaussian character and associated simulation difficulty. They quantified how quickly classical computers struggle to simulate quantum systems pinpointing an exponential increase in computational demand even with minor deviations from simple quantum states.

The research demonstrated that any quantum state deviating from Gaussian characteristics necessitates a rise in computational resources which grows at least exponentially as the system increases in size. This matters because it explains limitations of simulating complex quantum systems on conventional computers using decomposition methods.

Specifically, researchers proved this scaling behaviour by establishing robust lower bounds on ‘Gaussian rank’ for both bosonic and fermionic systems involving up to four modes. The authors detailed their approach through analysis reducing problems to these four modes then transferring results back while controlling error; they also derived explicit bounds for specific examples like the single-photon state.

👉 More information
🗞 Robust exponential lower bounds for fermionic and bosonic Gaussian ranks
✍️ Fuchuan Wei, Kong-Wing Wu, Zhengwei Liu and Zi-Wen Liu (Tsinghua University)
🧠 ArXiv: https://arxiv.org/abs/2610.02172

More like this