Quantum Zero-Error Algorithms Cannot be Composed
<|reference_start|>Quantum Zero-Error Algorithms Cannot be Composed: 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.<|reference_end|>
@article{buhrman2002quantum,
    title={Quantum Zero-Error Algorithms Cannot be Composed},
    author={Harry Buhrman and Ronald de Wolf (CWI, Amsterdam)},
    journal={Information Processing Letters, 87(2):79-84, 2003},
    year={2002},
    archivePrefix={arXiv},
    eprint={quant-ph/0211029},
    primaryClass={quant-ph cs.CC}
}