Speakers
Description
Parameterised graph theory studies how the complexity of solving graph-theoretic problems depends on specific parameters of a graph. This perspective has already proven fruitful for understanding the complexity of simulating quantum circuits through tensor network (TNs). However, beyond simulation, the scope of what graph theory has to offer for TNs remains underexplored. For example, how do graph parameters affect the complexity of TN state tomography? And which properties of a TN state's entanglement graph determine whether it can also be efficiently represented in a simple form, say, as a matrix product state (MPS) or as a tree tensor network (TTN) state?
We answer these questions using parameterised graph theory. First, we demonstrate that two well-known graph parameters govern the cost of representing a state as an MPS or TTN state. Namely, we show upper bounds on the bond dimension of MPS and TTN representations in terms of cut-width and tree-cut width, respectively. In proving these results about TN representations, we develop an entanglement analogue of rerouting information in classical communication networks. Second, we prove upper bounds on the sample and computational complexity of TN state tomography in terms of graph parameters. In doing so, we generalise the disentangling MPS learner introduced by (Cramer et al, 2010) to TTNs and, more broadly, to TNs with arbitrary underlying graphs via reductions that depend on relevant graph parameters.
| Topic | Quantum state and process tomography with learning-based approaches |
|---|---|
| Additional Topic | Tensor methods and quantum-inspired machine learning |