Infinite or indefinite: the query cost of simulating the quantum switch

The paper in detail

For Kraus operators \(A_i\) and \(B_j\) the switch has Kraus operators \(\ketbra00\otimes B_jA_i+\ketbra11\otimes A_iB_j\); the same pair appears in both orders, so the control can interfere \(B_jA_i\) with \(A_iB_j\). No circuit that calls each box once in a definite order reproduces this, yet photonic experiments realise it. The paper asks what an ordinary circuit must pay in extra calls, a definite way to say how much an indefinite order is worth.

Exact simulation fails for a structural reason. If a finite circuit worked for all channels, it would also work for each channel mixed with the identity, and expanding in the mixing weights extracts a circuit with one call per box that implements the switch diluted with weight \(1/(MN)\). The paper then shows that no definite-order circuit implements a diluted switch with any positive weight: positivity confines the circuit's Choi operator to a small subspace, where every definite-order circuit satisfies a linear identity that the switch term violates.

For approximate simulation the hard boxes are uniform mixtures of \(r\) Haar-random unitaries. With few calls, repeated indices are unlikely, so each sampled unitary is used at most once, and a circuit that calls \(U\) before \(V\) can produce \(UV\) only with average test probability \(O(d^{-2})\); its coherence between the two orders is \(O(1/d)\) while the switch keeps full coherence.

The one-bit task compares dephasing \(\mathcal E_{p,U}=(1-p)\mathrm{id}+p\Delta_U\) in a fixed unknown basis with the model \(\mathcal M_p=(1-p)\mathrm{id}+p\Lambda\), where \(\Lambda\) averages the dephasing over bases. Both have the same entanglement and average gate fidelities. The switch tests whether Kraus operators commute; an ordinary circuit must find a basis it does not know, and the lower bound uses the path-recording framework of Ma and Huang to show that its final states under the two hypotheses stay close. Open questions are tighter exponents and physically structured noise families that keep the separation.

Transferable methods

1. Identity mixtures extract a one-call circuit

   Universal correctness is a strong assumption: it must hold for channels mixed with the identity. Because the circuit's output is separately linear in each numbered call, the mixing weights turn correctness into a polynomial identity, and one coefficient of that polynomial is a circuit that keeps only one random call to each box.

   Number the \(M\) calls to \(A\) and the \(N\) calls to \(B\); let \(\mathcal Q_{S,S'}\) keep the calls in \(S,S'\) and replace the rest by the identity. With \(A_x=xA+(1-x)\mathrm{id}\) and \(B_y\) likewise, \[\mathcal S_+[A_x,B_y]=\sum_{S,S'}x^{\lvert S\rvert}(1-x)^{M-\lvert S\rvert}y^{\lvert S'\rvert}(1-y)^{N-\lvert S'\rvert}\,\mathcal Q_{S,S'}[A,B].\] These functions are linearly independent on \((0,1)^2\), so coefficients can be compared.

   The coefficient of \(x(1-x)^{M-1}y(1-y)^{N-1}\) on the right is \(MN\,\mathcal Q_1\), with \(\mathcal Q_1\) the average over one kept call per box. On the left, the switch is bilinear, so \(\mathcal S_+[A_x,B_y]\) has four terms; multiplying each by \((x+1-x)^{M-1}(y+1-y)^{N-1}=1\) and counting gives coefficients \(1\), \(N-1\), \(M-1\) and \((M-1)(N-1)\). Hence \[\mathcal Q_1=\tfrac{1}{MN}\Bigl(\mathcal S_+[A,B]+(N-1)\mathcal S_+[A,\mathrm{id}]+(M-1)\mathcal S_+[\mathrm{id},B]+(M-1)(N-1)\mathcal S_+[\mathrm{id},\mathrm{id}]\Bigr),\] a switch diluted with weight \(1/(MN)\) that a one-call-per-box circuit would then implement.

   Editorial remark: the argument needs correctness on non-unitary inputs, which is why it does not contradict the three-call simulation when one box is promised unitary; the identity mixtures break that promise.

   How to reuse it

   To show that finitely many queries cannot simulate a process that is multilinear in its oracles, mix each oracle with a trivial one and read off a low-order coefficient. This reduces many-query simulations to one-query ones with a diluted target, which is often easier to refute.

2. Switch visibility as a commutation test

   Measuring the control after a switch with control \(\ket+\) and maximally mixed target gives a single number, the visibility, that is 1 exactly when all Kraus operators of the two boxes commute. Dephasing in any fixed basis passes this test; the depolarizing model, which matches its fidelities, fails it.

   The visibility is \[v(A,B)=\frac1d\,\mathrm{Re}\sum_{i,j}\mathrm{Tr}\bigl(B_jA_iB_j^{\dagger}A_i^{\dagger}\bigr)=1-\frac{1}{2d}\sum_{i,j}\lVert[A_i,B_j]\rVert_{\mathrm{HS}}^2,\] and the outcome \(-\) has probability \((1-v)/2\). Dephasing has Kraus operators \(\sqrt{1-p}\,\mathbb 1\) and \(\sqrt p\,P_j\), which commute, so \(v(\mathcal E_{p,U})=1\). Writing \(\mathcal M_p=\alpha\,\mathrm{id}+(1-\alpha)\Omega\) with \(\alpha=1-pd/(d+1)\) and using \(v(\Omega,\Omega)=1/d^2\) gives \[v(\mathcal M_p)=1-p^2\,\frac{d-1}{d+1}.\]

   To avoid a \(1/p^2\) cost at weak noise, each slot holds \(m=\lceil1/p\rceil\) consecutive calls. Dephasing blocks still commute; the model's block is \(\alpha^m\mathrm{id}+(1-\alpha^m)\Omega\) with \(\alpha^m\le e^{-2/3}\), so \(\Pr[-]=\tfrac12(1-\alpha^m)^2(1-d^{-2})\) is at least about 0.089. A constant number of repetitions decides with one-sided error using \(O(1/p)\) calls.

   Editorial checks: the visibility formulas agree with direct Kraus sums for \(d=2,3,4\) and \(p\in\{0.3,1\}\); a Monte Carlo average of \(\Delta_U\) over \(2\times10^4\) Haar bases matches \((\rho+\mathbb 1\,\mathrm{Tr}\rho)/(d+1)\) to \(10^{-3}\); and the block probability stays above 0.089 for \(p\) from 0.01 to 1.

   How to reuse it

   When two noise models agree on every fidelity-type figure, look for a property of the Kraus operators themselves, such as commutation, and an interference experiment that reads it. The switch is one such experiment; a device that reports measurement outcomes allows an ordinary sequential version.

Source: Section 3.1 (Lemma 6); Section 2.3 and Section 5.1. 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. It prices indefinite causal order as a resource: doing without the switch costs exponentially many calls in the number of qubits, and infinitely many for exact reproduction. The third result is a provable query advantage on a noise-characterisation task, using two noise models that randomized benchmarking cannot tell apart.

Limitations. The statements are worst case, with Haar-random hard instances; structured families of channels may be easy. The bounds leave gaps (\(d^{1/4}\) against \(d^2\); the exponent \(1/16\) comes from the recording technique), and concurrent work by Goldin gives \(\Omega(d^{1/3})\) for approximate simulation. The advantage counts device calls and assumes the device returns only its quantum output; if a measurement reports its outcome, an ordinary circuit can estimate the same visibility. The author states that AI systems from the GPT, Claude and Gemini families worked out most of the technical details and wrote the Lean formalization.

Description based on the full arXiv HTML of v1, read 2026-11-13: Sections 1–2, Section 3.1 (Lemma 6) and the opening of 3.2, Sections 5.1–5.3, the Discussion with the concurrent-work note and AI statement, and the setup of Appendix A. The approximate-simulation proofs of Section 4, the linear certificate of Lemma 9 and the label-cache analysis were not checked. The visibility formulas of Section 5.1, the identity \(\Lambda=(\mathrm{id}+d\,\Omega)/(d+1)\) and the block-test constant were checked numerically.