Quantum Zero-Error Algorithms Cannot be Composed

2026-07-072026-07-07http://salesiana.dossiersoluciones.com/handle/123456789/90626We 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.7 pages LaTeX. 2nd version slightly rewrittenQuantum PhysicsComputational ComplexityQuantum Zero-Error Algorithms Cannot be Composedtext