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:2504.06940

More-efficient Quantum Multivariate Mean Value Estimator from Generalized Grover Operator

Letian Tang

Published Apr 9, 2025• 0 citations
arXivHTMLPDF

Abstract

In this work, we present an efficient algorithm for multivariate mean value estimation. Our algorithm outperforms previous work by polylog factors and nearly saturates the known lower bound. More formally, given a random vector $\vec{X}$ of dimension $d$, we find an algorithm that uses $O\left(n \log \frac{d}δ\right)$ samples to find a mean estimate that $\vec{\tildeμ}$ that differs from the true mean $\vecμ$ by $\frac{\sqrt{\text{tr } Σ}}{n}$ in $\ell^\infty$ norm and hence $\frac{\sqrt{d \text{ tr } Σ}}{n}$ in $\ell^2$ norm, where $Σ$ is the covariance matrix of the components of the random vector. We also presented another algorithm that uses smaller memory but costs an extra $d^\frac{1}{4}$ in complexity. Consider the Grover operator, the unitary operator used in Grover's algorithm. It contains an oracle that uses a $\pm 1$ phase for each candidate for the search space. Previous work has demonstrated that when we substitute the oracle in Grover operator with generic phases, it ended up being a good mean value estimator in some mathematical notion. We used this idea to build our algorithm. Our result remains not exactly optimal due to a $\log \frac{d}δ$ term in our complexity, as opposed to something nicer such as $\log \frac{1}δ$; This comes from the phase estimation primitive in our algorithm. So far, this primitive is the only major known method to tackle the problem, and moving beyond this idea seems hard. Our results demonstrates that the methodology with generalized Grover operator can be used develop the optimal algorithm without polylog overhead for different tasks relating to mean value estimation.

DOI
10.48550/arxiv.2504.06940

Related papers

Near-optimal Quantum algorithms for multivariate mean estimation

Arjan Cornelissen, Yassine Hamoudi, Sofiène Jerbi

We propose the first near-optimal quantum algorithm for estimating in Euclidean norm the mean of a vector-valued random variable with finite mean and covariance. Our result aims at extending the theory of multivariate sub-Gaussian estimators [Lugosi and Mendelson, 2019] to the quantum setting. Unlike classically, where any univariate estimator can be turned into a multivariate estimator with at most a logarithmic overhead in the dimension, no similar result can be proved in the quantum setting. Indeed, [Heinrich, 2004] ruled out the existence of a quantum advantage for the mean estimation problem when the sample complexity is smaller than the dimension. Our main result is to show that, outside this low-precision regime, there does exist a quantum estimator that outperforms any classical estimator. More precisely, we prove that the approximation error can be decreased by a factor of about the square root of the ratio between the dimension and the sample complexity. Our approach is substantially more involved than in the univariate setting, where most quantum estimators rely only on phase estimation. We exploit a variety of additional algorithmic techniques such as linear amplitude amplification, the Bernstein-Vazirani algorithm, and quantum singular value transformation. Our analysis is also deeply rooted in proving concentration inequalities for multivariate truncated statistics. Finally, we describe several applications of our algorithms, notably in measuring the expectation values of commuting observables and in the field of machine learning.

arXiv:2111.09787•ACM Symposium on Theory of Computing (STOC)•Jun 9, 2022•16 citations

Quantum Non-Identical Mean Estimation: Efficient Algorithms and Fundamental Limits

Jiachen Hu, Tongyang Li, Xinzhao Wang +3 more

We systematically investigate quantum algorithms and lower bounds for mean estimation given query access to non-identically distributed samples. On the one hand, we give quantum mean estimators with quadratic quantum speed-up given samples from different bounded or sub-Gaussian random variables. On the other hand, we prove that, in general, it is impossible for any quantum algorithm to achieve quadratic speed-up over the number of classical samples needed to estimate the mean $μ$, where the samples come from different random variables with mean close to $μ$. Technically, our quantum algorithms reduce bounded and sub-Gaussian random variables to the Bernoulli case, and use an uncomputation trick to overcome the challenge that direct amplitude estimation does not work with non-identical query access. Our quantum query lower bounds are established by simulating non-identical oracles by parallel oracles, and also by an adversarial method with non-identical oracles. Both results pave the way for proving quantum query lower bounds with non-identical oracles in general, which may be of independent interest.

arXiv:2405.12838•Leibniz international proceedings in informatics•Jan 1, 2024•0 citations

Multivariate Quantum Signal Processing

Guang Hao Low

We develop Multivariate Quantum Signal Processing for designing matrix-valued transformations of multiple noncommuting nonnormal block-encoded matrices. Our framework equips quantum transducers with the analytic structure of multiport Infinite-Impulse-Response (IIR) filters and establishes a transfer-function methodology for designing quantum query algorithms. Efficiently computable analytic bounds that hold uniformly across the oracle promise yield efficient quantum circuits with logarithmic error dependence and near-unity success probability, paralleling the approximation-theoretic guarantees of univariate QSP/QSVT. We provide a complete characterization of achievable transfer functions and a principled library of analytic IIR components. Our modular designs greatly improve or resolve the per-oracle query complexity of open multi-oracle problems: (1) Hamiltonian simulation under $H=\sum_j H_j$ with weighted quasinorm cost $\approx t\langle\vecλ,\vec C\rangle_{1/2}+\mathcal{O}(\|\vec C\|_1\log(1/ε))$ for block-encoding normalizations $\vecλ$ and costs $\vec C$; (2) sparse simulation with optimal time--norm $Θ(\sqrt{d}\|H\|_{\rm 1\to2}t)$ and additive error dependence; (3) solving linear systems and (4) differential equations under minimal matrix assumptions with optimal weighted state-preparation and multi-term cost; (5) ground-state preparation and energy estimation; (6) generalized eigenvalue problems. We apply these to exactly simulate downfolded Hamiltonians with leading cost $t\langle\vecλ_{\rm eff},\vec C_{\rm eff}\rangle_{1/2}$ further reduced by fractional dynamic correlation energy contributions from coarse-grained Hamiltonians, and show similar classical-data-input-reduction results for multiscale graph classification via Kron reduction. We also show the online generalization with anisotropic Kalman filtering of streaming quantum data.

quant-pharXiv:2610.01125•Oct 2, 2026•0 citations

Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise

Bin Luo, Chengchang Liu, Jonathan Allcock +2 more

We study stochastic optimization with heavy-tailed gradient noise. We first propose a novel quantum mean estimator for multivariate heavy-tailed random variables that achieves lower query complexity than optimal classical estimators in the low-dimensional regime. We further develop an unbiased quantum mean estimator by applying a generalized multi-level Monte Carlo technique. We prove quantum lower bounds showing that, when the dimension $d$ of the random vector is small and can be viewed as a constant, our quantum estimators are optimal up to logarithmic factors. We further derive stronger dimension-dependent lower bounds for tail index $p>4/3$, showing that a nontrivial dependence on the dimension is unavoidable in the low-dimensional regime. Based on these estimators, we propose a quantum normalized stochastic gradient descent method ($\texttt{QNSGD}$), which finds an $ε$-stationary point using $\tilde{\mathcal{O}}\big(\sqrt d\,ε^{-\frac{5p-4}{2p-2}}\big)$ queries to the quantum stochastic gradient oracle. For a convex objective function, we propose a quantum projected stochastic gradient descent method ($\texttt{QPSGD}$), which computes a solution with $ε$-optimal solution using $\tilde{\mathcal{O}}\big(\sqrt d\,ε^{-\frac{3p-2}{2p-2}}+ε^{-2}\big)$ queries in expectation. These sharper bounds improve upon the classical lower bounds $Ω\big(ε^{-\frac{3p-2}{p-1}}\big)$ for nonconvex problems and $Ω\big(ε^{-\frac{p}{p-1}}\big)$ for convex problems in the low-dimensional regimes $d\lesssimε^{-\frac{p}{p-1}}$ and $d\lesssimε^{-\frac{2-p}{p-1}}$, respectively.

arXiv:2607.25492•Jul 28, 2026•0 citations

Faster quantum searching with almost any diffusion operator

Avatar Tulsi

Grover's search algorithm drives a quantum system from an initial state $|s\ensuremath{\rangle}$ to a desired final state $|t\ensuremath{\rangle}$ by using selective phase inversions of these two states. Earlier, we studied a generalization of Grover's algorithm that relaxes the assumption of the efficient implementation of ${I}_{s}$, the selective phase inversion of the initial state, also known as a diffusion operator. This assumption is known to become a serious handicap in cases of physical interest. Our general search algorithm works with almost any diffusion operator ${D}_{s}$ with the only restriction of having $|s\ensuremath{\rangle}$ as one of its eigenstates. The price that we pay for using any operator is an increase in the number of oracle queries by a factor of $O(B)$, where $B$ is a characteristic of the eigenspectrum of ${D}_{s}$ and can be large in some situations. Here we show that by using a quantum Fourier transform, we can regain the optimal query complexity of Grover's algorithm without losing the freedom of using any diffusion operator for quantum searching. However, the total number of operators required by the algorithm is still $O(B)$ times more than that of Grover's algorithm. So our algorithm offers an advantage only if the oracle operator is computationally more expensive than the diffusion operator, which is true in most search problems.

arXiv:1503.05712•Physical Review A•May 7, 2015•10 citations

Generalized Grover’s Algorithm for Multiple Phase Inversion States

Tim Byrnes, Gary Forster, Louis Tessler

Grover's algorithm is a quantum search algorithm that proceeds by repeated applications of the Grover operator and the Oracle until the state evolves to one of the target states. In the standard version of the algorithm, the Grover operator inverts the sign on only one state. Here we provide an exact solution to the problem of performing Grover's search where the Grover operator inverts the sign on N states. We show the underlying structure in terms of the eigenspectrum of the generalized Hamiltonian, and derive an appropriate initial state to perform the Grover evolution. This allows us to use the quantum phase estimation algorithm to solve the search problem in this generalized case, completely bypassing the Grover algorithm altogether. We obtain a time complexity of this case of sqrt[D/M^{α}], where D is the search space dimension, M is the number of target states, and α≈1, which is close to the optimal scaling.

arXiv:1801.02809•Physical Review Letters•Feb 7, 2018•24 citations
In this work, we present an efficient algorithm for multivariate mean value estimation. Our algorithm outperforms previous work by polylog factors and nearly saturates the known lower bound. More formally, given a random vector X⃗\vec{X}X of dimension ddd, we find an algorithm that uses O(nlog⁡dδ)O\left(n \log \frac{d}δ\right)O(nlogδd​) samples to find a mean estimate that μ~⃗\vec{\tildeμ}μ~​​ that differs from the true mean μ⃗\vecμμ​ by tr Σn\frac{\sqrt{\text{tr } Σ}}{n}ntr Σ​​ in ℓ∞\ell^\inftyℓ∞ norm and hence d tr Σn\frac{\sqrt{d \text{ tr } Σ}}{n}nd tr Σ​​ in ℓ2\ell^2ℓ2 norm, where ΣΣΣ is the covariance matrix of the components of the random vector. We also presented another algorithm that uses smaller memory but costs an extra d14d^\frac{1}{4}d41​ in complexity. Consider the Grover operator, the unitary operator used in Grover's algorithm. It contains an oracle that uses a ±1\pm 1±1 phase for each candidate for the search space. Previous work has demonstrated that when we substitute the oracle in Grover operator with generic phases, it ended up being a good mean value estimator in some mathematical notion. We used this idea to build our algorithm. Our result remains not exactly optimal due to a log⁡dδ\log \frac{d}δlogδd​ term in our complexity, as opposed to something nicer such as log⁡1δ\log \frac{1}δlogδ1​; This comes from the phase estimation primitive in our algorithm. So far, this primitive is the only major known method to tackle the problem, and moving beyond this idea seems hard. Our results demonstrates that the methodology with generalized Grover operator can be used develop the optimal algorithm without polylog overhead for different tasks relating to mean value estimation.
We propose the first near-optimal quantum algorithm for estimating in Euclidean norm the mean of a vector-valued random variable with finite mean and covariance. Our result aims at extending the theory of multivariate sub-Gaussian estimators [Lugosi and Mendelson, 2019] to the quantum setting. Unlike classically, where any univariate estimator can be turned into a multivariate estimator with at most a logarithmic overhead in the dimension, no similar result can be proved in the quantum setting. Indeed, [Heinrich, 2004] ruled out the existence of a quantum advantage for the mean estimation problem when the sample complexity is smaller than the dimension. Our main result is to show that, outside this low-precision regime, there does exist a quantum estimator that outperforms any classical estimator. More precisely, we prove that the approximation error can be decreased by a factor of about the square root of the ratio between the dimension and the sample complexity. Our approach is substantially more involved than in the univariate setting, where most quantum estimators rely only on phase estimation. We exploit a variety of additional algorithmic techniques such as linear amplitude amplification, the Bernstein-Vazirani algorithm, and quantum singular value transformation. Our analysis is also deeply rooted in proving concentration inequalities for multivariate truncated statistics. Finally, we describe several applications of our algorithms, notably in measuring the expectation values of commuting observables and in the field of machine learning.
We systematically investigate quantum algorithms and lower bounds for mean estimation given query access to non-identically distributed samples. On the one hand, we give quantum mean estimators with quadratic quantum speed-up given samples from different bounded or sub-Gaussian random variables. On the other hand, we prove that, in general, it is impossible for any quantum algorithm to achieve quadratic speed-up over the number of classical samples needed to estimate the mean μμμ, where the samples come from different random variables with mean close to μμμ. Technically, our quantum algorithms reduce bounded and sub-Gaussian random variables to the Bernoulli case, and use an uncomputation trick to overcome the challenge that direct amplitude estimation does not work with non-identical query access. Our quantum query lower bounds are established by simulating non-identical oracles by parallel oracles, and also by an adversarial method with non-identical oracles. Both results pave the way for proving quantum query lower bounds with non-identical oracles in general, which may be of independent interest.
We develop Multivariate Quantum Signal Processing for designing matrix-valued transformations of multiple noncommuting nonnormal block-encoded matrices. Our framework equips quantum transducers with the analytic structure of multiport Infinite-Impulse-Response (IIR) filters and establishes a transfer-function methodology for designing quantum query algorithms. Efficiently computable analytic bounds that hold uniformly across the oracle promise yield efficient quantum circuits with logarithmic error dependence and near-unity success probability, paralleling the approximation-theoretic guarantees of univariate QSP/QSVT. We provide a complete characterization of achievable transfer functions and a principled library of analytic IIR components. Our modular designs greatly improve or resolve the per-oracle query complexity of open multi-oracle problems: (1) Hamiltonian simulation under H=∑jHjH=\sum_j H_jH=∑j​Hj​ with weighted quasinorm cost ≈t⟨λ⃗,C⃗⟩1/2+O(∥C⃗∥1log⁡(1/ε))\approx t\langle\vecλ,\vec C\rangle_{1/2}+\mathcal{O}(\|\vec C\|_1\log(1/ε))≈t⟨λ,C⟩1/2​+O(∥C∥1​log(1/ε)) for block-encoding normalizations λ⃗\vecλλ and costs C⃗\vec CC; (2) sparse simulation with optimal time--norm Θ(d∥H∥1→2t)Θ(\sqrt{d}\|H\|_{\rm 1\to2}t)Θ(d​∥H∥1→2​t) and additive error dependence; (3) solving linear systems and (4) differential equations under minimal matrix assumptions with optimal weighted state-preparation and multi-term cost; (5) ground-state preparation and energy estimation; (6) generalized eigenvalue problems. We apply these to exactly simulate downfolded Hamiltonians with leading cost t⟨λ⃗eff,C⃗eff⟩1/2t\langle\vecλ_{\rm eff},\vec C_{\rm eff}\rangle_{1/2}t⟨λeff​,Ceff​⟩1/2​ further reduced by fractional dynamic correlation energy contributions from coarse-grained Hamiltonians, and show similar classical-data-input-reduction results for multiscale graph classification via Kron reduction. We also show the online generalization with anisotropic Kalman filtering of streaming quantum data.
We study stochastic optimization with heavy-tailed gradient noise. We first propose a novel quantum mean estimator for multivariate heavy-tailed random variables that achieves lower query complexity than optimal classical estimators in the low-dimensional regime. We further develop an unbiased quantum mean estimator by applying a generalized multi-level Monte Carlo technique. We prove quantum lower bounds showing that, when the dimension ddd of the random vector is small and can be viewed as a constant, our quantum estimators are optimal up to logarithmic factors. We further derive stronger dimension-dependent lower bounds for tail index p>4/3p>4/3p>4/3, showing that a nontrivial dependence on the dimension is unavoidable in the low-dimensional regime. Based on these estimators, we propose a quantum normalized stochastic gradient descent method (QNSGD\texttt{QNSGD}QNSGD), which finds an εεε-stationary point using O~(d ε−5p−42p−2)\tilde{\mathcal{O}}\big(\sqrt d\,ε^{-\frac{5p-4}{2p-2}}\big)O~(d​ε−2p−25p−4​) queries to the quantum stochastic gradient oracle. For a convex objective function, we propose a quantum projected stochastic gradient descent method (QPSGD\texttt{QPSGD}QPSGD), which computes a solution with εεε-optimal solution using O~(d ε−3p−22p−2+ε−2)\tilde{\mathcal{O}}\big(\sqrt d\,ε^{-\frac{3p-2}{2p-2}}+ε^{-2}\big)O~(d​ε−2p−23p−2​+ε−2) queries in expectation. These sharper bounds improve upon the classical lower bounds Ω(ε−3p−2p−1)Ω\big(ε^{-\frac{3p-2}{p-1}}\big)Ω(ε−p−13p−2​) for nonconvex problems and Ω(ε−pp−1)Ω\big(ε^{-\frac{p}{p-1}}\big)Ω(ε−p−1p​) for convex problems in the low-dimensional regimes d≲ε−pp−1d\lesssimε^{-\frac{p}{p-1}}d≲ε−p−1p​ and d≲ε−2−pp−1d\lesssimε^{-\frac{2-p}{p-1}}d≲ε−p−12−p​, respectively.
Grover's search algorithm drives a quantum system from an initial state $|s\ensuremath{\rangle}$ to a desired final state $|t\ensuremath{\rangle}$ by using selective phase inversions of these two states. Earlier, we studied a generalization of Grover's algorithm that relaxes the assumption of the efficient implementation of Is{I}_{s}Is​, the selective phase inversion of the initial state, also known as a diffusion operator. This assumption is known to become a serious handicap in cases of physical interest. Our general search algorithm works with almost any diffusion operator Ds{D}_{s}Ds​ with the only restriction of having $|s\ensuremath{\rangle}$ as one of its eigenstates. The price that we pay for using any operator is an increase in the number of oracle queries by a factor of O(B)O(B)O(B), where BBB is a characteristic of the eigenspectrum of Ds{D}_{s}Ds​ and can be large in some situations. Here we show that by using a quantum Fourier transform, we can regain the optimal query complexity of Grover's algorithm without losing the freedom of using any diffusion operator for quantum searching. However, the total number of operators required by the algorithm is still O(B)O(B)O(B) times more than that of Grover's algorithm. So our algorithm offers an advantage only if the oracle operator is computationally more expensive than the diffusion operator, which is true in most search problems.
Grover's algorithm is a quantum search algorithm that proceeds by repeated applications of the Grover operator and the Oracle until the state evolves to one of the target states. In the standard version of the algorithm, the Grover operator inverts the sign on only one state. Here we provide an exact solution to the problem of performing Grover's search where the Grover operator inverts the sign on N states. We show the underlying structure in terms of the eigenspectrum of the generalized Hamiltonian, and derive an appropriate initial state to perform the Grover evolution. This allows us to use the quantum phase estimation algorithm to solve the search problem in this generalized case, completely bypassing the Grover algorithm altogether. We obtain a time complexity of this case of sqrt[D/M^{α}], where D is the search space dimension, M is the number of target states, and α≈1, which is close to the optimal scaling.