What Can Be Computed with Indefinite Causal Structure?

The paper in detail

A process matrix generator is an ordinary circuit \(C\) with designated feedback registers, whose outputs are wired back to their inputs through local laboratories. It must yield a quantum channel for every choice of local channels, including those with auxiliary systems. With identity operations in the slots, a unitary \(C\) gives \(T_D=\mathrm{Tr}_R(U_C)\), a partial trace of the matrix itself, and not the result of running \(C\) and discarding a register. The model grants access to this channel at a cost equal to the size of \(C\), which is where any jump in power would come from.

For NP, the paper turns a circuit that prepares the Choi state of \(V\) into a generator that applies \(V\). The generator teleports the input through the Choi state, which applies \(V P_j\) for a random Pauli \(P_j\), and it measures its feedback input \(r\) and outputs \(r\oplus j\). Closing the loop forces \(j=0\). For a unique witness \(z\), the Choi state of the swap \(S_z\) between \(\ket{0^n}\) and \(\ket z\) can be prepared from the verifier alone: on a marked branch the circuit writes the two exceptional terms, and the uncomputation works because the output reveals the input. Applying \(S_z\) to \(\ket{0^n}\) gives \(z\), and Valiant–Vazirani with a final check extends this to all of NP.

Those generators are not unitary because they contain measurements. Purifiability holds because validity survives even one joint channel on all feedback qubits, so a pure extension exists; the extension the author exhibits for unique witness uses \(z\) itself. Whether such extensions can be found efficiently is open, which raises a gap that does not exist for ordinary circuits, where purifying a circuit is easy.

For pure processes the paper tries to invert a permutation directly: \(U_C\ket x_R\ket y_Q=\ket{y\oplus x\oplus\pi(x)}_R\ket x_Q\). Closing the loop requires \(y=\pi(x)\), so \(\mathrm{Tr}_R(U_C)\ket y=\ket{\pi^{-1}(y)}\). This cannot work for all permutations, because validity fails for some local unitaries. The condition that rescues it is exactly the known characterisation of USO outmaps, and the sink is \(s^{-1}(0^n)\). Whether general NP has a pure efficient construction, and whether any of this is physical, stays open.

Transferable methods

1. Closing a loop to post-select a teleportation outcome, with a valid channel

   Teleportation applies \(V\) only with probability \(2^{-2n}\). Connecting a feedback register that records the outcome removes every other branch deterministically, while the sum over the free string restores the normalisation.

   The circuit measures its \(2n\) feedback inputs to get \(r\), teleports the input through \(\ket{J_V}\) to get outcome \(j\) and output \(VP_j\ket\psi\), and sets the feedback output to \(r\oplus j\). Identity feedback requires \(r=r\oplus j\), that is, \(j=0^{2n}\). Each \(r\) then contributes \(\rho\mapsto V\rho V^\dagger\) with weight \(2^{-2n}\), and there are \(2^{2n}\) values of \(r\), so the total weight is exactly 1. The normalisation does not depend on the input, and this is what separates the construction from nonlinear postselection.

   Validity asks for more: an arbitrary channel \(\mathcal A\) with Kraus operators \(A_k\) in the slot must still give a channel. Because \(r\) and \(j\) are measured, the branches do not interfere. \(V P_j\) cancels against its adjoint in the trace-preservation check. Changing variables from \((r,j)\) to \((r,a)\) with \(a=r\oplus j\) leaves, for each fixed \(a\), a sum over all returned \(r\) and all \(k\), which is the identity by \(\sum_kA_k^\dagger A_k=I\). Summing over \(2^{2n}\) values of \(a\) cancels the teleportation weight.

   The measurement is therefore essential to the proof and is also what makes the process not pure. A naive unitary purification of this circuit fails, because for some inputs on the added registers the connected map is no longer trace preserving.

   How to reuse it

   When a protocol succeeds only on one outcome, ask whether a consistency constraint can select it with a deterministic weight. The reusable test is whether the sum over Kraus operators survives a change of variables in the classical labels; if the labels interfere, this argument gives nothing.

2. Row orthogonality from a coordinate that is flipped equally

   Local unitaries inserted in the slots act on each feedback qubit independently, so a row of the connected transformation is a tensor product. Two rows are orthogonal if a single coordinate supplies orthogonal factors, which reduces unitarity to a combinatorial condition.

   With \(h(x)=x\oplus\pi(x)\) and single-qubit \(V_i\), the row of \(T_{\mathbf V}\) for output \(x\) is \[\bra x T_{\mathbf V}=\bigotimes_{i=1}^n\bra{x_i}V_iX^{h_i(x)}.\] Each factor is a row of a unitary, so each full row has norm one. For \(x\ne x^\prime\), suppose some \(i\) has \(x_i\ne x^\prime_i\) and \(h_i(x)=h_i(x^\prime)\). That coordinate gives two different rows of the same unitary \(V_iX^{h_i(x)}\), which are orthogonal for every \(V_i\), and the tensor product is then zero.

   A USO outmap \(s\) satisfies: for \(x\ne x^\prime\) there is an \(i\) with \(x_i\ne x^\prime_i\) and \(s_i(x)\ne s_i(x^\prime)\). Taking \(\pi=s\), both \(x_i\) and \(s_i(x)\) change at that coordinate, so their XOR \(h_i\) stays the same, which is the required condition. Permutations without this property have no such guarantee.

   Editorial check: for an acyclic USO on the 3-cube generated by a linear objective, with random local unitaries, \(T_{\mathbf V}\) was unitary to \(2\times10^{-15}\), and identity slots implemented \(s^{-1}\). For 50 random permutations of the same 8 strings, the largest deviation from unitarity was \(\lVert T^\dagger T-I\rVert_F\approx2.7\), so the condition is doing real work. This covers only the simple case without auxiliary registers.

   How to reuse it

   For a tensor-product family of operators, unitarity for all local choices can sometimes be reduced to a discrete condition on one coordinate. Before proving such a condition, check whether it already has a name in combinatorics, as happened here.

Source: Sections 1 and 2 (Theorems 1.1, 1.2, 2.1; the constructions of Sections 2.1 and 2.3). Based on the linked paper version. Derivations marked as editorial, and suggested uses in other problems, are editorial guidance rather than results of the paper.

Context & limitations

Why it matters. Linear postselected closed timelike curves were expected to lose their power once nonlinearity was removed; this shows linearity alone does not do that. It also separates purifiability, which only requires that an extension exists, from the ability to find that extension efficiently. USO reductions cover stochastic, mean-payoff and parity games and P-matrix linear complementarity, whose polynomial-time status is open.

Limitations. This is a result about a mathematical model, in which a circuit that describes the process is charged by its size. Nothing here shows such processes can be built, and the paper says their physical realisability is unknown; experiments so far concern the quantum switch. The pure result is conditional on USO being hard for quantum computers. We read the introduction and technical overview closely (Sections 1–2.3); the formal proofs in Sections 4–6 were not checked line by line.

Description based on the introduction and technical overview (Sections 1–2.3) of the linked arXiv version, read 2026-10-30; the formal proofs in Sections 4–6 were not checked line by line.