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 a “classical physical analogue” of these results, and show that a restricted version of BPPpath contains UP ∩ coUP and is contained in WAPP.
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 a “classical physical analogue” of these results, and show that a restricted version of BPPpath contains UP ∩ coUP and is contained in WAPP.
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.
From the general difficulty of simulating quantum systems using classical systems, and in particular \nthe existence of an efficient quantum algorithm for factoring, it is likely that quantum computation is \nintrinsically more powerful than classical computation. At present, the best upper bound known for \nthe power of quantum computation is that BQP AWPP ⊆ , where AWPP is a classical complexity \nclass (known to be included in PP, hence PSPACE). This work investigates limits on computational \npower that are imposed by simple physical, or information theoretic, principles. To this end, we define \na circuit-based model of computation in a class of operationally-defined theories more general than \nquantum theory, and ask: what is the minimal set of physical assumptions under which the above \ninclusions still hold? We show that given only an assumption of tomographic locality (roughly, that \nmultipartite states and transformations can be characterized by local measurements), efficient \ncomputations are contained in AWPP. This inclusion still holds even without assuming a basic notion \nof causality (where the notion is, roughly, that probabilities for outcomes cannot depend on future \nmeasurement choices). Following Aaronson, we extend the computational model by allowing postselection \non measurement outcomes. Aaronson showed that the corresponding quantum complexity \nclass, PostBQP, is equal to PP. Given only the assumption of tomographic locality, the inclusion in \nPP still holds for post-selected computation in general theories. Hence in a world with post-selection, \nquantum theory is optimal for computation in the space of all operational theories. We then consider \nwhether one can obtain relativized complexity results for general theories. It is not obvious how to \ndefine a sensible notion of a computational oracle in the general framework that reduces to the \nstandard notion in the quantum case. Nevertheless, it is possible to define computation relative to a \n‘classical oracle’. Then, we show there exists a classical oracle relative to which efficient computation in \nany theory satisfying the causality assumption does not include NP.
Abstract There is good evidence that quantum computers are more powerful than classical computers, and that various simple modifications of quantum theory yield computational power that is dramatically greater still. However, these modifications also violate fundamental physical principles. This raises the question of whether there exists a physical theory, allowing computation more powerful than quantum, but which still respects those fundamental physical principles. Prior work by two of us introduced this question within a suitable framework for theories that make good operational sense, and showed that in any theory satisfying tomographic locality, the class of problems that can be solved efficiently is contained in the complexity class AWPP. Here, we show that this bound is tight, in the sense that there exists a theory, satisfying tomographic locality, as well as a basic principle of causality, which can efficiently decide everything in AWPP. Hence this theory can efficiently simulate any computation in this framework, including quantum computation.
We explore the space "just above" BQP by defining a complexity class naCQP (non-adaptive Collapse-free Quantum Polynomial time) which is larger than BQP but does not contain NP relative to an oracle. The class is defined by imagining that quantum computers can perform (non-adaptive) measurements that do not collapse the wavefunction. This non-physical model of computation can efficiently solve problems such as Graph Isomorphism and Approximate Shortest Vector which are believed to be intractable for quantum computers. Furthermore, it can search an unstructured N-element list in Õ(N1/3) time, but no faster than Ω(N1/4), and hence cannot solve NP-hard problems in a black box manner. In short, this model of computation is more powerful than standard quantum computation, but only slightly so. This is surprising as most modifications of BQP increase the power of quantum computation to NP or beyond.
Quantum computers are widely believed have an advantage over classical computers, and some have even published some empirical evidence that this is the case. However, these publications do not include a rigorous proof of this advantage, which would have to minimally state that the class of problems decidable by a quantum computer in polynomial time, BQP, contains problems that are not in the class of problems decidable by a classical computer with similar time bounds, P. Here, I provide the proof of a stronger result that implies this result: BQP contains problems that lie beyond the much larger classical computing class NP. This proves that quantum computation is able to efficiently solve problems which are far beyond the capabilities of classical computers.
One can fix the randomness used by a randomized algorithm, but there is no analogous notion of fixing the quantumness used by a quantum algorithm. Underscoring this fundamental difference, we show that, in the black-box setting, the behavior of quantum polynomial-time (BQP) can be remarkably decoupled from that of classical complexity classes like NP. Specifically: -There exists an oracle relative to which NPBQP⊂BQPPH, resolving a 2005 problem of Fortnow. As a corollary, there exists an oracle relative to which P=NP but BQP=QCMA. -Conversely, there exists an oracle relative to which BQPNP⊂PHBQP. -Relative to a random oracle, PP=PostBQP is not contained in the "QMA hierarchy" QMAQMAQMA⋯. -Relative to a random oracle, Σk+1P⊂BQPΣkP for every k. -There exists an oracle relative to which BQP=P#P and yet PH is infinite. -There exists an oracle relative to which P=NP=BQP=P#P. To achieve these results, we build on the 2018 achievement by Raz and Tal of an oracle relative to which BQP⊂PH, and associated results about the Forrelation problem. We also introduce new tools that might be of independent interest. These include a "quantum-aware" version of the random restriction method, a concentration theorem for the block sensitivity of AC0 circuits, and a (provable) analogue of the Aaronson-Ambainis Conjecture for sparse oracles.