Quantum Zero-Error Algorithms Cannot be Composed
classification
🪐 quant-ph
cs.CC
keywords
quantumzero-erroralgorithmalgorithmscannotcomposedefficientalways
read the original abstract
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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.