テンソルネットワークの縮約 / 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.
Talks and presentations
Tight Query Complexity Bounds for Learning Graph Partitions
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.