The Signal
Shmueli Ties Indefinite Causal Order to Computation Beyond BQP
Omri Shmueli’s paper studies whether quantum operations without a fixed causal order can solve problems beyond ordinary polynomial-time quantum computation. It presents a polynomial-time method for a unique-sink orientation problem, with th
Quantum.world Team · Written with AI · fact-checked ·
“Assuming that unique-sink orientation has no quantum polynomial-time algorithm, our result shows that indefinite causal order can provide computational power beyond BQP within the process matrix formalism, even while preserving unitarity.”
Omri Shmueli, author of “What Can Be Computed with Indefinite Causal Structure?”
Shmueli’s BQP result depends on a complexity assumption
Omri Shmueli’s paper, submitted to arXiv on October 29, argues that computations built around indefinite causal structure can go beyond BQP—a standard class of problems solvable by a quantum computer in polynomial time. The claim is conditional, not an unconditional proof that such a computational advantage exists: it depends on unique-sink orientation having no quantum polynomial-time algorithm.
The paper studies process matrices, a mathematical framework for connecting quantum operations without prescribing a fixed global causal order. In the model, a polynomial-size quantum circuit describes a process matrix, and an algorithm receives access to the channel generated by that description. The paper counts the size of the generating circuit as the computational cost.
That cost convention matters. The result establishes what can be computed with access to the model’s generated channels; it does not demonstrate that a laboratory can build a device that supplies those channels for arbitrary problems.
Two results, with different restrictions
Shmueli gives two main results. In the broader setting, polynomial-time process computation can solve every problem in NP, the class whose proposed solutions can be checked in polynomial time. The constructed processes are purifiable and generate unitary channels, but the generating circuits are not themselves unitary, so those processes are not pure.
The second result imposes the stricter requirement of pure processes, whose generating circuits are unitary. In that setting, the paper provides a polynomial-time algorithm for unique-sink orientation, or USO. An instance assigns directions to the edges of an n-dimensional Boolean cube so that each face has exactly one sink; the task is to find the sink of the entire cube.
The algorithm uses the generated channel once and succeeds with probability one, according to the paper. Shmueli’s construction coherently inverts a function derived from the edge directions, then obtains the global sink by applying that inverse to the all-zero string. The paper notes that the most efficient known quantum algorithms for USO take 2Ω(n) time, but the gap does not by itself prove that no polynomial-time quantum algorithm exists.
Process matrices are not ordinary circuit wiring
In an ordinary quantum circuit, the order of gate operations is specified by the circuit. Process matrices instead describe how local quantum operations can be correlated without fixing a global order, while requiring the resulting transformation to remain a valid quantum channel for every choice of local operations. That condition is intended to retain ordinary quantum mechanics locally, even when the global causal structure is not fixed.
The paper distinguishes pure processes from purifiable ones. A pure process preserves unitary evolution when the local operations are unitary, including when they act on auxiliary registers; a purifiable process can be obtained from a larger pure process by preparing extra inputs and discarding extra outputs. Shmueli’s NP result meets the latter condition, while the USO result is formulated using pure processes.
That distinction affects how far the results can be taken as a physical proposal. Shmueli writes that efficient physical realization for arbitrary USO instances remains open. The paper also cautions that a short circuit description does not guarantee an easy physical implementation: in postselected-teleportation constructions, success probabilities can be exponentially small even when the resulting channel is unitary.
The open question is whether USO belongs in BQP
The central comparison is therefore conditional. If USO has no quantum polynomial-time algorithm, Shmueli’s pure-process result supplies a route to computation beyond BQP within the process-matrix model. If an ordinary quantum algorithm can solve USO in polynomial time, that particular result would not establish the claimed separation.
The NP result is distinct: it applies to a broader class of processes that are purifiable but not pure, and it does not establish that standard quantum circuits can solve NP problems efficiently. Neither result is an experimental demonstration of indefinite causal structure providing this computational power. The paper’s concrete endpoint is a mathematical algorithm for finding the unique sink of an oriented Boolean cube, with its beyond-BQP implication resting on the unresolved quantum complexity of that task.