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.
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.
Abstract Bosonic quantum systems operate in an infinite-dimensional Hilbert space, unlike discrete-variable quantum systems. This distinct mathematical structure leads to fundamental differences in quantum information processing, such as exponentially greater complexity of state tomography 1 and factoring in constant space 2 . Yet, it remains unclear whether this structural difference may translate to a practical computational advantage over finite-dimensional quantum computers. Here we take a step towards answering this question by showing that universal bosonic quantum computations can be simulated in polynomial space (and exponential time) on a classical computer, improving the previous best upper bound requiring exponential memory 3 . In complexity-theoretic terms, we improve the best upper bound on CVBQP with at most exponential energy from EXPSPACE to PSPACE. This result is achieved using a simulation strategy based on finite energy cutoffs and approximate coherent state decompositions. While we propose ways to potentially refine this bound, we also present arguments supporting the plausibility of an exponential computational advantage of bosonic quantum computers over their discrete-variable counterparts. Furthermore, we emphasize the role of circuit energy as a resource and discuss why it may act as the fundamental bottleneck in realizing this advantage in practice.
We investigate the role of energy, i.e. average photon number, as a resource in the computational complexity of bosonic systems. We show three sets of results: (1. Energy growth rates) There exist bosonic gate sets which increase energy incredibly rapidly, obtaining e.g. infinite energy in finite/constant time. We prove these high energies can make computing properties of bosonic computations, such as deciding whether a given computation will attain infinite energy, extremely difficult, formally undecidable. (2. Lower bounds on computational power) More energy ``='' more computational power. For example, certain gate sets allow poly-time bosonic computations to simulate PTOWER, the set of deterministic computations whose runtime scales as a tower of exponentials with polynomial height. Even just exponential energy and O(1) modes suffice to simulate NP, which, importantly, is a setup similar to that of the recent bosonic factoring algorithm of [Brenner, Caha, Coiteux-Roy and Koenig (2024)]. For simpler gate sets, we show an energy hierarchy theorem. (3. Upper bounds on computational power) Bosonic computations with polynomial energy can be simulated in BQP, ``physical'' bosonic computations with arbitrary finite energy are decidable, and the gate set consisting of Gaussian gates and the cubic phase gate can be simulated in PP, with exponential bound on energy, improving upon the previous PSPACE upper bound. Finally, combining upper and lower bounds yields no-go theorems for a continuous-variable Solovay--Kitaev theorem for gate sets such as the Gaussian and cubic phase gates.
We study computational problems related to the Schrödinger operator H=−Δ+V in the real space under the condition that (i) the potential function V is smooth and has its value and derivative bounded within some polynomial of n and (ii) V only consists of O(1)-body interactions. We prove that (i) simulating the dynamics generated by the Schrödinger operator implements universal quantum computation, i.e., it is BQP-hard, and (ii) estimating the ground energy of the Schrödinger operator is as hard as estimating that of local Hamiltonians with no sign problem (a.k.a. stoquastic Hamiltonians), i.e., it is StoqMA-complete. This result is particularly intriguing because the ground energy problem for general bosonic Hamiltonians is known to be QMA-hard and it is widely believed that StoqMAQMA.
The new computational paradigms of quantum computing change the current ideas of what can be efficiently computed. The chapter discusses the theory of quantum complexity classes such as bounderd-error quantum polynomial time (BQP), quantum Merlin-Arthur (QMA), and others, their theoretical foundations, their definition and their relationship with classical complexity classes like P, NP, and PSPACE. The special attention here is on the use of superposition, entanglement and interference to be able to solve problems more efficiently than with classical algorithms using quantum algorithms. The reduction relation, the completeness and separations of quantum complexity classes are discussed, along with some open problems including the quantum-classical separation of computational power. Case studies of important quantum algorithms, relevant to cryptography, optimization, and scientific computing like Shor's factoring algorithm, Grover's search algorithm, and quantum simulation methods follow the classes.
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 BQP-complete. Importantly, this class includes two known 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 PostBQP-complete problem, which constitutes a jump 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.
We connect both discrete and algebraic complexity theory with the satisfiability problem in certain non-Boolean lattices. Specifically, quantum logic was introduced in 1936 by Garrett Birkhoff and John von Neumann as a framework for capturing the logical peculiarities of quantum observables: in the 1D case it coincides with Boolean propositional logic but, starting with dimension two, violates the distributive law. We introduce the weak and strong satisfiability problem for quantum logic propositional formulae. It turns out that in dimension two, both are also NP --complete. For higher-dimensional spaces ℝ d and ℂ d with d ≥ 3 fixed, on the other hand, we show both problems to be complete for the nondeterministic Blum-Shub-Smale (BSS) model of real computation. This provides a unified view on both Turing and real BSS complexity theory, and extends the (still relatively scarce) list of problems established NP ℝ --complete with one, perhaps, closest in spirit to the classical Cook-Levin Theorem. More precisely, strong satisfiability of ∧ ∨ ∧ --terms is complete, while that of ∧ ∨--terms (i.e., those in conjunctive form) can be decided in polynomial time in dimensions d ≥ 2. The decidability of the infinite-dimensional case being still open, we proceed to investigate the case of indefinite finite dimensions. Here, weak satisfiability still belongs to NP R and strong satisfiability is still hard; the latter, in fact, turns out as polynomial-time equivalent to the feasibility of noncommutative integer polynomial equations over matrix rings.