Quantum Zero-Error Algorithms Cannot be Composed

摘要

We exhibit two black-box problems, both of which have an efficient quantumalgorithm with zero-error, yet whose composition does not have an efficientquantum algorithm with zero-error. This shows that quantum zero-erroralgorithms cannot be composed. In oracle terms, we give a relativized worldwhere ZQP^{ZQP}\=ZQP, while classically we always have ZPP^{ZPP}=ZPP.