Quantum interpretations of AWPP and APP

Abstract

AWPP is a complexity class introduced by Fenner, Fortnow, Kurtz, and Li, which is defined using GapP functions. Although it is an important class as the best upperbound of BQP, its definition seems to be somehow artificial, and therefore it would be better if we have some "physical interpretation" of AWPP. Here we provide a quantum physical interpretation of AWPP: we show that AWPP is equal to the class of problems efficiently solved by a quantum computer with the ability of postselecting an event whose probability is close to an FP function. This result is applied to also obtain a quantum physical interpretation of APP. In addition, we consider "classical physical analogue" of these results, and show that a restricted version of \({\rm BPP}_{\rm path}\) contains \({\rm UP}\cap{\rm coUP}\) and is contained in WAPP.