What Can Be Computed with Indefinite Causal Structure?
Abstract
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 computation suffices to solve every problem in NP. The valid processes used by our algorithm satisfy the purification postulate of Araújo et al. (Quantum, 2017), and their generated channels are unitary, although their generating circuits are not. Second, requiring the process matrices themselves to be pure, we give a polynomial-time algorithm for unique-sink orientation, a general problem capturing several longstanding computational problems in optimization. Our unitary generators are constructed explicitly and efficiently. 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.
Related
- Indefinite causal order with output-signalling instruments
- Superposition of dynamics, indefinite causal order, and quantum histories
- Measuring Geometric Phase based on Indefinite Causal Order in a Sagnac Interferometer
- Proof-of-Principle Implementation of Quantum Key Distribution in an Indefinite Causal Order
- Unbounded separation between definite and indefinite causal order in finite-dimensional quantum metrology
BibTeX
@misc{shmueli2026what,
title = {{What Can Be Computed with Indefinite Causal Structure?}},
author = {Omri Shmueli},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.40573},
eprint = {2610.40573},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.40573},
}
RIS
TY - UNPB
TI - What Can Be Computed with Indefinite Causal Structure?
AU - Omri Shmueli
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2610.40573
UR - https://arxiv.org/abs/2610.40573
AB - 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 computation suffices to solve every problem in NP. The valid processes used by our algorithm satisfy the purification postulate of Araújo et al. (Quantum, 2017), and their generated channels are unitary, although their generating circuits are not. Second, requiring the process matrices themselves to be pure, we give a polynomial-time algorithm for unique-sink orientation, a general problem capturing several longstanding computational problems in optimization. Our unitary generators are constructed explicitly and efficiently. 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.
ER -