Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.02172

Robust exponential lower bounds for fermionic and bosonic Gaussian ranks

Fuchuan Wei, Kong-Wing Wu, Zhengwei Liu, Zi-Wen Liu

quant-phSubmitted Oct 1, 2026• Announced Oct 2, 2026• 3 citations
arXivHTMLPDF

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.

Little sign of AI-generated text

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Related papers

Exponential lower bounds on the fermionic Gaussian rank of magic states and the bosonic coherent state rank of Fock states

Oliver Reardon-Smith

Recent algorithms for classical simulation of quantum mechanics have runtime whose superpolynomial component is given by a linear dependence on the number of terms required to write large tensor products of certain "magic" states as superpositions of "free" states (which may be stabilizer states, fermionic Gaussian states or others). Surprisingly little is known about the number of terms in such decompositions, called ranks (e.g. the stabilizer rank, fermionic-Gaussian rank etc.). For complexity theoretic reasons they are expected to grow exponentially in the number of tensor factors but, while exponential upper bounds are known for both the stabilizer and fermionic-Gaussian rank of magic states; the best known lower bounds on the stabiliser rank are quadratic, and no bounds on the fermionic-Gaussian rank are known beyond fixed constants. In this work we prove that any fermionic Gaussian decomposition of $\lvert M\rangle^{\otimes k}$ consists of $Ω(1.4^k)$ terms. Here $\lvert M\rangle$ is the most standard magic state for fermionic linear optics: the $4$ qubit state that may be consumed to implement a swap gate. We also prove essentially matching bounds on the $δ$-approximate rank of the same state, lower bounding it by the same quantity that bounds the exact rank, multiplied by a factor of $1-δ^2$. Our results on exact fermionic Gaussian rank apply directly to any product of $k$ fixed parity non-Gaussian states, although the same is not true of the approximate rank. Finally, we prove that the coherent state border rank of an $n$-mode bosonic Fock state with $m_j$ bosons in mode $j$ is exactly $\prod_{j}(1+m_j)$, answering a conjecture of Ref. [1] and obtain lower bounds on the approximate coherent state rank given by the same quantity multiplied by a function of the fidelity of the approximation, emphasizing the broad applicability of the method we employ.

quant-pharXiv:2610.03699•Oct 5, 2026•0 citations

Lower Bounds on Coherent State Rank

Florian Cottier, Ulysse Chabaud

The approximate coherent state rank is the minimal number of (classical) coherent states required to approximate a continuous-variable bosonic quantum state and directly relates to the classical complexity of simulating bosonic computations. Despite its importance, little is known about lower bounds on this quantity, even for basic families of states. In this work, we initiate a systematic study of lower bounds on the approximate coherent state rank. Our contributions are as follows. (i) We introduce a technique based on low-rank approximation theory yielding generic lower bounds on the approximate coherent state rank of arbitrary single-mode states. (ii) Using this technique, we find a complete characterization of all single-mode states of finite approximate coherent state rank, and we obtain in particular analytical expressions for the approximate coherent state rank of squeezed states and of finite superpositions of Fock states. (iii) We further show that our single-mode lower bounds can be lifted to multimode lower bounds for finite superpositions of multimode Fock states. (iv) Finally, we prove a super-polynomial lower bound on the approximate coherent state rank of the $n$-mode Fock state $|1\rangle^{\otimes n}$, by exploiting a connection to the permanent. To do so, we show that the algebraic complexity of approximate multi-linear formulas for the permanent is super-polynomial, building upon the proof of a lower bound for exact formulas due to [Raz, JACM 2009]. Our results establish an unconditional barrier to efficient classical simulation of Boson Sampling via coherent state decompositions and connect non-classicality of bosonic quantum systems to central questions in algebraic complexity.

quant-pharXiv:2604.00766•Apr 2, 2026•3 citations

Optimal and improved gate decompositions for accelerated classical simulation of near-Gaussian fermionic circuits

Beatriz Dias, Jan Lukas Bosse, James R. Seddon

Fermionic Gaussian circuits can be simulated efficiently on a classical computer, but become universal when supplemented with non-Gaussian operations. Similar to stabilizer circuits augmented with non-stabilizer resources, these non-Gaussian circuits can be simulated classically using rank- or extent-based methods. These methods decompose non-Gaussian states or operations into Gaussian ones, with runtimes that scale polynomially with measures of non-Gaussianity such as the rank and the extent -- quantities that typically grow exponentially with the number of non-Gaussian resources. Current fermionic rank- and extent-based simulators have mostly been limited to Gaussian circuits with magic-state injection. Extending them to mixed states and non-unitary channels has been hindered by the lack of known extent-optimized decompositions for physically relevant gates and noisy channels. In this work, we address this gap. First, we derive analytic decompositions for key non-Gaussian gates and channels, including decompositions for arbitrary two-qubit fermionic gates which are provably optimal for diagonal gates or those acting on Jordan-Wigner-adjacent qubit pairs. Second, we show that stochastic Pauli noise can reduce the effective extent of non-Gaussian rotation gates, but that fermionic magic is substantially more robust to such noise than stabilizer magic. Finally, we demonstrate how these decompositions can accelerate classical sampling from the output distribution of a quantum circuit. This involves a generalization of existing sparsification methods, previously limited to convex-unitary channels, to circuits involving intermediate measurements and feed-forward. Our decompositions also yield speedups for emulating noisy Pauli rotations with quasiprobability simulators in the large-angle/arbitrary-strength-noise and small-angle/low-noise parameter regimes.

quant-pharXiv:2603.18869•Mar 20, 2026•7 citations

Fermionic quantum error correction is never free

Yifan Tang, Ingo Roth, Philippe Faist +3 more

Fermionic platforms offer compelling architectures for quantum computing, ranging from topologically protected Majorana-based qubits to fermionic cold atoms. To achieve scalability, however, they require quantum error correction. In this work, we prove that any exact and sufficiently accurate approximate fermionic quantum error correction necessarily requires non-Gaussian operations, beyond the free-fermion regime of quadratic dynamics. This is in sharp contrast to the qubit setting, where the efficiently classically simulable stabilizer operations form the standard framework for quantum error correction. Specifically, we show that the logical space of any non-trivial fermionic error-correcting code contains no pure fermionic Gaussian state, utilizing a fundamental incompatibility between fermionic error correction and Wick's theorem. We further show that the required number of bounded-weight non-Gaussian gates for unitary codeword preparation grows at least linearly with both the code distance and the number of encoded modes, revealing an intrinsic resource overhead that increases simultaneously with error-protection strength and logical capacity. Furthermore, we analyze the performance of fermionic Gaussian operations in entanglement distillation, revealing a distinction from their bosonic counterparts. Our results reveal fundamental difficulties for fermionic error correction from the perspectives of both physical implementation and classical simulation, suggesting connections to fermionic phases of matter and state preparation complexity.

quant-pharXiv:2609.15059•Sep 15, 2026•0 citations

Balanced von Neumann entropy inequalities for bosonic and fermionic Gaussian states

Weiqi Jiang, Pengcheng Hou, Kun Chen

When arbitrary finite local dimensions are allowed, bosonic Gaussian states and nondegenerate classical Gaussian block vectors satisfy exactly the same unconditional balanced linear entropy inequalities. We establish this equivalence for von Neumann entropy, extending the known Rényi-2 correspondence. Spectral entropy integrals and compatible realification transfer classical determinant inequalities to bosonic states and, in the forward direction, to even fermionic Gaussian states under complete-mode canonical anticommutation relation (CAR) restrictions. A high-temperature limit gives the bosonic converse. Both transfers include pure modes and imply the Zhang-Yeung non-Shannon inequality. We also derive quantitative independence bounds from conditional mutual information ε = I(A:C | B). For bosons, bounded covariance or total photon number gives a trace-distance bound C√ε for ρAC relative to ρA ⊗ ρC, with spectral and matrix Gram refinements of the prefactor. For fermions, an explicit square-root bound requires no energy or spectral gap assumption, and a complementary bound of order √[ε log(1/ε)] is uniform in the number of conditioning modes with A, C fixed. Known Gaussian continuity theorems convert the new covariance estimates to state distance. The fixed-mode square-root exponents are optimal. Combining fermionic rigidity with the established entropy-deficit identity yields an operational lower bound on non-Gaussianity from CMI and a probability difference for an even measurement event on AC. Version 1.0. Complete manuscript with Appendices A–G.

•Oct 28, 2026•0 citations

Computable fermionic non-Gaussianity from the covariance matrix

Poetri Sonya Tarabunga, Bernhard Jobst, Raúl Morral-Yepes +4 more

Fermionic non-Gaussianity, or fermionic magic, is a key resource underlying the computational complexity of fermionic quantum systems, yet tractable and operationally meaningful ways to quantify it remain limited. We address this challenge by developing a convex resource theory of fermionic non-Gaussianity and introducing two families of computable quantities for pure fermionic states, both derived from the Williamson normal form of the covariance matrix. The first family, occupation number entropies, is defined as the Tsallis-$α$ entropy of the occupation numbers. We prove that one member of this family is monotonic under Gaussian protocols, establishing it as a computable convex resource monotone. It consequently lower bounds the number of non-Gaussian gates needed for state preparation. The second family, natural-orbital participation entropies, is given by the Rényi-$α$ entropy of the squared amplitudes of the state in the natural-orbital basis, defined by the eigenvectors of the covariance matrix. They quantify state compressibility in this basis and thus upper bound the classical simulation cost in an orthonormal Gaussian basis. We analyze both families for stabilizer and translation-invariant states, where they simplify and reveal additional structure. We further study representative examples, including random SWAP-doped matchgate circuits and the bond-modulated XXZ model, highlighting the role of non-Gaussianity in many-body phenomena. Our work establishes a resource-theoretic framework for computable fermionic non-Gaussianity that unifies notions arising across quantum information, condensed-matter physics, and quantum chemistry, opening new directions for studying the complexity of quantum many-body systems and providing practical tools to assess the classical simulability of fermionic states relevant for quantum advantage.

quant-pharXiv:2607.02242•Jul 3, 2026•21 citations
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.
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ψ>0c_\psi>0cψ​>0 satisfies χˉG(δ)(∣ψ⟩⊗k)≥ecψk\bar\chi_G^{(\delta)}(|\psi\rangle^{\otimes k})\ge e^{c_\psi k}χˉ​G(δ)​(∣ψ⟩⊗k)≥ecψ​k for sufficiently large kkk, at every fixed norm error 0≤δ<10\le\delta<10≤δ<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⟩=(∣0000⟩+∣1111⟩)/2|M\rangle=(|0000\rangle+|1111\rangle)/\sqrt2∣M⟩=(∣0000⟩+∣1111⟩)/2​, the bound is c(1−δ2)(343/243)kc(1-\delta^2)(343/243)^kc(1−δ2)(343/243)k. Single-photon tensor powers have eventual lower bound (11/10)k(11/10)^k(11/10)k at fixed error and border rank greater than (5/4)k(5/4)^k(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.
Recent algorithms for classical simulation of quantum mechanics have runtime whose superpolynomial component is given by a linear dependence on the number of terms required to write large tensor products of certain "magic" states as superpositions of "free" states (which may be stabilizer states, fermionic Gaussian states or others). Surprisingly little is known about the number of terms in such decompositions, called ranks (e.g. the stabilizer rank, fermionic-Gaussian rank etc.). For complexity theoretic reasons they are expected to grow exponentially in the number of tensor factors but, while exponential upper bounds are known for both the stabilizer and fermionic-Gaussian rank of magic states; the best known lower bounds on the stabiliser rank are quadratic, and no bounds on the fermionic-Gaussian rank are known beyond fixed constants. In this work we prove that any fermionic Gaussian decomposition of ∣M⟩⊗k\lvert M\rangle^{\otimes k}∣M⟩⊗k consists of Ω(1.4k)Ω(1.4^k)Ω(1.4k) terms. Here ∣M⟩\lvert M\rangle∣M⟩ is the most standard magic state for fermionic linear optics: the 444 qubit state that may be consumed to implement a swap gate. We also prove essentially matching bounds on the δδδ-approximate rank of the same state, lower bounding it by the same quantity that bounds the exact rank, multiplied by a factor of 1−δ21-δ^21−δ2. Our results on exact fermionic Gaussian rank apply directly to any product of kkk fixed parity non-Gaussian states, although the same is not true of the approximate rank. Finally, we prove that the coherent state border rank of an nnn-mode bosonic Fock state with mjm_jmj​ bosons in mode jjj is exactly ∏j(1+mj)\prod_{j}(1+m_j)∏j​(1+mj​), answering a conjecture of Ref. [1] and obtain lower bounds on the approximate coherent state rank given by the same quantity multiplied by a function of the fidelity of the approximation, emphasizing the broad applicability of the method we employ.
The approximate coherent state rank is the minimal number of (classical) coherent states required to approximate a continuous-variable bosonic quantum state and directly relates to the classical complexity of simulating bosonic computations. Despite its importance, little is known about lower bounds on this quantity, even for basic families of states. In this work, we initiate a systematic study of lower bounds on the approximate coherent state rank. Our contributions are as follows. (i) We introduce a technique based on low-rank approximation theory yielding generic lower bounds on the approximate coherent state rank of arbitrary single-mode states. (ii) Using this technique, we find a complete characterization of all single-mode states of finite approximate coherent state rank, and we obtain in particular analytical expressions for the approximate coherent state rank of squeezed states and of finite superpositions of Fock states. (iii) We further show that our single-mode lower bounds can be lifted to multimode lower bounds for finite superpositions of multimode Fock states. (iv) Finally, we prove a super-polynomial lower bound on the approximate coherent state rank of the nnn-mode Fock state ∣1⟩⊗n|1\rangle^{\otimes n}∣1⟩⊗n, by exploiting a connection to the permanent. To do so, we show that the algebraic complexity of approximate multi-linear formulas for the permanent is super-polynomial, building upon the proof of a lower bound for exact formulas due to [Raz, JACM 2009]. Our results establish an unconditional barrier to efficient classical simulation of Boson Sampling via coherent state decompositions and connect non-classicality of bosonic quantum systems to central questions in algebraic complexity.
Fermionic Gaussian circuits can be simulated efficiently on a classical computer, but become universal when supplemented with non-Gaussian operations. Similar to stabilizer circuits augmented with non-stabilizer resources, these non-Gaussian circuits can be simulated classically using rank- or extent-based methods. These methods decompose non-Gaussian states or operations into Gaussian ones, with runtimes that scale polynomially with measures of non-Gaussianity such as the rank and the extent -- quantities that typically grow exponentially with the number of non-Gaussian resources. Current fermionic rank- and extent-based simulators have mostly been limited to Gaussian circuits with magic-state injection. Extending them to mixed states and non-unitary channels has been hindered by the lack of known extent-optimized decompositions for physically relevant gates and noisy channels. In this work, we address this gap. First, we derive analytic decompositions for key non-Gaussian gates and channels, including decompositions for arbitrary two-qubit fermionic gates which are provably optimal for diagonal gates or those acting on Jordan-Wigner-adjacent qubit pairs. Second, we show that stochastic Pauli noise can reduce the effective extent of non-Gaussian rotation gates, but that fermionic magic is substantially more robust to such noise than stabilizer magic. Finally, we demonstrate how these decompositions can accelerate classical sampling from the output distribution of a quantum circuit. This involves a generalization of existing sparsification methods, previously limited to convex-unitary channels, to circuits involving intermediate measurements and feed-forward. Our decompositions also yield speedups for emulating noisy Pauli rotations with quasiprobability simulators in the large-angle/arbitrary-strength-noise and small-angle/low-noise parameter regimes.
Fermionic platforms offer compelling architectures for quantum computing, ranging from topologically protected Majorana-based qubits to fermionic cold atoms. To achieve scalability, however, they require quantum error correction. In this work, we prove that any exact and sufficiently accurate approximate fermionic quantum error correction necessarily requires non-Gaussian operations, beyond the free-fermion regime of quadratic dynamics. This is in sharp contrast to the qubit setting, where the efficiently classically simulable stabilizer operations form the standard framework for quantum error correction. Specifically, we show that the logical space of any non-trivial fermionic error-correcting code contains no pure fermionic Gaussian state, utilizing a fundamental incompatibility between fermionic error correction and Wick's theorem. We further show that the required number of bounded-weight non-Gaussian gates for unitary codeword preparation grows at least linearly with both the code distance and the number of encoded modes, revealing an intrinsic resource overhead that increases simultaneously with error-protection strength and logical capacity. Furthermore, we analyze the performance of fermionic Gaussian operations in entanglement distillation, revealing a distinction from their bosonic counterparts. Our results reveal fundamental difficulties for fermionic error correction from the perspectives of both physical implementation and classical simulation, suggesting connections to fermionic phases of matter and state preparation complexity.
When arbitrary finite local dimensions are allowed, bosonic Gaussian states and nondegenerate classical Gaussian block vectors satisfy exactly the same unconditional balanced linear entropy inequalities. We establish this equivalence for von Neumann entropy, extending the known Rényi-2 correspondence. Spectral entropy integrals and compatible realification transfer classical determinant inequalities to bosonic states and, in the forward direction, to even fermionic Gaussian states under complete-mode canonical anticommutation relation (CAR) restrictions. A high-temperature limit gives the bosonic converse. Both transfers include pure modes and imply the Zhang-Yeung non-Shannon inequality. We also derive quantitative independence bounds from conditional mutual information ε = I(A:C | B). For bosons, bounded covariance or total photon number gives a trace-distance bound C√ε for ρAC relative to ρA ⊗ ρC, with spectral and matrix Gram refinements of the prefactor. For fermions, an explicit square-root bound requires no energy or spectral gap assumption, and a complementary bound of order √[ε log(1/ε)] is uniform in the number of conditioning modes with A, C fixed. Known Gaussian continuity theorems convert the new covariance estimates to state distance. The fixed-mode square-root exponents are optimal. Combining fermionic rigidity with the established entropy-deficit identity yields an operational lower bound on non-Gaussianity from CMI and a probability difference for an even measurement event on AC. Version 1.0. Complete manuscript with Appendices A–G.
Fermionic non-Gaussianity, or fermionic magic, is a key resource underlying the computational complexity of fermionic quantum systems, yet tractable and operationally meaningful ways to quantify it remain limited. We address this challenge by developing a convex resource theory of fermionic non-Gaussianity and introducing two families of computable quantities for pure fermionic states, both derived from the Williamson normal form of the covariance matrix. The first family, occupation number entropies, is defined as the Tsallis-ααα entropy of the occupation numbers. We prove that one member of this family is monotonic under Gaussian protocols, establishing it as a computable convex resource monotone. It consequently lower bounds the number of non-Gaussian gates needed for state preparation. The second family, natural-orbital participation entropies, is given by the Rényi-ααα entropy of the squared amplitudes of the state in the natural-orbital basis, defined by the eigenvectors of the covariance matrix. They quantify state compressibility in this basis and thus upper bound the classical simulation cost in an orthonormal Gaussian basis. We analyze both families for stabilizer and translation-invariant states, where they simplify and reveal additional structure. We further study representative examples, including random SWAP-doped matchgate circuits and the bond-modulated XXZ model, highlighting the role of non-Gaussianity in many-body phenomena. Our work establishes a resource-theoretic framework for computable fermionic non-Gaussianity that unifies notions arising across quantum information, condensed-matter physics, and quantum chemistry, opening new directions for studying the complexity of quantum many-body systems and providing practical tools to assess the classical simulability of fermionic states relevant for quantum advantage.