This work gives the first near optimal algorithm for learning $n$-qubit $k$-sparse pure quantum states, obtaining fidelity at least $1-\varepsilon$ with high probability using $\tilde{O}(k/\varepsilon)$ copies of the state and $\tilde{O}(kn/\varepsilon)$ time.
Abstract
We study the problem of tomography for $k$-sparse quantum states. In contrast to classical distribution learning, where tight sample and time complexity bounds in terms of support size are well understood, no non-trivial bounds were previously shown for this problem. We give the first near optimal algorithm for learning $n$-qubit $k$-sparse pure quantum states, obtaining fidelity at least $1-\varepsilon$ with high probability using $\tilde{O}(k/\varepsilon)$ copies of the state and $\tilde{O}(kn/\varepsilon)$ time. Both bounds are optimal up to polylogarithmic factors. As an implication, we also obtain an algorithm with near optimal $\tilde{O}(kr/\varepsilon)$ sample complexity for learning $k$-sparse rank-$r$ mixed states, via the random purification channel technique. Obtaining time complexity nearly matching the sample complexity, for $r>1$, remains an important open question.
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 matr...
Low-energy estimation and state preparation for general $k$-local Hamiltonians are fundamental challenges in quantum complexity theory. Buhrman et al.~ [BGLGST, PRL 2025] recently broke the natural Grover bound $O^\ast(2^{n/2})$ for both problems, with the improvement depending on the relative accuracy $\varepsilon$ an...
Sevag Gharibian, François Le Gall, Ranitha Mataraarachchi et al.· 0 citations
We study tomography for quantum channels with input dimension $d_1$, output dimension $d_2$, and Kraus rank at most $r$, to within diamond norm error $\varepsilon$, using adaptive experiments that retain no quantum memory between channel queries. - For quantum channels whose non-zero Choi eigenvalues are bounded below...
We give collective tomography protocols for quantum states and channels with known symmetries, using random purification and dilation to reduce learning to pure-state estimation. For states commuting with a compact-group representation with multiplicities $m_\lambda$, the optimal copy complexity is $\Theta((\sum_\lambd...
Satoshi Yoshida, K. Okigami, P. M. Posta et al.· 0 citations
We study state tomography when each measurement acts on at most $k$ fresh copies and no quantum memory is retained between blocks. We prove a lower bound matching the upper bound in [arXiv:2510.07788]. Thus the copy complexity of estimating an arbitrary $d$-dimensional state to trace distance $\epsilon$ is, up to absol...
U. Keskin, Jason Luo, Mahbod Majid et al.· 2 citations· ⚡1
We study the query complexity of testing quantum juntas. Given an unknown $n$-qubit unitary or quantum channel, the goal is to decide whether it acts nontrivially on at most $k$ qubits or is $\varepsilon$-far from every such operation. For unitaries, we consider the forward-only model, where the tester has access to $U...
Jing Bao, Minbo Gao, Peng-Hui Yao· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
