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:2109.13166 · npj Quantum Information

Quantum causal unravelling

Ge Bai, Yadong Wu, Yan Zhu, Masahito Hayashi, Giulio Chiribella

Published Jun 21, 2022• 10 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1038/s41534-022-00578-4

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

Efficient Algorithms for Causal Order Discovery in Quantum Networks

Ge Bai, Yadong Wu, Yan Zhu +2 more

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.

arXiv:2012.01731•Dec 3, 2020•0 citations

Shadow process tomography of quantum channels

Jonathan Kunjummen, Minh C. Tran, Daniel Carney +1 more

Quantum process tomography is a critical capability for building quantum computers, enabling quantum networks, and understanding quantum sensors. Like quantum state tomography, the process tomography of an arbitrary quantum channel requires a number of measurements that scales exponentially in the number of quantum bits affected. However, the recent field of shadow tomography, applied to quantum states, has demonstrated the ability to extract key information about a state with only polynomially many measurements. In this work, we apply the concepts of shadow state tomography to the challenge of characterizing quantum processes. We make use of the Choi isomorphism to directly apply rigorous bounds from shadow state tomography to shadow process tomography, and we find additional bounds on the number of measurements that are unique to process tomography. Our results, which include algorithms for implementing shadow process tomography, enable new techniques including evaluation of channel concatenation and the application of channels to shadows of quantum states. This provides a dramatic improvement for understanding large-scale quantum systems.

arXiv:2110.03629•Physical Review A•Apr 4, 2023•54 citations

Experimental characterization of quantum processes: A selective and efficient method in arbitrary finite dimensions

Quimey Pears Stefano, Ignacio Perito, J. J. M. Varga +2 more

The temporal evolution of a quantum system can be characterized by quantum process tomography, a complex task that consumes a number of physical resources scaling exponentially with the number of subsystems. An alternative approach to the full reconstruction of a quantum channel is the selective and efficient quantum process tomography, a method that allows estimating, individually and up to the required accuracy, each element of the matrix that describes the process, using only a polynomial amount of resources. The implementation of this protocol is closely related to the possibility of building a complete set of mutually unbiased bases (MUBs), whose existence is known only when the dimension of the Hilbert space is the power of a prime number. However, an extension of the method that uses tensor products of maximal sets of MUBs has been recently introduced. Here we explicitly describe how to implement the algorithm for a selective and efficient estimation of a quantum process in a nonprime power dimension and conduct, an experimental verification of the method in a Hilbert space of dimension $d=6$. This is the smallest space for which a complete set of MUBs is not known to exist, but it can be decomposed as a tensor product of two Hilbert spaces of dimensions ${D}_{1}=2$ and ${D}_{2}=3$, in which a complete set of MUBs is already known. The six-dimensional states were codified in the discretized transverse linear momentum of photons. The state preparation and detection stages are dynamically programed with the use of only-phase spatial light modulators, in a versatile experimental setup that allows one to implement the algorithm in any finite dimension.

arXiv:2011.08228•Physical Review A•May 28, 2021•2 citations

Efficient Noisy Quantum State and Process Tomography

Chenyang Li, Shengxin Zhuang, Yukun Zhang +4 more

Efficiently characterizing large quantum states and processes is a central yet notoriously challenging task in quantum information science, as conventional tomography methods typically require resources that grow exponentially with system size. Here, we introduce a structure-agnostic learning framework for noisy $n$-qubit quantum circuits under~i.i.d.~single-qubit noise. We first prove that quantum states with unital noise channels admit an efficient learnable representation in the logarithmic-depth regime. We then extend this framework to quantum process tomography under constant noise, deriving a unified protocol that applies to both unital and non-unital noisy channels and retains efficient guarantees for logarithmic-depth circuits. This process-learning formulation is input-agnostic and imposes no distributional assumptions on the input quantum states. We further study a more general regime with arbitrary noise strength. In this setting, low-weight Pauli propagation induces a terminal truncation whose threshold depends logarithmically on the inverse accuracy, leading to quasi-polynomial complexity and near-unit success probability in the average case. In contrast to the preceding two results, this arbitrary-noise guarantee does not impose any restriction on the circuit depth, and therefore covers arbitrary-depth circuits, including both the noiseless limit ($γ= 0$) and the strong-decoherence regime ($γ= Θ(1)$). Numerical simulations of two-dimensional Hamiltonian dynamics further demonstrate the accuracy and robustness of the approach, including for structured circuits beyond the random-circuit setting assumed in the theoretical analysis. These results provide a scalable and practically relevant route toward characterizing large-scale noisy quantum devices, addressing a key bottleneck in the development of quantum technologies.

quant-pharXiv:2603.01521•Quantum Science and Technology•Mar 3, 2026•0 citations

Detection of Properties and Capacities of Quantum Channels

Chiara Macchiavello, Massimiliano Federico Sacchi

We review in a unified way a recently proposed method to detect properties of unknown quantum channels and lower bounds to quantum capacities, without resorting to full quantum process tomography. The method is based on the preparation of a fixed bipartite entangled state at the channel input or, equivalently, an ensemble of an overcomplete set of single-system states, along with few local measurements at the channel output.

arXiv:1712.06342•Open Systems & Information Dynamics•Dec 1, 2017•3 citations
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.
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.
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.
Quantum process tomography is a critical capability for building quantum computers, enabling quantum networks, and understanding quantum sensors. Like quantum state tomography, the process tomography of an arbitrary quantum channel requires a number of measurements that scales exponentially in the number of quantum bits affected. However, the recent field of shadow tomography, applied to quantum states, has demonstrated the ability to extract key information about a state with only polynomially many measurements. In this work, we apply the concepts of shadow state tomography to the challenge of characterizing quantum processes. We make use of the Choi isomorphism to directly apply rigorous bounds from shadow state tomography to shadow process tomography, and we find additional bounds on the number of measurements that are unique to process tomography. Our results, which include algorithms for implementing shadow process tomography, enable new techniques including evaluation of channel concatenation and the application of channels to shadows of quantum states. This provides a dramatic improvement for understanding large-scale quantum systems.
The temporal evolution of a quantum system can be characterized by quantum process tomography, a complex task that consumes a number of physical resources scaling exponentially with the number of subsystems. An alternative approach to the full reconstruction of a quantum channel is the selective and efficient quantum process tomography, a method that allows estimating, individually and up to the required accuracy, each element of the matrix that describes the process, using only a polynomial amount of resources. The implementation of this protocol is closely related to the possibility of building a complete set of mutually unbiased bases (MUBs), whose existence is known only when the dimension of the Hilbert space is the power of a prime number. However, an extension of the method that uses tensor products of maximal sets of MUBs has been recently introduced. Here we explicitly describe how to implement the algorithm for a selective and efficient estimation of a quantum process in a nonprime power dimension and conduct, an experimental verification of the method in a Hilbert space of dimension d=6d=6d=6. This is the smallest space for which a complete set of MUBs is not known to exist, but it can be decomposed as a tensor product of two Hilbert spaces of dimensions D1=2{D}_{1}=2D1​=2 and D2=3{D}_{2}=3D2​=3, in which a complete set of MUBs is already known. The six-dimensional states were codified in the discretized transverse linear momentum of photons. The state preparation and detection stages are dynamically programed with the use of only-phase spatial light modulators, in a versatile experimental setup that allows one to implement the algorithm in any finite dimension.
Efficiently characterizing large quantum states and processes is a central yet notoriously challenging task in quantum information science, as conventional tomography methods typically require resources that grow exponentially with system size. Here, we introduce a structure-agnostic learning framework for noisy nnn-qubit quantum circuits under~i.i.d.~single-qubit noise. We first prove that quantum states with unital noise channels admit an efficient learnable representation in the logarithmic-depth regime. We then extend this framework to quantum process tomography under constant noise, deriving a unified protocol that applies to both unital and non-unital noisy channels and retains efficient guarantees for logarithmic-depth circuits. This process-learning formulation is input-agnostic and imposes no distributional assumptions on the input quantum states. We further study a more general regime with arbitrary noise strength. In this setting, low-weight Pauli propagation induces a terminal truncation whose threshold depends logarithmically on the inverse accuracy, leading to quasi-polynomial complexity and near-unit success probability in the average case. In contrast to the preceding two results, this arbitrary-noise guarantee does not impose any restriction on the circuit depth, and therefore covers arbitrary-depth circuits, including both the noiseless limit (γ=0γ= 0γ=0) and the strong-decoherence regime (γ=Θ(1)γ= Θ(1)γ=Θ(1)). Numerical simulations of two-dimensional Hamiltonian dynamics further demonstrate the accuracy and robustness of the approach, including for structured circuits beyond the random-circuit setting assumed in the theoretical analysis. These results provide a scalable and practically relevant route toward characterizing large-scale noisy quantum devices, addressing a key bottleneck in the development of quantum technologies.