Lower Bounds on Coherent State Rank
Florian Cottier, Ulysse Chabaud
Abstract
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 -mode Fock state , 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.
AI Impact Assessments
(3 models)Scientific Impact Assessment: "Lower Bounds on Coherent State Rank"
1. Core Contribution
This paper initiates a systematic study of lower bounds on the approximate coherent state rank — the minimal number of coherent states required to approximate a bosonic quantum state to arbitrary precision. The approximate coherent state rank is the continuous-variable (CV) analog of the stabilizer rank in qubit systems and directly governs the classical simulation complexity of bosonic quantum computations.
The paper makes four main contributions: (i) a generic lower-bounding technique for single-mode states based on Hankel matrix low-rank approximation theory; (ii) a complete characterization of all single-mode states with finite approximate coherent state rank; (iii) a lifting procedure from single-mode to multimode lower bounds for core states; and (iv) a super-polynomial lower bound κ(|1⟩⊗n) = n^{Ω(log n)} for the n-mode Fock state, established by proving that the border complexity of multi-linear formulas for the permanent is super-polynomial — extending Raz's celebrated 2009 result to the approximate setting.
2. Methodological Rigor
The technical approach is highly rigorous and creative, combining tools from disparate areas: low-rank matrix approximation (Young–Eckart–Mirsky theorem), linear recurrence theory, Segal–Bargmann representation, and algebraic complexity theory.
Single-mode results: The Hankel matrix technique is elegant. The key insight — that rescaled Fock amplitudes of coherent state superpositions satisfy linear recurrence relations, constraining the rank of associated Hankel matrices — is clean and powerful. The characterization theorem (Theorem 2) is particularly strong: it gives a complete if-and-only-if condition, showing that finite approximate coherent state rank is equivalent to the rescaled amplitudes following a finite linear recurrence, which in turn corresponds to the state being a superposition of displaced core states.
Multimode results: The lifting argument via passive linear unitaries and vacuum projection is natural and well-executed. The bunching lemma (Lemma 3) is a neat application of the polynomial representation of bosonic states.
Super-polynomial bound: The proof of Theorem 4 is the technical crown jewel. The chain of reasoning — from coherent state decompositions to multi-linear formulas, from uniform convergence over unitaries to coefficient convergence, and finally to a border complexity lower bound via an extension of Raz's partial derivatives matrix method — is intricate but clearly presented. The key technical innovation is handling the approximation: extracting a subsequence with fixed formula structure (via pigeonhole) and using lower semi-continuity of rank to bridge between exact and approximate settings. This is a non-trivial extension of Raz's framework.
One limitation is that the single-mode bounds from Theorem 7 suffer from a (2N)! factorial factor that makes them quantitatively loose for large Fock numbers, though the optimized version (Theorem 12) partially mitigates this.
3. Potential Impact
Quantum computing complexity: The super-polynomial lower bound on κ(|1⟩⊗n) establishes an unconditional barrier to classical simulation of Boson Sampling via coherent state decompositions. This is significant because, unlike conditional hardness results (which assume non-collapse of the polynomial hierarchy), this is unconditional. It parallels — and in some ways surpasses — the state of affairs for stabilizer rank, where only quadratic lower bounds are known for |H⟩⊗n.
Algebraic complexity: Theorem 5 (border complexity of multi-linear formulas for the permanent) is independently interesting. It extends Raz's result to the approximate/border setting and connects quantum non-classicality to algebraic complexity in a novel way.
Resource theory of non-classicality: The complete characterization of single-mode states with finite approximate coherent state rank, including the result that squeezed states have infinite rank, enriches the resource-theoretic understanding of bosonic non-classicality.
Classical algorithms for permanents: The connection between coherent state decompositions and permanent computation means any improvement in upper bounds would yield faster permanent algorithms, and the lower bounds constrain what's achievable via this route.
4. Timeliness & Relevance
The paper is highly timely. Bosonic quantum computing is experiencing rapid experimental progress (GKP codes, cat qubits, photonic platforms), making rigorous complexity-theoretic foundations increasingly important. The stabilizer rank problem in qubit systems has attracted significant attention but remains stuck at quadratic lower bounds; this work demonstrates that stronger results are achievable in the bosonic setting by leveraging the algebraic structure of the permanent. The paper also responds directly to the framework of Marshall and Anand (2023), which established the simulation relevance of approximate coherent state rank but left open the question of lower bounds.
5. Strengths & Limitations
Strengths:
Limitations:
6. Overall Assessment
This is an excellent paper that makes foundational contributions at the intersection of quantum information, quantum optics, and computational complexity. The combination of a complete characterization theorem, a novel proof technique, and an unconditional super-polynomial lower bound makes it a substantial advance. The connection between coherent state rank and algebraic complexity of the permanent is likely to inspire significant follow-up work.
Generated Apr 2, 2026
Comparison History (42)
Paper 2 has higher potential impact due to its strong complexity-theoretic consequences and broader relevance. It provides unconditional (super-polynomial) lower bounds tied to the permanent, establishing concrete barriers to classical simulation of Boson Sampling—highly timely for quantum advantage debates. It also develops general techniques, characterizes finite-rank states, and connects continuous-variable non-classicality with algebraic complexity, spanning quantum optics, computational complexity, and quantum computing. Paper 1 is novel and rigorous in quantum information theory, but its main impact is likely more specialized within resource theories and asymptotic hypothesis testing.
Paper 2 establishes fundamental, unconditional lower bounds on the classical simulation of bosonic quantum systems, bridging quantum information and algebraic complexity theory. This theoretical breakthrough provides deep insights into the classical hardness of Boson Sampling. While Paper 1 offers a highly practical architectural framework for scaling fluxonium quantum processors, Paper 2's foundational contributions to quantum complexity theory give it a broader and more lasting potential scientific impact.
Paper 2 establishes fundamental theoretical results connecting quantum computing complexity (Boson Sampling hardness) to algebraic complexity theory, proving unconditional super-polynomial lower bounds—a rare achievement in computational complexity. It provides a complete characterization of coherent state rank for single-mode states and creates lasting connections between non-classicality and the permanent's algebraic complexity. While Paper 1 presents a valuable applied framework for MRS pulse design with clinical relevance, Paper 2's foundational contributions to quantum complexity theory, classical simulation barriers, and cross-field connections to algebraic complexity give it broader and deeper long-term scientific impact.
Paper 1 presents a significant experimental breakthrough in quantum communication, achieving over an order-of-magnitude enhancement in secure key rate for long-distance QKD. The use of microcombs to solve the scalability problem of wavelength-division multiplexing in TF-QKD offers immediate, highly relevant real-world applications for building secure inter-city quantum networks. While Paper 2 provides strong theoretical contributions to quantum complexity, Paper 1's experimental success and scalable architecture promise broader and more immediate technological impact.
Paper 2 addresses a central open problem in quantum error correction: achieving fault-tolerant non-Clifford gates on codes with near-optimal parameters. Combining nearly optimal LDPC/LTC code parameters with transversal non-Clifford gates is a major breakthrough with direct implications for scalable fault-tolerant quantum computing. The algebraic-topological framework ('cupcap gates') introduces powerful new methodology. While Paper 1 makes important contributions connecting coherent state rank to simulation complexity and algebraic complexity, Paper 2's results are more transformative for the practical realization of quantum computing and bridge multiple mathematical fields.
Paper 2 establishes fundamental theoretical lower bounds on classical simulability of bosonic quantum systems, bridging quantum non-classicality with algebraic complexity theory. By proving a super-polynomial lower bound and creating unconditional barriers to efficient classical simulation of Boson Sampling, it addresses central questions in theoretical computer science and quantum advantage. Paper 1 offers a valuable but more narrowly focused methodological improvement for specific quantum simulations.
Paper 1 makes fundamental contributions connecting quantum complexity theory, bosonic quantum computing simulation, and algebraic complexity. It establishes unconditional barriers to classical simulation of Boson Sampling via coherent state decompositions—a central problem in quantum computational advantage. The super-polynomial lower bound connecting to the permanent's algebraic complexity bridges quantum information and theoretical computer science, with broad implications. Paper 2 extends nonlinear Thouless pumping to quasiperiodic lattices, which is interesting but more incremental, building on established frameworks with narrower impact scope.
Paper 2 addresses a critical bottleneck in the classical simulation of quantum systems (Boson Sampling) by establishing unconditional super-polynomial lower bounds on coherent state rank. By connecting continuous-variable non-classicality to deep questions in algebraic complexity (specifically the permanent), it offers significant theoretical breakthroughs with broad implications for proving quantum computational advantage, whereas Paper 1 focuses on a more specialized scenario in quantum channel capacity.
While Paper 1 offers strong theoretical contributions to quantum complexity, Paper 2 provides a highly timely and deployable technological solution to a critical global challenge (plastic pollution). The innovative use of undetected photon spectroscopy for rapid, portable material identification bridges advanced optics with immediate real-world environmental applications, giving it a broader and more tangible societal impact.
Paper 2 is likely higher impact: it delivers unconditional super-polynomial lower bounds tied to the permanent, creating rigorous barriers to classical simulation (high rigor, broad relevance to quantum optics, complexity theory, and simulation theory). Its techniques (low-rank approximation framework, characterization of finite rank states, lifting to multimode, algebraic complexity connections) are foundational and broadly reusable. Paper 1 is innovative and timely for quantum PDEs, but its claimed “exponential advantage” hinges on standard QLSA assumptions and discretization/oracle models, and applicability depends on fault-tolerant resources, making near-term impact narrower.