We study how complexity classes above BQP, such as postBQP, postBQPFP, and SBQP, change if we “Merlinize” them, i.e., if we allow an extra input quantum state (or classical bit string) given by Merlin as witness. Our main results are the following: First, the Merlinized version of postBQP is equal to PSPACE. Second, if the Merlinized postBQP is restricted in such a way that the postselection probability is equal for all witness states, then the class is equal to PP. Finally, the Merlinization does not change the class SBQP.
We consider restricted versions of
postBQP where postselection probabilities can be efficiently calculated by classical or quantum computers. We show that such restricted
postBQP classes are in
AWPP(⊆PP=postBQP). This result suggests that postselecting an event with an exponentially small probability does not necessarily boost
BQP to PP. The best upperbound of
BQP is
AWPP, and therefore restricted
postBQP classes are other examples of complexity classes slightly above
BQP. In [C. M. Lee and J. Barrett, arXiv:1412.8671], it was shown that the computational capacity of a general probabilistic theory which satisfies the tomographic locality is in
AWPP. Our result therefore implies that quantum physics with restricted postselections is an example of a super quantum theory which seems to be outside of their general probabilistic theory but its computational capacity is also in
AWPP. Although it is physically natural to expect that such restricted
postBQP classes are not equivalent to BQP, we show that
UP∩coUP, which is unlikely to be in BQP, is contained in the restricted
postBQP classes. Finally, we also consider another restricted class of
postBQP, where the postselected probability depends only on the size of inputs. We show that this restricted version is contained in
APP, where
AWPP⊆APP⊆PP=postBQP.
The new computational paradigms of quantum computing change the current ideas of what can be efficiently computed. The chapter discusses the theory of quantum complexity classes such as bounderd-error quantum polynomial time (BQP), quantum Merlin-Arthur (QMA), and others, their theoretical foundations, their definition and their relationship with classical complexity classes like P, NP, and PSPACE. The special attention here is on the use of superposition, entanglement and interference to be able to solve problems more efficiently than with classical algorithms using quantum algorithms. The reduction relation, the completeness and separations of quantum complexity classes are discussed, along with some open problems including the quantum-classical separation of computational power. Case studies of important quantum algorithms, relevant to cryptography, optimization, and scientific computing like Shor's factoring algorithm, Grover's search algorithm, and quantum simulation methods follow the classes.
This paper introduces a new technique for removing existential quantifiers over quantum states. Using this technique, we show that there is no way to pack an exponential number of bits into a polynomial-size quantum state, in such a way that the value of any one of those bits can later be proven with the help of a polynomial-size quantum witness. We also show that any problem in QMA with polynomial-size quantum advice, is also in PSPACE with polynomial-size classical advice. This builds on our earlier result that BQP/qpoly sube PP/poly, and offers an intriguing counterpoint to the recent discovery of Raz that QIP/qpoly = ALL. Finally, we show that QCMA/qpoly sube PP/poly and that QMA/rpoly = QMA/poly
This paper introduces a new technique for removing existential quantifiers over quantum states. Using this technique, we show that there is no way to pack an exponential number of bits into a polynomial-size quantum state, in such a way that the value of any one of those bits can later be proven with the help of a polynomial-size quantum witness. We also show that any problem in QMA with polynomial-size quantum advice, is also in PSPACE with polynomial-size classical advice. This builds on our earlier result that BQP/qpoly ⊆ PP/poly, and offers an intriguing counterpoint to the recent discovery of Raz that QIP/qpoly = ALL. Finally, we show that QCMA/qpoly ⊆ PP/poly and that QMA/rpoly = QMA/poly. 1
This paper studies quantum Arthur–Merlin games, which are Arthur–Merlin games in which Arthur and Merlin can perform quantum computations and Merlin can send Arthur quantum information. As in the classical case, messages from Arthur to Merlin are restricted to be strings of uniformly generated random bits. It is proved that for one-message quantum Arthur–Merlin games, which correspond to the complexity class QMA, completeness and soundness errors can be reduced exponentially without increasing the length of Merlin’s message. Previous constructions for reducing error required a polynomial increase in the length of Merlin’s message. Applications of this fact include a proof that logarithmic length quantum certificates yield no increase in power over BQP and a simple proof that
QMA⊆PP. Other facts that are proved include the equivalence of three (or more) message quantum Arthur–Merlin games with ordinary quantum interactive proof systems and some basic properties concerning two-message quantum Arthur–Merlin games.
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 register to its most likely measurement outcome. Specifically, we consider two variants,
MajBQP and
AdMajBQP, where the latter may perform intermediate measurements. We exactly characterize the computational power of the models,
CorrBQP=AdMajBQP=BPPPP and
MajBQP=PPP. 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
BPPPP. We show that
CorrBQP and
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
BPPPP. Lastly, we extend the adversary lower-bounding technique to
AdPDQP,
BQP with the ability to sample the current state of an algorithm with collapsing it and adapt the computation based on the samples.