David Miloschewsky

In 2004, Aaronson introduced the complexity class PostBQP~(BQP with postselection) and showed that it is equal to PP. Following their line of work, we introduce two new complexity classes. The first, CorrBQP, is a modification of BQP which has the power to perform correlated measurements, i.e. measurements that output the same value across a partition of registers. The second, MajBQP, augments BQP with the ability to collapse a qubit to its most likely outcome. We exactly characterize the models, showing MajBQP = CorrBQP = BPP^PP = P^PP. This characterization allows us to obtain a derandomization of BPP with respect to a PP oracle. In fact, we show that other metaphysical modifications of BQP, such as CBQP (i.e. BQP with the ability to clone arbitrary quantum states), are also equal to P^PP. We show that CorrBQP is self-low with respect to classical queries. In contrast, if it were self-low under quantum queries, the counting hierarchy (CH) would collapse to P^PP. Furthermore, we introduce a variant of rational degree that lower-bounds the query complexity of P^PP. Lastly, we extend the adversary lower-bounding technique to AdPDQP, BQP with the ability to sample the current state of the algorithm and adapt the computation based on the samples.