quantum-computing

Bosonic Quantum Computational Complexity

Quantum Journal

29 min read

0 likes

Bosonic Quantum Computational Complexity

Summarize this article with:

AbstractQuantum 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.Popular summaryIn recent years, quantum computing involving physical systems with continuous degrees of freedom, such as the bosonic quantum states of light, has attracted significant interest. However, a well-defined quantum complexity theory for these bosonic computations over infinite-dimensional Hilbert spaces is missing. Mathematically, Bosonic states are described using a vector in infinite-dimensional systems. Unlike discrete variable quantum systems, continuous variable observables are in principle unbounded, satisfying algebraic relationships that do not have a discrete variable counterpart. An important implication of these properties is that energy (average particle number) in bosonic systems can grow very fast, leading to extremely complex behavior. Due to these features, many results that we take for granted in the theory of quantum complexity for discrete variables, such as universality and efficient compiling, are not fully established in the continuous-variable case. In this work, we take initial steps in formulating quantum complexity theory over continuous variables. We study both the complexity of dynamics and the ground-state problem.► BibTeX data@article{Chabaud2026bosonicquantum, doi = {10.22331/q-2026-05-20-2110}, url = {https://doi.org/10.22331/q-2026-05-20-2110}, title = {Bosonic {Q}uantum {C}omputational {C}omplexity}, author = {Chabaud, Ulysse and Joseph, Michael and Mehraban, Saeed and Motamedi, Arsalan}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2110}, month = may, year = {2026} }► References [1] Scott Aaronson and Alex Arkhipov. The computational complexity of linear optics. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 333–342, 2011. https://doi.org/10.1145/1993636.1993682. https://doi.org/10.1145/1993636.1993682 [2] Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach.

Cambridge University Press, 2009. https://doi.org/10.1017/CBO9780511804090. https://doi.org/10.1017/CBO9780511804090 [3] Francesco Arzani, Robert I Booth, and Ulysse Chabaud. Effective descriptions of bosonic systems can be considered complete. Nature Communications, 16(1):9744, 2025. https://doi.org/10.1038/s41467-025-64872-3. https://doi.org/10.1038/s41467-025-64872-3 [4] Scott Aaronson and Daniel Gottesman. Improved simulation of stabilizer circuits. Physical Review A, 70(5):052328, 2004. https://doi.org/10.1103/PhysRevA.70.052328. https://doi.org/10.1103/PhysRevA.70.052328 [5] Ulrik L Andersen, Jonas S Neergaard-Nielsen, Peter Van Loock, and Akira Furusawa. Hybrid discrete-and continuous-variable quantum information. Nature Physics, 11(9):713–719, 2015. https://doi.org/10.1038/nphys3410. https://doi.org/10.1038/nphys3410 [6] Valentine Bargmann. On a Hilbert space of analytic functions and an associated integral transform part i. Communications on pure and applied mathematics, 14(3):187–214, 1961. https://doi.org/10.1002/cpa.3160140303. https://doi.org/10.1002/cpa.3160140303 [7] Ryan Babbush, Dominic W Berry, Robin Kothari, Rolando D Somma, and Nathan Wiebe. Exponential quantum speedup in simulating coupled classical oscillators. Physical Review X, 13(4):041041, 2023. https://doi.org/10.1103/PhysRevX.13.041041. https://doi.org/10.1103/PhysRevX.13.041041 [8] Lukas Brenner, Libor Caha, Xavier Coiteux-Roy, and Robert Koenig. Factoring an integer with three oscillators and a qubit. Nature Communications, 2025. https://doi.org/10.1038/s41467-025-67694-5. https://doi.org/10.1038/s41467-025-67694-5 [9] Dominic W Berry, Andrew M Childs, and Robin Kothari. Hamiltonian simulation with nearly optimal dependence on all parameters. In 2015 IEEE 56th annual symposium on foundations of computer science, pages 792–809. IEEE, 2015. https://doi.org/10.1109/FOCS.2015.54. https://doi.org/10.1109/FOCS.2015.54 [10] Dominic W Berry, Andrew M Childs, Aaron Ostrander, and Guoming Wang. Quantum algorithm for linear differential equations with exponentially improved dependence on precision. Communications in Mathematical Physics, 356:1057–1081, 2017. https://doi.org/10.1007/s00220-017-3002-y. https://doi.org/10.1007/s00220-017-3002-y [11] Alice Barthe, M. Cerezo, Andrew T. Sornborger, Martín Larocca, and Diego García-Martín. Gate-based quantum simulation of gaussian bosonic circuits on exponentially many modes. Phys. Rev. Lett., 134:070604, Feb 2025. https://doi.org/10.1103/PhysRevLett.134.070604. https://doi.org/10.1103/PhysRevLett.134.070604 [12] Lenore Blum, Felipe Cucker, Mike Shub, and Steve Smale. Complexity and real computation. Springer Science & Business Media, 1998. https://doi.org/10.1007/978-1-4612-0701-6. https://doi.org/10.1007/978-1-4612-0701-6 [13] José L Balcázar, Josep Díaz, and Joaquim Gabarró. Structural complexity II, volume 22. Springer Science & Business Media, 2012. https://doi.org/10.1007/978-3-642-75357-2. https://doi.org/10.1007/978-3-642-75357-2 [14] Lukas Brenner, Beatriz Dias, and Robert Koenig. Trading modes against energy. arXiv preprint arXiv:2509.18854, 2025. https://doi.org/10.48550/arXiv.2509.18854. https://doi.org/10.48550/arXiv.2509.18854 arXiv:2509.18854 [15] Simon Becker, Nilanjana Datta, Ludovico Lami, and Cambyse Rouzé. Energy-constrained discrimination of unitaries, quantum speed limits, and a Gaussian Solovay-Kitaev theorem.

Physical Review Letters, 126(19):190504, 2021. https://doi.org/10.1103/PhysRevLett.126.190504. https://doi.org/10.1103/PhysRevLett.126.190504 [16] Olivier Bournez and Amaury Pouly. A survey on analog models of computation. In Handbook of computability and complexity in analysis, pages 173–226. Springer, 2021. https://doi.org/10.48550/arXiv.1805.05729. https://doi.org/10.48550/arXiv.1805.05729 [17] Stephen D Bartlett, Barry C Sanders, Samuel L Braunstein, and Kae Nemoto. Efficient classical simulation of continuous variable quantum information processes.

Physical Review Letters, 88(9):097904, 2002. https://doi.org/10.1103/PhysRevLett.88.097904. https://doi.org/10.1103/PhysRevLett.88.097904 [18] Lenore Blum, Mike Shub, and Steve Smale. On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. Bulletin of the American Mathematical Society, 21(1):1–46, 1989. http://dx.doi.org/10.1090/S0273-0979-1989-15750-9. https://doi.org/10.1090/S0273-0979-1989-15750-9 [19] Sergey Bravyi, Graeme Smith, and John A Smolin. Trading classical and quantum computational resources. Physical Review X, 6(2):021043, 2016. https://doi.org/10.1103/PhysRevX.6.021043. https://doi.org/10.1103/PhysRevX.6.021043 [20] Stephen P Boyd and Lieven Vandenberghe. Convex optimization.

Cambridge University Press, 2004. https://doi.org/10.1017/CBO9780511804441. https://doi.org/10.1017/CBO9780511804441 [21] Ulysse Chabaud, Giulia Ferrini, Frédéric Grosshans, and Damian Markham. Classical simulation of Gaussian quantum circuits with non-Gaussian input states.

Physical Review Research, 3(3):033018, 2021. https://doi.org/10.1103/PhysRevResearch.3.033018. https://doi.org/10.1103/PhysRevResearch.3.033018 [22] Ulysse Chabaud, Sevag Gharibian, Saeed Mehraban, Arsalan Motamedi, Hamid Reza Naeij, Dorian Rudolph, and Dhruva Sambrani. Energy, bosons and computational complexity. arXiv preprint arXiv:2510.08545, 2025. https://doi.org/10.48550/arXiv.2510.08545. https://doi.org/10.48550/arXiv.2510.08545 arXiv:2510.08545 [23] Andrew M Childs, David Gosset, and Zak Webb. The Bose-Hubbard model is QMA-complete. In Automata, Languages, and Programming: 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I 41, pages 308–319. Springer, 2014. https://doi.org/10.1007/978-3-662-43948-7_26. https://doi.org/10.1007/978-3-662-43948-7_26 [24] Robert M Corless, David J Jeffrey, and H Rasmussen. Numerical evaluation of airy functions with complex arguments. Journal of Computational Physics, 99(1):106–114, 1992. https://doi.org/10.1016/0021-9991(92)90279-8. https://doi.org/10.1016/0021-9991(92)90279-8 [25] Ulysse Chabaud and Saeed Mehraban. Holomorphic representation of quantum computations. Quantum, 6:831, 2022. https://doi.org/10.22331/q-2022-10-06-831. https://doi.org/10.22331/q-2022-10-06-831 [26] Ulysse Chabaud, Damian Markham, and Frédéric Grosshans. Stellar representation of non-Gaussian quantum states.

Physical Review Letters, 124(6):063605, 2020. https://doi.org/10.1103/PhysRevLett.124.063605. https://doi.org/10.1103/PhysRevLett.124.063605 [27] Eleanor Crane, Kevin C Smith, Teague Tomesh, Alec Eickbusch, John M Martyn, Stefan Kühn, Lena Funcke, Michael Austin DeMarco, Isaac L Chuang, Nathan Wiebe, et al. Hybrid oscillator-qubit quantum processors: Simulating fermions, bosons, and gauge fields. arXiv preprint arXiv:2409.03747, 2024. https://doi.org/10.48550/arXiv.2409.03747. https://doi.org/10.48550/arXiv.2409.03747 arXiv:2409.03747 [28] Carsten Damm. Problems complete for $\oplus$L. In Aspects and Prospects of Theoretical Computer Science: 6th International Meeting of Young Computer Scientists Smolenice, Czechoslovakia, November 19–23, 1990 Proceedings 6, pages 130–137. Springer, 1990. https://doi.org/10.1016/0020-0190(90)90150-V. https://doi.org/10.1016/0020-0190(90)90150-V [29] Martin Davis. Hilbert's tenth problem is unsolvable.

The American Mathematical Monthly, 80(3):233–269, 1973. https://doi.org/10.1080/00029890.1973.11993265. https://doi.org/10.1080/00029890.1973.11993265 [30] Abhinav Deshpande, Alexey V Gorshkov, and Bill Fefferman. Importance of the spectral gap in estimating ground-state energies. PRX Quantum, 3(4):040327, 2022. https://doi.org/10.1103/PRXQuantum.3.040327. https://doi.org/10.1103/PRXQuantum.3.040327 [31] Danial Dervovic, Mark Herbster, Peter Mountney, Simone Severini, Naïri Usher, and Leonard Wossnig. Quantum linear systems algorithms: a primer. arXiv preprint arXiv:1802.08227, 2018. https://doi.org/10.48550/arXiv.1802.08227. https://doi.org/10.48550/arXiv.1802.08227 arXiv:1802.08227 [32] Beatriz Dias and Robert König. Classical simulation of non-gaussian bosonic circuits. Physical Review A, 110(4):042402, 2024. https://doi.org/10.1103/PhysRevA.110.042402. https://doi.org/10.1103/PhysRevA.110.042402 [33] Martin Davis, Yuri Matijasevič, and Julia Robinson. Hilbert's tenth problem. Diophantine equations: positive aspects of a negative solution. American Math. Soc Providence, 1, 1976. [34] Christopher M Dawson and Michael A Nielsen. The Solovay-Kitaev algorithm. arXiv preprint quant-ph/0505030, 2005. https://doi.org/10.48550/arXiv.quant-ph/0505030. https://doi.org/10.48550/arXiv.quant-ph/0505030 arXiv:quant-ph/0505030 [35] Jaromír Fiurášek. Efficient construction of witnesses of the stellar rank of nonclassical states of light. Optics Express, 30(17):30630–30639, 2022. https://doi.org/10.1364/OE.466175. https://doi.org/10.1364/OE.466175 [36] Alessandro Ferraro, Stefano Olivares, and Matteo GA Paris. Gaussian states in continuous variable quantum information. arXiv preprint quant-ph/0503237, 2005. https://doi.org/10.48550/arXiv.quant-ph/0503237. https://doi.org/10.48550/arXiv.quant-ph/0503237 arXiv:quant-ph/0503237 [37] LH Ford. Negative energy densities in quantum field theory. International Journal of Modern Physics A, 25(11):2355–2363, 2010. https://doi.org/10.1142/S0217751X10049633. https://doi.org/10.1142/S0217751X10049633 [38] Bill Fefferman and Zachary Remscrim. Eliminating intermediate measurements in space-bounded quantum computation. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1343–1356, 2021. https://doi.org/10.1145/3406325.3451051. https://doi.org/10.1145/3406325.3451051 [39] Daniel Gottesman, Alexei Kitaev, and John Preskill. Encoding a qubit in an oscillator. Physical Review A, 64(1):012310, 2001. https://doi.org/10.1103/PhysRevA.64.012310. https://doi.org/10.1103/PhysRevA.64.012310 [40] Daniel Gottesman. The Heisenberg representation of quantum computers. arXiv preprint quant-ph/9807006, 1998. https://doi.org/10.48550/arXiv.quant-ph/9807006. https://doi.org/10.48550/arXiv.quant-ph/9807006 arXiv:quant-ph/9807006 [41] Arne L Grimsmo and Shruti Puri. Quantum error correction with the Gottesman-Kitaev-Preskill code. PRX Quantum, 2(2):020101, 2021. https://doi.org/10.1103/PRXQuantum.2.020101. https://doi.org/10.1103/PRXQuantum.2.020101 [42] Brian C Hall. Quantum theory for mathematicians, volume 267. Springer Science & Business Media, 2013. https://doi.org/10.1007/978-1-4614-7116-5. https://doi.org/10.1007/978-1-4614-7116-5 [43] Brian C Hall. Lie groups, Lie algebras, and representations: An Elementary Introduction. Springer, 2015. https://doi.org/10.1007/978-3-319-13467-3. https://doi.org/10.1007/978-3-319-13467-3 [44] Matthew B Hastings. Perturbation theory and the sum of squares. arXiv preprint arXiv:2205.12325, 2022. https://doi.org/10.48550/arXiv.2205.12325. https://doi.org/10.48550/arXiv.2205.12325 arXiv:2205.12325 [45] David Hilbert. Mathematical problems (transl. mw newson). Bull. Amer. Math. Soc, 8:437–479, 1902. [46] Roger A. Horn and Charles R. Johnson. Hermitian and symmetric matrices, page 167–256.

Cambridge University Press, 1985. https://doi.org/10.1017/CBO9780511810817.006. https://doi.org/10.1017/CBO9780511810817.006 [47] Martin Houde, Will McCutcheon, and Nicolás Quesada. Matrix decompositions in quantum optics: Takagi/autonne, bloch–messiah/euler, iwasawa, and williamson. Canadian Journal of Physics, 102(10):497–507, 2024. https://doi.org/10.1139/cjp-2024-0070. https://doi.org/10.1139/cjp-2024-0070 [48] Oliver Hahn, Ryuji Takagi, Giulia Ferrini, and Hayata Yamasaki. Classical simulation and quantum resource theory of non-gaussian optics. Quantum, 9:1881, 2025. https://doi.org/10.22331/q-2025-10-13-1881. https://doi.org/10.22331/q-2025-10-13-1881 [49] Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen. MIP*= RE. Communications of the ACM, 64(11):131–138, 2021. https://doi.org/10.1145/3485628. https://doi.org/10.1145/3485628 [50] James P Jones. Three universal representations of recursively enumerable sets. The Journal of Symbolic Logic, 43(3):549––571, 1978. https://doi.org/10.2307/2272832. https://doi.org/10.2307/2272832 [51] Timjan Kalajdzievski and Juan Miguel Arrazola. Exact gate decompositions for photonic quantum computing. Physical Review A, 99(2):022341, 2019. https://doi.org/10.1103/PhysRevA.99.022341. https://doi.org/10.1103/PhysRevA.99.022341 [52] Dmitri Karp. Holomorphic spaces related to orthogonal polynomials and analytic continuation of functions. In Analytic extension formulas and their applications, pages 169–187. Springer, 2001. https://doi.org/10.1007/978-1-4757-3298-6_10. https://doi.org/10.1007/978-1-4757-3298-6_10 [53] Tien D Kieu. Quantum algorithm for Hilbert's tenth problem. International Journal of Theoretical Physics, 42:1461–1478, 2003. https://doi.org/10.1023/A:1025780028846. https://doi.org/10.1023/A:1025780028846 [54] A Yu Kitaev. Quantum computations: algorithms and error correction.

Russian Mathematical Surveys, 52(6):1191, 1997. https://doi.org/10.1070/RM1997v052n06ABEH002155. https://doi.org/10.1070/RM1997v052n06ABEH002155 [55] Julia Kempe, Alexei Kitaev, and Oded Regev. The complexity of the local hamiltonian problem. FSTTCS 2004. Lecture Notes in Computer Science, vol 3328, 2004. https://doi.org/10.1007/978-3-540-30538-5_31. https://doi.org/10.1007/978-3-540-30538-5_31 [56] Emanuel Knill, Raymond Laflamme, and Gerald J Milburn. A scheme for efficient quantum computation with linear optics. Nature, 409(6816):46–52, 2001. https://doi.org/10.1038/35051009. https://doi.org/10.1038/35051009 [57] Pascal Koiran. A weak version of the blum, shub, and smale model. Journal of Computer and System Sciences, 54(1):177–189, 1997. https://doi.org/10.1006/jcss.1997.1478. https://doi.org/10.1006/jcss.1997.1478 [58] Timjan Kalajdzievski and Nicolás Quesada. Exact and approximate continuous-variable gate decompositions. Quantum, 5:394, 2021. https://doi.org/10.22331/q-2021-02-08-394. https://doi.org/10.22331/q-2021-02-08-394 [59] Julia Kempe and Oded Regev. 3-local hamiltonian is QMA-complete. arXiv preprint quant-ph/0302079, 2003. https://doi.org/10.48550/arXiv.quant-ph/0302079. https://doi.org/10.48550/arXiv.quant-ph/0302079 arXiv:quant-ph/0302079 [60] Hari Krovi. Improved quantum algorithms for linear and nonlinear differential equations. Quantum, 7:913, 2023. https://doi.org/10.22331/q-2023-02-02-913. https://doi.org/10.22331/q-2023-02-02-913 [61] Seth Lloyd and Samuel L Braunstein. Quantum computation over continuous variables.

Physical Review Letters, 82(8):1784, 1999. https://doi.org/10.1103/PhysRevLett.82.1784. https://doi.org/10.1103/PhysRevLett.82.1784 [62] Yuan Liu, Shraddha Singh, Kevin C Smith, Eleanor Crane, John M Martyn, Alec Eickbusch, Alexander Schuckert, Richard D Li, Jasmine Sinanan-Singh, Micheline B Soley, et al. Hybrid oscillator-qubit quantum processors: Instruction set architectures, abstract machine models, and applications. PRX Quantum, 7(1):010201, 2026. https://doi.org/10.1103/4rf7-9tfx. https://doi.org/10.1103/4rf7-9tfx [63] Wilhelm Magnus. On the exponential solution of differential equations for a linear operator. Communications on pure and applied mathematics, 7(4):649–673, 1954. https://doi.org/10.1002/cpa.3160070404. https://doi.org/10.1002/cpa.3160070404 [64] Yuri Vladimirovich Matiyasevich. Diophantine representation of enumerable predicates.

Izvestiya Rossiiskoi Akademii Nauk. Seriya Matematicheskaya, 35(1):3–30, 1971. https://doi.org/10.1070/IM1971v005n01ABEH001004. https://doi.org/10.1070/IM1971v005n01ABEH001004 [65] Katta G. Murty and Santosh N. Kabadi. Some NP-complete problems in quadratic and nonlinear programming. Mathematical Programming, 39(2):117–129, 1987. https://doi.org/10.1007/BF02592948. https://doi.org/10.1007/BF02592948 [66] Lars S Madsen, Fabian Laudenbach, Mohsen Falamarzi Askarani, Fabien Rortais, Trevor Vincent, Jacob FF Bulmer, Filippo M Miatto, Leonhard Neuhaus, Lukas G Helt, Matthew J Collins, et al. Quantum computational advantage with a programmable photonic processor. Nature, 606(7912):75–81, 2022. https://doi.org/10.1038/s41586-022-04725-x. https://doi.org/10.1038/s41586-022-04725-x [67] R Vilela Mendes and Vladimir I Man'ko. On the problem of quantum control in infinite dimensions. Journal of Physics A: Mathematical and Theoretical, 44(13):135302, 2011. https://doi.org/10.1088/1751-8113/44/13/135302. https://doi.org/10.1088/1751-8113/44/13/135302 [68] Eduardo Martín-Martínez. Quantum mechanics in phase space: an introduction. arXiv preprint arXiv:2208.08682, 2022. https://doi.org/10.48550/arXiv.2208.08682. https://doi.org/10.48550/arXiv.2208.08682 arXiv:2208.08682 [69] Takaya Matsuura, Nicolas C Menicucci, and Hayata Yamasaki. Continuous-variable fault-tolerant quantum computation under general noise. Nature Communications, 17(1):1709, 2026. https://doi.org/10.1038/s41467-026-69036-5. https://doi.org/10.1038/s41467-026-69036-5 [70] Filippo M Miatto and Nicolás Quesada. Fast optimization of parametrized quantum optical circuits. Quantum, 4:366, 2020. https://doi.org/10.22331/q-2020-11-30-366. https://doi.org/10.22331/q-2020-11-30-366 [71] Fabian Meylahn, Benno Willke, and Henning Vahlbruch. Squeezed states of light for future gravitational wave detectors at a wavelength of 1550 nm.

Physical Review Letters, 129(12):121103, 2022. https://doi.org/10.1103/PhysRevLett.129.121103. https://doi.org/10.1103/PhysRevLett.129.121103 [72] Michael A Nielsen and Isaac L Chuang. Quantum computation and quantum information. Phys. Today, 54(2):60, 2001. https://doi.org/10.1017/CBO9780511976667. https://doi.org/10.1017/CBO9780511976667 [73] Matteo GA Paris. Quantum state measurement by realistic heterodyne detection. Physical Review A, 53(4):2658, 1996. https://doi.org/10.1103/PhysRevA.53.2658. https://doi.org/10.1103/PhysRevA.53.2658 [74] Pablo A Parrilo. Semidefinite programming relaxations for semialgebraic problems. Mathematical programming, 96:293–320, 2003. https://doi.org/10.1007/s10107-003-0387-5. https://doi.org/10.1007/s10107-003-0387-5 [75] Askol'd Mikhailovich Perelomov. On the completeness of a system of coherent states. arXiv preprint math-ph/0210005, 2002. https://doi.org/10.48550/arXiv.math-ph/0210005. https://doi.org/10.48550/arXiv.math-ph/0210005 [76] Bo Peng, Yuan Su, Daniel Claudino, Karol Kowalski, Guang Hao Low, and Martin Roetteler. Quantum simulation of boson-related hamiltonians: techniques, effective hamiltonian construction, and error analysis. Quantum Science and Technology, 2023. https://doi.org/10.1088/2058-9565/adbf42. https://doi.org/10.1088/2058-9565/adbf42 [77] Paolo Stornati, Antonio Acin, Ulysse Chabaud, Alexandre Dauphin, Valentina Parigi, and Federico Centrone. Variational quantum simulation using non-Gaussian continuous-variable systems. arXiv preprint arXiv:2310.15919, 2023. https://doi.org/10.48550/arXiv.2310.15919. https://doi.org/10.48550/arXiv.2310.15919 arXiv:2310.15919 [78] Laurent Schwartz. Théorie des distributions et transformation de fourier. Annales de l'université de Grenoble. Nouvelle série. Section sciences mathématiques et physiques, 23:7–24, 1947. [79] Konrad Schmüdgen. An invitation to unbounded representations of *-algebras on Hilbert space. Springer, 2020. https://doi.org/10.1007/978-3-030-46366-3. https://doi.org/10.1007/978-3-030-46366-3 [80] Alessio Serafini. Quantum continuous variables: a primer of theoretical methods. CRC press, 2017. https://doi.org/10.1201/9781315118727. https://doi.org/10.1201/9781315118727 [81] Irving Ezra Segal and George W Mackey. Mathematical problems of relativistic physics, volume 2.

American Mathematical Soc., 1963. [82] Steve Smale. Mathematical problems for the next century. The mathematical intelligencer, 20:7–15, 1998. https://doi.org/10.1007/BF03025291. https://doi.org/10.1007/BF03025291 [83] Dennis Stanton. Some q-krawtchouk polynomials on chevalley groups. American Journal of Mathematics, 102(4):625–662, 1980. https://doi.org/10.2307/2374091. https://doi.org/10.2307/2374091 [84] Seckin Sefi and Peter Van Loock. How to decompose arbitrary continuous-variable quantum operations. Physical review letters, 107(17):170501, 2011. https://doi.org/10.1103/PhysRevLett.107.170501. https://doi.org/10.1103/PhysRevLett.107.170501 [85] Jerry L Trahan, Michael C Loui, and Vijaya Ramachandran. Multiplication, division, and shift instructions in parallel random access machines. Theoretical computer science, 100(1):1–44, 1992. https://doi.org/10.1016/0304-3975(92)90362-J. https://doi.org/10.1016/0304-3975(92)90362-J [86] Amnon Ta-Shma. Inverting well conditioned matrices in quantum logspace. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 881–890, 2013. https://doi.org/10.1145/2488608.2488720. https://doi.org/10.1145/2488608.2488720 [87] Varun Upreti, Dorian Rudolph, and Ulysse Chabaud. Bounding the computational power of bosonic systems, 2025. https://doi.org/10.48550/arXiv.2503.03600. https://doi.org/10.48550/arXiv.2503.03600 [88] Ryuji Ukai, Jun-ichi Yoshikawa, Noriaki Iwata, Peter van Loock, and Akira Furusawa. Universal linear bogoliubov transformations through one-way quantum computation. Physical review A, 81(3):032315, 2010. https://doi.org/10.1103/PhysRevA.81.032315. https://doi.org/10.1103/PhysRevA.81.032315 [89] SJL Van Eijndhoven and JLH Meyers. New orthogonality relations for the hermite polynomials and related Hilbert spaces. Journal of Mathematical Analysis and Applications, 146(1):89–98, 1990. https://doi.org/10.1016/0022-247X(90)90334-C. https://doi.org/10.1016/0022-247X(90)90334-C [90] 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. https://doi.org/10.1103/PhysRevLett.117.110801. https://doi.org/10.1103/PhysRevLett.117.110801 [91] A Vourdas. Analytic representations in quantum mechanics. Journal of Physics A: Mathematical and General, 39(7):R65, 2006. https://doi.org/10.1088/0305-4470/39/7/R01. https://doi.org/10.1088/0305-4470/39/7/R01 [92] Leslie G Valiant and Sven Skyum. Fast parallel computation of polynomials using few processors.

In Mathematical Foundations of Computer Science 1981: Proceedings, 10th Symposium Štrbské Pleso, Czechoslovakia August 31–September 4, 1981 10, pages 132–139. Springer, 1981. https://doi.org/10.1137/0212043. https://doi.org/10.1137/0212043 [93] John Watrous. Quantum computational complexity. arXiv preprint arXiv:0804.3401, 2008. https://doi.org/10.48550/arXiv.0804.3401. https://doi.org/10.48550/arXiv.0804.3401 arXiv:0804.3401 [94] Christian Weedbrook, Stefano Pirandola, Raúl García-Patrón, Nicolas J Cerf, Timothy C Ralph, Jeffrey H Shapiro, and Seth Lloyd. Gaussian quantum information. Reviews of Modern Physics, 84(2):621, 2012. https://doi.org/10.1103/RevModPhys.84.621. https://doi.org/10.1103/RevModPhys.84.621 [95] Re-Bing Wu, Tzyh-Jong Tarn, and Chun-Wen Li. Smooth controllability of infinite-dimensional quantum-mechanical systems. Physical Review A, 73(1):012719, 2006. https://doi.org/10.1103/PhysRevA.73.012719. https://doi.org/10.1103/PhysRevA.73.012719 [96] Walter Wyss. Two non-commutative binomial theorems. arXiv preprint arXiv:1707.03861, 2017. https://doi.org/10.48550/arXiv.1707.03861. https://doi.org/10.48550/arXiv.1707.03861 arXiv:1707.03861 [97] Gjergii Zaimi. Math Overflow: Binomial expansion for non-commutative setting. Math Overflow, 2011. https://mathoverflow.net/questions/78813/binomial-expansion-for-non-commutative-setting. https://mathoverflow.net/questions/78813/binomial-expansion-for-non-commutative-setting [98] Han-Sen Zhong, Hui Wang, Yu-Hao Deng, Ming-Cheng Chen, Li-Chao Peng, Yi-Han Luo, Jian Qin, Dian Wu, Xing Ding, Yi Hu, et al. Quantum computational advantage using photons. Science, 370(6523):1460–1463, 2020. https://doi.org/10.1126/science.abe8770. https://doi.org/10.1126/science.abe8770Cited byCould not fetch Crossref cited-by data during last attempt 2026-05-20 10:33:20: Could not fetch cited-by data for 10.22331/q-2026-05-20-2110 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-05-20 10:33:20: Cannot retrieve data from ADS due to rate limitations.This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions. AbstractQuantum 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.Popular summaryIn recent years, quantum computing involving physical systems with continuous degrees of freedom, such as the bosonic quantum states of light, has attracted significant interest. However, a well-defined quantum complexity theory for these bosonic computations over infinite-dimensional Hilbert spaces is missing. Mathematically, Bosonic states are described using a vector in infinite-dimensional systems. Unlike discrete variable quantum systems, continuous variable observables are in principle unbounded, satisfying algebraic relationships that do not have a discrete variable counterpart. An important implication of these properties is that energy (average particle number) in bosonic systems can grow very fast, leading to extremely complex behavior. Due to these features, many results that we take for granted in the theory of quantum complexity for discrete variables, such as universality and efficient compiling, are not fully established in the continuous-variable case. In this work, we take initial steps in formulating quantum complexity theory over continuous variables. We study both the complexity of dynamics and the ground-state problem.► BibTeX data@article{Chabaud2026bosonicquantum, doi = {10.22331/q-2026-05-20-2110}, url = {https://doi.org/10.22331/q-2026-05-20-2110}, title = {Bosonic {Q}uantum {C}omputational {C}omplexity}, author = {Chabaud, Ulysse and Joseph, Michael and Mehraban, Saeed and Motamedi, Arsalan}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2110}, month = may, year = {2026} }► References [1] Scott Aaronson and Alex Arkhipov. The computational complexity of linear optics. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 333–342, 2011. https://doi.org/10.1145/1993636.1993682. https://doi.org/10.1145/1993636.1993682 [2] Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach.

Read Original

Source Information

Source: Quantum Journal

Website: https://quantum-journal.org/feed/

Bosonic Quantum Computational Complexity

Tags

Source Information