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 RwBQP ,
CBQP CBQP , and
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 BPP PP ⊆ RwBQP = CBQP = AdPostBQP ⊆ PSPACE . As a byproduct of this result, we show that any problem in
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 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 PP .
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.
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