← All research questions
Q03 / Algorithms & primitives / question

How efficiently can we compile into STP?

How much of the cost of a universal STP construction is essential?

Discuss this question
Working mathematical formulation

Fix Clifford+TT circuits with computational-basis input and output. Given a circuit CC of GG gates on nn logical qubits and rational ε\varepsilon, can a uniform classical compiler produce an adaptive STP protocol from maximally mixed physical qubits whose classical output distribution is within ε\varepsilon in total variation distance of CC? Give explicit bounds in nn, GG, and log⁡(1/ε)\log(1/\varepsilon) on physical qubits, expected measurement count, a high-probability runtime bound, disjoint-pair layers, and classical processing. State the interaction graph and count every failed preparation attempt.

Scope & assumptions

This primary task concerns classical output distributions. Coherent simulation of an encoded channel is a stronger variant: specify the encoding and require diamond-norm error at most ε\varepsilon, including action on a reference system.

Why this is interesting

A universality theorem leaves substantial room between a possible computer and an effective architecture.

A place to start

Benchmark a small encoded gate library with exact branch probabilities, including failed attempts, recycled states, and precision dependence.

Related work

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

Discuss this question

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