Quantum Computation with Correlated Measurements: Implications for the Complexity Landscape
David Miloschewsky, Supartha Podder · 2025
Read Quantum Computation with Correlated Measurements: Implications for the Complexity Landscape by David Miloschewsky, Supartha Podder (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-03692.txt.
Introduction
David Miloschewsky and Supartha Podder study variants of quantum computation in a paper from 2025. The text head gives the work a different title, about modifications of quantum computation and adaptive queries, and the description follows the head. A famous result equates quantum computing with postselection to a counting class called PP. The pair define two new classes that tweak how measurements work.
One class lets measurements output linked values across registers. The other lets a register collapse to its most likely outcome. They prove exactly how powerful each variant is, in terms of known classes. Some other exotic tweaks turn out to match the same power. The results map the borders of quantum advantage more sharply.
Catalog record
| CREATOR | David Miloschewsky, Supartha Podder |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 53 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-03692
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Quantum Computation with Correlated Measurements: Implications for the Complexity Landscape 0 0 footnotetext: This work is supported by US Department of Energy (grant no DE-SC0023179) and partially supported by US National Science Foundation (award no 1954311). 0 0 footnotetext: We thank Dorian Rudolph and Thomas Huffstutler for helpful discussions. David Miloschewsky, Supartha Podder Abstract In 2004, Aaronson [ Aar04 ] introduced the complexity class 𝖯𝗈𝗌𝗍𝖡𝖰𝖯 \mathsf{PostBQP} ( 𝖡𝖰𝖯 \mathsf{BQP} with postselection) and showed that it is equal to 𝖯𝖯 \mathsf{PP} . In this paper, we define a new complexity class, 𝖢𝗈𝗋𝗋𝖡𝖰𝖯 \mathsf{CorrBQP} , 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. We show that 𝖢𝗈𝗋𝗋𝖡𝖰𝖯 \mathsf{CorrBQP} is exactly equal to 𝖡𝖯𝖯 𝖯𝖯 \mathsf{BPP}^{\mathsf{PP}} , placing it “just above” 𝖯𝖯 \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, introduced in [ BBJ16 , Hir+25 ] ), are also equal to 𝖡𝖯𝖯 𝖯𝖯 \mathsf{BPP}^{\mathsf{PP}} . We show that 𝖢𝗈𝗋𝗋𝖡𝖰𝖯 \mathsf{CorrBQP} is self-low with respect to classical queries. In contrast, if it were self-low under quantum queries, the counting hierarchy ( 𝖢𝖧 \mathsf{CH} ) would collapse to 𝖡𝖯𝖯 𝖯𝖯 \mathsf{BPP}^{\mathsf{PP}} . Finally, we introduce a variant of rational degree that lower-bounds the query complexity of 𝖡𝖯𝖯 𝖯𝖯 \mathsf{BPP}^{\mathsf{PP}} . 1 Introduction The study of quantum computing spurred the study of various quantum complexity classes. Starting with the introduction of \mathsf{BQP} , the quantum analogue of \mathsf{P} , numerous quantum counterparts to standard classical complexity classes, such as \mathsf{QMA} , \mathsf{QIP} and \mathsf{QAC_{0}} (which corresponds to \mathsf{NP} , \mathsf{IP} , and \mathsf{AC_{0}} respectively), have been defined. One question about these classes is how they relate to their classical counterparts and whether such connections can reveal new structural insights or lead to progress on foundational questions in computational complexity. One such results is \mathsf{PostBQP}=\mathsf{PP} [ Aar04 ] , where \mathsf{PostBQP} denotes \mathsf{BQP} with the ability to postselect on any specific measurement outcome, even that occurs with exponentially small probability. This result led to a much simpler proof that \mathsf{PP} is closed under intersection and shows how exploring alternative formulations of \mathsf{BQP} can potentially yield new insights into the structure and limitations of other complexity classes. This work contributes to that exploration by studying a new modification of \mathsf{BQP} and its complexity theoretic implications. 1.1 Results We introduce \mathsf{CorrBQP} , a modified version of \mathsf{BQP} enhanced with the power to perform correlated measurements . A correlated measurement is the operation where we obtain the same measurement outcome across multiple registers and the probability distribution of such outcomes is dictated by a specific register. \mathsf{PP}=\mathsf{PostBQP} \mathsf{PH} \mathsf{P}^{\mathsf{PP}} \mathsf{QCPH} \mathsf{BPP}^{\mathsf{PP}}=\mathsf{CorrBQP}{}^{\dagger} \mathsf{BQP}^{\mathsf{PP}} \mathsf{CorrBQP}^{\mathsf{CorrBQP}} \mathsf{PSPACE} \mathsf{PDQP} \mathsf{CH} Figure 1: A map of relationships between complexity classes discussed. Given two classes C and D , C\rightarrow D indicates C\subseteq D . † See Result 1 for all classes equal to \mathsf{BPP}^{\mathsf{PP}} . Result 1: We define the complexity class \mathsf{CorrBQP} (Definition 3.2 ) and show that \mathsf{CorrBQP}=\mathsf{BPP}^{\mathsf{PP}}=\mathsf{CBQP}=\mathsf{AdPostBQP}=\mathsf{RwBQP} (Definition 2.7 ; Theorems 3.10 and 3.13 ). We begin by exactly characterizing \mathsf{CorrBQP} , showing that it is equal to \mathsf{BPP}^{\mathsf{PP}} . This allows us to show that the same holds for other modifications of \mathsf{BQP} such as \mathsf{CBQP} , \mathsf{AdPostBQP} , and \mathsf{RwBQP} 1 1 1 \mathsf{CBQP} is \mathsf{BQP} with the ability to copy any state; \mathsf{AdPostBQP} is \mathsf{PostBQP} with the ability to perform intermediate measurements; \mathsf{RwBQP} is \mathsf{BQP} with the ability to uncompute measurements. . As the best prior upper-bounds for these classes were \mathsf{PSPACE} , and \mathsf{BPP}^{\mathsf{PP}} is not believed to be equal to \mathsf{PSPACE} , this result indicates that their computational power is only slightly stronger than \mathsf{PostBQP} . Furthermore, we find that \mathsf{CorrBQP} is self-low with respect to classical queries, a quality which \mathsf{PostBQP} is not known to possess. We use this result to study the counting hierarchy, \mathsf{CH} . It is defined as \mathsf{CH}=\cup_{i\in\mathbb{N}}\mathsf{C_{i}P} where \mathsf{C_{1}P}=\mathsf{PP} and \mathsf{C_{i}P}=\mathsf{PP}^{\mathsf{C_{i-1}P}} 2 2 2 Alternatively, one may look at \mathsf{CH} as a version of the polynomial hierarchy, \mathsf{PH} , where the \exists and \forall quantifiers are replaced by a counting quantifier \mathcal{C} , a quantifier which asks whether the ratio of computational paths an \mathsf{NP} machine accepts is over 1/2 . . One motivation behind the study of \mathsf{CH} is the seminal result of Toda which shows that \mathsf{PH}\subseteq\mathsf{P}^{\mathsf{PP}} , placing it between the first and second levels of \mathsf{CH} [ Tod91 ] . Result 2: If \mathsf{CorrBQP} is self-low with respect to quantum queries, i.e. \mathsf{CorrBQP}^{\mathsf{CorrBQP}}\subseteq\mathsf{CorrBQP} , then \mathsf{CH}=\mathsf{BPP}^{\mathsf{PP}} (Lemma 3.12 ). Assuming \mathsf{CH} does not collapse, this result implies the existence of a class that is self-low with respect to classical queries but not with respect to quantum queries. This offers additional evidence that relativizing proof techniques can behave differently depending on whether the oracle is classically or quantum accessible. The first such example is due to [ AK25 ] , who showed that there exists a quantum oracle relative to which a certain problem lies in \mathsf{QMA} but not in \mathsf{PSPACE} , even though \mathsf{QMA}\subseteq\mathsf{PSPACE} relative to every classical oracle. However, note that one significant difference between these two examples is that in [ AK25 ] , the comparison is between quantum and classical oracles, whereas in our case, the distinction lies in whether superposition queries are allowed or not. Next, we study alterations of \mathsf{BQP} in the query complexity setting. Result 3: We define the measure rational tree degree (Definition 4.1 ) which lower-bounds the query complexity of \mathsf{AdPostBQP} (Lemma 4.2 ). We define a new variant of rational degree ( rdeg ), which we call rational tree degree ( trdeg ), and show that it lower-bounds the query complexity of \mathsf{AdPostBQP} . We find that in the zero error case, the measures are equal, while in the constant error case, we are able to separate them. Two reasons motivate the study of trdeg . Firstly, we want to expand on the prior work which connected rational degree and \mathsf{PostBQP} [ MdW14 ] . Secondly, due to the fact that \mathsf{BPP}^{\mathsf{PP}}\subseteq\mathsf{AdPostBQP} relativizes, trdeg may be used as a lower-bounding technique for \mathsf{BPP}^{\mathsf{PP}} , potentially leading to an oracle separation between \mathsf{BPP}^{\mathsf{PP}} and \mathsf{PSPACE} . Finally, we explore what happens when the query access of a quantum class to an oracle is restricted to classical queries. Specifically, we place this restriction on \mathsf{PostBQP} , obtaining the class \mathsf{PostBQP}_{\textup{classical}} . Result 4: There exists an oracle O such that \mathsf{BQP}^{O}\not\subseteq\mathsf{PostBQP}^{O}_{\textup{classical}} and \mathsf{PP}^{O}\not\subseteq\mathsf{PostBQP}^{O}_{\textup{classical}} (Theorem 5.2 ) where \mathsf{PostBQP}_{\textup{classical}} is \mathsf{PostBQP} restricted to classical queries. Our motivation for this is due to the fact that the equality \mathsf{PP}=\mathsf{PostBQP} holds relative to every quantum accessible classical oracle [ Aar04 , Che16a ] . One would wonder if the same would hold true for every classically accessible oracles 3 3 3 In fact it turns out that, if \mathsf{PP}^{O}\subseteq\mathsf{PostBQP}^{O}_{\textup{classical}} for all oracles O , then \mathsf{CH} collapses to \mathsf{BPP}^{\mathsf{PP}} . . This result shows that this is indeed false. We do this by extending the oracle separation between \mathsf{BQP} (with quantum queries) and \mathsf{PostBPP} 4 4 4 \mathsf{PostBPP} , also known as \mathsf{BPP}_{\mathsf{Path}}