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

Power of quantum computing with restricted postselections.

Tomoyuki Morimae, Harumichi Nishimura

Published Jan 31, 2015• 1 citation
OpenAlex

Abstract

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}$.

Related papers

Computation in generalised probabilisitic theories

Ciarán M. Lee, Jonathan Barrett

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.

•Aug 1, 2015•35 citations

Computation in generalised probabilisitic theories

Ciarán M. Lee, Jonathan Barrett

From the general difficulty of simulating quantum systems using classical systems, and in particular the existence of an efficient quantum algorithm for factoring, it is likely that quantum computation is intrinsically more powerful than classical computation. At present, the best upper bound known for the power of quantum computation is that , where is a classical complexity class (known to be included in , hence ). This work investigates limits on computational power that are imposed by simple physical, or information theoretic, principles. To this end, we define a circuit-based model of computation in a class of operationally-defined theories more general than quantum theory, and ask: what is the minimal set of physical assumptions under which the above inclusions still hold? We show that given only an assumption of tomographic locality (roughly, that multipartite states and transformations can be characterized by local measurements), efficient computations are contained in . This inclusion still holds even without assuming a basic notion of causality (where the notion is, roughly, that probabilities for outcomes cannot depend on future measurement choices). Following Aaronson, we extend the computational model by allowing post-selection on measurement outcomes. Aaronson showed that the corresponding quantum complexity class, , is equal to . Given only the assumption of tomographic locality, the inclusion in still holds for post-selected computation in general theories. Hence in a world with post-selection, quantum theory is optimal for computation in the space of all operational theories. We then consider whether one can obtain relativized complexity results for general theories. It is not obvious how to define a sensible notion of a computational oracle in the general framework that reduces to the standard notion in the quantum case. Nevertheless, it is possible to define computation relative to a 'classical oracle'. Then, we show there exists a classical oracle relative to which efficient computation in any theory satisfying the causality assumption does not include .

arXiv:1412.8671•New Journal of Physics•Aug 3, 2015•36 citations

Quantum interpretations of AWPP and APP

Tomoyuki Morimae, Harumichi Nishimura

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.

arXiv:1502.00067•Quantum Information and Computation•Apr 1, 2016•2 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•5 citations

Rewindable Quantum Computation and Its Equivalence to Cloning and Adaptive Postselection

Ryo Hiromasa, Akihiro Mizutani, Yuki Takeuchi +1 more

Abstract We define rewinding operators that invert quantum measurements. Then, we define complexity classes $$\textsf{RwBQP}$$ RwBQP , $$\textsf{CBQP}$$ CBQP , and $$\textsf{AdPostBQP}$$ AdPostBQP as sets of decision problems solvable by polynomial-size quantum circuits with a polynomial number of rewinding operators, cloning operators, and adaptive postselections, respectively. Our main result is that $$\textsf{BPP}^\textsf{PP}\subseteq \textsf{RwBQP}=\textsf{CBQP}=\textsf{AdPostBQP}\subseteq \textsf{PSPACE}$$ BPP PP ⊆ RwBQP = CBQP = AdPostBQP ⊆ PSPACE . As a byproduct of this result, we show that any problem in $$\textsf{PostBQP}$$ PostBQP can be solved with only postselections of events that occur with probabilities polynomially close to one. Under the strongly believed assumption that $$\textsf{BQP}\nsupseteq \textsf{SZK}$$ BQP ⊉ SZK , or the shortest independent vectors problem cannot be efficiently solved with quantum computers, we also show that a single rewinding operator is sufficient to achieve tasks that are intractable for quantum computation. Finally, we show that rewindable Clifford circuits remain classically simulatable, but rewindable instantaneous quantum polynomial time circuits can solve any problem in $$\textsf{PP}$$ PP .

arXiv:2206.05434•Theory of Computing Systems•Jan 17, 2025•2 citations

Merlinization of complexity classes above BQP

Tomoyuki Morimae, Harumichi Nishimura

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.

arXiv:1704.01514•Quantum Information and Computation•Sep 1, 2017•5 citations
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.
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.
From the general difficulty of simulating quantum systems using classical systems, and in particular the existence of an efficient quantum algorithm for factoring, it is likely that quantum computation is intrinsically more powerful than classical computation. At present, the best upper bound known for the power of quantum computation is that , where is a classical complexity class (known to be included in , hence ). This work investigates limits on computational power that are imposed by simple physical, or information theoretic, principles. To this end, we define a circuit-based model of computation in a class of operationally-defined theories more general than quantum theory, and ask: what is the minimal set of physical assumptions under which the above inclusions still hold? We show that given only an assumption of tomographic locality (roughly, that multipartite states and transformations can be characterized by local measurements), efficient computations are contained in . This inclusion still holds even without assuming a basic notion of causality (where the notion is, roughly, that probabilities for outcomes cannot depend on future measurement choices). Following Aaronson, we extend the computational model by allowing post-selection on measurement outcomes. Aaronson showed that the corresponding quantum complexity class, , is equal to . Given only the assumption of tomographic locality, the inclusion in still holds for post-selected computation in general theories. Hence in a world with post-selection, quantum theory is optimal for computation in the space of all operational theories. We then consider whether one can obtain relativized complexity results for general theories. It is not obvious how to define a sensible notion of a computational oracle in the general framework that reduces to the standard notion in the quantum case. Nevertheless, it is possible to define computation relative to a 'classical oracle'. Then, we show there exists a classical oracle relative to which efficient computation in any theory satisfying the causality assumption does not include .
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.
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.
Abstract We define rewinding operators that invert quantum measurements. Then, we define complexity classes RwBQP\textsf{RwBQP}RwBQP RwBQP , CBQP\textsf{CBQP}CBQP CBQP , and AdPostBQP\textsf{AdPostBQP}AdPostBQP AdPostBQP as sets of decision problems solvable by polynomial-size quantum circuits with a polynomial number of rewinding operators, cloning operators, and adaptive postselections, respectively. Our main result is that BPPPP⊆RwBQP=CBQP=AdPostBQP⊆PSPACE\textsf{BPP}^\textsf{PP}\subseteq \textsf{RwBQP}=\textsf{CBQP}=\textsf{AdPostBQP}\subseteq \textsf{PSPACE}BPPPP⊆RwBQP=CBQP=AdPostBQP⊆PSPACE BPP PP ⊆ RwBQP = CBQP = AdPostBQP ⊆ PSPACE . As a byproduct of this result, we show that any problem in PostBQP\textsf{PostBQP}PostBQP PostBQP can be solved with only postselections of events that occur with probabilities polynomially close to one. Under the strongly believed assumption that BQP⊉SZK\textsf{BQP}\nsupseteq \textsf{SZK}BQP⊉SZK BQP ⊉ SZK , or the shortest independent vectors problem cannot be efficiently solved with quantum computers, we also show that a single rewinding operator is sufficient to achieve tasks that are intractable for quantum computation. Finally, we show that rewindable Clifford circuits remain classically simulatable, but rewindable instantaneous quantum polynomial time circuits can solve any problem in PP\textsf{PP}PP PP .
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.