Singlet
← All research questions
Q07 / Restricted models / question

How does the number of adaptive rounds affect STP?

Compare nonadaptive, constant-round, and polynomial-round STP for decision and sampling, keeping the classical controller and error conventions fixed. No postselection is allowed.

Discuss this question
Working mathematical formulation

Start with polynomially many maximally mixed qubits. In each of rr adaptive batches, a uniform polynomial-time classical controller chooses a fixed ordered list of pair measurements using only earlier batches’ outcomes. Measurements inside a batch may overlap but their order and pair choices are fixed. Compare decision power at r=1r=1, constant rr, r=O(log⁡N)r=O(\log N), and polynomial rr, with 2/32/3 versus 1/31/3 acceptance and no postselection. For sampling, compare full-record distributions in total variation distance.

Why this is interesting

The number of adaptive batches can vary independently of total measurement count. Separations would identify tasks that require feedback between measurements.

Explicit variants

  1. Restricted postselection

    Keep the fixed-sequence model but impose a lower bound on the total selected-history probability, a depth bound, or a connectivity restriction. Quantify the cost of obtaining the selected event; do not restate the unrestricted postselected equality as an open problem.

  2. Logarithmic-round universality

    Do O(log⁡N)O(\log N) adaptive batches, each with polynomially many predetermined pair measurements, suffice for every bounded-error quantum computation? Give a uniform simulation with explicit error and size overhead, or prove a lower bound for a specified task. Intermediate round bounds must also be considered; logarithmic and polynomial rounds are not an exhaustive dichotomy.

  3. Nonadaptive sampling and intermediate models

    For a predetermined polynomial-length sequence of pair measurements from mixed input, determine whether the full outcome record is efficiently classically samplable in total variation distance. Alternatively, identify an intermediate quantum sampling model that reduces to it, preserving the preparation, output, and approximation conventions.

A place to start

Find a concrete task or state-preparation family with a provable difference between nonadaptive and one- or two-round protocols.

Related work

These works provide context and established results. They need not be the origin of this exact formulation.

  1. The two-qubit singlet/triplet measurement is universal for quantum computing given only maximally-mixed initial states ↗

    Terry Rudolph, Shashank Soyuz Virmani · 2023

    Read the relevance note
  2. Symmetry Protected Quantum Computation ↗

    Michael H. Freedman, Matthew B. Hastings, Modjtaba Shokrian Zini · 2021

    Read the relevance note
  3. A one-way quantum computer ↗

    Robert Raussendorf, Hans J. Briegel · 2001

    Read the relevance note

Related questions

Q06 / QuestionWhat can constant- and logarithmic-depth STP compute?For constant or logarithmic STP depth, characterize decision power and classical sampling complexity under stated restrictions on the classical controller.Q08 / QuestionHow does interaction geometry constrain STP?Restrict pair measurements to an interaction graph. Characterize classical simulation, universal computation, and routing overhead on paths, trees, and lattices.

Discuss this question

Continue on GitHub Propose a research question

Reading is public. Posting requires a GitHub account. You can also write to Kunal.