More Like this

1. Bosonic Quantum Computational Complexity

   https://doi.org/10.4230/lipics.itcs.2025.33  

   Chabaud, Ulysse; Joseph, Michael; Mehraban, Saeed; Motamedi, Arsalan (January 2025, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Meka, Raghu (Ed.)

   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. 

   more » « less
2. Leibniz International Proceedings in Informatics (LIPIcs):15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

   https://doi.org/10.4230/LIPIcs.ITCS.2024.72  

   Li, Xingjian; Liu, Qipeng; Pelecanos, Angelos; Yamakawa, Takashi (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Guruswami, Venkatesan (Ed.)

   It is a long-standing open question to construct a classical oracle relative to which BQP/qpoly ≠ BQP/poly or QMA ≠ QCMA. In this paper, we construct classically-accessible classical oracles relative to which BQP/qpoly ≠ BQP/poly and QMA ≠ QCMA. Here, classically-accessible classical oracles are oracles that can be accessed only classically even for quantum algorithms. Based on a similar technique, we also show an alternative proof for the separation of QMA and QCMA relative to a distributional quantumly-accessible classical oracle, which was recently shown by Natarajan and Nirkhe. 

   more » « less
3. Unitary Property Testing Lower Bounds by Polynomials

   https://doi.org/10.4230/LIPIcs.ITCS.2023.96  

   She, Adrian; Yuen, Henry (January 2023, Leibniz International Proceedings in Informatics (LIPIcs):14th Innovations in Theoretical Computer Science Conference (ITCS 2023))

   Tauman Kalai, Yael (Ed.)

   We study unitary property testing, where a quantum algorithm is given query access to a black-box unitary and has to decide whether it satisfies some property. In addition to containing the standard quantum query complexity model (where the unitary encodes a binary string) as a special case, this model contains "inherently quantum"; problems that have no classical analogue. Characterizing the query complexity of these problems requires new algorithmic techniques and lower bound methods. Our main contribution is a generalized polynomial method for unitary property testing problems. By leveraging connections with invariant theory, we apply this method to obtain lower bounds on problems such as determining recurrence times of unitaries, approximating the dimension of a marked subspace, and approximating the entanglement entropy of a marked state. We also present a unitary property testing-based approach towards an oracle separation between QMA and QMA(2), a long standing question in quantum complexity theory. 

   more » « less
4. QMA Lower Bounds for Batch Verification via Approximate Degree

   https://doi.org/10.4230/lipics.approx/random.2026.69  

   Bun, Mark; Juvekar, Mandar; King, Samuel (January 2026, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Singh, Mohit; Gur, Tom (Ed.)

   Abstract: We study batch verification in QMA query and communication complexity, where the goal is to understand how the resources needed to verify m copies of a Boolean function f depend on m. We give a general technique for proving lower bounds on the witness-query tradeoff needed to batch verify a function f in terms of its approximate degree. Applying this technique to an explicit family of DNF formulas f, we show that attempting to save even a constant factor on the witness length of the baseline approach to batch verifying f necessitates a large polynomial increase in the query cost. We also obtain new lower bounds on the QMA query complexity of read-once CNF formulas and on the surjectivity and k-element distinctness functions. Our lower bounds also lift to give communication analogs of these results. 

   more » « less
5. Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits

   https://doi.org/10.1145/3313276.3316404  

   Watts, Adam Bene; Kothari, Robin; Schaeffer, Luke; Tal, Avishay (June 2019, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing)

   Recently, Bravyi, Gosset, and Konig (Science, 2018) exhibited a search problem called the 2D Hidden Linear Function (2D HLF) problem that can be solved exactly by a constant-depth quantum circuit using bounded fan-in gates (or QNC^0 circuits), but cannot be solved by any constant-depth classical circuit using bounded fan-in AND, OR, and NOT gates (or NC^0 circuits). In other words, they exhibited a search problem in QNC^0 that is not in NC^0. We strengthen their result by proving that the 2D HLF problem is not contained in AC^0, the class of classical, polynomial-size, constant-depth circuits over the gate set of unbounded fan-in AND and OR gates, and NOT gates. We also supplement this worst-case lower bound with an average-case result: There exists a simple distribution under which any AC^0 circuit (even of nearly exponential size) has exponentially small correlation with the 2D HLF problem. Our results are shown by constructing a new problem in QNC^0, which we call the Parity Halving Problem, which is easier to work with. We prove our AC^0 lower bounds for this problem, and then show that it reduces to the 2D HLF problem. 

   more » « less