In 2004, Aaronson introduced the complexity class $\mathsf{ PostBQP}$ ($\mathsf{ BQP}$ with postselection) and showed that it is equal to $\mathsf{ PP}$. Following their line of work, we introduce two new complexity classes. The first, $\mathsf{ CorrBQP}$, is a modification of $\mathsf{ BQP}$ which has the power to perform correlated measurements, i.e. measurements that output the same value across a partition of registers. The second, $\mathsf{ MajBQP}$, augments $\mathsf{ BQP}$ with the ability to collapse a register to its most likely measurement outcome. Specifically, we consider two variants, $\mathsf{ MajBQP}$ and $\mathsf{ AdMajBQP}$, where the latter may perform intermediate measurements. We exactly characterize the computational power of the models, $\mathsf{ CorrBQP} = \mathsf{ AdMajBQP} = \mathsf{ BPP}^{ \mathsf{ PP}}$ and $\mathsf{ MajBQP} = \mathsf{ P}^{ \mathsf{ PP}}$. In fact, we show that other metaphysical modifications of $\mathsf{ BQP}$, such as $\mathsf{ CBQP}$ (i.e. $\mathsf{ BQP}$ with the ability to clone arbitrary quantum states), are also equal to $\mathsf{ BPP}^{ \mathsf{ PP}}$. We show that $\mathsf{ CorrBQP}$ and $\mathsf{ MajBQP}$ are self-low with respect to classically-accessible queries. In contrast, if they were self-low under quantumly-accessible queries, the counting hierarchy would collapse. Furthermore, we introduce a variant of rational degree that lower-bounds the query complexity of $\mathsf{ BPP}^{ \mathsf{ PP}}$. Lastly, we extend the adversary lower-bounding technique to $\mathsf{ AdPDQP}$, $\mathsf{ BQP}$ with the ability to sample the current state of an algorithm with collapsing it and adapt the computation based on the samples.
Categories: cs.CC quant-ph