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:1107.3271

On the Simulation of Adaptive Measurements via Postselection

Vikram Dhillon

Published Jul 17, 2011• 0 citations
arXivHTMLPDF

Abstract

In this note we address the question of whether any any quantum computational model that allows adaptive measurements can be simulated by a model that allows postselected measurements. We argue in the favor of this question and prove that adaptive measurements can be simulated by postselection. We also discuss some potentially stunning consequences of this result such as the ability to solve #P problems.

DOI
10.48550/arxiv.1107.3271

Related papers

Notes on distinguishability of postselected computations

Zuzana Gavorová

The framework of postselection is becoming more and more important in various recent directions in Quantum Computation research. Postselection renders simple computational models able to perform general quantum computation. This was first observed for the linear optics model [E. Knill, R. Laflamme, G. J. Milburn, Nature 409, 46 (2001)], and has since provided us with many near-term candidates for the quantum advantage, commuting computations [M. J. Bremner, R. Jozsa, D. J. Shepherd, Proc. R. Soc. A 467, 459 (2011)] being the first. To facilitate the discussion of errors in the presence of postselection, we define and characterize trace-induced distance and diamond distance of postselected computations. We show counterexamples to simple properties that one would expect of any distance measure; the properties of convexity (when considering only the pure-state inputs would suffice), contractivity, and subadditivity of errors. On the positive side, we prove that certain weaker versions of contractivity and subadditivity and a number of other properties are preserved in the postselected setting. We achieve this via a "conversion lemma" that translates any inequality from the standard to the postselected setting.

arXiv:2011.08487•Nov 17, 2020•3 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

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•5 citations

Modifications of Quantum Computation and Adaptive Queries to PP

David Miloschewsky, Supartha Podder

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.

arXiv:2507.03692•Jul 4, 2025•1 citation

Postselection-Free Learning of Measurement-Induced Quantum Dynamics

Max McGinley

We address how one can empirically infer properties of quantum states generated by dynamics involving measurements. Our focus is on many-body settings where the number of measurements is extensive, making brute-force approaches based on postselection intractable due to their exponential sample complexity. We introduce a general-purpose scheme that can be used to infer any property of the postmeasurement ensemble of states (e.g., the average entanglement entropy, or frame potential) using a scalable number of experimental repetitions. We first identify a general class of “estimable properties” that can be directly extracted from experimental data. Then, based on empirical observations of such quantities, we show how one can indirectly infer information about any particular given nonestimable quantity of interest through classical postprocessing. Our approach is based on an optimization task, where one asks what are the minimum and maximum values that the desired quantity could possibly take, while ensuring consistency with observations. The true value of this quantity must then lie within a feasible range between these extrema, resulting in two-sided bounds. Narrow feasible ranges can be obtained by using a classical simulation of the device to determine which estimable properties one should measure. Even in cases where this simulation is inaccurate, unambiguous information about the true value of a given quantity realized on the quantum device can be learned. As an immediate application, we show that our method can be used to verify the emergence of quantum state designs in experiments. We identify some fundamental obstructions that in some cases prevent sharp knowledge of a given quantity from being inferred, and discuss what can be learned in cases where classical simulation is too computationally demanding to be feasible. In particular, we prove that any observer who cannot perform a classical simulation cannot distinguish the output states from those sampled from a maximally structureless ensemble. Published by the American Physical Society 2024

arXiv:2310.04156•PRX Quantum•May 29, 2024•32 citations

Implementation of POVMs by Projective Measurements and Postselection:Optimal Strategies and Applications to Unambiguous State Discrimination

Filip B. Maciejewski, Michał Oszmaniec

We present new results concerning simulation of general quantum measurements (POVMs) by projective measurements (PMs) for the task of Unambiguous State Discrimination (USD). We formulate a problem of finding optimal strategy of simulation for given quantum measurement. The problem can be solved for qubit and qutrits measurements by Semi-Definite Programming (SDP) methods.

Italian Quantum Information Science Conference (IQIS)•Nov 19, 2019•0 citations
In this note we address the question of whether any any quantum computational model that allows adaptive measurements can be simulated by a model that allows postselected measurements. We argue in the favor of this question and prove that adaptive measurements can be simulated by postselection. We also discuss some potentially stunning consequences of this result such as the ability to solve #P problems.
The framework of postselection is becoming more and more important in various recent directions in Quantum Computation research. Postselection renders simple computational models able to perform general quantum computation. This was first observed for the linear optics model [E. Knill, R. Laflamme, G. J. Milburn, Nature 409, 46 (2001)], and has since provided us with many near-term candidates for the quantum advantage, commuting computations [M. J. Bremner, R. Jozsa, D. J. Shepherd, Proc. R. Soc. A 467, 459 (2011)] being the first. To facilitate the discussion of errors in the presence of postselection, we define and characterize trace-induced distance and diamond distance of postselected computations. We show counterexamples to simple properties that one would expect of any distance measure; the properties of convexity (when considering only the pure-state inputs would suffice), contractivity, and subadditivity of errors. On the positive side, we prove that certain weaker versions of contractivity and subadditivity and a number of other properties are preserved in the postselected setting. We achieve this via a "conversion lemma" that translates any inequality from the standard to the postselected setting.
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.
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 .
In 2004, Aaronson introduced the complexity class PostBQP\mathsf{PostBQP}PostBQP (BQP\mathsf{BQP}BQP with postselection) and showed that it is equal to PP\mathsf{PP}PP. Following their line of work, we introduce two new complexity classes. The first, CorrBQP\mathsf{CorrBQP}CorrBQP, is a modification of BQP\mathsf{BQP}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\mathsf{MajBQP}MajBQP, augments BQP\mathsf{BQP}BQP with the ability to collapse a register to its most likely measurement outcome. Specifically, we consider two variants, MajBQP\mathsf{MajBQP}MajBQP and AdMajBQP\mathsf{AdMajBQP}AdMajBQP, where the latter may perform intermediate measurements. We exactly characterize the computational power of the models, CorrBQP=AdMajBQP=BPPPP\mathsf{CorrBQP} = \mathsf{AdMajBQP} = \mathsf{BPP}^{\mathsf{PP}}CorrBQP=AdMajBQP=BPPPP and MajBQP=PPP\mathsf{MajBQP} = \mathsf{P}^{\mathsf{PP}}MajBQP=PPP. In fact, we show that other metaphysical modifications of BQP\mathsf{BQP}BQP, such as CBQP\mathsf{CBQP}CBQP (i.e. BQP\mathsf{BQP}BQP with the ability to clone arbitrary quantum states), are also equal to BPPPP\mathsf{BPP}^{\mathsf{PP}}BPPPP. We show that CorrBQP\mathsf{CorrBQP}CorrBQP and MajBQP\mathsf{MajBQP}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\mathsf{BPP}^{\mathsf{PP}}BPPPP. Lastly, we extend the adversary lower-bounding technique to AdPDQP\mathsf{AdPDQP}AdPDQP, BQP\mathsf{BQP}BQP with the ability to sample the current state of an algorithm with collapsing it and adapt the computation based on the samples.
We address how one can empirically infer properties of quantum states generated by dynamics involving measurements. Our focus is on many-body settings where the number of measurements is extensive, making brute-force approaches based on postselection intractable due to their exponential sample complexity. We introduce a general-purpose scheme that can be used to infer any property of the postmeasurement ensemble of states (e.g., the average entanglement entropy, or frame potential) using a scalable number of experimental repetitions. We first identify a general class of “estimable properties” that can be directly extracted from experimental data. Then, based on empirical observations of such quantities, we show how one can indirectly infer information about any particular given nonestimable quantity of interest through classical postprocessing. Our approach is based on an optimization task, where one asks what are the minimum and maximum values that the desired quantity could possibly take, while ensuring consistency with observations. The true value of this quantity must then lie within a feasible range between these extrema, resulting in two-sided bounds. Narrow feasible ranges can be obtained by using a classical simulation of the device to determine which estimable properties one should measure. Even in cases where this simulation is inaccurate, unambiguous information about the true value of a given quantity realized on the quantum device can be learned. As an immediate application, we show that our method can be used to verify the emergence of quantum state designs in experiments. We identify some fundamental obstructions that in some cases prevent sharp knowledge of a given quantity from being inferred, and discuss what can be learned in cases where classical simulation is too computationally demanding to be feasible. In particular, we prove that any observer who cannot perform a classical simulation cannot distinguish the output states from those sampled from a maximally structureless ensemble. Published by the American Physical Society 2024