Bosonic Quantum Computational Complexity

Chabaud, Ulysse; Joseph, Michael; Mehraban, Saeed; Motamedi, Arsalan

doi:10.4230/LIPIcs.ITCS.2025.33

Bosonic Quantum Computational Complexity

Ulysse Chabaud

DIENS, ENS, PSL University, CNRS, INRIA, Paris, France Michael Joseph Department of Computer Science, Tufts University, Medford, MA, USA Saeed Mehraban

Department of Computer Science, Tufts University, Medford, MA, USA Arsalan Motamedi Institute for Quantum Computing, Waterloo, Canada

Abstract

In 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. In this work, we lay the 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. Our main contributions include the following:

1.

Bosonic computations. We show that the power of Gaussian computations up to logspace reductions is equivalent to bounded-error quantum logspace (BQL, characterized by the problem of inverting well-conditioned matrices). More generally, we define classes of continuous-variable quantum polynomial time computations with a bounded probability of error (CVBQP) based on gates generated by polynomial bosonic Hamiltonians and particle-number measurements. 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 we demonstrate a BQP lower bound and an EXPSPACE upper bound by proving bounds on the average energy throughout the computation. We further show that the problem of computing expectation values of polynomial bosonic observables at the output of bosonic quantum circuits using Gaussian and cubic phase gates is in PSPACE.
2.

Bosonic ground energy problems. We prove that the problem of deciding whether the spectrum of a bosonic Hamiltonian is bounded from below 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 zero stellar rank, i.e., optimizing over Gaussian states, it is NP-complete; for polynomially-bounded stellar rank, it is in QMA; for unbounded stellar rank, it is RE-hard, i.e., undecidable.

Keywords and phrases:

continuous-variable quantum computing, infinite-dimensional quantum systems, stellar rank, Hamiltonian complexity

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Quantum information theory ; Theory of computation

\rightarrow

Quantum complexity theory

Related Version:

Full Version: https://arxiv.org/abs/2410.04274 [8]

Acknowledgements:

U.C. acknowledges inspiring discussions with F. Arzani, R. I. Booth, F. Grosshans, D. Markham, O. Bournez, S. Lloyd, T. Vidick, W. Slofstra, L. Lami, and A. Winter. S.M. thanks A. Natarajan, P. Love, V. Podolskii, V.V. Albert, M. Hafezi, A. Gorshkov, D. Jacobs, and J. Jeang for inspiring discussions. A.M. acknowledges discussions with P. Sinha, Z. Mann, and R. Cleve. M. J. thanks V. Podolskii, D. Jacobs, W. Khangtragool and A. Saha for helpful exchanges. The authors are grateful to S. Aaronson for helpful discussions and to T. Vidick and F. Grosshans for comments on earlier versions of this manuscript.

Funding:

S. M. and M. J. are grateful to the National Science Foundation (NSF CCF-2013062) for supporting this project. U.C. acknowledges support from the Plan France 2030 project NISQ2LSQ (ANR-22-PETQ-0006). U.C. and S.M. are grateful to have been supported by the Institute for Quantum Information and Matter, an NSF Physics Frontiers Center (NSF Grant PHY- 1733907), where preliminary ideas were discussed.

DOI:

10.4230/LIPIcs.ITCS.2025.33

Event:

16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Editors:

Raghu Meka

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Many quantum mechanical systems, such as spin systems, are effectively described using discrete variables and are captured using qubits or qudits. The standard model of quantum computation is formulated based on such discrete degrees of freedom [37]. However, quantum variables such as the position, momentum, or amplitudes of electromagnetic fields are continuous. These degrees of freedom are described mathematically using infinite-dimensional Hilbert spaces. Continuous-variable systems are also present in many fundamental problems in theoretical physics, such as the solution to energy levels of a molecular system, quantum field theories, or exotic quantum states of matter such as Bose–Einstein condensates.

Continuous-variable quantum architectures have recently been used in practical quantum computing implementations, with several leading quantum error-correction schemes being fundamentally infinite-dimensional [20, 21]. Several important physical frameworks for quantum computing, such as quantum photonic processors, are based on continuous-variable degrees of freedom. These architectures have recently been demonstrated at scales sufficient to solve computational sampling problems that are believed to exceed the power of classical computations [46, 34].

What are the fundamental computational limitations and power of quantum degrees of freedom? This question is the subject of quantum complexity theory [44]. The standard quantum computing model and quantum complexity theory are formulated using discrete-variable quantum degrees of freedom over finite-dimensional Hilbert spaces. Several complexity classes have been defined to capture the computational power associated with these quantum degrees of freedom. One can define various natural models of quantum computations, such as adiabatic computation, quantum circuits, topological quantum computation, or measurement-based quantum computing, and all of these variants have been proven to have power equal to the computational complexity class BQP, which captures the power of polynomial-size quantum circuits in deciding logical statements with a small probability of error. Another important complexity class that captures the complexity of estimating the energy levels of a quantum physical system is QMA, which can be viewed as a quantum generalization of NP and, in particular, MA as the randomized generalization of NP. Due to a seminal result of Kitaev [28] (and many follow-up works, e.g., [29]), the problem of estimating the ground state energy of a physical system up to inverse-polynomial additive error (known as the local Hamiltonian problem) is complete for QMA. In fact, the local Hamiltonian problem can be viewed as the quantum generalization of the canonical constraint satisfaction problem over the Boolean hypercube, which is itself complete for NP. In recent years, the relationship between these complexity classes and standard complexity classes such as polynomial time P, polynomial space PSPACE, nondeterministic polynomial time NP, $\#$ P (corresponding to counting the number of solutions to constraint satisfaction problems), PP (the class of problems that are solvable on a probabilistic Turing machine with probability of error $<1/2$ ) have been extensively studied. All of these complexity classes are contained in the class of problems solvable in exponential space EXPSPACE, itself included in the set of recursively enumerable languages RE. The known relationships between these complexity classes are illustrated in Figure 1.

Figure 1: Known relations between complexity classes used in this work. If a line connects complexity class

\mathbf{C}_{1}

to

\mathbf{C}_{2}

, with

\mathbf{C}_{1}

being on the right of

\mathbf{C}_{2}

, it is implied that

\mathbf{C}_{2}\subseteq\mathbf{C}_{1}

.

What are the basic relationships between the power of computations using bosonic continuous-variables over infinite-dimensional Hilbert spaces and these standard discrete-variable complexity classes over finite-dimensional ones? As it turns out, one can robustly encode discrete-variable computations into infinite-dimensional Hilbert spaces. For instance, Knill, Laflamme and Milburn showed that one can simulate arbitrary discrete-variable quantum computations using linear optics, particle-number measurements and feed-forward [32], i.e. adapting the computation based on the result of intermediate measurements, while Gottesman, Kitaev and Preskill gave a protocol to encode a qubit into the continuous degrees of freedom of a quantum harmonic oscillator in a fault-tolerant way [20]; the latter is among the leading proposals for reaching fault-tolerance in continuous-variable quantum architectures. As a consequence of these results, BQP can be robustly simulated using continuous quantum degrees of freedom. However, a formal complexity theory of bosonic computations is still missing.

In the continuous-variable setting, a model of quantum computation was first proposed by Lloyd and Braunstein [33]. In this model, the state of a quantum system evolves according to Hamiltonians, which are finite-degree polynomials in canonical continuous-variable (unbounded) operators such as the position operator $X$ and the momentum operator $P$ . These operators have fundamentally different mathematical properties from their discrete-variable counterparts. For instance, for any pair of discrete-variable operators acting on a finite-dimensional Hilbert space, $A$ and $B$ , $\mathrm{Tr}([A,B])=0$ , it is well known that $[X,P]=iI$ , which is not trace-class (i.e., does not have finite trace). The operators $X$ and $P$ have unbounded spectra with respective formal eigenbases $\ket{x},x\in\mathbb{R}$ such that $X\ket{x}=x\ket{x}$ , and $\ket{p},p\in\mathbb{R}$ such that $P\ket{p}=p\ket{p}$ , which are related to each other by a Fourier transform $\ket{x}\propto\int e^{ipx}\ket{p}dp$ , with their inner product giving Dirac delta functions $\innerproduct{x}{x^{\prime}}=\delta(x-x^{\prime})$ , to be interpreted in the sense of distributions. Another striking example of the peculiarities of infinite dimensions comes from quantum states such as $(\sqrt{6}/\pi)\sum_{n\geq 1}\frac{1}{n}\ket{n}$ , which are normalized but have infinite energy with respect to the harmonic oscillator Hamiltonian $X^{2}+P^{2}$ . Yet another famous example, known as Tsirelson’s problem, is that the tensor product and the commuting operator formulations of quantum mechanics are equivalent in finite dimensions but not in infinite dimensions, because of complexity-theoretic reasons in particular [24].

Due to such nontrivial features, standard quantum complexity results in the discrete-variable setting, such as the Solovay–Kitaev theorem [31], do not have a clear counterpart in the continuous case. In particular, if one defines continuous-variable analogs of standard discrete-variable quantum computational complexity classes BQP and QMA, does it lead to relationships similar to the discrete-variable case?

Beyond its fundamental relevance, developing such a complexity-theoretic foundation for continuous quantum degrees of freedom would widen our horizon of knowledge in several ways. Firstly, it would help us to understand the computational power of continuous quantum degrees of freedom for real-world applications. Many physical architectures that are promising candidates for realizing a full-fledged universal discrete-variable quantum computer, such as photonic systems, superconducting qubits, and acoustic modes like phonons, are, in fact, inherently continuous. Developing a fundamentally continuous language for studying these systems could be essential to fully utilize the potential of such quantum computational devices, e.g., to devise fast compilation strategies [40] or performing Hamiltonian simulation with optimal constants [39].

Secondly, it touches on fundamental questions in theoretical physics. For instance, a standard approach to understanding continuous systems is to discretize them to a certain precision. We face an immediate question: can we reduce the study of these systems by approximating them with discrete variables, or are continuous-variable systems fundamentally distinct and require their own separate formulation? Theoretical physics provides some evidence for the latter. For instance, the renormalization group provides insight that the fundamental behavior of a physical system can vary significantly at different scales of precision. Or, in quantum field theory, one needs to impose energy cut-offs to avoid divergences in the computation of scattering amplitudes. Computational complexity studies the fundamental limits of finding reductions between two models, and we believe that tools from this framework would play a fundamental role in studying reductions between discrete and continuous degrees of freedom.

In this paper, we lay the groundwork for a computational complexity theory for quantum continuous variables. We formulate several Boolean quantum computational complexity classes based on continuous-variable bosonic generalizations of BQP and QMA. We study the relationship between these and their discrete-variable counterparts, highlight their fundamental similarities and differences, and identify outstanding open problems.

2 Main models and results

A bosonic quantum state can be described using a vector in the infinite-dimensional Hilbert space of square-summable complex sequences $\ell^{2}(\mathbb{C})$ which we refer to as a bosonic mode or a qumode. Let $\mathcal{H}_{n}\cong\ell^{2}(\mathbb{C}^{\otimes n})$ be the tensor-product space of $n$ bosonic modes. We consider bosonic computations based on Hamiltonians $H$ acting on $\mathcal{H}_{n}$ that are polynomials of degree $d$ in the canonical operators $X$ and $P$ . Commonly known as position and momentum operators, they satisfy the canonical commutation relations

[X_{a},P_{b}]=i\delta_{a,b}I,\quad[X_{a},X_{b}]=0,\quad[P_{a},P_{b}]=0.

(1)

Polynomial Hamiltonians are ubiquitous in quantum physics and allow us to describe most existing models of bosonic quantum computations. The spectrum of such Hamiltonians is a subset of the reals, which can be discrete (e.g., for $X^{2}+P^{2}$ ), continuous (e.g., for $X$ ) or both. In our presentation, we always distinguish between the cases of Gaussian Hamiltonians (polynomials of degree $d\leq 2$ ), which are typically less powerful, and non-Gaussian Hamiltonians (polynomials of degree $d>2$ ).

We will often make use of the particle number operator (or simply, number operator) defined in terms of the position and momentum operators by,

N:=\frac{X^{2}+P^{2}-I}{2}

(2)

where $N\ket{n}=n\ket{n}$ for the Fock basis states $\ket{n}$ . The number operator plays a key role in our analysis as it quantifies the quanta of excitation, or ’particles,’ in a bosonic mode. In terms of the energy of a bosonic state, we often refer to the average particle number, which corresponds to the expectation value $\langle N\rangle$ .

2.1 Structure and summary of results

Figure 2: Relations between complexity classes and computational problems proven in this paper and described below, up to logspace reductions on the left and polynomial-time reductions on the right. If a line connects two complexity classes, it is implied that the one below in the diagram is included in the one above. If a line connects a problem to a complexity class, it is implied that the problem is in that class if it is below, and hard for that class if it is above. Square brackets indicate specific choices of non-Gaussian gates, where

X^{3}

and

\overline{\sigma}_{x}

are polynomial Hamiltonians of degree

3

, while

\overline{\sigma}_{z}\otimes\overline{\sigma}_{z}

is a polynomial Hamiltonian of degree

4

. The other inclusions are given by the corresponding theorems or trivial from the definitions of the classes.

The structure of the full version of the paper [8] is as follows. After preliminary background in Section 2, we first consider Boolean complexity classes based on bounded-error continuous-variable quantum computations in Section 3 (Gaussian) and Section 4 (non-Gaussian). These contributions are summarised in Figure 2.

$\blacksquare$

We define a complexity class corresponding to the power of Gaussian dynamical computations (GDC) with logspace preprocessing. We prove that the power of this model is equivalent to the complexity class BQL corresponding to quantum logspace (See Theorem 3.1 in [8]). A complete problem for this class is inverting well-conditioned matrices [16, 42]. This can be viewed as a continuous-variable version of a result by Aaronson and Gottesman [2], which places the problem of simulating Clifford circuits in the complexity class $\oplus$ L (a complete problem for this class is computing the determinant over the finite field $\mathbb{Z}_{2}$ [12]).
$\blacksquare$

We then define bounded-error quantum computations using gates generated by polynomials in the bosonic position and momentum operators (CVBQP). In this model, we sample the output of the quantum computation in the particle number basis (eigenstates of $X^{2}+P^{2}$ ). We show that a specific instance of this class contains BQP (Theorem 4.1 in [8]) and that continuous-variable quantum computations using only Gaussian and cubic phase gates (generated by $X^{3}$ ) can be strongly simulated in EXPSPACE when no energy upper bound is assumed (Theorem 4.2 in [8]). We explain why proving a stronger upper bound of PSPACE or even PP as in the discrete-variable case (if true) would require nontrivial ideas. Finally, we give a polynomial-time parallel algorithm for computing output continuous-variable observable expectation values of such computations (Theorem 4.7 in [8]), which is in PSPACE by standard results [43]. We explain in Section 4.3.3 of [8] that the $\mathbf{EXPSPACE}$ and $\mathbf{PSPACE}$ results for particle-number measurements v.s. continuous-variable observable measurements are due to fundamental computational differences in Schrödinger v.s. Heisenberg dynamical evolution in continuous-variable systems. We conjecture that a strong simulation of the former model is strictly more difficult in terms of computational complexity.

Next, we consider ground state energy problems and Boolean non-deterministic quantum complexity classes in Section 5. These contributions are summarised in Table 1:

$\blacksquare$

We show that deciding the boundedness of the ground state energy is in P for Gaussian Hamiltonians (Theorem 5.1 in [8]) and co-NP-hard for constant-degree polynomial Hamiltonians (Theorem 5.2 in [8]). Furthermore, we give an efficient classical algorithm for verifying the boundedness of the ground state energy of a subclass of Hamiltonians of degree $d=4$ via a reduction to a classical sum-of-squares method (Proposition 5.4 in [8]).
$\blacksquare$
We study the continuous-variable local Hamiltonian problem ( $\mathsf{CVLH}^{d}_{\mathcal{S}}$ ) of estimating the lowest energy of a bosonic Hamiltonian of degree $d$ in the position and momentum operators over a set of states $\mathcal{S}$ . For Gaussian Hamiltonians, we show that this problem is in P whenever the set $\mathcal{S}$ contains the set of Gaussian states (Theorem 5.1 in [8]). For non-Gaussian Hamiltonians, we prove that the complexity of this problem critically depends on the stellar rank $r$ , a measure of the non-Gaussian character of a continuous-variable quantum state [9, 10]. In order to simplify the presentation of the second result below, we rely on a mathematical conjecture (Conjecture 2 in [8], for which we provide numerical evidence), which allows us to parametrize the relevant family of states one optimizes over using simple constraints on the energy (average particle number):
- –
  
  For $r=0$ (corresponding to optimization over Gaussian states) with at most $\mathsf{exp}(n):=e^{n^{O(1)}}$ energy (average particle number), we prove that the problem is NP-complete using a reduction from deciding when a matrix is not copositive (Theorem 5.3 in [8]).
- –
  
  When energy and stellar rank are both at most $\mathsf{poly}(n):=n^{O(1)}$ , we prove that the problem is in QMA (Theorem 5.4 in [8]). The same proof technique also shows that for arbitrary $r$ and at most $\mathsf{exp}(n)$ energy (average particle number), the problem is in NTIME ( $n^{O(r)}$ ), where NTIME $(t)$ is the class of problems that are solvable by a nondeterministic Turing machine that runs in time $O(t)$ on each branch.
- –
  
  For $r=\infty$ with no energy bound, using an observation of [30], we encode the solution to Hilbert’s tenth problem in the ground state of a Hamiltonian. As a consequence, the problem is RE-hard (undecidable) when we assume no bound on the stellar rank (Theorem 5.6 in [8]).
$\blacksquare$

Finally, we introduce a continuous-variable version of QMA, based on a CVBQP verifier (CVQMA). We give preliminary ideas for relating the complexity of the continuous-variable local Hamiltonian problem to this class, based on a continuous-variable analog of Kitaev’s history state construction [29, 28].

Table 1: Computational complexity of the Hamiltonian boundedness problem and the continuous-variable local Hamiltonian problem for Gaussian and non-Gaussian polynomial bosonic Hamiltonians over

n

modes.

\mathcal{S}^{\mathsf{exp}}_{O(1)}

denotes the set of states with constant stellar rank with at most exponential energy (average particle number) and

\mathcal{S}^{\mathsf{poly}}_{\mathsf{poly}}

the set of states with polynomially bounded stellar rank and energy. Note that Theorem 5.4 and Theorem 5.5 of [8] rely on Conjecture 2, for which we provide numerical evidence. For all non-Gaussian results, assuming a degree

d=4

is sufficient except for the undecidability result where we show that

d=8

is sufficient (for

d=4

, the problem is

\mathbf{QMA}

-hard as a consequence of [11]).

Ground state problems	Gaussian Hamiltonians	Non-Gaussian Hamiltonians
$\mathsf{HBound}$	$\in\mathbf{P}$ (Theorem 5.1 in [8])	co-NP-hard (Theorem 5.2 in [8])
$\mathsf{CVLH}$ over ${\mathcal{S}^{\mathsf{exp}}_{0}}$	$\in\mathbf{P}$ (Theorem 5.1 in [8])	NP-complete (Theorem 5.3 in [8])
$\mathsf{CVLH}$ over ${\mathcal{S}^{\mathsf{poly}}_{\mathsf{poly}}}$	$\in\mathbf{P}$ (Theorem 5.1 in [8])	$\in\mathbf{QMA}$ (Theorem 5.4 in [8])
$\mathsf{CVLH}$ over ${\mathcal{S}^{\mathsf{exp}}_{r}}$	$\in\mathbf{P}$ (Theorem 5.1 in [8])	$\in\mathbf{NTIME}(n^{O(r)})$ (Theorem 5.5 in [8])
$\mathsf{CVLH}$	$\in\mathbf{P}$ (Theorem 5.1 in [8])	$\mathbf{RE}$ -hard (Theorem 5.6 in [8])

3 Details of the contributions

In what follows, we detail our contributions and provide some intuition. All definitions and results are stated informally and we refer to [8] for formal statements and proofs.

Gaussian computations

Let us first consider the power of bounded-error quantum computations using polynomial Hamiltonians of degree at most $2$ . The unitary gates generated by such Hamiltonians are known as Gaussian gates. It is well-known that Gaussian gates are efficiently simulatable in polynomial time P when acting on Gaussian states [4], i.e., states that may be obtained from the vacuum using Gaussian gates [17], together with Gaussian measurements, i.e., projection onto Gaussian states. We define a model of Gaussian computations as follows (see Definition 3.1 of [8] for a formal statement):

Definition 1 (Gaussian dynamical computations, informal).

Gaussian dynamical computation ( $\mathbf{GDC}$ ) is the class of problems that can be solved by evolving input Gaussian states via logspace uniform quadratic Hamiltonians for polynomial time, followed by measuring a single mode in the position basis (see Section 2.3.3 of [8] for more details about the formalism). The computation accepts if the measured outcome has a value greater than a fixed constant $b$ and rejects if it is below a fixed constant $a$ .

$\mathbf{GDC}$ allows evolving a quantum state according to different Gaussian Hamiltonians one after the other, so long as the total time and number of Hamiltonians do not exceed a polynomial bound. Gaussian computations are known to be continuous-variable analogs of the so-called Clifford computations in the discrete-variable case. Clifford computations are also known to be classically simulatable in polynomial time, by the Gottesmann–Knill theorem [19]. In [2], Aaronson and Gottesman showed that one can actually simulate Clifford computations (i.e., sample from one qubit) in the complexity class $\oplus$ L, which is believed to be strictly contained in P. Performing linear algebra (such as computing the determinant) over $\mathbb{Z}_{2}$ is a complete problem for this class. It is natural to ask whether a continuous-variable analog of this result holds. Our first result resolves this question in the affirmative (see Theorem 3.1 in [8] for a formal statement):

Theorem 2 (The computational power of Gaussian dynamics, informal).

The power of Gaussian computations up to logspace reductions is captured by bounded-error quantum logspace (BQL) and, equivalently, the problem of inverting a well-conditioned matrix.

The proof is based on the symplectic formulation of Gaussian operators [17].

Recently and independently, in [3], it was shown that simulating a particular class of gate-based Gaussian computations over exponentially many modes is $\mathbf{BQP}$ -complete. Recall that approximate matrix inversion is a $\mathbf{BQP}$ -complete problem when the matrix under consideration is sparse and well-conditioned [14]. Although our models and results are technically different, both reveal a strong connection between Gaussian computations and linear algebra.

Bounded-error continuous-variable quantum polynomial time (CVBQP)

Arguably, there are many ways one can define a continuous-variable version of BQP based on how computation is being performed. We consider bosonic computations using gates generated by polynomials of constant degree in the position and momentum bosonic operators, which are ubiquitous in quantum physics, with particle-number measurements. We define gate set-dependent classes (see e.g., Definition 3 below) and investigate the computational power of these models for different choices of gate sets. In particular, we show that bosonic computations based on specific gates generated by degree-4 and $2$ -local Hamiltonians can perform universal (discrete-variable) quantum computation on an input vacuum state and without requiring feed-forward of measurement outcomes (see Theorem 4.1 of [8]). Interestingly, the equivalence between these different continuous-variable classes is unknown, in part due to the delicate features of unbounded operators such as those pointed out in the introduction. Some of these relationships, such as the fast compiling of polynomial-degree Hamiltonians into Gaussian and cubic phase gates, are outstanding open questions; see, e.g., [40, 27].

We then consider bosonic computations based on a family of circuits generated by cubic phase gates $e^{iX^{3}}$ and Gaussian gates $e^{iH}$ , where $H$ is a quadratic Hamiltonian in $X$ and $P$ . Notably, this gate set is believed/conjectured to be universal for the set of unitaries generated by arbitrary polynomials over an arbitrary number of modes [40, 27], a claim that was proven in a controllability sense in [45]. Due to [20], this computational model, when equipped with the ability of performing Gaussian measurements and feed-forward, is capable of performing universal (discrete-variable) quantum computation, when complex input states known as Gottesman–Kitaev–Preskill states are available.

Gaussian gates are closed under multiplication, which is one way we can understand the classical simulation of Gaussians. The single-mode Gaussian dynamics can furthermore be understood via specific integrable classical equations of motion (known as Calogero–Moser dynamics) [10]. However, once we add higher-degree gates to the gate set, the operators generated by the resulting gates generate a vastly larger set of operators, and the single-mode dynamics becomes chaotic [33, 45]. Define $\mathbf{CVBQP}[X^{3}]$ as the class of decision problems that are solvable using quantum circuits based on Gaussian and cubic phase gate sets (see Definition 4.4 of [8] for a formal definition):

Definition 3 ( $\mathbf{CVBQP}{[}X^{3}{]}$ , informal).

$\mathbf{CVBQP}[X^{3}]$ is the class of decision problems that are solvable with a bounded probability of error by applying a polynomial-time uniform sequence of Gaussian and cubic phase gates to the vacuum state and measuring the number of particles at the end, with the promise that the energy (average particle number) at the output is polynomially bounded.

We show that, in between the computation, the energy of states prepared from the vacuum by polynomial-time sequences of Gaussian and cubic phase gates is upper bounded by a doubly-exponential function of the number of gates and modes (see Proposition 4.3 of [8]). The reason for such drastic energy growth in the system is that consecutive application of cubic and Gaussian gates can lead to repeated squaring of basic observables. This, in turn, leads to an upper bound of EEXP on the strong simulation (computing output amplitudes up to exponential precision) of $\mathbf{CVBQP}[X^{3}]$ when the final measurement is made in the computational basis. We then apply standard depth reduction techniques to bring the complexity down to $\mathbf{EXPSPACE}$ (see Theorem 4.2 of [8] for a formal statement):

Theorem 4 (Upper bound on the computational power of Gaussian and cubic phase gates, informal).

Bosonic computations consisting of Gaussian and cubic phase gates on input vacuum and measurement in the Fock basis can be strongly simulated in $\mathbf{EXPSPACE}$ .

This theorem assumes no energy upper bound for each of the computational steps. When introducing an energy (average particle number) upper bound of $E^{*}$ in the above result, we note that the space complexity of the classical simulation in the single-mode case scales as $O(\textsf{log}(E^{*}))$ .

Next, we focus on the problem of computing expectation values at the output of $\mathbf{CVBQP}[X^{3}]$ circuits for a low-degree observable $O$ (see Definition 4.7 and Theorem 4.7 of [8] for formal statements):

Theorem 5 (The computational complexity of bosonic expectation values, informal).

The problem of computing expectation values of low-degree observables for states prepared by applying Gaussian and cubic phase gates to the vacuum can be solved in $\mathbf{PSPACE}$ .

Proof sketch.

Let $W_{i}:=U_{i}\cdots U_{1}$ where the unitary gates $\set{U_{i}}_{1\leq i\leq n}$ selected from the Gaussian and cubic-phase gateset, are sequentially applied to a vacuum state. Suppose that $W_{i}X_{1}W_{i}^{\dagger}$ takes the form $O_{i}=\sum_{\mu,\nu}\alpha_{\mu,\nu}X^{\mu}P^{\nu}$ . Here we used the multi-index notations $\mu=(\mu_{1},\cdots,\mu_{n})\in\mathbb{Z}_{+}^{n}$ and $X^{\mu}=X_{1}^{\mu_{1}}\cdots X^{\mu_{n}}_{n}$ . Let $O_{i+1}=U_{i+1}O_{i}U_{i+1}^{\dagger}$ be the value after the application of the next gate. We can write $O_{i+1}=\sum_{\mu,\nu}\alpha_{\mu,\nu}(U_{i}XU_{i}^{\dagger})^{\mu}(U_{i}PU^{% \dagger}_{i})^{\nu}$ . If $U_{i+1}$ is a Gaussian gate, then the degree of $X$ and $P$ in $O_{i}$ will be the same as that of $O_{i+1}$ . However, if $U_{i+1}$ is a cubic phase gate, then the degree of $O_{i+1}$ is at most twice the degree of $O_{i}$ . That is because of the unitary evolution due to the cubic-phase gate $U_{i}PU_{i}^{\dagger}=P+c\cdot X^{2}$ , where $c$ is a constant. As a result, the degree of $O_{T}$ is at most $2^{T}$ . We note that coefficients involving the expansion of $O_{T}$ into a normal form may be doubly exponentially large. Hence, the naive brute-force approach runs in exponential space. To bring the complexity upper bound down to PSPACE, we give a polynomial-time parallel algorithm using exponentially many processors. Standard results in computational complexity imply a PSPACE upper bound (see, for instance, [43]). We further show that the upper bound remains true for the multimode case, using the fact that the only multimode operators we need to add are the so-called two-mode $S U M$ gates. $\hfill\blacktriangleleft$

We emphasize that the standard relationships outlined in Figure 1 indicate a PP upper bound on BQP. Proving a $\mathbf{EXPSPACE}$ upper bound on $\mathbf{CVBQP}[X^{3}]$ (outlined in Theorem 4) already utilizes nontrivial tools, and we do not know if a stronger upper bound such as PP would hold in this case based on current techniques. Indeed, from the previous proof sketch, a remarkable feature of the cubic phase gate becomes apparent: starting with a single position operator $X$ and applying $T$ cubic phase gates interleaved with suitable Gaussian gates (the Fourier gate $e^{i\frac{\pi}{4}(X^{2}+P^{2})}$ , mapping $X$ to $P$ and $P$ to $-X$ ), one can perform repeated squaring, i.e., obtain an observable of the form $\propto X^{2^{T}}+\cdots$ after $T$ rounds ¹¹1We thank Francesco Arzani for pointing out this fact.. This implies that doubly exponentially large numbers may naturally arise after polynomially many gates in the continuous-variable setting, in stark contrast with the discrete-variable setting.

The boundedness problem

Next, we aim to study the complexity of estimating the ground state energy of a bosonic Hamiltonian. Due to the infinite-dimensional setting, however, the spectrum may be unbounded. Hence, we first formulate and study the problem of deciding whether a bosonic Hamiltonian has a bounded ground state energy (see Definition 5.3 of [8] for a formal definition). Note that this problem is equivalent to deciding whether a bosonic Hamiltonian has a bounded spectrum, by checking boundedness of the ground energy for $H$ and $-H$ . The spectrum of any Hamiltonian that is a polynomial of odd degree (such as $X$ or $X^{3}$ or $X^{2}P+PX^{2}$ , etc.) is not bounded, as can be seen by computing the expectation value for an arbitrary coherent state (eigenstates of the operator $X+iP$ ), so we focus on polynomial Hamiltonians of even degree.

It turns out that the quadratic (Gaussian) case is solvable in polynomial time via a reduction to the problem of deciding whether a polynomial-size matrix, which may be computed efficiently from the coefficients of the Hamiltonian, is positive semi-definite (see Theorem 5.1 of [8]).

In the non-Gaussian case, we prove that the problem is significantly harder, even for degree-4 Hamiltonians (see Theorem 5.2 of [8] for a formal statement):

Theorem 6 (Complexity of the boundedness problem, informal).

The problem of deciding whether the spectrum of a bosonic Hamiltonian with degree $4$ is bounded is $\mathbf{co}$ - $\mathbf{NP}$ -hard .

Proof sketch.

The proof proceeds via reduction from matrix copositivity, which is the problem of deciding, given $M\in\mathbb{R}^{n\times n}$ , whether $\bra{x}M\ket{x}\geq 0$ for all $\ket{x}\in\mathbb{R}_{\geq 0}^{n}$ with non-negative entries. This problem is known to be co-NP-complete [36]. $\hfill\blacktriangleleft$

How hard is it to find a witness for the boundedness of the ground state energy? From the above, if we could find it in polynomial time in general, then we would at least collapse co-NP to P, which is highly unlikely. However, we may find a procedure to achieve this goal at least in some instances. This is what we do next, based on a sum-of-squares technique.

Consider a polynomial Hamiltonian in the form $H=\sum_{\mu,\nu\in\mathbb{Z}^{n}_{+}}\frac{1}{2}h_{\boldsymbol{\mu},% \boldsymbol{\nu}}\{X^{\boldsymbol{\mu}},P^{\boldsymbol{\nu}}\}$ , where we used multi-index notation (in Lemma 5.2 of [8] we show that any polynomial Hamiltonian can be brought to this form with real coefficients $h_{\boldsymbol{\mu},\boldsymbol{\nu}}\in\mathbb{R}$ ). The classical polynomial $p_{H}:\mathbb{R}^{2n}\rightarrow\mathbb{R}$ corresponding to $H$ is defined as

p_{H}(x_{1},\cdots,x_{n},p_{1},\cdots,p_{n})=\sum_{\boldsymbol{\mu},% \boldsymbol{\nu}\in\mathbb{Z}^{n}_{+}}h_{{\boldsymbol{\mu}},{\boldsymbol{\nu}}% }x^{\boldsymbol{\mu}}p^{\boldsymbol{\nu}}.

We prove the following (see Proposition 5.4 of [8] for a formal statement):

Proposition 7 (Checking boundedness for degree-4 Hamiltonians, informal).

Let $H$ be a bosonic Hamiltonian of degree $4$ . If $p_{H}$ is a sum-of-squares polynomial, then the spectrum of $H$ is bounded from below by an efficiently computable constant.

As a result, a sum-of-squares approach provides a sound algorithm for deciding boundedness of the ground state energy of polynomial Hamiltonians in the $d=4$ case, meaning that if we find a valid sum-of-squares decomposition for $p_{H}$ , then $H$ is bounded, but if $p_{H}$ is not a sum-of-squares that does not imply unboundedness for $H$ . Since the degree of $p_{H}$ is constant, one can look for a sum-of-squares decomposition by running a polynomial-time semi-definite program [38]. Note that if $p_{H}$ is not a sum of squares and we conjugate $H$ by a Gaussian unitary $U$ (which does not change the degree of $H$ ) and try again, we may find a different valid witness for boundedness.

The continuous-variable local Hamiltonian problem

We consider the case of general polynomial Hamiltonians and define the continuous-variable local Hamiltonian problem as follows (see Definition 5.2 of [8] for a formal definition):

Definition 8 (The continuous-variable local Hamiltonian problem, informal).

Let $\mathcal{S}\subset\mathcal{H}$ be a subset of continuous-variable quantum states. The continuous-variable local Hamiltonian problem $\mathsf{CVLH}^{d}_{\mathcal{S}}$ is the problem of estimating the lowest energy of a poynomial Hamiltonian $H$ of degree $d$ over the set $\mathcal{S}$ .

Note that the name local for this problem comes here from the fact that any polynomial Hamiltonian of degree $d$ is at most $d$ -local by definition.

For Gaussian Hamiltonians, our solution to the boundedness problem also provides a polynomial-time algorithm to estimate the ground state energy, thus placing the continuous-variable local Hamiltonian problem $\mathsf{CVLH}^{2}_{\mathcal{H}}$ for Gaussian Hamiltonians in $\mathbf{P}$ (see Theorem 5.1 of [8]).

For non-Gaussian Hamiltonians, in the case of states with bounded particle number, a result of [11] proves that the problem of estimating the ground state energy of the Bose–Hubbard model at finite (polynomial) number of bosons is QMA-complete. This Hamiltonian is of the form $H_{\mathrm{bh}}=t\cdot\sum_{i,j}A_{i,j}\,a_{i}^{\dagger}a_{j}+J\cdot\sum_{i}N_% {i}(N_{i}-1)$ , where $N=(X^{2}+P^{2}-1)/2$ and $a=(X+iP)/\sqrt{2}$ , and where $A_{i,j}$ is the $(i,j)$ -th entry of the adjacency matrix of an undirected graph. Note that the Hamiltonian $H_{\mathrm{bh}}$ conserves the number of particles, and hence, this operator may be thought of as a finite-dimensional Hamiltonian. In particular, denoting by $\mathcal{H}_{n}$ the set of states with less than $n$ particles, this shows that $\textsf{CVLH}^{d}_{\mathcal{H}_{n}}$ is QMA-hard already for $d=4$ (and thus $\textsf{CVLH}^{4}_{\mathcal{H}}$ as well).

In general, the complexity of the problem for non-Gaussian Hamiltonians depends significantly on the complexity of the set of states one optimizes. Following [9, 10], we consider the stellar rank of a quantum state as a parameter for specifying this set of states (see Section 2.3 of [8] for a brief review of the stellar rank). In short, to any continuous-variable quantum state $\ket{\psi}$ over $n$ modes, one can associate a holomorphic function $F^{\star}_{\psi}:\mathbb{C}^{n}\rightarrow\mathbb{C}$ . When this holomorphic function can be decomposed as a product of a polynomial $P$ and a Gaussian $G$ , i.e., $F^{\star}_{\psi}(z_{1},\cdots,z_{n})=P(z_{1},\cdots,z_{n})G(z_{1},\cdots,z_{n})$ , the degree of the polynomial $P$ defines the stellar rank $r$ of $\ket{\psi}$ . Otherwise, the stellar rank is infinite. When $r=0$ , we obtain the set of all Gaussian states, which can be produced by Gaussian gates applied to the vacuum state. The stellar rank can be finite (e.g., the stellar rank of $n$ indistinguishable particles is $n$ ). It can also be infinite, e.g., $\alpha_{1}\ket{\psi_{1}}+\alpha_{2}\ket{\psi_{2}}$ for Gaussian states $\ket{\psi_{1}},\ket{\psi_{2}}$ ( $\alpha_{1},\alpha_{2}\in\mathbb{C}$ ). We further constrain the energy of these states with respect to the number operator $N$ (see Definition 5.5 of [8] for a formal definition).

For zero stellar rank, we show (see Theorem 5.3 of [8] for a formal statement):

Theorem 9 (Lowest energy over Gaussian states, informal).

The problem of estimating the lowest energy of an $n$ -mode polynomial bosonic Hamiltonian of constant degree over the set ${\mathcal{S}^{\mathsf{exp}}_{0}}$ of states of stellar rank $0$ (Gaussian states) with energy (average particle number) at most $\mathsf{exp}(n)$ is NP-complete.

Proof sketch.

NP-hardness comes from a reduction from matrix non-copositivity (rather than matrix copositivity for Theorem 6). To place the problem in NP, note that the expectation value of a constant-degree polynomial Hamiltonian over a Gaussian state with energy at most $\mathsf{exp}(n)$ may be computed efficiently, so the NP witness is a description of the Gaussian state of lowest energy. $\hfill\blacktriangleleft$

For logarithmically and polynomially-bounded stellar ranks, we show (see Theorem 5.4 of [8] for a formal statement):

Theorem 10 (Lowest energy over bounded stellar rank, informal).

The problem of estimating the lowest energy of an $n$ -mode polynomial bosonic Hamiltonian of constant degree over the set ${\mathcal{S}^{\mathsf{poly}}_{\mathsf{poly}}}$ of states of stellar rank $r=\mathsf{poly}(n)$ with energy (average particle number) at most $\mathsf{poly}(n)$ is in $\mathbf{QMA}$ (this result holds up to Conjecture 2 of [8]).

Proof sketch.

To place the problem in QMA, we use the fact that any state of finite stellar rank is related by a Gaussian unitary $G$ to a state of bounded particle number $\ket{c}$ [10]. This allows us to efficiently rewrite the optimisation in terms of a (sparse) finite-dimensional Hamiltonian, once the Gaussian unitary corresponding to the lowest energy state is known. The QMA witness is then given by a classical description of that Gaussian unitary $G$ provided in the computational basis, together with a finite-dimensional state $\ket{c}$ that is the ground state of the finite-dimensional Hamiltonian, such that $G\ket{c}$ is the lowest energy state of the original Hamiltonian.

When the stellar rank is logarithmically bounded instead, $\ket{c}$ has an efficient classical description and the witness can be made fully classical. $\hfill\blacktriangleleft$

Finally, we consider the general case of unbounded stellar rank, with no restrictions on the set of states over which the optimisation takes place, and we show (see Theorem 5.6 of [8] for a formal statement):

Theorem 11 (The complexity of the continuous-variable local Hamiltonian problem, informal).

The problem of estimating the ground energy of a polynomial bosonic Hamiltonian of constant degree is undecidable. This problem is already undecidable for $d=8$ .

Proof sketch.

The proof of this result proceeds via a reduction from Hilbert’s tenth problem (a Nüllstellensatz problem over the integers) due to [30], combined with the fact that there exist explicit undecidable polynomial equations over non-negative integers of degree $4$ and a constant number of unknowns [25]. $\hfill\blacktriangleleft$

Continous-Variable Quantum Merlin Arthur games

Finally, we introduce a continuous-variable analog of QMA (see Definition 5.1 of [8] for a formal definition):

Definition 12 (Continuous-variable quantum Merlin-Arthur, informal).

$\mathbf{CVQMA}$ is the class of decision problems, for which a solution encoded in a continuous-variable quantum state can be verified efficiently by a $\mathbf{CVBQP}$ machine.

Motivated by the relationship between the local Hamiltonian problem and QMA in the discrete-variable case based on Kitaev’s history state construction [28], we aim to connect the class CVQMA to the continuous-variable local Hamiltonian problem. We give the basis for a continuous-variable history state construction providing such a connection (see Section 5.3 of [8]), and identify the challenges associated with such a construction.

4 Outlook

The study of continuous-variable quantum computations may have various interactions with the foundations of computational complexity, computability, and quantum mechanics, which we discuss in the next section. After that, in Section 4.1.1, we list several open questions.

4.1 Discussion

Energy of continuous-variable computations

One of the key insights of this work is that by alternating Gaussian and cubic phase gates, the average energy of the system – even for a single mode – can grow to be doubly exponential in the number of cubic phase gates used in the circuit. This observation suggests that strong simulation (calculating each amplitude individually) of continuous-variable quantum systems could be significantly more challenging than for discrete-variable ones, potentially being hard for complexity classes like PSPACE or even EXPSPACE. This suggests that on top of time and space complexity, energy plays a significant role in the computational power of bosonic systems.

In practical physical experiments, the energy must be supplied by the experimentalist, requiring a physical definition of computational cost that accounts for time, space, and energy. Specifically, if one is willing to expend up to $E^{*}$ units of energy, our results show that a single mode can be simulated within $\mathbf{SPACE}(O(\log E^{*}))$ . This highlights a trade-off between time, space, and energy, which we believe deserves a thorough examination. Understanding time, energy, and space tradeoffs for multimode systems equipped with multi-mode non-Gaussian gates is an interesting open question.

In our definition of CVBQP, we enforce the “promise” that the quantum state in the beginning and the end has limited energy, as measured by the average particle number, but it may take any value in between. A natural question to ask is: is the power of this model the same as the one where we impose restrictions on average energy at any point during the computation? See Figure 3 for a visual depiction. We can ask a similar question about classical continuous (time and/or space) models of computation where we are promised that the system’s state is effectively discrete (e.g., a two-level system) at the beginning and the end. Still, the system can utilize its continuous degrees of freedom in between to an arbitrary precision. Is the power of this hypothetical model the same as digital computation? We first note that without such promise in the beginning, it is not clear how one can program such a system, and without the promise on the energy in the end, no physically viable device would be able to measure the quantum state. Even if we assume the existence of such a hypothetical device, it is not difficult to approximately predict the output of such a hypothetical device (we output random numbers because, at high energy, no concentration of measure is expected).

We may face the objection that assuming no mechanism to bound energy (e.g., dissipation), this promise is unreasonable because we cannot verify it. We first note that it is not difficult to come up with trivial examples that satisfy such a promise. Consider the unitary $UU^{\dagger}$ where $U\ket{0}$ has high energy. Clearly, $UU^{\dagger}$ has bounded energy at the beginning and the end and very high energy in between. Second, promises that are possibly difficult to verify are common in quantum complexity theory, e.g., promise on the gap of a Hamiltonian or promise that a BQP computation either accepts with probability $\geq 2/3$ or $\leq 1/3$ . We have a similar scenario for the energy promise.

As a thought experiment, assume we have a fragile quantum processing device that breaks if it holds more than $N_{0}$ particles. Now, we design a quantum experiment such that the system (on average) has $\ll N_{0}$ particles at the beginning and the end but may (on average) have $\gg N_{0}$ particles in a way that many of the computational paths involve $\ll N_{0}$ particles and many involve $\gg N_{0}$ . In the end, we measure the device’s output and measure $\ll N_{0}$ particles. Do we measure the device to be broken or unbroken? This is similar to the Schrödinger’s cat (or Wigner’s) paradox. In the mentioned thought experiment, the device played the cat’s role. In other words, if the device’s condition (i.e., broken or unbroken) is determined only at the time of measurement, then CVBQP with mild (or no) energy restriction in between might be a plausible model. Otherwise, if broken paths are forbidden, then CVBQP with energy bound on the entire computation path is a more reasonable model from a physical standpoint. We note that in an actual experiment, energy is pumped from an outside source, and the closedness of the experiment is only an approximation.

Connections with the extended Church–Turing thesis

Our result leaves open the possibility that CVBQP $\nsubseteq$ BQP; due to doubly exponential growth of energy in between computations, such a separation is plausible. What would that imply about the nature of computation in the physical world? If CVBQP is a plausible model for computation in the physical world, then CVBQP $\nsubseteq$ BQP seems to imply a contradiction to the extended Church Turing Thesis. But how realistic is CVBQP as a model of computation? In particular, how should one determine the energy cap in between the computations? Consider scattering amplitude for quantum field theories, where the specific amplitude sets the number of particles at the beginning and the end, and still, fluctuations in the vacuum may lead to many particle creations, and annihilations can occur in between. Are bounds on the fluctuations of the vacuum (see, for instance, [18]) such that the computational complexity of scattering amplitudes do not exceed that of BQP? Are there computational phase transitions depending on $\gamma_{1}$ and $\gamma_{2}$ ?

What can we say about noisy systems? Suppose we define $\mathbf{DissCVBQP}(\gamma_{1},\gamma_{2})$ as a dissipated model where we have a mechanism that pumps bosons into the system with rate $\gamma_{1}$ and another mechanism that bosons are emitted to the environment with rate $\gamma_{2}$ . How does the power computational complexity of $\mathbf{DissCVBQP}(\gamma_{1},\gamma_{2})$ depend on $\gamma_{1}$ and $\gamma_{2}$ ? Can we show for physically relevant parameters the power of this model is BQP-complete?

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 the end of the computation, but may have arbitrary high energy in between. The blue curve depicts a model where we impose energy restrictions at any point during the computation.

Logarithmic number of cubic phase gates

Standard results in the discrete-variable model of quantum computing (e.g., [7]) imply that starting with a computational basis, discrete-variable quantum circuits with a logarithmic number of $T$ gates and polynomially many Clifford gates can be efficiently strongly simulated on classical computers. Can we prove a similar result for continuous-variable systems, i.e., can we show that starting from the vacuum state, a polynomial-size quantum circuit with a logarithmic number of cubic phase gates can be simulated on a classical computer? Based on our results, the best upper bound we could prove for this problem was PSPACE. We furthermore note that, due to repeated squaring of energy, the “effective dimension” that the quantum system explores is exponential even if the circuit has, at most, a logarithmic number of cubic phase gates. Based on this intuition, we conjecture that (noiseless) continuous variable quantum circuits with a logarithmic number of cubic phase gates cannot be simulated efficiently on a classical computer.

Noiseless model as a foundation to study noisy systems

Even though a realistic model for the experimental implementation of bosonic computations is a dissipative (or noisy) model, noise models are various, and by understanding the computability limits of the noiseless system, one can gain a reliable foundation to study computational complexity after imposing different restrictions on the model. A similar approach has been pursued for computational complexity in the discrete-variable domain where we define BQP as an idealized noiseless quantum computing model and pin down its computational complexity. We then use this foundation to study the model’s different variants and restrictions. For instance, we know that computing the amplitudes of a noiseless quantum circuit is $\#\textbf{P}$ -complete. Obviously, this result is not directly relevant to understanding the cost of simulating practical problems. However, this observation has been utilized via tools in computational complexity to lay the foundations for demonstrating quantum speedup in noisy or restricted models such as Boson Sampling [1]. Moreover, we describe a way to encode BQP computations in bosonic subspaces (see Theorem 4.1 of [8]) relying on the Solovay–Kitaev theorem [13], but this result does not appear to be robust to noise, because the noise may induce leakage to unbounded regions of state space where the theorem no longer holds. This motivates further study of robust quantum computations in continuous-variable systems.

Truncating CV systems using the stellar rank

Standard approaches to describe continuous-variable quantum systems using a finite number of variables include (i) truncating their infinite-dimensional Hilbert space, which amounts to restricting to bounded particle-number supports, or (ii) keeping track only of the covariance matrix and displacement vector of the state. These have immediate shortcomings: (i) is not stable under Gaussian evolutions, which may be thought of as computationally easy [4], and truncating a Gaussian state usually makes it non-Gaussian; (ii) only faithfully describes Gaussian computations.

Our results suggest that the stellar rank may be a meaningful approach for describing continuous-variable quantum systems, in particular for studying ground state problems for continuous-variable systems [41]. Informally, the stellar rank combines both approaches (i) and (ii), as states of finite stellar rank can always be expressed as (mixture of) Gaussian unitary operators acting on (core) states of finite support.

4.1.1 Open questions

Since the aim of the present work is to lay foundations for a theory of bosonic quantum complexity, it naturally leads to many open questions, some of which we list in the following:

1.

The most immediate open question from this work is whether we can bring the EXPSPACE upper bound on CVBQP to smaller complexity classes such as PSPACE or even PP. What about lower bounds? Due to the doubly exponentially large dimensionality of the effective Hilbert space, it is natural to conjecture that strong simulation of CVBQP is hard for a complexity class such as PSPACE (or even EXPSPACE) which is believed to be strictly larger than PP. Such a result would be important evidence that CVBQP may surpass the power of BQP.
2.

A related question is: what energy bound on CVBQP makes it equal to BQP? In an actual physical computation (such as a bosonic system subject to dissipation), one would expect that the energy stays polynomially bounded. Is it the case that $\textbf{CVBQP}=\textbf{BQP}$ under the promise that the energy stays polynomially bounded throughout the computation? Can we prove that a variant of CVBQP subject to dissipation is equivalent to BQP?
3.

It is usually assumed in the continuous-variable quantum information literature that a single non-Gaussian gate together with all Gaussian ones is sufficient to perform “universal” quantum computations. However, this notion of universality is somewhat restricted, as it relates to the ability to approximate evolutions generated by polynomial Hamiltonians [33]. In particular, is the cubic phase gate (for instance) and Gaussian gate set universal, in the sense that any state can be reached to arbitrary precision from the vacuum state using unitary gates from this set? See [45] for a formal statement of this open problem, and [35] for an example of a continuous-variable gate set satisfying this property.
4.

In the discrete-variable setting, the computational power of quantum circuits is essentially independent of the choice of universal gate set. Is it also the case in the continuous-variable setting? If so, can a continuous-variable Solovay–Kitaev theorem [31, 13] be derived for these gates? See [5] for such a result in the case of Gaussian gates. This also relates to the existence of fast compilation algorithms for bosonic gates [40, 26, 27].
5.

What is the precise complexity of the Hamiltonian spectrum boundedness problem? We prove co-NP-hardness and conjecture hardness for co-QMA. Can we show co-QMA is an upper bound? We describe a sound algorithm for verifying boundedness in the $d=4$ case. Do similar results exist for $d>4$ ?
6.

After possible conjugations with arbitrary unitary matrices, can we write a Hamiltonian as a sum-of-squares of other Hamiltonians (c.f. [23])? We have obtained partial results in this direction for degree-4 polynomial bosonic Hamiltonians.
7.

We can define families of Hamiltonians with a ground state of a given exact or approximate stellar rank $r$ . Is there a procedure to decide the opposite? I.e., given the description of the Hamiltonian and an approximation parameter, decide whether it has an approximate ground state of stellar rank $<r$ .
8.

Our results indicate if we minimize the energy of a continuous-variable Hamiltonian over an ensemble with polynomially bounded energy (particle number) and stellar rank $r$ , then for $r=\mathsf{poly}(n)$ it is contained in QMA. Can we show that these containments are tight? What about $r=\mathsf{exp(n)}$ and higher particle numbers? Proving such results would involve continuous-variable versions of Kitaev’s history state [29, 28] in the continuous-variable setting. This construction would involve nontrivial ideas, which we leave for future work.
9.

What is the complexity of the continuous-variable local Hamiltonian problem for other natural families of continuous-variable quantum states? For instance, the family of quantum states that are superpositions of $\mathsf{poly}(n)$ Gaussians? This class of states has recently been considered in the context of classical simulation of bosonic computations, leading to the introduction of the continuous-variable notion of Gaussian rank [15, 22], akin to the discrete-variable notion of stabilizer rank [7]. Note that the stellar rank for such states is typically infinite.
10.

What is the complexity of deciding whether the spectrum of a polynomial bosonic Hamiltonian has a continuous part or if is it discrete? When it is discrete, is CVLH RE-complete?

Bosonic quantum computations also provide a natural setting for generalizing classical complexity theory over the reals (e.g., in the Blum–Shub–Smale model [6]) to the quantum case, given that bosonic Hamiltonians may have a continuous spectrum. We expect that most of our results should have counterparts over the reals.

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. doi:10.1145/1993636.1993682.
[2] Scott Aaronson and Daniel Gottesman. Improved simulation of stabilizer circuits. Physical Review A, 70(5):052328, 2004. doi:10.1103/PhysRevA.70.052328.
[3] Alice Barthe, M Cerezo, Andrew T Sornborger, Martin Larocca, and Diego García-Martín. Gate-based quantum simulation of Gaussian bosonic circuits on exponentially many modes. arXiv preprint, 2024. doi:10.48550/arXiv.2407.06290.
[4] 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. doi:10.1103/PhysRevLett.88.097904.
[5] 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. doi:10.1103/PhysRevLett.126.190504.
[6] Lenore Blum, Felipe Cucker, Mike Shub, and Steve Smale. Complexity and real computation. Springer Science & Business Media, 1998. doi:10.1007/978-1-4612-0701-6.
[7] Sergey Bravyi, Graeme Smith, and John A Smolin. Trading classical and quantum computational resources. Physical Review X, 6(2):021043, 2016. doi:10.1103/PhysRevX.6.021043.
[8] Ulysse Chabaud, Michael Joseph, Saeed Mehraban, and Arsalan Motamedi. Bosonic quantum computational complexity. arXiv preprint, 2024. doi:10.48550/arXiv.2410.04274.
[9] Ulysse Chabaud, Damian Markham, and Frédéric Grosshans. Stellar representation of non-Gaussian quantum states. Physical Review Letters, 124(6):063605, 2020. doi:10.1103/PhysRevLett.124.063605.
[10] Ulysse Chabaud and Saeed Mehraban. Holomorphic representation of quantum computations. Quantum, 6:831, 2022. doi:10.22331/Q-2022-10-06-831.
[11] 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. doi:10.1007/978-3-662-43948-7_26.
[12] 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. doi:10.1016/0020-0190(90)90150-V.
[13] Christopher M Dawson and Michael A Nielsen. The Solovay-Kitaev algorithm. arXiv preprint quant-ph/0505030, 2005. doi:10.48550/arXiv.quant-ph/0505030.
[14] Danial Dervovic, Mark Herbster, Peter Mountney, Simone Severini, Naïri Usher, and Leonard Wossnig. Quantum linear systems algorithms: a primer. arXiv preprint, 2018. doi:10.48550/arXiv.1802.08227.
[15] Beatriz Dias and Robert Koenig. Classical simulation of non-Gaussian bosonic circuits. arXiv preprint, 2024. doi:10.48550/arXiv.2403.1905.
[16] 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. doi:10.1145/3406325.3451051.
[17] Alessandro Ferraro, Stefano Olivares, and Matteo GA Paris. Gaussian states in continuous variable quantum information. arXiv preprint, 2005. doi:10.48550/arXiv.quant-ph/0503237.
[18] LH Ford. Negative energy densities in quantum field theory. International Journal of Modern Physics A, 25(11):2355–2363, 2010. doi:10.1142/S0217751X10049633.
[19] Daniel Gottesman. The Heisenberg representation of quantum computers. arXiv preprint, 1998. doi:10.48550/arXiv.quant-ph/9807006.
[20] Daniel Gottesman, Alexei Kitaev, and John Preskill. Encoding a qubit in an oscillator. Physical Review A, 64(1):012310, 2001. doi:10.1103/PhysRevA.64.012310.
[21] Arne L Grimsmo and Shruti Puri. Quantum error correction with the Gottesman-Kitaev-Preskill code. PRX Quantum, 2(2):020101, 2021. doi:10.1103/PRXQuantum.2.020101.
[22] Oliver Hahn, Ryuji Takagi, Giulia Ferrini, and Hayata Yamasaki. Classical simulation and quantum resource theory of non-Gaussian optics. arXiv preprint, 2024. doi:10.48550/arXiv.2404.07115.
[23] Matthew B Hastings. Perturbation theory and the sum of squares. arXiv preprint arXiv:2205.12325, 2022. doi:10.48550/arXiv.2205.12325.
[24] Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen. MIP*= RE. Communications of the ACM, 64(11):131–138, 2021. doi:10.48550/arXiv.2001.04383.
[25] James P Jones. Three universal representations of recursively enumerable sets. The Journal of Symbolic Logic, 43(3):549–571, 1978. doi:10.2307/2272832.
[26] Timjan Kalajdzievski and Juan Miguel Arrazola. Exact gate decompositions for photonic quantum computing. Physical Review A, 99(2):022341, 2019. doi:10.1103/PhysRevA.99.022341.
[27] Timjan Kalajdzievski and Nicolás Quesada. Exact and approximate continuous-variable gate decompositions. Quantum, 5:394, 2021. doi:10.22331/Q-2021-02-08-394.
[28] Julia Kempe, Alexei Kitaev, and Oded Regev. The complexity of the local hamiltonian problem. FSTTCS 2004. Lecture Notes in Computer Science, vol 3328, 2004. doi:10.1007/978-3-540-30538-5_31.
[29] Julia Kempe and Oded Regev. 3-local hamiltonian is QMA-complete. arXiv preprint, 2003. doi:10.48550/arXiv.quant-ph/0302079.
[30] Tien D Kieu. Quantum algorithm for Hilbert’s tenth problem. International Journal of Theoretical Physics, 42:1461–1478, 2003. doi:10.1023/A:1025780028846.
[31] A Yu Kitaev. Quantum computations: algorithms and error correction. Russian Mathematical Surveys, 52(6):1191, 1997. doi:10.1070/RM1997v052n06ABEH002155.
[32] Emanuel Knill, Raymond Laflamme, and Gerald J Milburn. A scheme for efficient quantum computation with linear optics. Nature, 409(6816):46–52, 2001. doi:10.1038/35051009.
[33] Seth Lloyd and Samuel L Braunstein. Quantum computation over continuous variables. Physical Review Letters, 82(8):1784, 1999. doi:10.1103/PhysRevLett.82.1784.
[34] 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. doi:10.1038/s41586-022-04725-x.
[35] 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. doi:10.1088/1751-8113/44/13/135302.
[36] Katta G. Murty and Santosh N. Kabadi. Some NP-complete problems in quadratic and nonlinear programming. Mathematical Programming, 39(2):117–129, 1987. doi:10.1007/BF02592948.
[37] Michael A Nielsen and Isaac L Chuang. Quantum computation and quantum information. Phys. Today, 54(2):60, 2001. doi:10.1017/CBO9780511976667.
[38] Pablo A Parrilo. Semidefinite programming relaxations for semialgebraic problems. Mathematical programming, 96:293–320, 2003. doi:10.1007/S10107-003-0387-5.
[39] 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. arXiv preprint, 2023. doi:10.48550/arXiv.2307.06580.
[40] Seckin Sefi and Peter Van Loock. How to decompose arbitrary continuous-variable quantum operations. Physical review letters, 107(17):170501, 2011. doi:10.1103/PhysRevLett.107.170501.
[41] Paolo Stornati, Antonio Acin, Ulysse Chabaud, Alexandre Dauphin, Valentina Parigi, and Federico Centrone. Variational quantum simulation using non-Gaussian continuous-variable systems. arXiv preprint, 2023. doi:10.48550/arXiv.2310.15919.
[42] 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. doi:10.1145/2488608.2488720.
[43] 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. doi:10.1016/0304-3975(92)90362-J.
[44] John Watrous. Quantum computational complexity. arXiv preprint, 2008. doi:10.48550/arXiv.0804.3401.
[45] 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. doi:10.1103/PhysRevA.73.012719.
[46] 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. doi:10.1126/science.abe8770.

[bib.bib1] [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. doi:10.1145/1993636.1993682.

[bib.bib2] [2] Scott Aaronson and Daniel Gottesman. Improved simulation of stabilizer circuits. Physical Review A, 70(5):052328, 2004. doi:10.1103/PhysRevA.70.052328.

[bib.bib3] [3] Alice Barthe, M Cerezo, Andrew T Sornborger, Martin Larocca, and Diego García-Martín. Gate-based quantum simulation of Gaussian bosonic circuits on exponentially many modes. arXiv preprint, 2024. doi:10.48550/arXiv.2407.06290.

[bib.bib4] [4] 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. doi:10.1103/PhysRevLett.88.097904.

[bib.bib5] [5] 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. doi:10.1103/PhysRevLett.126.190504.

[bib.bib6] [6] Lenore Blum, Felipe Cucker, Mike Shub, and Steve Smale. Complexity and real computation. Springer Science & Business Media, 1998. doi:10.1007/978-1-4612-0701-6.

[bib.bib7] [7] Sergey Bravyi, Graeme Smith, and John A Smolin. Trading classical and quantum computational resources. Physical Review X, 6(2):021043, 2016. doi:10.1103/PhysRevX.6.021043.

[bib.bib8] [8] Ulysse Chabaud, Michael Joseph, Saeed Mehraban, and Arsalan Motamedi. Bosonic quantum computational complexity. arXiv preprint, 2024. doi:10.48550/arXiv.2410.04274.

[bib.bib9] [9] Ulysse Chabaud, Damian Markham, and Frédéric Grosshans. Stellar representation of non-Gaussian quantum states. Physical Review Letters, 124(6):063605, 2020. doi:10.1103/PhysRevLett.124.063605.

[bib.bib10] [10] Ulysse Chabaud and Saeed Mehraban. Holomorphic representation of quantum computations. Quantum, 6:831, 2022. doi:10.22331/Q-2022-10-06-831.

[bib.bib11] [11] 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. doi:10.1007/978-3-662-43948-7_26.

[bib.bib12] [12] 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. doi:10.1016/0020-0190(90)90150-V.

[bib.bib13] [13] Christopher M Dawson and Michael A Nielsen. The Solovay-Kitaev algorithm. arXiv preprint quant-ph/0505030, 2005. doi:10.48550/arXiv.quant-ph/0505030.

[bib.bib14] [14] Danial Dervovic, Mark Herbster, Peter Mountney, Simone Severini, Naïri Usher, and Leonard Wossnig. Quantum linear systems algorithms: a primer. arXiv preprint, 2018. doi:10.48550/arXiv.1802.08227.

[bib.bib15] [15] Beatriz Dias and Robert Koenig. Classical simulation of non-Gaussian bosonic circuits. arXiv preprint, 2024. doi:10.48550/arXiv.2403.1905.

[bib.bib16] [16] 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. doi:10.1145/3406325.3451051.

[bib.bib17] [17] Alessandro Ferraro, Stefano Olivares, and Matteo GA Paris. Gaussian states in continuous variable quantum information. arXiv preprint, 2005. doi:10.48550/arXiv.quant-ph/0503237.

[bib.bib18] [18] LH Ford. Negative energy densities in quantum field theory. International Journal of Modern Physics A, 25(11):2355–2363, 2010. doi:10.1142/S0217751X10049633.

[bib.bib19] [19] Daniel Gottesman. The Heisenberg representation of quantum computers. arXiv preprint, 1998. doi:10.48550/arXiv.quant-ph/9807006.

[bib.bib20] [20] Daniel Gottesman, Alexei Kitaev, and John Preskill. Encoding a qubit in an oscillator. Physical Review A, 64(1):012310, 2001. doi:10.1103/PhysRevA.64.012310.

[bib.bib21] [21] Arne L Grimsmo and Shruti Puri. Quantum error correction with the Gottesman-Kitaev-Preskill code. PRX Quantum, 2(2):020101, 2021. doi:10.1103/PRXQuantum.2.020101.

[bib.bib22] [22] Oliver Hahn, Ryuji Takagi, Giulia Ferrini, and Hayata Yamasaki. Classical simulation and quantum resource theory of non-Gaussian optics. arXiv preprint, 2024. doi:10.48550/arXiv.2404.07115.

[bib.bib23] [23] Matthew B Hastings. Perturbation theory and the sum of squares. arXiv preprint arXiv:2205.12325, 2022. doi:10.48550/arXiv.2205.12325.

[bib.bib24] [24] Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen. MIP*= RE. Communications of the ACM, 64(11):131–138, 2021. doi:10.48550/arXiv.2001.04383.

[bib.bib25] [25] James P Jones. Three universal representations of recursively enumerable sets. The Journal of Symbolic Logic, 43(3):549–571, 1978. doi:10.2307/2272832.

[bib.bib26] [26] Timjan Kalajdzievski and Juan Miguel Arrazola. Exact gate decompositions for photonic quantum computing. Physical Review A, 99(2):022341, 2019. doi:10.1103/PhysRevA.99.022341.

[bib.bib27] [27] Timjan Kalajdzievski and Nicolás Quesada. Exact and approximate continuous-variable gate decompositions. Quantum, 5:394, 2021. doi:10.22331/Q-2021-02-08-394.

[bib.bib28] [28] Julia Kempe, Alexei Kitaev, and Oded Regev. The complexity of the local hamiltonian problem. FSTTCS 2004. Lecture Notes in Computer Science, vol 3328, 2004. doi:10.1007/978-3-540-30538-5_31.

[bib.bib29] [29] Julia Kempe and Oded Regev. 3-local hamiltonian is QMA-complete. arXiv preprint, 2003. doi:10.48550/arXiv.quant-ph/0302079.

[bib.bib30] [30] Tien D Kieu. Quantum algorithm for Hilbert’s tenth problem. International Journal of Theoretical Physics, 42:1461–1478, 2003. doi:10.1023/A:1025780028846.

[bib.bib31] [31] A Yu Kitaev. Quantum computations: algorithms and error correction. Russian Mathematical Surveys, 52(6):1191, 1997. doi:10.1070/RM1997v052n06ABEH002155.

[bib.bib32] [32] Emanuel Knill, Raymond Laflamme, and Gerald J Milburn. A scheme for efficient quantum computation with linear optics. Nature, 409(6816):46–52, 2001. doi:10.1038/35051009.

[bib.bib33] [33] Seth Lloyd and Samuel L Braunstein. Quantum computation over continuous variables. Physical Review Letters, 82(8):1784, 1999. doi:10.1103/PhysRevLett.82.1784.

[bib.bib34] [34] 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. doi:10.1038/s41586-022-04725-x.

[bib.bib35] [35] 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. doi:10.1088/1751-8113/44/13/135302.

[bib.bib36] [36] Katta G. Murty and Santosh N. Kabadi. Some NP-complete problems in quadratic and nonlinear programming. Mathematical Programming, 39(2):117–129, 1987. doi:10.1007/BF02592948.

[bib.bib37] [37] Michael A Nielsen and Isaac L Chuang. Quantum computation and quantum information. Phys. Today, 54(2):60, 2001. doi:10.1017/CBO9780511976667.

[bib.bib38] [38] Pablo A Parrilo. Semidefinite programming relaxations for semialgebraic problems. Mathematical programming, 96:293–320, 2003. doi:10.1007/S10107-003-0387-5.

[bib.bib39] [39] 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. arXiv preprint, 2023. doi:10.48550/arXiv.2307.06580.

[bib.bib40] [40] Seckin Sefi and Peter Van Loock. How to decompose arbitrary continuous-variable quantum operations. Physical review letters, 107(17):170501, 2011. doi:10.1103/PhysRevLett.107.170501.

[bib.bib41] [41] Paolo Stornati, Antonio Acin, Ulysse Chabaud, Alexandre Dauphin, Valentina Parigi, and Federico Centrone. Variational quantum simulation using non-Gaussian continuous-variable systems. arXiv preprint, 2023. doi:10.48550/arXiv.2310.15919.

[bib.bib42] [42] 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. doi:10.1145/2488608.2488720.

[bib.bib43] [43] 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. doi:10.1016/0304-3975(92)90362-J.

[bib.bib44] [44] John Watrous. Quantum computational complexity. arXiv preprint, 2008. doi:10.48550/arXiv.0804.3401.

[bib.bib45] [45] 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. doi:10.1103/PhysRevA.73.012719.

[bib.bib46] [46] 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. doi:10.1126/science.abe8770.

Bosonic Quantum Computational Complexity

Abstract

Keywords and phrases:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Acknowledgements:

Funding:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

2 Main models and results

2.1 Structure and summary of results

3 Details of the contributions

Gaussian computations

Definition 1 (Gaussian dynamical computations, informal).

Theorem 2 (The computational power of Gaussian dynamics, informal).

Bounded-error continuous-variable quantum polynomial time (CVBQP)

Definition 3 (𝐂𝐕𝐁𝐐𝐏⁢[X3], informal).

Theorem 4 (Upper bound on the computational power of Gaussian and cubic phase gates, informal).

Theorem 5 (The computational complexity of bosonic expectation values, informal).

Proof sketch.

The boundedness problem

Theorem 6 (Complexity of the boundedness problem, informal).

Proof sketch.

Proposition 7 (Checking boundedness for degree-4 Hamiltonians, informal).

The continuous-variable local Hamiltonian problem

Definition 8 (The continuous-variable local Hamiltonian problem, informal).

Theorem 9 (Lowest energy over Gaussian states, informal).

Proof sketch.

Theorem 10 (Lowest energy over bounded stellar rank, informal).

Proof sketch.

Theorem 11 (The complexity of the continuous-variable local Hamiltonian problem, informal).

Proof sketch.

Continous-Variable Quantum Merlin Arthur games

Definition 12 (Continuous-variable quantum Merlin-Arthur, informal).

4 Outlook

4.1 Discussion

Energy of continuous-variable computations

Connections with the extended Church–Turing thesis

Logarithmic number of cubic phase gates

Noiseless model as a foundation to study noisy systems

Truncating CV systems using the stellar rank

4.1.1 Open questions

References

Definition 3 ( $\mathbf{CVBQP}{[}X^{3}{]}$ , informal).