QMA error reduction

ID: qma-error-reduction

Starting from completeness and soundness , run an odd number of parallel copies and take majority. The QMA parallel repetition with entangled witnesses argument proves soundness for arbitrary repeated witnesses. Exponential Markov's inequality gives majority error at most . Hence copies suffice for error , with polynomial overhead when the target error is inverse-polynomial or exponentially small in input length.

New to topics? Read the docs here!