pith. sign in

arxiv: 2410.04274 · v3 · pith:VAK2ZWD6new · submitted 2024-10-05 · 🪐 quant-ph · cs.CC

Bosonic Quantum Computational Complexity

Ulysse Chabaud , Michael Joseph , Saeed Mehraban , Arsalan Motamedi This is my paper

Pith reviewed 2026-05-23 20:14 UTC · model grok-4.3

classification 🪐 quant-ph cs.CC
keywords bosonic quantum computingquantum complexity classesstellar rankGaussian dynamicsminimum energy problemcontinuous-variable systemsBQLQMA
0
0 comments X

The pith

Bosonic minimum energy problem is NP-complete at constant stellar rank but undecidable when unbounded.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper defines complexity classes for quantum computations on bosonic systems with continuous degrees of freedom. It proves that quadratic Gaussian dynamics match the class BQL. The minimum energy problem for bosonic Hamiltonians changes with the stellar rank of the states: NP-complete for constant rank, in QMA for polynomially bounded rank, and undecidable for unbounded rank. Spectrum boundedness is co-NP-hard, and polynomial observable expectations lie in PSPACE. These distinctions arise because bosonic systems act on infinite-dimensional spaces unlike discrete qubit models.

Core claim

The power of quadratic quantum dynamics is equivalent to BQL. The minimum energy problem for bosonic Hamiltonians is NP-complete for constant stellar rank, in QMA for polynomially-bounded rank, and undecidable for unbounded rank. Deciding boundedness of the spectrum is co-NP-hard. Computing expectation values of polynomial bosonic observables is in PSPACE. Higher-degree gate classes have a BQP lower bound and EXPSPACE upper bound.

What carries the argument

Stellar rank of energy-constrained bosonic states, a measure of non-Gaussianity that sets the complexity of the minimum energy problem.

If this is right

  • Gaussian dynamics are exactly as powerful as BQL.
  • Expectation values of polynomial bosonic observables can be computed in PSPACE.
  • Continuous-variable polynomial-time classes sit between BQP and EXPSPACE.
  • Spectrum boundedness for bosonic Hamiltonians is co-NP-hard.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Limited non-Gaussian resources might suffice to reach NP-hard bosonic problems but not higher.
  • Optical experiments with bounded non-Gaussianity could test whether NP-complete instances appear at low stellar rank.
  • The gap between polynomial and unbounded rank suggests a sharp threshold where decidability fails.

Load-bearing premise

The chosen definitions of bosonic complexity classes, stellar rank, and energy-constrained states correctly capture essential computational features of continuous-variable systems without artifacts from infinite dimensions.

What would settle it

A polynomial-time algorithm deciding the minimum energy for constant stellar rank bosonic Hamiltonians to within inverse-polynomial precision would falsify the NP-completeness claim.

Figures

Figures reproduced from arXiv: 2410.04274 by Arsalan Motamedi, Michael Joseph, Saeed Mehraban, Ulysse Chabaud.

Figure 1
Figure 1. Figure 1: Known relations between complexity classes used in this work. If a line connects complexity class [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Relations between complexity classes and computational problems proven in this paper and described below, up to logspace reductions on the [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Energy bound conditions for quantum computations. The red curve depicts a system that is promised to have low energy at the beginning and [PITH_FULL_IMAGE:figures/full_fig_p013_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: A schematic of an instance of evolution for the problem of Gaussian evolution described in [PITH_FULL_IMAGE:figures/full_fig_p028_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: An example of the circuit for computing sample mean of many Gaussian circuits. Here we have shown an example where there are 4 Gaussian [PITH_FULL_IMAGE:figures/full_fig_p029_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Numerical illustrations supporting Conjecture 2. of non-diagonal entries i.e., λmin(X 2 ) ≥ min n∈{0,1,··· ,r}  n + 1 2 − 1 2 q n(n − 1) + q (n + 1)(n + 2)  . (258) Note that for any given n, we have n + 1 2 − 1 2 q n(n − 1) + q (n + 1)(n + 2)  = n + 1 2 − n 2 r 1 − 1 n + r (1 + 1 n )(1 + 2 n ) ! , (259) we now notice that √ 1 − x ≤ 1 − x 2 − x 2 8 for x ≥ 0. Moreover, we have p (1 + x)(1 + 2x) ≤ 1 +… view at source ↗
read the original abstract

Quantum computing involving physical systems with continuous degrees of freedom, such as the quantum states of light, has recently attracted significant interest. However, a well-defined quantum complexity theory for these bosonic computations over infinite-dimensional Hilbert spaces is missing. In this work, we lay foundations for such a research program. We introduce natural complexity classes and problems based on bosonic generalizations of BQP, the local Hamiltonian problem, and QMA. We uncover several relationships and subtle differences between standard Boolean classical and discrete variable quantum complexity classes and identify outstanding open problems. In particular: 1. We show that the power of quadratic (Gaussian) quantum dynamics is equivalent to the class BQL. More generally, we define classes of continuous-variable quantum polynomial time computations with a bounded probability of error based on higher-degree gates. Due to the infinite dimensional Hilbert space, it is not a priori clear whether a decidable upper bound can be obtained for these classes. We identify complete problems for these classes and demonstrate a BQP lower and EXPSPACE upper bound. We further show that the problem of computing expectation values of polynomial bosonic observables is in PSPACE. 2. We prove that the problem of deciding the boundedness of the spectrum of a bosonic Hamiltonian is co-NP-hard. Furthermore, we show that the problem of finding the minimum energy of a bosonic Hamiltonian critically depends on the non-Gaussian stellar rank of the family of energy-constrained states one optimizes over: for constant stellar rank, it is NP-complete; for polynomially-bounded rank, it is in QMA; for unbounded rank, it is undecidable.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 3 minor

Summary. The manuscript introduces bosonic generalizations of standard quantum complexity classes (BQP, QMA, local Hamiltonian problem) for continuous-variable systems over infinite-dimensional Hilbert spaces. It establishes that quadratic/Gaussian dynamics are equivalent to BQL, defines higher-degree classes with a BQP lower bound and EXPSPACE upper bound, shows that computing expectation values of polynomial bosonic observables is in PSPACE, proves that deciding spectrum boundedness of a bosonic Hamiltonian is co-NP-hard, and shows that the minimum-energy problem has complexity depending on stellar rank: NP-complete for constant rank, in QMA for polynomially bounded rank, and undecidable for unbounded rank.

Significance. If the central claims hold, the work provides a foundational framework relating bosonic/continuous-variable computations to discrete-variable classes while addressing infinite-dimensional challenges. The rank-dependent hardness results for the minimum-energy problem and the identification of complete problems are notable contributions that clarify the role of non-Gaussian resources. The Gaussian-to-BQL equivalence and PSPACE result for observables are clean relationships that could inform CV quantum computing research.

major comments (2)
  1. [Section defining the bosonic complexity classes and Gaussian dynamics equivalence] The equivalence of quadratic dynamics to BQL (point 1) and the BQP/EXPSPACE bounds for higher-degree classes rest on the precise definitions of the bosonic classes and energy-constrained states; without explicit verification that these definitions avoid artifacts from the infinite-dimensional space (e.g., in the handling of unbounded operators or probability bounds), the load-bearing relationships cannot be fully assessed from the provided claims.
  2. [Section on the minimum-energy problem and stellar rank] The stellar-rank dependence of the minimum-energy problem (point 2) is central, yet the transition from NP-completeness at constant rank to undecidability at unbounded rank requires explicit confirmation that the reductions and state families remain well-defined across all cases without additional constraints on the Hamiltonian family.
minor comments (3)
  1. [Introduction] The abstract and introduction would benefit from a short table or diagram summarizing the new classes and their relationships to BQL/BQP/QMA to improve readability.
  2. [Preliminaries on stellar rank] Notation for the stellar rank and energy-constrained optimization should be introduced with a brief motivation or reference to prior CV literature to aid readers unfamiliar with the measure.
  3. [Section on higher-degree gate classes] A few sentences clarifying how the EXPSPACE upper bound is obtained (e.g., via simulation or reduction) would strengthen the presentation of the higher-degree classes.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript, positive assessment of its significance, and recommendation for minor revision. We address each major comment below with clarifications on the definitions, proofs, and handling of infinite-dimensional aspects.

read point-by-point responses

  1. Referee: [Section defining the bosonic complexity classes and Gaussian dynamics equivalence] The equivalence of quadratic dynamics to BQL (point 1) and the BQP/EXPSPACE bounds for higher-degree classes rest on the precise definitions of the bosonic classes and energy-constrained states; without explicit verification that these definitions avoid artifacts from the infinite-dimensional space (e.g., in the handling of unbounded operators or probability bounds), the load-bearing relationships cannot be fully assessed from the provided claims.

    Authors: The bosonic complexity classes are defined in Section 3 using energy-constrained states to ensure all relevant operators (including unbounded ones) are densely defined and self-adjoint on the appropriate domains. The Gaussian-to-BQL equivalence is established in Theorem 4.1 by explicit computation of error probabilities under these constraints, which bound the support away from pathological infinite-energy behaviors. The BQP lower bound and EXPSPACE upper bound for higher-degree classes follow from reductions in Sections 4 and 5 that employ finite-energy truncations preserving the original dynamics; the PSPACE result for observables is obtained via similar controlled approximations. These steps already incorporate the necessary verifications to avoid artifacts. To make this fully explicit for readers, we will add a short clarifying subsection and an appendix with the operator-domain and probability-bound checks in the revised version. revision: yes

  2. Referee: [Section on the minimum-energy problem and stellar rank] The stellar-rank dependence of the minimum-energy problem (point 2) is central, yet the transition from NP-completeness at constant rank to undecidability at unbounded rank requires explicit confirmation that the reductions and state families remain well-defined across all cases without additional constraints on the Hamiltonian family.

    Authors: Section 6 constructs the reductions with explicit state families that are energy-constrained by design. For constant stellar rank, the NP-completeness reduction (Theorem 6.2) employs rank-1 states and a Hamiltonian family whose matrix elements are polynomials in the bosonic operators, ensuring the operators are well-defined without extra constraints. The QMA membership for polynomially bounded rank follows directly from the witness being a state of controlled rank. Undecidability for unbounded rank (Theorem 6.5) is obtained by embedding the halting problem into an unbounded-rank family whose Hamiltonians remain valid bosonic operators on the Fock space. All reductions are stated with the precise Hamiltonian families and state constraints used, so the well-definedness holds across the cases. We will insert a brief remark summarizing these construction details if the current presentation leaves any ambiguity. revision: partial

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper introduces new bosonic complexity classes and problems by generalizing standard definitions (BQP, local Hamiltonian, QMA) to continuous-variable systems, then proves relationships such as Gaussian dynamics equivalence to BQL and rank-dependent complexity of the minimum-energy problem. These steps rely on explicit definitions of stellar rank, energy-constrained states, and polynomial-time computations with bounded error, without reducing any central claim to a fitted parameter, self-referential construction, or load-bearing self-citation. The derivations establish upper/lower bounds and completeness results relative to known classes using standard proof techniques, remaining self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The paper rests on standard axioms of quantum mechanics and complexity theory plus newly introduced definitions for bosonic classes and stellar rank; no free parameters are fitted and no new physical entities are postulated.

axioms (1)
  • standard math Standard axioms of quantum mechanics and computational complexity theory (Hilbert spaces, unitary evolution, polynomial-time reductions)
    Invoked throughout to define the bosonic generalizations of BQP, QMA and the local Hamiltonian problem.
invented entities (1)
  • Stellar rank no independent evidence
    purpose: Parameterizes the non-Gaussianity of energy-constrained states to classify the complexity of bosonic minimum-energy problems
    Introduced in the abstract to obtain the NP-complete / QMA / undecidable trichotomy; no independent evidence supplied.

pith-pipeline@v0.9.0 · 5828 in / 1309 out tokens · 25907 ms · 2026-05-23T20:14:43.783869+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Quantum state isomorphism problems for groups

    quant-ph 2026-05 unverdicted novelty 8.0

    Quantum state isomorphism under group actions is BQP-hard for pure states across nontrivial groups and QSZK-complete for mixed states with finite groups; Pauli group version is BQP-complete and Clifford is GI-hard, ru...

  2. Simulating Thermal Properties of Bose-Hubbard Models on a Quantum Computer

    quant-ph 2026-04 unverdicted novelty 8.0

    A new rigorous Gibbs sampling method is given for bosonic models by proving that their dissipative generators have positive spectral gaps, enabling efficient quantum preparation of thermal states for Bose-Hubbard Hami...

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages · cited by 2 Pith papers · 2 internal anchors

  1. [1]

    Quantum linear systems algorithms: a primer

    Cited on page 59. [CFGM21] Ulysse Chabaud, Giulia Ferrini, Frédéric Grosshans, and Damian Markham. Classical simu- lation of Gaussian quantum circuits with non-Gaussian input states. Physical Review Research, 3(3):033018, 2021. Cited on page 30. 68 [CGW14] Andrew M Childs, David Gosset, and Zak Webb. The Bose-Hubbard model is QMA-complete. In Automata, La...

    work page internal anchor Pith review Pith/arXiv arXiv 2021

  2. [2]

    [Has22] Matthew B Hastings

    Cited on page 22. [Has22] Matthew B Hastings. Perturbation theory and the sum of squares. arXiv preprint arXiv:2205.12325, 2022. Cited on page 14. [Hil02] David Hilbert. Mathematical problems (transl. mw newson). Bull. Amer. Math. Soc, 8:437–479,

    work page arXiv 2022

  3. [3]

    [HJ85] Roger A

    Cited on page 15. [HJ85] Roger A. Horn and Charles R. Johnson. Hermitian and symmetric matrices, page 167–256. Cam- bridge University Press, 1985. Cited on pages 74 and 80. [HMQ24] Martin Houde, Will McCutcheon, and Nicolás Quesada. Matrix decompositions in quan- tum optics: Takagi/autonne, bloch-messiah/euler, iwasawa, and williamson. arXiv preprint arXi...

    work page arXiv 1985

  4. [4]

    [Kie03] Tien D Kieu

    Cited on page 43. [Kie03] Tien D Kieu. Quantum algorithm for Hilbert’s tenth problem.International Journal of Theoretical Physics, 42:1461–1478, 2003. Cited on pages 6, 11, and 67. [Kit97] A Yu Kitaev. Quantum computations: algorithms and error correction. Russian Mathematical Surveys, 52(6):1191, 1997. Cited on pages 4 and 14. [KKR04] Julia Kempe, Alexei...

    work page arXiv 2003

  5. [5]

    Quantum Computational Complexity

    Cited on page 43. [VMDS16] Henning Vahlbruch, Moritz Mehmet, Karsten Danzmann, and Roman Schnabel. Detection of 15 dB squeezed states of light and their application for the absolute calibration of photoelectric quantum efficiency. Physical review letters, 117(11):110801, 2016. Cited on page 30. [Vou06] A Vourdas. Analytic representations in quantum mechan...

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  6. [6]

    ⟨F⋆ ψ, aF ⋆ ψ⟩ = b−ab 1−|a|2 ,

    work page

  7. [7]

    ⟨F⋆ ψ, a2F⋆ ψ⟩ = −a 1−|a|2 + (b−ab)2 (1−|a|2)2 ,

    work page

  8. [8]

    Lemma A.2

    ⟨F⋆ ψ, aa†F⋆ ψ⟩ = 1 1−|a|2 + |b−ab|2 (1−|a|2)2 . Lemma A.2. Let F⋆ ψ(z) = N −1 exp − 1 2 zTAz + bTz . We have ⟨F⋆ ψ, e∑i tiaie∑i sia† i F⋆ ψ⟩ = exp  − 1 2 sT tT Σ  s t   + cTt + cts   (220) where Σ =  U† 0 0 UT     D 1−D2 − 1 1−D2 − 1 1−D2 D 1−D2    U 0 0 U   , c = UT 1 1 − D2 (Ub − DUb), (221) and A = UTDU is the Takagi factorization ...

    work page

  9. [9]

    (⟨F⋆ ψ, aiF⋆ ψ⟩)i = c,

    work page

  10. [10]

    (⟨F⋆ ψ, aiajF⋆ ψ⟩)ij = UT −D 1−D2 U + ccT,

    work page

  11. [11]

    (⟨F⋆ ψ, aja† i F⋆ ψ⟩)ij = UT 1 1−D2 U + cTc,

    work page

  12. [12]

    For degree-4 terms that conserve the number of particles we have ⟨F⋆ ψ, ajaia† j a† i F⋆ ψ⟩ =(U† 1 1 − D2 U)jj (U† 1 1 − D2 U)ii + U† 1 1 − D2 U ij 2 + U† D 1 − D2 U ij 2 − 2 Re cicj U† D 1 − D2 U ij ! + 2 Re cicj UT 1 1 − D2 U ji ! + |ci|2 U† 1 1 − D2 U jj + |cj|2 U† 1 1 − D2 U ii + |ci|2 · |cj|2 (229) where c = UT 1 1−D2 (Ub − DUb). B Commutation relati...

    work page

  13. [13]

    (260) Combining the above inequality with Eq

    As a result, we get that for all x ≥ 0 √ 1 − x + q (1 + x)(1 + 2x) ≤ 2 + x − x2 8 . (260) Combining the above inequality with Eq. (258), we get λmin(X2) ≥ min n∈{0,··· ,r} n + 1 2 − n 2 2 + 1 n − 1 8n2 = min n∈{0,··· ,r} 1 16n = 1 16r . (261) ♣ Using numerical tools, we noticed that this behavior can be extended as follows. However, we do not currently ha...

    work page