REVIEW 1 cited by
Quantum Zero-Error Algorithms Cannot be Composed
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
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.
Forward citations
Cited by 1 Pith paper
-
Composing Quantum Algorithms
A survey explaining that bounded-error quantum algorithms can be composed without the log factor that classical randomized composition requires, using the transducer model.
Discussion (0). Continue with ORCID to comment.