Quantum computing power increased by indefinite causal orders
What Can Be Computed with Indefinite Causal Structure?
Computational Complexity
Summary
This paper explores whether quantum computers can solve harder problems when their steps don’t have to happen in a fixed order. The authors show that by allowing quantum operations without a definite sequence, some tough problems in computer science can be solved efficiently. They use a framework where circuits generate quantum processes that don’t have a clear before-and-after order. Their results suggest that this unconventional approach can do more than regular quantum computers while still preserving certain quantum rules.
What this means in practice
- •For quantum algorithm designers: Design algorithms that leverage indefinite causal orders to solve optimization problems beyond current quantum computing limits.
- •For quantum hardware engineers: Explore hardware supporting non-fixed operation orders to implement new computational models with enhanced problem-solving capacity.
A theory result. No direct application yet.
Authors
Omri Shmueli
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 $\textbf{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 $\textbf{BQP}$ within the process matrix formalism, even while preserving unitarity.