Efficient Data Compression and Causal Order Discovery for Multipartite Quantum Systems

In this talk, I will discuss two problems: quantum data compression
and quantum causal order discovery, both for multipartite quantum
systems. For data compression, we model finitely correlated states as
tensor networks, and design quantum compression algorithms. We first
establish an upper bound on the amount of memory needed to store an
arbitrary state from a given state family. The bound is determined by
the minimum cut of a suitable flow network, and is related to the flow
of information from the manifold of parameters that specify the states
to the physical systems in which the states are embodied. We then
provide a compression algorithm for general state families, and show
that the algorithm runs in polynomial time for matrix product states.

For quantum causal order discovery, we develop the first efficient
quantum causal order discovery algorithm with polynomial black-box
queries with respect to the number of systems. We model the causal
order with quantum combs, and our algorithm outputs the order of
inputs and outputs that the given process is compatible with. 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 results 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.