Q06: What can constant- and logarithmic-depth STP compute?

Working mathematical formulation

Fix polynomially many qubits initially in $I/2^N$ . A depth- $d$ protocol has $d$ layers of disjoint pairwise STP measurements; the pairs in a layer may depend on the entire preceding outcome record through uniform polynomial-time classical computation. With no postselection, determine the decision power at $d=O(1)$ and $d=O(\log N)$ , using completeness $2/3$ and soundness $1/3$ . Separately ask for classical sampling of the full outcome record within inverse-polynomial total variation error.

Scope & assumptions

The main model counts quantum layers and permits polynomial-time classical control. It therefore already contains classical polynomial-time decision procedures. Comparisons with $\mathsf{AC}^{0}$ and $\mathsf{NC}^{1}$ require the separate total-depth model below. Geometry, input encoding, copy count, postselection, and output decoding must be fixed.

Why this is interesting

The quantum depth, interaction geometry, and amount of classical control are distinct resources. Keeping them separate may reveal useful upper and lower bounds.

Explicit variants

Total depth, including classical control
Define a uniform polynomial-size hybrid circuit with disjoint-pair STP layers and explicit classical AND/OR/NOT gates. Count the entire dependency depth, including feed-forward and final decoding. Compare bounded-fan-in logarithmic depth with unbounded-fan-in constant-depth classical control; do not grant threshold or parity gates without declaring them. No postselection.
A Majority benchmark
For odd $n$ , receive one copy of $\rho_x=\bigotimes_i\rho_{x_i}$ , with unknown $x$ , $\rho_1=P_s$ and $\rho_0=P_t/3$ . Using polynomially many mixed ancillas, decide $\lvert x\rvert>n/2$ with error at most $1/3$ . Is constant STP depth together with constant TOTAL $\mathsf{AC}^{0}$ classical-control depth sufficient? One STP layer plus logarithmic-depth bounded-fan-in classical decoding is a baseline.
A quantum spin threshold
Given one unknown $n$ -qubit state supported either on $J\le J_{\mathrm{minus}}$ or on $J\ge J_{\mathrm{plus}}$ , determine STP depth as a function of $n$ and the sector separation. Specify retained output and copy access. A projective measurement that distinguishes only the two promised ranges must preserve coherence within each range. Reading the exact $J$ label and forgetting it can destroy that coherence.
Lower bounds native to STP
Develop light-cone, representation-theoretic, subsystem-spin martingale, or communication-cut bounds for an explicit STP task. Relate the chosen progress quantity to success probability and bound its change per layer or crossing measurement, allowing the declared classical feed-forward. Distinguish measurement depth from the total depth of the hybrid computation.

A place to start

Write exact tensor-network descriptions of the first few depth classes and identify a graph parameter that yields efficient classical simulation.

Related work

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

Discuss this question

Continue on GitHub Propose a research question

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

Why this is interesting

Explicit variants

Total depth, including classical control

A Majority benchmark

A quantum spin threshold

Lower bounds native to STP

A place to start

Related work

Related questions

Discuss this question