Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2410.04630

Unitary Closed Timelike Curves can Solve all of NP

Omri Shmueli

quant-phSubmitted Oct 6, 2024• Announced Oct 8, 2024• 0 citations• Revised Oct 29, 2026 (v2)
v1 · Oct 6, 2024v2 · Oct 29, 2026
arXivHTMLPDF

Abstract

Born in the intersection between quantum mechanics and general relativity, indefinite causal structure is the idea that in the continuum of time, some sets of events do not have an inherent causal order between them. Process matrices, introduced by Oreshkov, Costa and Brukner (Nature Communications, 2012), define quantum information processing with indefinite causal structure -- a generalization of the operations allowed in standard quantum information processing, and to date, are the most studied such generalization. Araujo et al. (Physical Review A, 2017) defined the computational complexity of process matrices, and showed that polynomial-time process matrix computation is equivalent to standard polynomial-time quantum computation with access to a weakening of post-selection Closed Timelike Curves (CTCs), that are restricted to be $\textit{linear}$. Araujo et al. accordingly defined the complexity class for efficient process matrix computation as $\mathbf{BQP}_{\ell CTC}$ (which trivially contains $\mathbf{BQP}$), and posed the open question of whether $\mathbf{BQP}_{\ell CTC}$ contains computational tasks that are outside $\mathbf{BQP}$. In this work we solve this open question under a widely believed hardness assumption, by showing that $\mathbf{NP} \subseteq \mathbf{BQP}_{\ell CTC}$. Our solution is captured by an even more restricted subset of process matrices that are purifiable (Araujo et al., Quantum, 2017), which (1) is conjectured more likely to be physical than arbitrary process matrices, and (2) is equivalent to polynomial-time quantum computation with access to $\textit{unitary}$ (which are in particular linear) post-selection CTCs. Conceptually, our work shows that the previously held belief, that non-linearity is what enables CTCs to solve $\mathbf{NP}$, is false, and raises the importance of understanding whether purifiable process matrices are physical or not.

Comments
The paper is withdrawn due to an error in the definition of the computational model, which invalidates the proof of the main result. The model imposes consistency only for identity local operations but does not impose the stronger consistency requirement under arbitrary local operations, which is needed for valid process matrices

Related papers

What Can Be Computed with Indefinite Causal Structure?

Omri Shmueli

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.

quant-pharXiv:2610.40573•Oct 30, 2026•0 citations

Quantum computation with indefinite causal structures

Mateus Araújo, Philippe Allard Guérin, Ämin Baumeler

One way to study the physical plausibility of closed timelike curves (CTCs) is to examine their computational power. This has been done for Deutschian CTCs (D-CTCs) and postselection CTCs (P-CTCs), with the result that they allow for the efficient solution of problems in PSPACE and PP, respectively. Since these are extremely powerful complexity classes, which are not expected to be solvable in reality, this can be taken as evidence that these models for CTCs are pathological. This problem is closely related to the nonlinearity of this models, which also allows, for example, cloning quantum states, in the case of D-CTCs, or distinguishing nonorthogonal quantum states, in the case of P-CTCs. In contrast, the process matrix formalism allows one to model indefinite causal structures in a linear way, getting rid of these effects and raising the possibility that its computational power is rather tame. In this paper, we show that process matrices correspond to a linear particular case of P-CTCs, and therefore that its computational power is upperbounded by that of PP. We show, furthermore, a family of processes that can violate causal inequalities but nevertheless can be simulated by a causally ordered quantum circuit with only a constant overhead, showing that indefinite causality is not necessarily hard to simulate.

arXiv:1706.09854•Physical Review A•Nov 13, 2017•73 citations

Higher-order quantum processes respecting closed labs in a spacetime have quantum controlled causal order

Matthias Salzger, V. Vilasini

In quantum causality and quantum information, there is a vast landscape of abstract quantum protocols permitting cyclic or non-acyclic causal structures between operations, including frameworks for indefinite causal order and higher-order quantum processes such as process matrices. A longstanding open question is what is the largest class of abstract processes that admit physical realisations without post-selection. In this work, we provide a rigorous answer using a top-down approach grounded in relativistic causality principles. Building on the framework of causal boxes, which characterise the most general quantum information-processing protocols compatible with fixed background spacetimes, we formalise additional constraints (Acting Once + Local Order) capturing the closed-laboratory assumptions of the process matrix framework at a fine-grained spacetime level. We prove that any protocol in a classical acyclic spacetime satisfying these conditions is behaviourally equivalent to a quantum circuit with quantum control of causal order (QC-QC), providing a top-down derivation of QC-QCs from physical principles. Our results show that QC-QCs constitute precisely the class of higher-order quantum processes, including those with indefinite order, that can be physically realised within classical spacetime, ruling out more general non-causal processes under the closed-labs assumption. This clarifies the relationship between abstract higher-order process matrix frameworks and experimentally accessible quantum protocols, as well as the interplay between coarse-grained cyclic and fine-grained acyclic operational causal structures. We also develop characterisation techniques for process box protocols that lead to new causality-based open questions concerning spacetime quantum protocols and relativistic quantum experiments.

quant-pharXiv:2605.08351•May 12, 2026•2 citations

Closed timelike curves make quantum and classical computing equivalent

Scott Aaronson, John Watrous

While closed timelike curves (CTCs) are not known to exist, studying their consequences has led to non-trivial insights into general relativity, quantum information and other areas. In this paper, we show that, if CTCs existed, quantum computers would be no more powerful than classical computers: both would have the (extremely large) power of the complexity class polynomial space ( ), consisting of all problems solvable by a conventional computer using a polynomial amount of memory. This solves an open problem proposed by one of us in 2005, and gives an essentially complete understanding of computational complexity in the presence of CTCs. Following the work of Deutsch, we treat a CTC as simply a region of spacetime where a ‘causal consistency’ condition is imposed, meaning that nature has to produce a (probabilistic or quantum) fixed point of some evolution operator. Our conclusion is then a consequence of the following theorem: given any quantum circuit (not necessarily unitary), a fixed point of the circuit can be (implicitly) computed in . This theorem might have independent applications in quantum information.

arXiv:0808.2669•Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences•Nov 11, 2008•109 citations

Connecting processes with indefinite causal order and multi-time quantum states

Ralph Silva, Yelena Guryanova, Anthony J. Short +3 more

Recently, the possible existence of quantum processes with indefinite causal order has been extensively discussed, in particular using the formalism of process matrices. Here we give a new perspective on this question, by establishing a direct connection to the theory of multi-time quantum states. Specifically, we show that process matrices are equivalent to a particular class of pre- and post-selected quantum states. This offers a new conceptual point of view to the nature of process matrices. Our results also provide an explicit recipe to experimentally implement any process matrix in a probabilistic way, and allow us to generalize some of the previously known properties of process matrices. Finally we raise the issue of the difference between the notions of indefinite temporal order and indefinite causal order, and show that one can have indefinite causal order even with definite temporal order.

arXiv:1701.08638•New Journal of Physics•Oct 23, 2017•49 citations

A purification postulate for quantum mechanics with indefinite causal order

Mateus Araújo, Adrien Feix, Miguel Navascués +1 more

To study which are the most general causal structures which are compatible with local quantum mechanics, Oreshkov e t a l . \cite{oreshkov12} introduced the notion of a process: a resource shared between some parties that allows for quantum communication between them without a predetermined causal order. These processes can be used to perform several tasks that are impossible in standard quantum mechanics: they allow for the violation of causal inequalities, and provide an advantage for computational and communication complexity. Nonetheless, no process that can be used to violate a causal inequality is known to be physically implementable. There is therefore considerable interest in determining which processes are physical and which are just mathematical artefacts of the framework. Here we make key progress in this direction by proposing a purification postulate: processes are physical only if they are purifiable. We derive necessary conditions for a process to be purifiable, and show that several known processes do not satisfy them.

arXiv:1611.08535•Quantum•Apr 25, 2017•100 citations
Born in the intersection between quantum mechanics and general relativity, indefinite causal structure is the idea that in the continuum of time, some sets of events do not have an inherent causal order between them. Process matrices, introduced by Oreshkov, Costa and Brukner (Nature Communications, 2012), define quantum information processing with indefinite causal structure -- a generalization of the operations allowed in standard quantum information processing, and to date, are the most studied such generalization.
Araujo et al. (Physical Review A, 2017) defined the computational complexity of process matrices, and showed that polynomial-time process matrix computation is equivalent to standard polynomial-time quantum computation with access to a weakening of post-selection Closed Timelike Curves (CTCs), that are restricted to be linear\textit{linear}linear. Araujo et al. accordingly defined the complexity class for efficient process matrix computation as BQPℓCTC\mathbf{BQP}_{\ell CTC}BQPℓCTC​ (which trivially contains BQP\mathbf{BQP}BQP), and posed the open question of whether BQPℓCTC\mathbf{BQP}_{\ell CTC}BQPℓCTC​ contains computational tasks that are outside BQP\mathbf{BQP}BQP.
In this work we solve this open question under a widely believed hardness assumption, by showing that NP⊆BQPℓCTC\mathbf{NP} \subseteq \mathbf{BQP}_{\ell CTC}NP⊆BQPℓCTC​. Our solution is captured by an even more restricted subset of process matrices that are purifiable (Araujo et al., Quantum, 2017), which (1) is conjectured more likely to be physical than arbitrary process matrices, and (2) is equivalent to polynomial-time quantum computation with access to unitary\textit{unitary}unitary (which are in particular linear) post-selection CTCs. Conceptually, our work shows that the previously held belief, that non-linearity is what enables CTCs to solve NP\mathbf{NP}NP, is false, and raises the importance of understanding whether purifiable process matrices are physical or not.
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\textbf{NP}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\textbf{BQP}BQP within the process matrix formalism, even while preserving unitarity.
One way to study the physical plausibility of closed timelike curves (CTCs) is to examine their computational power. This has been done for Deutschian CTCs (D-CTCs) and postselection CTCs (P-CTCs), with the result that they allow for the efficient solution of problems in PSPACE and PP, respectively. Since these are extremely powerful complexity classes, which are not expected to be solvable in reality, this can be taken as evidence that these models for CTCs are pathological. This problem is closely related to the nonlinearity of this models, which also allows, for example, cloning quantum states, in the case of D-CTCs, or distinguishing nonorthogonal quantum states, in the case of P-CTCs. In contrast, the process matrix formalism allows one to model indefinite causal structures in a linear way, getting rid of these effects and raising the possibility that its computational power is rather tame. In this paper, we show that process matrices correspond to a linear particular case of P-CTCs, and therefore that its computational power is upperbounded by that of PP. We show, furthermore, a family of processes that can violate causal inequalities but nevertheless can be simulated by a causally ordered quantum circuit with only a constant overhead, showing that indefinite causality is not necessarily hard to simulate.
In quantum causality and quantum information, there is a vast landscape of abstract quantum protocols permitting cyclic or non-acyclic causal structures between operations, including frameworks for indefinite causal order and higher-order quantum processes such as process matrices. A longstanding open question is what is the largest class of abstract processes that admit physical realisations without post-selection. In this work, we provide a rigorous answer using a top-down approach grounded in relativistic causality principles. Building on the framework of causal boxes, which characterise the most general quantum information-processing protocols compatible with fixed background spacetimes, we formalise additional constraints (Acting Once + Local Order) capturing the closed-laboratory assumptions of the process matrix framework at a fine-grained spacetime level. We prove that any protocol in a classical acyclic spacetime satisfying these conditions is behaviourally equivalent to a quantum circuit with quantum control of causal order (QC-QC), providing a top-down derivation of QC-QCs from physical principles. Our results show that QC-QCs constitute precisely the class of higher-order quantum processes, including those with indefinite order, that can be physically realised within classical spacetime, ruling out more general non-causal processes under the closed-labs assumption. This clarifies the relationship between abstract higher-order process matrix frameworks and experimentally accessible quantum protocols, as well as the interplay between coarse-grained cyclic and fine-grained acyclic operational causal structures. We also develop characterisation techniques for process box protocols that lead to new causality-based open questions concerning spacetime quantum protocols and relativistic quantum experiments.
While closed timelike curves (CTCs) are not known to exist, studying their consequences has led to non-trivial insights into general relativity, quantum information and other areas. In this paper, we show that, if CTCs existed, quantum computers would be no more powerful than classical computers: both would have the (extremely large) power of the complexity class polynomial space ( ), consisting of all problems solvable by a conventional computer using a polynomial amount of memory. This solves an open problem proposed by one of us in 2005, and gives an essentially complete understanding of computational complexity in the presence of CTCs. Following the work of Deutsch, we treat a CTC as simply a region of spacetime where a ‘causal consistency’ condition is imposed, meaning that nature has to produce a (probabilistic or quantum) fixed point of some evolution operator. Our conclusion is then a consequence of the following theorem: given any quantum circuit (not necessarily unitary), a fixed point of the circuit can be (implicitly) computed in . This theorem might have independent applications in quantum information.
Recently, the possible existence of quantum processes with indefinite causal order has been extensively discussed, in particular using the formalism of process matrices. Here we give a new perspective on this question, by establishing a direct connection to the theory of multi-time quantum states. Specifically, we show that process matrices are equivalent to a particular class of pre- and post-selected quantum states. This offers a new conceptual point of view to the nature of process matrices. Our results also provide an explicit recipe to experimentally implement any process matrix in a probabilistic way, and allow us to generalize some of the previously known properties of process matrices. Finally we raise the issue of the difference between the notions of indefinite temporal order and indefinite causal order, and show that one can have indefinite causal order even with definite temporal order.
To study which are the most general causal structures which are compatible with local quantum mechanics, Oreshkov e t a l . \cite{oreshkov12} introduced the notion of a process: a resource shared between some parties that allows for quantum communication between them without a predetermined causal order. These processes can be used to perform several tasks that are impossible in standard quantum mechanics: they allow for the violation of causal inequalities, and provide an advantage for computational and communication complexity. Nonetheless, no process that can be used to violate a causal inequality is known to be physically implementable. There is therefore considerable interest in determining which processes are physical and which are just mathematical artefacts of the framework. Here we make key progress in this direction by proposing a purification postulate: processes are physical only if they are purifiable. We derive necessary conditions for a process to be purifiable, and show that several known processes do not satisfy them.