We study algorithms for approximating the multimarginal optimal transport (MOT) distance, a generalization of the classic optimal transport distance, between $m$ discrete probability distributions each supported on at most $n$ points. We give a classical algorithm that computes a coupling between these marginals whose expected transportation cost is within an additive $\varepsilon > 0$ of the MOT distance in time $O(m^2 n^m \varepsilon^{-1}\mathrm{polylog}(m,n,\varepsilon^{-1}))$. This is, to our knowledge, the first bound for general MOT problems with simultaneous linear dependence on the dimension $n^m$ and on the accuracy parameter $\varepsilon^{-1}$, improving the prior state of the art.
On the quantum side, we give two algorithms that achieve speedups in dimension, though with worse accuracy dependence than classical approaches. First, we construct a quantum projected subgradient method for estimating the MOT distance within an additive $\varepsilon >0$ with runtime $O( m^3 n^{\frac{m}{2}+1} \varepsilon^{-2} \mathrm{polylog}(m,n,\varepsilon^{-1}))$. This algorithm works with the linear programming dual of the MOT problem, and does not return a coupling. We also give a quantum multimarginal Sinkhorn algorithm for entropy-regularized MOT. This algorithm returns an implicit description of an approximately optimal coupling with runtime $O(m^8n^{\frac{m+1}{2}} \varepsilon^{-5} \mathrm{polylog}(m,n,\varepsilon^{-1})))$ after the usual reduction from entropic MOT to unregularized MOT. We also record query lower bounds: for any precision $\varepsilon<1/2$, randomized classical algorithms require $Ω(n^m/(1+\varepsilon n))$ queries and quantum algorithms require $Ω(\sqrt{n^m/(1+\varepsilon n)})$ queries.
We study algorithms for approximating the multimarginal optimal transport (MOT) distance, a generalization of the classic optimal transport distance, between m discrete probability distributions each supported on at most n points. We give a classical algorithm that computes a coupling between these marginals whose expected transportation cost is within an additive ε>0 of the MOT distance in time O(m2nmε−1polylog(m,n,ε−1)). This is, to our knowledge, the first bound for general MOT problems with simultaneous linear dependence on the dimension nm and on the accuracy parameter ε−1, improving the prior state of the art.
On the quantum side, we give two algorithms that achieve speedups in dimension, though with worse accuracy dependence than classical approaches. First, we construct a quantum projected subgradient method for estimating the MOT distance within an additive ε>0 with runtime O(m3n2m+1ε−2polylog(m,n,ε−1)). This algorithm works with the linear programming dual of the MOT problem, and does not return a coupling. We also give a quantum multimarginal Sinkhorn algorithm for entropy-regularized MOT. This algorithm returns an implicit description of an approximately optimal coupling with runtime O(m8n2m+1ε−5polylog(m,n,ε−1))) after the usual reduction from entropic MOT to unregularized MOT. We also record query lower bounds: for any precision ε<1/2, randomized classical algorithms require Ω(nm/(1+εn)) queries and quantum algorithms require Ω(nm/(1+εn)) queries.
Quantum linear system solvers form one of the central algorithmic primitives in quantum computing, with applications ranging from differential equations and optimization to machine learning. Their cost is commonly measured through query complexity, which counts the number of oracle calls needed to access the input matrix. In the sparse-access model, this complexity is governed by three parameters: the condition number κ, the sparsity s of the input matrix, and the target precision ε. The dependence on κ and ε is already well understood through the lower bound Ω(κlog(1/ε)), which matches the best known scaling in these parameters. Once the sparsity s is included, however, the expected lower bound has long been conjectured to be Ω(κslog(1/ε)). Recent work by Mori et al. [Quantum Sci. Tech. 11 035063 (2026)] made an important step towards this goal by establishing the lower bound Ω(κs) for constant error ε. In this work, we complete the picture and prove the full joint lower bound Ω(κslog(1/ε)) in the sparse-access model, thereby establishing the anticipated dependence on all three parameters simultaneously.
We study quantum sparse recovery in non-orthogonal, overcomplete dictionaries: given coherent quantum access to a state and a dictionary of vectors, the goal is to reconstruct the state up to ℓ2 error using as few vectors as possible. We first show that the general recovery problem is NP-hard, ruling out efficient exact algorithms in full generality. To overcome this, we introduce Quantum Orthogonal Matching Pursuit (QOMP), the first quantum analogue of the classical OMP greedy algorithm. QOMP combines quantum subroutines for inner product estimation, maximum finding, and block-encoded projections with an error-resetting design that avoids iteration-to-iteration error accumulation. Under standard mutual incoherence and well-conditioned sparsity assumptions, QOMP provably recovers the exact support of a K-sparse state in polynomial time. As an application, we give the first framework for sparse quantum tomography with non-orthogonal dictionaries in ℓ2 norm, achieving query complexity O(N/ε) in favorable regimes and reducing tomography to estimating only K coefficients instead of N amplitudes. In particular, for pure-state tomography with m=O(N) dictionary vectors and sparsity K=O(1) on a well-conditioned subdictionary, this circumvents the Ω(N/ε) lower bound that holds in the dense, orthonormal-dictionary setting, without contradiction, by leveraging sparsity together with non-orthogonality. Beyond tomography, we analyze QOMP in the QRAM model, where it yields polynomial speedups over classical OMP implementations, and provide a quantum algorithm to estimate the mutual incoherence of a dictionary of m vectors in O(m/ε) queries, improving over both deterministic and quantum-inspired classical methods.
We study quantum random self-reductions for linear problems over finite fields. Let M∈Fn×n be an arbitrary matrix, and let O be an oracle that agrees with the linear map x↦Mx on an ε-fraction of inputs x∼Fn. Given coherent access to O and coherent entry access to M, we give a uniform quantum reduction that computes Mx on any prescribed input x with probability at least 2/3 in time O(nT1/3), for n≤T≤n3/2 and constant field size and ε, where T is the cost of one coherent query to O. In particular, when T=O(n), the reduction runs in time O(n4/3), improving the O(n3/2+T) reduction of Asadi, Golovnev, Gur, Shinkar, and Subramanian (SODA 2024).
Our reduction uses the Bogolyubov--Ruzsa subspace guaranteed by additive combinatorics, but it avoids learning this subspace explicitly, which was computationally expensive for the previous reduction; in particular, it does not recover a basis for its orthogonal complement. The main technical step is to decompose the inputs into sparse pieces and find a vector that lies outside the Bogolyubov--Ruzsa subspace via a quantum search based on amplitude amplification. This yields a tunable tradeoff between the cost of querying the average-case oracle and the cost of verifying matrix-vector products.
We establish a linear quantum query lower bound for high-accuracy convex optimization over an explicit family of n-dimensional ellipsoids. We focus on linear optimization with an explicitly given objective, where the feasible set is accessed through a membership oracle. We show that any algorithm that, for every unit linear objective, returns an exactly feasible point with additive objective error Θ(n−1/2) requires Ω(n) membership queries, where the ellipsoids are contained in the unit ball. The same lower bound can be shown to hold if the returned point is only required to be approximately feasible, within Θ(n−3/2) distance from the feasible set. This resolves an open question posed by Chakrabarti, Childs, Li, and Wu~(\textit{Quantum}, 2020) and by van Apeldoorn, Gilyén, Gribling, and de Wolf~(\textit{Quantum}, 2020). Coupled with the upper bounds in these papers, the query complexity of high-accuracy convex optimization is characterized tightly up to logarithmic factors. The proof is built around a lower bound for determinant computation that is derived via a novel polynomial method based on Fourier-rank. In the continuous matrix phase-query model, computing the determinant of a real n×n matrix requires at least n/2 matrix-vector product queries. The construction also yields an Ω(n) phase-query lower bound for estimating the minimum eigenvalue of a real symmetric n×n matrix to additive accuracy Θ(n−2). These results extend the determinant and minimum-eigenvalue lower bounds of Childs, Hung, and Li~(ICALP 2021) from finite fields to the real-valued setting. Based on the same constructions, we also prove an Ω(min{κ,n}) gradient-query lower bound for constant-accuracy optimization of 1-strongly convex and κ-smooth functions, which is optimal up to a logarithmic factor.
We study quantum sparse recovery in non-orthogonal, overcomplete dictionaries: given coherent quantum access to a state and a dictionary of vectors, the goal is to reconstruct the state up to ℓ2 error using as few vectors as possible. We first show that the general recovery problem is NP-hard, ruling out efficient exact algorithms in full generality. To overcome this, we introduce Quantum Orthogonal Matching Pursuit (QOMP), the first quantum analogue of the classical OMP greedy algorithm. QOMP combines quantum subroutines for inner product estimation, maximum finding, and block-encoded projections with an error-resetting design that avoids iteration-to-iteration error accumulation. Under standard mutual incoherence and well-conditioned sparsity assumptions, QOMP provably recovers the exact support of a K-sparse state in polynomial time. As an application, we give the first framework for sparse quantum tomography with non-orthogonal dictionaries in ℓ2 norm, achieving query complexity O(N/ε) in favorable regimes and reducing tomography to estimating only K coefficients instead of N amplitudes. In particular, for pure-state tomography with m=O(N) dictionary vectors and sparsity K=O(1) on a well-conditioned subdictionary, this circumvents the Ω(N/ε) lower bound that holds in the dense, orthonormal-dictionary setting, without contradiction, by leveraging sparsity together with non-orthogonality. Beyond tomography, we analyze QOMP in the QRAM model, where it yields polynomial speedups over classical OMP implementations, and provide a quantum algorithm to estimate the mutual incoherence of a dictionary of m vectors in O(m/ε) queries, improving over both deterministic and quantum-inspired classical methods.
Discrete nonlinear dynamical systems arise in population models, iterative optimization, and numerical simulations, where computing many iterations can be costly in high dimensions. We study Carleman embedding for forced quadratic discrete systems and its application to quantum state preparation. Under explicit stability and initial-state assumptions, we prove that the truncation error decreases geometrically with the embedding degree, uniformly over all iterations. A central obstacle in discrete time is that the lifted update can become dense even when the original coefficient maps are sparse. We overcome this obstacle by constructing an exact auxiliary linear-system representation that applies the coefficient maps one tensor factor at a time, with row and column sparsities bounded independently of the truncation degree. After rescaling, the associated history system has a condition number that grows linearly with the iteration count, uniformly in the truncation degree. These results yield a quantum algorithm for preparing an approximation to the normalized nth iterate with constant success probability. Under coherent input-access assumptions, and for fixed sparsity, stability parameters, and a known positive lower bound on the final-state norm, the oracle query complexity is linear in n and polylogarithmic in the inverse accuracy. Numerical experiments in one and three dimensions illustrate the convergence of the truncated embedding.