Quantum Non-Identical Mean Estimation: Efficient Algorithms and Fundamental Limits
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_ | 1866909207875289088 |
|---|---|
| author | Hu, Jiachen Li, Tongyang Wang, Xinzhao Xue, Yecheng Zhang, Chenyi Zhong, Han |
| author_facet | Hu, Jiachen Li, Tongyang Wang, Xinzhao Xue, Yecheng Zhang, Chenyi Zhong, Han |
| contents | We systematically investigate quantum algorithms and lower bounds for mean estimation given query access to non-identically distributed samples. On the one hand, we give quantum mean estimators with quadratic quantum speed-up given samples from different bounded or sub-Gaussian random variables. On the other hand, we prove that, in general, it is impossible for any quantum algorithm to achieve quadratic speed-up over the number of classical samples needed to estimate the mean $μ$, where the samples come from different random variables with mean close to $μ$. Technically, our quantum algorithms reduce bounded and sub-Gaussian random variables to the Bernoulli case, and use an uncomputation trick to overcome the challenge that direct amplitude estimation does not work with non-identical query access. Our quantum query lower bounds are established by simulating non-identical oracles by parallel oracles, and also by an adversarial method with non-identical oracles. Both results pave the way for proving quantum query lower bounds with non-identical oracles in general, which may be of independent interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_12838 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Quantum Non-Identical Mean Estimation: Efficient Algorithms and Fundamental Limits Hu, Jiachen Li, Tongyang Wang, Xinzhao Xue, Yecheng Zhang, Chenyi Zhong, Han Quantum Physics Computation We systematically investigate quantum algorithms and lower bounds for mean estimation given query access to non-identically distributed samples. On the one hand, we give quantum mean estimators with quadratic quantum speed-up given samples from different bounded or sub-Gaussian random variables. On the other hand, we prove that, in general, it is impossible for any quantum algorithm to achieve quadratic speed-up over the number of classical samples needed to estimate the mean $μ$, where the samples come from different random variables with mean close to $μ$. Technically, our quantum algorithms reduce bounded and sub-Gaussian random variables to the Bernoulli case, and use an uncomputation trick to overcome the challenge that direct amplitude estimation does not work with non-identical query access. Our quantum query lower bounds are established by simulating non-identical oracles by parallel oracles, and also by an adversarial method with non-identical oracles. Both results pave the way for proving quantum query lower bounds with non-identical oracles in general, which may be of independent interest. |
| title | Quantum Non-Identical Mean Estimation: Efficient Algorithms and Fundamental Limits |
| topic | Quantum Physics Computation |
| url | https://arxiv.org/abs/2405.12838 |