Sample-Optimal Quantum Estimators for Pure-State Trace Distance and Fidelity via Samplizer
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912090156957696 |
|---|---|
| author | Wang, Qisheng Zhang, Zhicheng |
| author_facet | Wang, Qisheng Zhang, Zhicheng |
| contents | Trace distance and infidelity (induced by square root fidelity), as basic measures of the closeness of quantum states, are commonly used in quantum state discrimination, certification, and tomography. However, the sample complexity for their estimation still remains open. In this paper, we solve this problem for pure states. We present a quantum algorithm that estimates the trace distance and square root fidelity between pure states to within additive error $\varepsilon$, given sample access to their identical copies. Our algorithm achieves the optimal sample complexity $Θ(1/\varepsilon^2)$, improving the long-standing folklore $O(1/\varepsilon^4)$. Our algorithm is composed of a samplized phase estimation of the product of two Householder reflections. Notably, an improved (multi-)samplizer for pure states is used as an algorithmic tool in our construction, through which any quantum query algorithm using $Q$ queries to the reflection operator about a pure state $|ψ\rangle$ can be converted to a $δ$-close (in the diamond norm) quantum sample algorithm using $Θ(Q^2/δ)$ samples of $|ψ\rangle$. This samplizer for pure states is shown to be optimal. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_21201 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Sample-Optimal Quantum Estimators for Pure-State Trace Distance and Fidelity via Samplizer Wang, Qisheng Zhang, Zhicheng Quantum Physics Computational Complexity Data Structures and Algorithms Information Theory Trace distance and infidelity (induced by square root fidelity), as basic measures of the closeness of quantum states, are commonly used in quantum state discrimination, certification, and tomography. However, the sample complexity for their estimation still remains open. In this paper, we solve this problem for pure states. We present a quantum algorithm that estimates the trace distance and square root fidelity between pure states to within additive error $\varepsilon$, given sample access to their identical copies. Our algorithm achieves the optimal sample complexity $Θ(1/\varepsilon^2)$, improving the long-standing folklore $O(1/\varepsilon^4)$. Our algorithm is composed of a samplized phase estimation of the product of two Householder reflections. Notably, an improved (multi-)samplizer for pure states is used as an algorithmic tool in our construction, through which any quantum query algorithm using $Q$ queries to the reflection operator about a pure state $|ψ\rangle$ can be converted to a $δ$-close (in the diamond norm) quantum sample algorithm using $Θ(Q^2/δ)$ samples of $|ψ\rangle$. This samplizer for pure states is shown to be optimal. |
| title | Sample-Optimal Quantum Estimators for Pure-State Trace Distance and Fidelity via Samplizer |
| topic | Quantum Physics Computational Complexity Data Structures and Algorithms Information Theory |
| url | https://arxiv.org/abs/2410.21201 |