## テンソルネットワークの縮約 / Contraction of Tensor Networks

Talk, Blueqat Summit 2022, Online

We give a very basic (and hand-wavy) introduction to Tensor network simulation of quantum circuits, and discuss and compare different ways of contracting them.

Talk, Blueqat Summit 2022, Online

We give a very basic (and hand-wavy) introduction to Tensor network simulation of quantum circuits, and discuss and compare different ways of contracting them.

Talk, 35th Conference on Learning Theory, London, UK

Given a partition of a graph into connected components, the membership oracle asserts whether any two vertices of the graph lie in the same component or not. We prove that for $n\ge k\ge 2$, learning the components of an $n$-vertex hidden graph with $k$ components requires at least $(k-1)n-\binom k2$ membership queries. Our result improves on the best known information-theoretic bound of $\Omega(n\log k)$ queries, and exactly matches the query complexity of the algorithm introduced by *Reyzin and Srivastava, 2007* for this problem. Additionally, we introduce an oracle that can learn the number of components of $G$ in asymptotically fewer queries than learning the full partition, thus answering another question posed by the same authors. Lastly, we introduce a more applicable version of this oracle, and prove asymptotically tight bounds of $\widetilde\Theta(m)$ queries for both learning and verifying an $m$-edge hidden graph $G$ using it.