Complexity of Quadratic Bosonic Hamiltonian Simulation: $\mathsf{BQP}$-Completeness and $\mathsf{PostBQP}$-Hardness

Quantum Physics [Submitted on 27 Mar 2026] Complexity of Quadratic Bosonic Hamiltonian Simulation: \mathsf{BQP}-Completeness and \mathsf{PostBQP}-Hardness Lilith Zschetzsche, Refik Mansuroğlu, Norbert Schuch The computational complexity of simulating the dynamics of physical quantum systems is a central question at the interface of quantum physics and computer science. In this work, we address this question for the simulation of exponentially large bosonic Hamiltonians with quadratic interactions. We present two results: First, we introduce a broad class of quadratic bosonic problems for which we prove that they are \mathsf{BQP}-complete. Importantly, this class includes two known \mathsf{BQP}-complete problems as special cases: Classical oscillator networks and continuous-time quantum walks. Second, we show that extending the aforementioned class to even more general quadratic Hamiltonians results in a \mathsf{PostBQP}-hard problem. This reveals a sharp transition in the complexity of simulating large quantum systems on a quantum computer, as well as in the difference in complexity between their simulation on classical and quantum computers. Comments: 5+9 pages, 1 figure Subjects: Quantum Physics (quant-ph); Computational Complexity (cs.CC) Cite as: arXiv:2603.26561 [quant-ph]   (or arXiv:2603.26561v1 [quant-ph] for this version)   https://doi.org/10.48550/arXiv.2603.26561 Focus to learn more Submission history From: Refik Mansuroglu [view email] [v1] Fri, 27 Mar 2026 16:25:41 UTC (30 KB) Access Paper: HTML (experimental) view license Current browse context: quant-ph < prev   |   next > new | recent | 2026-03 Change to browse by: cs cs.CC References & Citations INSPIRE HEP NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)