Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1502.00067 · Quantum Information and Computation

Quantum interpretations of AWPP and APP

Tomoyuki Morimae, Harumichi Nishimura

Published Apr 1, 2016• 4 citations
arXivHTMLPDF

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 a “classical physical analogue” of these results, and show that a restricted version of BPPpath contains UP ∩ coUP and is contained in WAPP.

DOI
10.26421/qic16.5-6-6

Related papers

Power of quantum computing with restricted postselections.

Tomoyuki Morimae, Harumichi Nishimura

We consider restricted versions of ${\rm postBQP}$ where postselection probabilities can be efficiently calculated by classical or quantum computers. We show that such restricted ${\rm postBQP}$ classes are in ${\rm AWPP}(\subseteq{\rm PP}={\rm postBQP})$. This result suggests that postselecting an event with an exponentially small probability does not necessarily boost ${\rm BQP}$ to PP. The best upperbound of ${\rm BQP}$ is ${\rm AWPP}$, and therefore restricted ${\rm postBQP}$ classes are other examples of complexity classes slightly above ${\rm 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 ${\rm 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 ${\rm AWPP}$. Although it is physically natural to expect that such restricted ${\rm postBQP}$ classes are not equivalent to BQP, we show that ${\rm UP}\cap{\rm coUP}$, which is unlikely to be in BQP, is contained in the restricted ${\rm postBQP}$ classes. Finally, we also consider another restricted class of ${\rm postBQP}$, where the postselected probability depends only on the size of inputs. We show that this restricted version is contained in ${\rm APP}$, where ${\rm AWPP}\subseteq{\rm APP}\subseteq{\rm PP}={\rm postBQP}$.

•Jan 31, 2015•1 citation

Quantum Complexity Classes

Tereza Tušarová

In our thesis, we try to shed more light onto the complexity of quantum complexity classes by refining the related part of the hierarchy. First, we review the basic concepts of quantum computing in general. Then, inspired by BQP, we define new complexity classes. They are placed between BPP and PSPACE. We show that they incorporate the current important quantum algorithms. Furthermore, the importance of the unitarity constraint given by quantum mechanics is revealed. Without this requirement, we naturally arrive at the class AWPP, which was up to now thought to be just an artificially defined class. We hope that some of our newly defined classes could find their use in proving results about BQP.

arXiv:cs/0409051•Sep 26, 2004•3 citations

Bounds on computation from physical principles

Ciarán M. Lee

The advent of quantum computing has challenged classical conceptions of which problems are efficiently solvable in our physical world. This raises the general question of what broad relationships exist between physical principles and computation. The current thesis explores this question within the operationally-defined framework of generalised probabilistic theories. In particular, we investigate the limits on computational power imposed by simple physical principles. At present, the best known upper bound on the power of quantum computers is that BQP is contained in AWPP, where AWPP is a classical complexity class contained in PP. We define a circuit-based model of computation in the above mentioned operational framework and show that in theories where local measurements suffice for tomography, efficient computations are also contained in AWPP. Moreover, we explicitly construct a theory in which the class of efficiently solvable problems exactly equals AWPP, showing this containment to be tight. We also investigate how simple physical principles bound the power of computational paradigms which combine computation and communication in a non-trivial fashion, such as interactive proof systems. Additionally, we show how some of the essential components of computational algorithms arise from certain natural physical principles. We use these results to investigate the relationship between interference behaviour and computational power, demonstrating that non-trivial interference behaviour is a general resource for post-classical computation. We then investigate whether post-quantum interference is a resource for post-quantum computation. Sorkin has defined a hierarchy of possible post-quantum interference behaviours where, informally, the order in the hierarchy corresponds to the number of paths that have an irreducible interaction in a multi-slit experiment. In quantum theory, at most pairs of paths can ever interact in a fundamental way. We consider how Grover's speed-up depends on the order of interference in a theory, and show that, surprisingly, the quadratic lower bound holds regardless of the order of interference.

•Jan 1, 2017•4 citations

A new sibling of BQP

Tereza Tušarová

We present a new quantum complexity class, called MQ^2, which is contained in AWPP. This class has a compact and simple mathematical definition, involving only polynomial-time computable functions and a unitarity condition. It contains both Deutsch-Jozsa's and Shor's algorithm, while its relation to BQP is unknown. This shows that in the complexity class hierarchy, BQP is not an extraordinary isolated island, but has ''siblings'' which as well can solve prime-factorization.

arXiv:cs/0507057•Jul 21, 2005•0 citations

The computational landscape of general physical theories

Jonathan Barrett, Niel de Beaudrap, Matty J. Hoban +1 more

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.

arXiv:1702.08483•npj Quantum Information•May 20, 2019•41 citations

Quantum computing, postselection, and probabilistic polynomial-time

Scott Aaronson

I study the class of problems efficiently solvable by a quantum computer, given the ability to ‘postselect’ on the outcomes of measurements. I prove that this class coincides with a classical complexity class called PP, or probabilistic polynomial-time. Using this result, I show that several simple changes to the axioms of quantum mechanics would let us solve PP-complete problems efficiently. The result also implies, as an easy corollary, a celebrated theorem of Beigel, Reingold and Spielman that PP is closed under intersection, as well as a generalization of that theorem due to Fortnow and Reingold. This illustrates that quantum computing can yield new and simpler proofs of major results about classical computation.

arXiv:quant-ph/0412187•Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences•Sep 5, 2005•360 citations
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{\rm postBQP}postBQP where postselection probabilities can be efficiently calculated by classical or quantum computers. We show that such restricted postBQP{\rm postBQP}postBQP classes are in AWPP(⊆PP=postBQP){\rm AWPP}(\subseteq{\rm PP}={\rm postBQP})AWPP(⊆PP=postBQP). This result suggests that postselecting an event with an exponentially small probability does not necessarily boost BQP{\rm BQP}BQP to PP. The best upperbound of BQP{\rm BQP}BQP is AWPP{\rm AWPP}AWPP, and therefore restricted postBQP{\rm postBQP}postBQP classes are other examples of complexity classes slightly above BQP{\rm BQP}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{\rm AWPP}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{\rm AWPP}AWPP. Although it is physically natural to expect that such restricted postBQP{\rm postBQP}postBQP classes are not equivalent to BQP, we show that UP∩coUP{\rm UP}\cap{\rm coUP}UP∩coUP, which is unlikely to be in BQP, is contained in the restricted postBQP{\rm postBQP}postBQP classes. Finally, we also consider another restricted class of postBQP{\rm postBQP}postBQP, where the postselected probability depends only on the size of inputs. We show that this restricted version is contained in APP{\rm APP}APP, where AWPP⊆APP⊆PP=postBQP{\rm AWPP}\subseteq{\rm APP}\subseteq{\rm PP}={\rm postBQP}AWPP⊆APP⊆PP=postBQP.
In our thesis, we try to shed more light onto the complexity of quantum complexity classes by refining the related part of the hierarchy. First, we review the basic concepts of quantum computing in general. Then, inspired by BQP, we define new complexity classes. They are placed between BPP and PSPACE. We show that they incorporate the current important quantum algorithms. Furthermore, the importance of the unitarity constraint given by quantum mechanics is revealed. Without this requirement, we naturally arrive at the class AWPP, which was up to now thought to be just an artificially defined class. We hope that some of our newly defined classes could find their use in proving results about BQP.
The advent of quantum computing has challenged classical conceptions of which problems are efficiently solvable in our physical world. This raises the general question of what broad relationships exist between physical principles and computation. The current thesis explores this question within the operationally-defined framework of generalised probabilistic theories. In particular, we investigate the limits on computational power imposed by simple physical principles. At present, the best known upper bound on the power of quantum computers is that BQP is contained in AWPP, where AWPP is a classical complexity class contained in PP. We define a circuit-based model of computation in the above mentioned operational framework and show that in theories where local measurements suffice for tomography, efficient computations are also contained in AWPP. Moreover, we explicitly construct a theory in which the class of efficiently solvable problems exactly equals AWPP, showing this containment to be tight. We also investigate how simple physical principles bound the power of computational paradigms which combine computation and communication in a non-trivial fashion, such as interactive proof systems. Additionally, we show how some of the essential components of computational algorithms arise from certain natural physical principles. We use these results to investigate the relationship between interference behaviour and computational power, demonstrating that non-trivial interference behaviour is a general resource for post-classical computation. We then investigate whether post-quantum interference is a resource for post-quantum computation. Sorkin has defined a hierarchy of possible post-quantum interference behaviours where, informally, the order in the hierarchy corresponds to the number of paths that have an irreducible interaction in a multi-slit experiment. In quantum theory, at most pairs of paths can ever interact in a fundamental way. We consider how Grover's speed-up depends on the order of interference in a theory, and show that, surprisingly, the quadratic lower bound holds regardless of the order of interference.
We present a new quantum complexity class, called MQ^2, which is contained in AWPP. This class has a compact and simple mathematical definition, involving only polynomial-time computable functions and a unitarity condition. It contains both Deutsch-Jozsa's and Shor's algorithm, while its relation to BQP is unknown. This shows that in the complexity class hierarchy, BQP is not an extraordinary isolated island, but has ''siblings'' which as well can solve prime-factorization.
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.
I study the class of problems efficiently solvable by a quantum computer, given the ability to ‘postselect’ on the outcomes of measurements. I prove that this class coincides with a classical complexity class called PP, or probabilistic polynomial-time. Using this result, I show that several simple changes to the axioms of quantum mechanics would let us solve PP-complete problems efficiently. The result also implies, as an easy corollary, a celebrated theorem of Beigel, Reingold and Spielman that PP is closed under intersection, as well as a generalization of that theorem due to Fortnow and Reingold. This illustrates that quantum computing can yield new and simpler proofs of major results about classical computation.