Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2608.09513

Faster Algorithms for Multimarginal Optimal Transport

Brandon Augustino, Yue Sun, Atithi Acharya, Shouvanik Chakrabarti, Junhyung Lyle Kim, Shree Hari Sureshbabu, Charlie Che

quant-phcs.DSmath.OCSubmitted Aug 10, 2026• Announced Aug 11, 2026• 0 citations• Revised Oct 6, 2026 (v2)
v1 · Aug 10, 2026v2 · Oct 6, 2026
arXivHTMLPDF

Abstract

We study constructive discrete multimarginal optimal transport (MOT) among $m$ distributions on $n$ points, where the cost tensor $C$ has $N=n^m$ entries. For additive accuracy $\varepsilon$, let $κ=\max\{1,(\max C-\min C)/\varepsilon\}$. Classically, we give two algorithms that return exactly feasible additive-$\varepsilon$ couplings. A deterministic box--simplex method with rounding runs in $O(m^2Nκ\log N)=\widetilde O(m^3Nκ)$ time, while an exact reduction to positive packing followed by rank-one completion runs in randomized time $\widetilde O(m^2Nκ)$. At fixed $κ$, both match the $Ω(N)$ cost of writing a dense coupling, up to factors in $m$ and logarithms. Quantumly, in the general entry-access model, tensor Sinkhorn followed by sparse recovery returns an exactly feasible additive-$\varepsilon$ coupling as a classical list of $\widetilde O(m^2nκ^2)$ atoms, using $\widetilde O(m^4\sqrt{Nn}\,κ^3)$ coherent cost queries without materializing the tensor. Finally, for fixed $m$ and constant normalized accuracy, we prove sparse-output lower bounds of $\widetildeΩ(N)$ randomized classical queries, even with unrestricted output size, and $\widetildeΩ(\sqrt{Nn})$ quantum queries for outputs with at most $n\operatorname{polylog}(n)$ atoms. Hence, for fixed $m$ and normalized accuracy between $(\log n)^{-O(1)}$ and a sufficiently small constant, explicit sparse MOT construction has query complexity $\widetildeΘ(N)$ classically and $\widetildeΘ(\sqrt{Nn})$ quantumly.

Related papers

A Near-Optimal Joint Lower Bound for Sparse Quantum Linear System Solvers

Dhrumil Patel

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 $\varepsilon$. The dependence on $κ$ and $\varepsilon$ is already well understood through the lower bound $Ω(κ\log(1/\varepsilon))$, 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 $Ω(κ\sqrt{s}\log(1/\varepsilon))$. Recent work by Mori et al. [Quantum Sci. Tech. 11 035063 (2026)] made an important step towards this goal by establishing the lower bound $Ω(κ\sqrt{s})$ for constant error $\varepsilon$. In this work, we complete the picture and prove the full joint lower bound $Ω(κ\sqrt{s}\log(1/\varepsilon))$ in the sparse-access model, thereby establishing the anticipated dependence on all three parameters simultaneously.

quant-pharXiv:2609.22445•Sep 22, 2026•0 citations

Quantum Sparse Recovery and Quantum Orthogonal Matching Pursuit

Armando Bellante, Stefano Vanerio, Stefano Zanero

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 $\ell_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 $\ell_2$ norm, achieving query complexity $\widetilde{O}(\sqrt{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=\widetilde{O}(1)$ on a well-conditioned subdictionary, this circumvents the $\widetildeΩ(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.

arXiv:2510.06925•Oct 8, 2025•0 citations

Improved Quantum Random Self-Reduction for Linear Problems

Vahid R. Asadi, Shuichi Hirahara, Nobutaka Shimizu

We study quantum random self-reductions for linear problems over finite fields. Let $M\in\mathbb{F}^{n\times n}$ be an arbitrary matrix, and let $\mathcal{O}$ be an oracle that agrees with the linear map $x\mapsto Mx$ on an $\varepsilon$-fraction of inputs $x\sim\mathbb{F}^n$. Given coherent access to $\mathcal{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 $\widetilde{O}(nT^{1/3})$, for $n\le T\le n^{3/2}$ and constant field size and $\varepsilon$, where $T$ is the cost of one coherent query to $\mathcal{O}$. In particular, when $T=\widetilde{O}(n)$, the reduction runs in time $\widetilde{O}(n^{4/3})$, improving the $\widetilde{O}(n^{3/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.

quant-pharXiv:2609.39823•Oct 1, 2026•0 citations

Near-Optimal Quantum Lower Bounds for Convex Optimization via Fourier Rank

Brandon Augustino, Shouvanik Chakrabarti, Enrico Fontana +4 more

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\times 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\times 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\{\sqrtκ,n\})$ gradient-query lower bound for constant-accuracy optimization of $1$-strongly convex and $κ$-smooth functions, which is optimal up to a logarithmic factor.

quant-pharXiv:2609.09035•Sep 9, 2026•0 citations

Preprint arXiv:2510.06925 Submitted on 8 Oct 2025

Armando Bellante, Stefano Vanerio, S. Zanero

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 $\ell_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 $\ell_2$ norm, achieving query complexity $\widetilde{O}(\sqrt{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=\widetilde{O}(1)$ on a well-conditioned subdictionary, this circumvents the $\widetildeΩ(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.

•Oct 9, 2025•0 citations

Sparse Carleman Embeddings for Nonlinear Discrete Dynamical Systems

Hsuan-Cheng Wu, Xiantao Li

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 $n$th 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.

quant-pharXiv:2610.35824•Oct 27, 2026•0 citations
We study constructive discrete multimarginal optimal transport (MOT) among mmm distributions on nnn points, where the cost tensor CCC has N=nmN=n^mN=nm entries. For additive accuracy ε\varepsilonε, let κ=max⁡{1,(max⁡C−min⁡C)/ε}κ=\max\{1,(\max C-\min C)/\varepsilon\}κ=max{1,(maxC−minC)/ε}. Classically, we give two algorithms that return exactly feasible additive-ε\varepsilonε couplings. A deterministic box--simplex method with rounding runs in O(m2Nκlog⁡N)=O~(m3Nκ)O(m^2Nκ\log N)=\widetilde O(m^3Nκ)O(m2NκlogN)=O(m3Nκ) time, while an exact reduction to positive packing followed by rank-one completion runs in randomized time O~(m2Nκ)\widetilde O(m^2Nκ)O(m2Nκ). At fixed κκκ, both match the Ω(N)Ω(N)Ω(N) cost of writing a dense coupling, up to factors in mmm and logarithms. Quantumly, in the general entry-access model, tensor Sinkhorn followed by sparse recovery returns an exactly feasible additive-ε\varepsilonε coupling as a classical list of O~(m2nκ2)\widetilde O(m^2nκ^2)O(m2nκ2) atoms, using O~(m4Nn κ3)\widetilde O(m^4\sqrt{Nn}\,κ^3)O(m4Nn​κ3) coherent cost queries without materializing the tensor. Finally, for fixed mmm and constant normalized accuracy, we prove sparse-output lower bounds of Ω~(N)\widetildeΩ(N)Ω(N) randomized classical queries, even with unrestricted output size, and Ω~(Nn)\widetildeΩ(\sqrt{Nn})Ω(Nn​) quantum queries for outputs with at most npolylog⁡(n)n\operatorname{polylog}(n)npolylog(n) atoms. Hence, for fixed mmm and normalized accuracy between (log⁡n)−O(1)(\log n)^{-O(1)}(logn)−O(1) and a sufficiently small constant, explicit sparse MOT construction has query complexity Θ~(N)\widetildeΘ(N)Θ(N) classically and Θ~(Nn)\widetildeΘ(\sqrt{Nn})Θ(Nn​) quantumly.
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 sss of the input matrix, and the target precision ε\varepsilonε. The dependence on κκκ and ε\varepsilonε is already well understood through the lower bound Ω(κlog⁡(1/ε))Ω(κ\log(1/\varepsilon))Ω(κlog(1/ε)), which matches the best known scaling in these parameters. Once the sparsity sss is included, however, the expected lower bound has long been conjectured to be Ω(κslog⁡(1/ε))Ω(κ\sqrt{s}\log(1/\varepsilon))Ω(κs​log(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)Ω(κ\sqrt{s})Ω(κs​) for constant error ε\varepsilonε. In this work, we complete the picture and prove the full joint lower bound Ω(κslog⁡(1/ε))Ω(κ\sqrt{s}\log(1/\varepsilon))Ω(κs​log(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\ell_2ℓ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 KKK-sparse state in polynomial time. As an application, we give the first framework for sparse quantum tomography with non-orthogonal dictionaries in ℓ2\ell_2ℓ2​ norm, achieving query complexity O~(N/ε)\widetilde{O}(\sqrt{N}/ε)O(N​/ε) in favorable regimes and reducing tomography to estimating only KKK coefficients instead of NNN amplitudes. In particular, for pure-state tomography with m=O(N)m=O(N)m=O(N) dictionary vectors and sparsity K=O~(1)K=\widetilde{O}(1)K=O(1) on a well-conditioned subdictionary, this circumvents the Ω~(N/ε)\widetildeΩ(N/ε)Ω(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 mmm vectors in O(m/ε)O(m/ε)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×nM\in\mathbb{F}^{n\times n}M∈Fn×n be an arbitrary matrix, and let O\mathcal{O}O be an oracle that agrees with the linear map x↦Mxx\mapsto Mxx↦Mx on an ε\varepsilonε-fraction of inputs x∼Fnx\sim\mathbb{F}^nx∼Fn. Given coherent access to O\mathcal{O}O and coherent entry access to MMM, we give a uniform quantum reduction that computes MxMxMx on any prescribed input xxx with probability at least 2/32/32/3 in time O~(nT1/3)\widetilde{O}(nT^{1/3})O(nT1/3), for n≤T≤n3/2n\le T\le n^{3/2}n≤T≤n3/2 and constant field size and ε\varepsilonε, where TTT is the cost of one coherent query to O\mathcal{O}O. In particular, when T=O~(n)T=\widetilde{O}(n)T=O(n), the reduction runs in time O~(n4/3)\widetilde{O}(n^{4/3})O(n4/3), improving the O~(n3/2+T)\widetilde{O}(n^{3/2}+T)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 nnn-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)Θ(n^{-1/2})Θ(n−1/2) requires Ω(n)Ω(n)Ω(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)Θ(n^{-3/2})Θ(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×nn\times nn×n matrix requires at least n/2n/2n/2 matrix-vector product queries. The construction also yields an Ω(n)Ω(n)Ω(n) phase-query lower bound for estimating the minimum eigenvalue of a real symmetric n×nn\times nn×n matrix to additive accuracy Θ(n−2)Θ(n^{-2})Θ(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})Ω(\min\{\sqrtκ,n\})Ω(min{κ​,n}) gradient-query lower bound for constant-accuracy optimization of 111-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\ell_2ℓ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 KKK-sparse state in polynomial time. As an application, we give the first framework for sparse quantum tomography with non-orthogonal dictionaries in ℓ2\ell_2ℓ2​ norm, achieving query complexity O~(N/ε)\widetilde{O}(\sqrt{N}/ε)O(N​/ε) in favorable regimes and reducing tomography to estimating only KKK coefficients instead of NNN amplitudes. In particular, for pure-state tomography with m=O(N)m=O(N)m=O(N) dictionary vectors and sparsity K=O~(1)K=\widetilde{O}(1)K=O(1) on a well-conditioned subdictionary, this circumvents the Ω~(N/ε)\widetildeΩ(N/ε)Ω(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 mmm vectors in O(m/ε)O(m/ε)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 nnnth 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 nnn and polylogarithmic in the inverse accuracy. Numerical experiments in one and three dimensions illustrate the convergence of the truncated embedding.