Abstract:We settle the problem of estimating the trace distance and (square root) fidelity between $n$-qubit pure quantum states to within additive error $\varepsilon$, given their independent samples, which was raised as an open question by Wang (IEEE Trans. Inf. Theory 2024). This is achieved by a quantum algorithm with optimal sample complexity $\Theta(1/\varepsilon^2)$, improving the long-standing folklore with sample complexity $O(1/\varepsilon^4)$. At the heart of our algorithm is a samplized phase estimation of the product of two Householder reflections. This is realized by an improved (multi-)samplizer for pure states, through which any quantum query algorithm using $Q$ queries to the reflection operator $I - 2|\psi\rangle\!\langle\psi|$ can be converted to a $\delta$-close (in the diamond norm distance) quantum sample algorithm using $\Theta(Q^2/\delta)$ samples of the state $|\psi\rangle$. This samplizer for pure states is also shown to be optimal.
From: Qisheng Wang [view email]
[v1]
Mon, 28 Oct 2024 16:48:21 UTC (23 KB)
[v2]
Mon, 6 Jul 2026 15:50:32 UTC (23 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。