Improved Quantum data analysis

DOI10.1145/3406325.3451109MaRDI QIDQ6065262zbMATH OpenOpenAlexWikidataFDO

Authors Costin Bădescu, Ryan O'Donnell

Publication date 14 November 2023

Published in Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2011.10908

zbMATH Keywords

quantum sample complexityshadow tomography

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: We provide more sample-efficient versions of some basic routines in quantum data analysis, along with simpler proofs. Particularly, we give a quantum "Threshold Search" algorithm that requires only $O((lo{g}^{2}m)/epsilo{n}^2)$ samples of a $d$-dimensional state $ho$. That is, given observables $0le{A}_1,A_2,\mathrm{...},A_{m}le1$ such that $mathrmtr(ho{A}_i)ge1/2$ for at least one $i$, the algorithm finds $j$ with $mathrmtr(ho{A}_j)ge1/2-epsilon$. As a consequence, we obtain a Shadow Tomography algorithm requiring only $ildeO((lo{g}^{2}m)(logd)/epsilo{n}^4)$ samples, which simultaneously achieves the best known dependence on each parameter $m$, $d$, $epsilon$. This yields the same sample complexity for quantum Hypothesis Selection among $m$ states; we also give an alternative Hypothesis Selection method using $ildeO((lo{g}^{3}m)/epsilo{n}^2)$ samples.

Cited in

(9)

• Quantum process tomography on cloud-accessible quantum computing platforms
• Classical shadows meet quantum optimal mass transport
• Quantum event learning and gentle random measurements
• Lower bounds for learning quantum states with single-copy measurements
• Quantum data sketches
• Efficient quantum pseudorandomness from Hamiltonian phase states
• Quantum approximate k-minimum finding
• Consumable data via quantum communication
• Consumable data via quantum communication

This page was built for publication: Improved Quantum data analysis

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6065262)