Quantum Zero-Error Algorithms Cannot be Composed
| dc.creator | Buhrman, Harry | |
| dc.creator | de Wolf, Ronald | |
| dc.date | 2002-11-06 | |
| dc.date | 2003-07-05 | |
| dc.date.accessioned | 2026-07-07T06:05:25Z | |
| dc.date.available | 2026-07-07T06:05:25Z | |
| dc.description | We exhibit two black-box problems, both of which have an efficient quantum algorithm with zero-error, yet whose composition does not have an efficient quantum algorithm with zero-error. This shows that quantum zero-error algorithms cannot be composed. In oracle terms, we give a relativized world where ZQP^{ZQP}ZQP, while classically we always have ZPP^{ZPP}=ZPP. | |
| dc.description | 7 pages LaTeX. 2nd version slightly rewritten | |
| dc.identifier | https://arxiv.org/abs/quant-ph/0211029 | |
| dc.identifier | http://arxiv.org/abs/quant-ph/0211029 | |
| dc.identifier | Information Processing Letters, 87(2):79-84, 2003 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/90626 | |
| dc.subject | Quantum Physics | |
| dc.subject | Computational Complexity | |
| dc.title | Quantum Zero-Error Algorithms Cannot be Composed | |
| dc.type | text |