Quantum zero-error algorithms cannot be composed

✍ Scribed by Harry Buhrman; Ronald de Wolf

• Book ID: 104136958
• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 94 KB
• Volume: 87
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(03)00254-0

✦ Synopsis

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.