Given black-box access to the input and output systems, we develop the first efficient quantum causal order discovery algorithm with polynomial query complexity with respect to the number of systems. We model the causal order with quantum combs, and our algorithms output the order of inputs and outputs that the given process is compatible with. Our algorithm searches for the last input and the last output in the causal order, removes them, and iteratively repeats the above procedure until we get the order of all inputs and outputs. Our method guarantees a polynomial running time for quantum combs with a low Kraus rank, namely processes with low noise and little information loss. For special cases where the causal order can be inferred from local observations, we also propose algorithms that have lower query complexity and only require local state preparation and local measurements. Our algorithms will provide efficient ways to detect and optimize available transmission paths in quantum communication networks, as well as methods to verify quantum circuits and to discover the latent structure of multipartite quantum systems.
Given black-box access to the input and output systems, we develop the first efficient quantum causal order discovery algorithm with polynomial query complexity with respect to the number of systems. We model the causal order with quantum combs, and our algorithms output the order of inputs and outputs that the given process is compatible with. Our algorithm searches for the last input and the last output in the causal order, removes them, and iteratively repeats the above procedure until we get the order of all inputs and outputs. Our method guarantees a polynomial running time for quantum combs with a low Kraus rank, namely processes with low noise and little information loss. For special cases where the causal order can be inferred from local observations, we also propose algorithms that have lower query complexity and only require local state preparation and local measurements. Our algorithms will provide efficient ways to detect and optimize available transmission paths in quantum communication networks, as well as methods to verify quantum circuits and to discover the latent structure of multipartite quantum systems.
Abstract Complex processes often arise from sequences of simpler interactions involving a few particles at a time. These interactions, however, may not be directly accessible to experiments. Here we develop the first efficient method for unravelling the causal structure of the interactions in a multipartite quantum process, under the assumption that the process has bounded information loss and induces causal dependencies whose strength is above a fixed (but otherwise arbitrary) threshold. Our method is based on a quantum algorithm whose complexity scales polynomially in the total number of input/output systems, in the dimension of the systems involved in each interaction, and in the inverse of the chosen threshold for the strength of the causal dependencies. Under additional assumptions, we also provide a second algorithm that has lower complexity and requires only local state preparation and local measurements. Our algorithms can be used to identify processes that can be characterized efficiently with the technique of quantum process tomography. Similarly, they can be used to identify useful communication channels in quantum networks, and to test the internal structure of uncharacterized quantum circuits.
Polynomial transformations are basic primitives in quantum algorithms: quantum signal processing and singular value transformation compile univariate polynomials into circuits with query complexity essentially set by degree. Multivariable transformations of noncommuting matrices, however, lack a comparable synthesis theory. We develop a complete constructive theory under joint block access for all polynomials contractive on the prescribed matrix domain. Given a compact finite-state description of a degree-D polynomial P and 0<τ<1, we synthesize P with (1+τ)-optimal normalization using O(D/τ) queries, and exactly D under row-block access, matching a degree lower bound. The complete circuit realization is classically computable in polynomial time with polylogarithmic dependence on accuracy. The key to our construction is a finite algorithmic Schur--Agler theorem: the coefficient recurrence defines a polynomial-dimensional continuation space supporting a complete semidefinite certificate for contractivity on the prescribed domain. Factoring this certificate yields the contractive realization underlying the query algorithm.
Beyond matrix transformations, our framework lifts multivariable polynomial synthesis to quantum channel transformations. Given coherent Kraus access K={Ka}a, we synthesize any finite jointly contractive family of noncommutative polynomial maps K↦{Fb(K)}b as completely positive operations, allowing coherent interference among Kraus histories. Furthermore, channel-level transformations specified by causal Choi data can be synthesized explicitly as fixed-order quantum combs. Collectively, these results point to a broader program: multivariable approximation as a language for multi-operator quantum algorithms and higher-order quantum information processing.
Abstract Finding a causal model for a set of classical variables is now a well-established task—but what about the quantum equivalent? Even the notion of a quantum causal model is controversial. Here, we present a causal discovery algorithm for quantum systems. The input to the algorithm is a process matrix describing correlations between quantum events. Its output consists of different levels of information about the underlying causal model. Our algorithm determines whether the process is causally ordered by grouping the events into causally ordered non-signaling sets. It detects if all relevant common causes are included in the process, which we label Markovian, or alternatively if some causal relations are mediated through some external memory. For a Markovian process, it outputs a causal model, namely the causal relations and the corresponding mechanisms, represented as quantum states and channels. Our algorithm opens the route to more general quantum causal discovery methods.
We examine the number T of queries that a quantum network requires to compute several Boolean functions on {0,1}^N in the black-box model. We show that, in the black-box model, the exponential quantum speed-up obtained for partial functions (i.e. problems involving a promise on the input) by Deutsch and Jozsa and by Simon cannot be obtained for any total function: if a quantum algorithm computes some total Boolean function f with bounded-error using T black-box queries then there is a classical deterministic algorithm that computes f exactly with O(T^6) queries. We also give asymptotically tight characterizations of T for all symmetric f in the exact, zero-error, and bounded-error settings. Finally, we give new precise bounds for AND, OR, and PARITY. Our results are a quantum extension of the so-called polynomial method, which has been successfully applied in classical complexity theory, and also a quantum extension of results by Nisan about a polynomial relationship between randomized and deterministic decision tree complexity.
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.
This paper investigates the optimization of quantum algorithms by leveraging the principles of causal inference. Traditional quantum algorithm optimization often relies on heuristic methods or black-box approaches, lacking the transparency and robustness required for complex systems. We propose a novel framework that integrates causal inference with quantum algorithm design, aiming to identify and mitigate critical factors influencing algorithm performance. The core of our approach involves constructing a causal model of the quantum algorithm, represented as a causal Bayesian network. This network allows us to explicitly model dependencies between algorithmic components, enabling targeted interventions to improve efficiency and accuracy. We demonstrate the potential of this approach through a theoretical analysis, outlining a methodology for identifying confounding variables and implementing causal interventions. The resulting framework offers a more interpretable and reliable path towards optimizing quantum algorithms, particularly in scenarios where understanding underlying causal relationships is paramount.