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. Fréchet Distance for Uncertain Curves

   https://doi.org/10.1145/3597640  

   Buchin, Kevin; Fan, Chenglin; Löffler, Maarten; Popov, Aleksandr; Raichel, Benjamin; Roeloffzen, Marcel (July 2023, ACM Transactions on Algorithms)

   In this article, we study a wide range of variants for computing the (discrete and continuous) Fréchet distance between uncertain curves. An uncertain curve is a sequence of uncertainty regions, where each region is a disk, a line segment, or a set of points. A realisation of a curve is a polyline connecting one point from each region. Given an uncertain curve and a second (certain or uncertain) curve, we seek to compute the lower and upper bound Fréchet distance, which are the minimum and maximum Fréchet distance for any realisations of the curves. We prove that both problems are NP-hard for the Fréchet distance in several uncertainty models, and that the upper bound problem remains hard for the discrete Fréchet distance. In contrast, the lower bound (discrete [ 5 ] and continuous) Fréchet distance can be computed in polynomial time in some models. Furthermore, we show that computing the expected (discrete and continuous) Fréchet distance is #P-hard in some models. On the positive side, we present an FPTAS in constant dimension for the lower bound problem when Δ/δ is polynomially bounded, where δ is the Fréchet distance and Δ bounds the diameter of the regions. We also show a near-linear-time 3-approximation for the decision problem on roughly δ-separated convex regions. Finally, we study the setting with Sakoe–Chiba time bands, where we restrict the alignment between the curves, and give polynomial-time algorithms for the upper bound and expected discrete and continuous Fréchet distance for uncertainty modelled as point sets. 

   more » « less
3. On the partial convexification for low-rank spectral optimization: rank bounds and algorithms

   https://doi.org/10.1007/s10107-025-02316-y  

   Li, Yongchun; Xie, Weijun (December 2025, Mathematical Programming)

   Abstract A Low-rank Spectral Optimization Problem (LSOP) minimizes a linear objective function subject to multiple two-sided linear inequalities intersected with a low-rank and spectral constrained domain. Although solving LSOP is generally NP-hard, its partial convexification (i.e., replacing the domain with its convex hull), termed “LSOP-R, is often tractable and yields a high-quality solution. This motivates us to study the strength of LSOP-R. Specifically, we derive rank bounds for any extreme point of LSOP-R in different matrix spaces and prove their tightness. The proposed rank bounds recover two well-known results in the literature from a fresh angle and allow us to derive sufficient conditions under which the relaxation LSOP-R is equivalent to LSOP. To effectively solve LSOP-R, we develop a column generation algorithm with a vector-based convex pricing oracle and a rank-reduction algorithm, which ensures that the output solution always satisfies the theoretical rank bound. Finally, we numerically verify the strength of LSOP-R and the efficacy of the proposed algorithms. 

   more » « less
4. The Replenishment Schedule to Minimize Peak Storage Problem: The Gap Between the Continuous and Discrete Versions of the Problem

   https://doi.org/10.1287/opre.2018.1839  

   Hochbaum, Dorit S.; Rao, Xu (September 2019, Operations Research)

   The replenishment storage problem (RSP) is to minimize the storage capacity requirement for a deterministic demand, multi-item inventory system, where each item has a given reorder size and cycle length. We consider the discrete RSP, where reorders can only take place at an integer time unit within the cycle. Discrete RSP was shown to be NP-hard for constant joint cycle length (the least common multiple of the length of all individual cycles). We show here that discrete RSP is weakly NP-hard for constant joint cycle length and prove that it is strongly NP-hard for nonconstant joint cycle length. For constant joint cycle-length discrete RSP, we further present a pseudopolynomial time algorithm that solves the problem optimally and the first known fully polynomial time approximation scheme (FPTAS) for the single-cycle RSP. The scheme is utilizing a new integer programming formulation of the problem that is introduced here. For the strongly NP-hard RSP with nonconstant joint cycle length, we provide a polynomial time approximation scheme (PTAS), which for any fixed [Formula: see text], provides a linear time [Formula: see text] approximate solution. The continuous RSP, where reorders can take place at any time within a cycle, seems (with our results) to be easier than the respective discrete problem. We narrow the previously known complexity gap between the continuous and discrete versions of RSP for the multi-cycle RSP (with either constant or nonconstant cycle length) and the single-cycle RSP with constant cycle length and widen the gap for single-cycle RSP with nonconstant cycle length. For the multi-cycle case and constant joint cycle length, the complexity status of continuous RSP is open, whereas it is proved here that the discrete RSP is weakly NP-hard. Under our conjecture that the continuous RSP is easier than the discrete one, this implies that continuous RSP on multi-cycle and constant joint cycle length (currently of unknown complexity status) is at most weakly NP-hard. 

   more » « less
5. Public-Key Cryptography in the Fine-Grained Setting

   https://doi.org/10.1007/978-3-030-26954-8_20  

   LaVigne, R.; Lincoln, A.; Vassilevska Williams, V. (January 2019, Advances in Cryptology {\textendash} {CRYPTO} 2019)

   Cryptography is largely based on unproven assumptions, which, while believable, might fail. Notably if P=NP, or if we live in Pessiland, then all current cryptographic assumptions will be broken. A compelling question is if any interesting cryptography might exist in Pessiland. A natural approach to tackle this question is to base cryptography on an assumption from fine-grained complexity. Ball, Rosen, Sabin, and Vasudevan [BRSV’17] attempted this, starting from popular hardness assumptions, such as the Orthogonal Vectors (OV) Conjecture. They obtained problems that are hard on average, assuming that OV and other problems are hard in the worst case. They obtained proofs of work, and hoped to use their average-case hard problems to build a fine-grained one-way function. Unfortunately, they proved that constructing one using their approach would violate a popular hardness hypothesis. This motivates the search for other fine-grained average-case hard problems. The main goal of this paper is to identify sufficient properties for a fine-grained average-case assumption that imply cryptographic primitives such as fine-grained public key cryptography (PKC). Our main contribution is a novel construction of a cryptographic key exchange, together with the definition of a small number of relatively weak structural properties, such that if a computational problem satisfies them, our key exchange has provable fine-grained security guarantees, based on the hardness of this problem. We then show that a natural and plausible average-case assumption for the key problem Zero-k-Clique from fine-grained complexity satisfies our properties. We also develop fine-grained one-way functions and hardcore bits even under these weaker assumptions. Where previous works had to assume random oracles or the existence of strong one-way functions to get a key-exchange computable in O(n) time secure against O(n^2) time adversaries (see [Merkle’78] and [BGI’08]), our assumptions seem much weaker. Our key exchange has a similar gap between the computation of the honest party and the adversary as prior work, while being non-interactive, implying fine-grained PKC. 

   more » « less