Efficient Data Compression and Causal Order Discovery for Multipartite Quantum Systems

Abstract:

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.