This paper presents tight upper and lower bounds for minimum number of samples (copies of a quantum state) required to attain a prescribed accuracy (measured by error variance) for scalar parameters estimation using unbiased estimators under quantum local differential privacy for qubits. Particularly, the best-case (optimal) scenario is considered by minimizing the sample complexity over all differentially-private channels; the worst-case channels can be arbitrarily uninformative and render the problem ill-defined. In the small privacy budget regime, i.e., 1, the sample complexity scales as (-2). This bound matches that of classical parameter estimation under local differential privacy. The lower bound however loosens in the large privacy budget regime, i.e., 1. The upper bound for the minimum number of samples is generalized to qudits (with dimension d) resulting in sample complexity of O(d-2).This paper presents tight upper and lower bounds for minimum number of samples (copies of a quantum state) required to attain a prescribed accuracy (measured by error variance) for scalar parameters estimation using unbiased estimators under quantum local differential privacy for qubits. Particularly, the best-case (optimal) scenario is considered by minimizing the sample complexity over all differentially-private channels; the worst-case channels can be arbitrarily uninformative and render the problem ill-defined. In the small privacy budget regime, i.e., 1, the sample complexity scales as (-2). This bound matches that of classical parameter estimation under local differential privacy. The lower bound however loosens in the large privacy budget regime, i.e., 1. The upper bound for the minimum number of samples is generalized to qudits (with dimension d) resulting in sample complexity of O(d-2).

arXiv:2501.14184IEEE Control Systems LettersJan 1, 20250 citations

Sparsity-dependent Complexity Lower Bound of Quantum Linear System Solvers

Hitomi Mori, Yuta Kikuchi, Marcello Benedetti +1 more

Quantum linear system (QLS) solvers are a fundamental class of quantum algorithms used in many potential quantum computing applications, including machine learning and solving differential equations. The performance of quantum algorithms is often measured by their query complexity, which quantifies the number of oracle calls required to access the input. The main parameters determining the complexity of QLS solvers are the condition number $κ$ and sparsity $s$ of the linear system, and the target error $ε$ . To date, the best known query-complexity lower bound is $Ω(κ\log(1/ε))$ , which establishes the optimality of the most recent QLS solvers. The original proof of this lower bound is attributed to Harrow and Kothari, but their result is unpublished. Furthermore, when discussing a more general lower bound including the sparsity $s$ of the linear system, it has become folklore that it should read as $Ω( κ\sqrt{s}\log(1/ε))$ . In this work, we establish the rigorous lower bound capturing the sparsity dependence of QLS. We prove the lower bound of $Ω(κ\sqrt{s})$ for any quantum algorithm that solves QLS with constant error. While the dependence on all parameters $κ,s,ε$ remains an open problem, our result provides a crucial stepping stone toward the complete characterization of QLS complexity.Quantum linear system (QLS) solvers are a fundamental class of quantum algorithms used in many potential quantum computing applications, including machine learning and solving differential equations. The performance of quantum algorithms is often measured by their query complexity, which quantifies the number of oracle calls required to access the input. The main parameters determining the complexity of QLS solvers are the condition number $κ$ and sparsity $s$ of the linear system, and the target error $ε$. To date, the best known query-complexity lower bound is $Ω(κ\log(1/ε))$, which establishes the optimality of the most recent QLS solvers. The original proof of this lower bound is attributed to Harrow and Kothari, but their result is unpublished. Furthermore, when discussing a more general lower bound including the sparsity $s$ of the linear system, it has become folklore that it should read as $Ω( κ\sqrt{s}\log(1/ε))$. In this work, we establish the rigorous lower bound capturing the sparsity dependence of QLS. We prove the lower bound of $Ω(κ\sqrt{s})$ for any quantum algorithm that solves QLS with constant error. While the dependence on all parameters $κ,s,ε$ remains an open problem, our result provides a crucial stepping stone toward the complete characterization of QLS complexity.

quant-pharXiv:2601.16697Quantum Science and TechnologyJan 26, 20260 citations

Towards a Geometrization of Quantum Complexity and Chaos

Davide Rattacaso, Patrizia Vitale, Alioscia Hamma

arXiv:2107.06557Lecture notes in computer scienceJan 1, 20210 citations

The Price of π: Why Finite Quantum Data Cannot Forge a Perfect Sphere.

Marcelo Esteban Paz

We derive a fundamental operational limit on the reconstruction of smooth cur-ved geometry from finite quantum data. Leveraging Wang’s recent sample comple-xity lower bound for estimating quantum functionals (arXiv:2608.02600v1), and theidentity I(A : B) = 2S(ρA) for pure states, we show that the reconstruction of aperfect sphere S2 from an emergent geometry model requires an infinite number ofsamples.Specifically, any finitely-sampled emergent geometry deviates from the perfectsphere by at least di $\Theta\left(\frac{1}{\sqrt{n}\log_2 d}\right)$ implying that the constant π itself cannot be exactly recovered with finite resources.This result provides a rigorous bridge between quantum information theory(sample complexity), differential geometry (curvature and area), and models ofemergent spacetime (AdS/CFT and relational realism). We explicitly delineate thecontinuity assumptions required for this inheritance, thus framing the transitionfrom discrete correlations to continuous geometry as a rigorous inverse problem.We derive a fundamental operational limit on the reconstruction of smooth cur-ved geometry from finite quantum data. Leveraging Wang’s recent sample comple-xity lower bound for estimating quantum functionals (arXiv:2608.02600v1), and theidentity I(A : B) = 2S(ρA) for pure states, we show that the reconstruction of aperfect sphere S2 from an emergent geometry model requires an infinite number ofsamples.Specifically, any finitely-sampled emergent geometry deviates from the perfectsphere by at least di $\Theta\left(\frac{1}{\sqrt{n}\log_2 d}\right)$ implying that the constant π itself cannot be exactly recovered with finite resources.This result provides a rigorous bridge between quantum information theory(sample complexity), differential geometry (curvature and area), and models ofemergent spacetime (AdS/CFT and relational realism). We explicitly delineate thecontinuity assumptions required for this inheritance, thus framing the transitionfrom discrete correlations to continuous geometry as a rigorous inverse problem.

Aug 5, 20260 citations

Complexity Lower Bounds for Quantum Circuits

Mika Hirvensalo

Springer eBooksJan 1, 20010 citations

κ

and sparsity

s

of the linear system, and the target error

ε

. To date, the best known query-complexity lower bound is

Ω(κ\log(1/ε))

, which establishes the optimality of the most recent QLS solvers. The original proof of this lower bound is attributed to Harrow and Kothari, but their result is unpublished. Furthermore, when discussing a more general lower bound including the sparsity

s

of the linear system, it has become folklore that it should read as

Ω( κ\sqrt{s}\log(1/ε))

. In this work, we establish the rigorous lower bound capturing the sparsity dependence of QLS. We prove the lower bound of

Ω(κ\sqrt{s})

for any quantum algorithm that solves QLS with constant error. While the dependence on all parameters

κ,s,ε

remains an open problem, our result provides a crucial stepping stone toward the complete characterization of QLS complexity.

\Theta\left(\frac{1}{\sqrt{n}\log_2 d}\right)

implying that the constant π itself cannot be exactly recovered with finite resources.This result provides a rigorous bridge between quantum information theory(sample complexity), differential geometry (curvature and area), and models ofemergent spacetime (AdS/CFT and relational realism). We explicitly delineate thecontinuity assumptions required for this inheritance, thus framing the transitionfrom discrete correlations to continuous geometry as a rigorous inverse problem.