{"id":"arxiv/2610.40573","url":"https://arxiv.org/abs/2610.40573","tags":["quant-ph","cs.CC"],"score":0,"title":"What Can Be Computed with Indefinite Causal Structure?","domain":"quant-ph","source":"arxiv","authors":["Omri Shmueli"],"reviews":0,"subject":"quant-ph","summary":"Can quantum computation become more powerful when operations do not need to follow a definite causal order? We study this question in the process matrix formalism of Oreshkov et al. (Nature Communications, 2012), which allows quantum operations to be connected without a fixed global order. In the computational model, a quantum circuit succinctly describes a process matrix, and the algorithm is given access to its generated channel, with computational cost measured by the size of the generating circuit. We give polynomial-time algorithms in two settings. First, general process matrix…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-10-29","reactions":{}}