⚛️ quantum physics

Modifications of Quantum Computation and Adaptive Queries to PP

This paper introduces and characterizes new quantum complexity classes based on correlated measurements, majority collapses, and adaptive queries, demonstrating that they are equivalent to $\mathsf{BPP}^{\mathsf{PP}}$ or $\mathsf{P}^{\mathsf{PP}}$ and establishing their self-lowness properties alongside new lower-bound techniques for query complexity.

Original authors: David Miloschewsky, Supartha Podder

Published 2026-03-17

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: David Miloschewsky, Supartha Podder

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are playing a high-stakes game of "Guess the Secret Code" using a magical quantum computer. Normally, this computer is incredibly powerful but has strict rules: it can explore many possibilities at once (superposition), but the moment you look at the answer, the magic collapses, and you only see one result.

This paper introduces two new, slightly "cheating" rules for this quantum game. The authors ask: What happens if we tweak the rules of quantum mechanics just a little bit? Does the computer become a god-like super-brain, or does it just get a little bit better?

Here is the breakdown of their findings using simple analogies.

1. The Two New "Cheats"

The authors invented two new ways to manipulate the quantum computer:

The "Synchronized Twins" (CorrBQP):
Imagine you have two identical quantum coins spinning in the air. In a normal quantum world, if you look at one, it lands on Heads or Tails randomly, and the other does its own thing.
In this new model, you have a "Leader" coin and a "Follower" coin. If the Leader lands on Heads, the Follower is forced to land on Heads too, even if it was leaning toward Tails. If the Leader is Tails, the Follower becomes Tails. You get to pick which coin is the boss, and the other one must copy it perfectly.
- The Result: This ability to force synchronization turns the computer into a machine that can solve problems as hard as PP (a class of problems involving counting massive numbers of possibilities).
The "Majority Vote" (MajBQP):
Imagine the quantum computer is flipping a coin, but the coin is slightly weighted. It lands on Heads 51% of the time and Tails 49% of the time.
In a normal computer, you just get a random result. In this new model, you have a "Majority Gate." It looks at the coin, sees it's leaning toward Heads, and forces the coin to land on Heads. It essentially says, "I know the most likely outcome is Heads, so I'm just going to make it happen."
- The Result:
  - If you can only do this at the very end of the game, the computer becomes a PPP machine (even stronger than PP).
  - If you can do this during the game (checking the coin halfway through and forcing a result), the computer becomes a BPPPP machine (a very powerful class involving randomness and counting).

2. The Big Discovery: "It's Not as Crazy as We Thought"

Before this paper, scientists wondered if these "metaphysical" cheats (like cloning states or forcing outcomes) would make the computer so powerful it could solve any problem (PSPACE).

The Surprise: The authors found that these cheats don't make the computer infinitely powerful.

CorrBQP (Synchronized Twins) and AdMajBQP (Majority Vote with mid-game checks) are exactly as powerful as BPPPP.
MajBQP (Majority Vote only at the end) is exactly as powerful as PPP.

The Analogy: Think of the "Complexity Zoo" as a ladder.

P is the bottom rung (easy problems).
PP is a high rung (hard counting problems).
PSPACE is the top of the ladder (the hardest possible problems).
The authors found that these new "cheats" only let the computer climb a few rungs higher than PP, but they do not let it reach the very top (PSPACE). They are powerful, but they have a ceiling.

3. The "Self-Low" Mystery (The Mirror Test)

There is a concept in computer science called "self-low." Imagine a computer that can ask itself questions.

The Question: "If I can solve a hard problem, can I solve a problem about solving hard problems without getting stuck in an infinite loop?"
The Finding:
- These new models are "self-low" when asking classical questions (like reading a book). They can handle their own questions efficiently.
- However, if they try to ask quantum questions (asking while in a superposition), they get stuck. If they could handle quantum questions efficiently, it would mean the entire "Counting Hierarchy" (a massive structure of complexity classes) would collapse into a single layer. This is considered unlikely, so it proves these models have limits.

4. The "Adaptive" Twist (Changing Plans Mid-Game)

The paper also looked at "Adaptive" versions of these models.

Adaptive Postselection: Usually, you decide your "cheat" (postselection) at the start. But what if you can look at the results halfway through and change your cheat?
- Result: This makes the computer much stronger. It can solve "Parity" (checking if a list of bits has an odd or even number of 1s) very quickly.
Adaptive Non-Collapsing Measurements: This is a different cheat where you peek at the system without breaking the magic. The authors asked: "If we can peek and then change our plan based on what we saw, does it get stronger?"
- Result: Surprisingly, no. Even with the ability to peek and adapt, the computer cannot solve "Unstructured Search" (finding a needle in a haystack) any faster than before. The "peek" doesn't give enough extra power to break the speed limits.

5. The "Classical vs. Quantum" Oracle

Finally, they tested what happens if you restrict the computer to only ask "Classical" questions to an oracle (a magical black box that answers questions).

The Finding: If you force a quantum computer to only ask classical questions, it loses its superpowers. There are problems a quantum computer can solve that a "Post-selection" computer (even with cheats) cannot solve if it's restricted to classical questions.
The Lesson: To get the full power of these advanced models, you need to let them ask questions in a quantum way (superposition). Restricting them to classical questions breaks the magic.

Summary

This paper is like a physicist testing new rules for a video game. They asked, "What if we add a 'Copy' button or a 'Force Win' button?"

Answer: These buttons make the game much harder to beat (moving from PP to BPPPP), but they don't make the game impossible to understand.
Key Takeaway: Even with these "metaphysical" powers, quantum computers have a hard ceiling. They can't solve everything, and they can't break the fundamental laws of the complexity hierarchy unless some very unlikely mathematical collapses happen.

The authors essentially mapped out the "Power Ceiling" for these new quantum models, showing us exactly how high they can jump, but confirming they can't fly.

1. Problem Statement and Motivation

The paper investigates the computational power of "metaphysical" modifications to the standard quantum complexity class BQP (Bounded-Error Quantum Polynomial time). While standard quantum computing is constrained by the laws of quantum mechanics (e.g., no-cloning, wavefunction collapse upon measurement), previous research has explored hypothetical extensions such as:

Postselection: Selecting specific measurement outcomes even if they occur with exponentially small probability (leading to the class PostBQP, known to equal PP).
Non-collapsing measurements: Sampling a state without collapsing it (PDQP).
State cloning: Copying arbitrary quantum states (CBQP).

The authors aim to:

Introduce two new modifications: CorrBQP (Correlated Measurements) and MajBQP (Quantum Majority).
Precisely characterize the computational power of these new classes relative to the Counting Hierarchy (CH) and classes like PP, BPP $^{PP}$ , and PSPACE.
Analyze the impact of adaptivity (intermediate measurements) on these classes.
Develop new lower-bound techniques for query complexity in these adaptive settings.

2. Methodology and Models

The authors define and analyze two primary new complexity classes:

A. CorrBQP (Correlated Measurements)

This class augments BQP with the ability to perform correlated measurements across multiple registers.

Mechanism: Given a partition of registers into a "leader" set and "follower" sets, the measurement discards any amplitude where the registers do not agree. It then re-normalizes the state such that the probability distribution of the outcome is dictated strictly by the leader register.
Significance: This operation is non-unitary and violates standard quantum postulates but allows for the simulation of cloning and postselection.

B. MajBQP (Quantum Majority)

This class augments BQP with a Quantum Majority Gate.

Mechanism: A single-qubit gate that collapses a state $|\psi\rangle = \alpha|0\rangle + \beta|1\rangle$ to $|0\rangle$ if $|\alpha|^2 \geq |\beta|^2$ , and to $|1\rangle$ otherwise. This effectively forces the system to the "most likely" outcome.
Variants:
- MajBQP: No intermediate measurements allowed.
- AdMajBQP: Allows intermediate measurements (adaptivity).

C. Adaptive Models

The paper extensively studies the role of adaptivity (intermediate measurements). It defines AdPostBQP (PostBQP with intermediate measurements) and AdPDQP (PDQP with adaptivity), comparing them to their non-adaptive counterparts.

3. Key Contributions and Results

The paper establishes exact characterizations of these classes and explores their structural properties.

Result 1: Exact Characterization of Computational Power

The authors prove that these metaphysical modifications collapse to specific levels of the counting hierarchy:

MajBQP = $\text{P}^{\text{PP}}$ : The class with majority gates but no intermediate measurements is equivalent to one level of the counting hierarchy above PP.
CorrBQP = AdMajBQP = $\text{BPP}^{\text{PP}}$ : The class with correlated measurements (or adaptive majority) is equivalent to BPP with access to a PP oracle.
Equivalence Chain: The paper further shows that these classes are equal to other known metaphysical classes:
$\text{CorrBQP} = \text{AdMajBQP} = \text{BPP}^{\text{PP}} = \text{CBQP} \text{ (Cloning)} = \text{AdPostBQP} = \text{RwBQP} \text{ (Rewindable)}$
Significance: This unifies various "super-quantum" models, showing they all possess the power of $\text{BPP}^{\text{PP}}$ , which is strictly stronger than PostBQP (PP) but likely weaker than PSPACE.

Result 2: Self-Low Properties and the Counting Hierarchy

The paper investigates whether these classes are self-low (i.e., whether $\mathcal{C}^{\mathcal{C}} = \mathcal{C}$ ).

Classical Queries: CorrBQP and MajBQP are self-low with respect to classically accessible queries.
Quantum Queries: The authors prove that if CorrBQP were self-low with respect to quantumly accessible queries (i.e., $\text{CorrBQP}^{\text{CorrBQP}} \subseteq \text{CorrBQP}$ ), the Counting Hierarchy (CH) would collapse to $\text{BPP}^{\text{PP}}$ .
Implication: Assuming CH does not collapse, there exists a fundamental distinction between classical and quantum oracle access for these powerful classes.

Result 3: Query Complexity and Rational Tree Degree

To analyze the query complexity of adaptive postselection, the authors introduce a new measure: Rational Tree Degree (trdeg).

Definition: A generalization of the rational degree (rdeg) where the computation is modeled as a tree of rational functions rather than a single ratio.
Lower Bound: They prove that $trdeg(f)$ lower-bounds the query complexity of AdPostBQP.
Separation: They demonstrate a separation between rdeg and trdeg for the function $AdaAND_{n, \log n}$ , showing that adaptivity allows for significantly lower query complexity in the tree model compared to the rational function model.

Result 4: Oracle Separations (Classical vs. Quantum Access)

The paper addresses whether $\text{PP} = \text{PostBQP}$ holds when restricted to classical oracle queries.

Theorem: There exists an oracle $O$ such that $\text{BQP}^O \not\subseteq \text{PostBQP}^O_{\text{classical}}$ and $\text{PP}^O \not\subseteq \text{PostBQP}^O_{\text{classical}}$ .
Significance: This refutes the idea that PostBQP's power is robust even with restricted (classical) oracle access, highlighting the necessity of quantum superposition in oracle queries for certain separations.

Result 5: Adaptive Non-Collapsing Measurements (AdPDQP)

The authors extend the Adversary Method to AdPDQP (PDQP with adaptivity).

Finding: Unlike PostBQP, where adaptivity drastically increases power (allowing efficient Parity computation), adaptivity in PDQP does not provide a major advantage.
Lower Bounds: They prove that AdPDQP still requires $\Omega(n^{1/4})$ queries for unstructured search and $\Omega(n^{1/2})$ for Parity.
Conclusion: This resolves an open question from [Aar+16], showing that adaptivity does not bridge the gap between PDQP and classes like NP or $\oplus$ P in the query setting.

4. Significance and Impact

Unification of Metaphysical Classes: The paper provides a cohesive framework showing that diverse "super-quantum" capabilities (cloning, rewinding, correlated measurements, adaptive postselection) all converge to the same computational power: $\text{BPP}^{\text{PP}}$ .
Structural Insights into CH: By linking these classes to the Counting Hierarchy, the paper clarifies the "space" between PP and PSPACE. It suggests that while these models are powerful, they do not reach PSPACE unless the Counting Hierarchy collapses.
Oracle Access Distinctions: The results emphasize that the power of quantum complexity classes is highly sensitive to the type of oracle access (classical vs. quantum), particularly for classes involving postselection.
New Lower Bound Techniques: The introduction of Rational Tree Degree and the extension of the Adversary method to adaptive non-collapsing measurements provide new tools for analyzing query complexity in non-standard quantum models.
Adaptivity Limits: The finding that adaptivity helps PostBQP (for Parity) but not PDQP (for Search/Parity) offers a nuanced understanding of how different quantum modifications interact with algorithmic adaptivity.

In summary, this work rigorously maps the landscape of "what-if" quantum computing models, demonstrating that while they exceed standard BQP, their power is precisely bounded within the Counting Hierarchy, and their behavior is deeply tied to the nature of oracle access and adaptivity.