A List of Complexity Bounds for Property Testing by Quantum Sample-to-Query Lifting
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909938587009024 |
|---|---|
| author | Chen, Kean Wang, Qisheng Zhang, Zhicheng |
| author_facet | Chen, Kean Wang, Qisheng Zhang, Zhicheng |
| contents | Quantum sample-to-query lifting, a relation between quantum sample complexity and quantum query complexity presented in Wang and Zhang (SIAM J. Comput. 2025), was significantly strengthened by Tang, Wright, and Zhandry (2025) to the case of state-preparation oracles. In this paper, we compile a list of quantum lower and upper bounds for property testing that are obtained by quantum sample-to-query lifting. The problems of interest include testing properties of probability distributions and quantum states, such as entropy and closeness. This collection contains new results, as well as new proofs of known bounds. In total, we present 49 complexity bounds, where 41 are new and 18 are (near-)optimal. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_01971 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A List of Complexity Bounds for Property Testing by Quantum Sample-to-Query Lifting Chen, Kean Wang, Qisheng Zhang, Zhicheng Quantum Physics Computational Complexity Information Theory Quantum sample-to-query lifting, a relation between quantum sample complexity and quantum query complexity presented in Wang and Zhang (SIAM J. Comput. 2025), was significantly strengthened by Tang, Wright, and Zhandry (2025) to the case of state-preparation oracles. In this paper, we compile a list of quantum lower and upper bounds for property testing that are obtained by quantum sample-to-query lifting. The problems of interest include testing properties of probability distributions and quantum states, such as entropy and closeness. This collection contains new results, as well as new proofs of known bounds. In total, we present 49 complexity bounds, where 41 are new and 18 are (near-)optimal. |
| title | A List of Complexity Bounds for Property Testing by Quantum Sample-to-Query Lifting |
| topic | Quantum Physics Computational Complexity Information Theory |
| url | https://arxiv.org/abs/2512.01971 |