Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2111.02391 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918217641885696 |
|---|---|
| author | Gavorová, Zuzana |
| author_facet | Gavorová, Zuzana |
| contents | To better understand quantum computation we can search for its limits or no-gos, especially if analogous limits do not appear in classical computation. Classical computation easily implements and extensively employs the addition of two bit strings, so here we study 'quantum addition': the superposition of two quantum states. We prove the impossibility of superposing two unknown states, no matter how many samples of each state are available. The proof uses topology; a quantum algorithm of any sample complexity corresponds to a continuous function, but the function required by the superposition task cannot be continuous by topological arguments. Our result for the first time quantifies the approximation error and the sample complexity $N$ of the superposition task, and it is tight. We present a trivial algorithm with a large approximation error and $N=1$, and the matching impossibility of any smaller approximation error for any $N$. Consequently, our results limit state tomography as a useful subroutine for the superposition. State tomography is useful only in a model that tolerates randomness in the superposed state. The optimal protocol in this random model remains open. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2111_02391 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Topologically driven no-superposing theorem with a tight error bound Gavorová, Zuzana Quantum Physics To better understand quantum computation we can search for its limits or no-gos, especially if analogous limits do not appear in classical computation. Classical computation easily implements and extensively employs the addition of two bit strings, so here we study 'quantum addition': the superposition of two quantum states. We prove the impossibility of superposing two unknown states, no matter how many samples of each state are available. The proof uses topology; a quantum algorithm of any sample complexity corresponds to a continuous function, but the function required by the superposition task cannot be continuous by topological arguments. Our result for the first time quantifies the approximation error and the sample complexity $N$ of the superposition task, and it is tight. We present a trivial algorithm with a large approximation error and $N=1$, and the matching impossibility of any smaller approximation error for any $N$. Consequently, our results limit state tomography as a useful subroutine for the superposition. State tomography is useful only in a model that tolerates randomness in the superposed state. The optimal protocol in this random model remains open. |
| title | Topologically driven no-superposing theorem with a tight error bound |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2111.02391 |