時間: 12月26日

地點: 中科院軟件所5號樓334報告廳

10:00-10:45 Counting hypergraph colourings in the local lemma regime 郭珩（英國愛丁堡大學）

11:00-11:45 Tensors, computational complexity and tensor network states 葉科（中科院數學與系統科學研究院）

14:00-14:45 Efficient classical simulation of noisy quantum circuit 郜勛（清華大學交叉信息研究院）

15:00-15:45 Variable Version Lovasz Local Lemma: Beyond Shearer's Bound 劉興武（中科院計算技術研究所 ）

------------------------------

Title: Counting hypergraph colourings in the local lemma regime

Abstract: The local lemma is a powerful tool to show the existence of q-colourings for k-uniform hypergraphs under a simple degree bound. The original lemma is non-constructive, but Moser-Tardos' algorithm allows us to efficiently find such a colouring. However, if we want to uniformly at random generate one, the classic Markov chain approach does not work any longer in the said regime. In this talk, we will present an alternative approach to approximately counting and sampling hypergraph colorings in the local lemma regime. It is based on the recent work of Moitra (STOC, 2017). Our main contribution is to remove certain restrictions in Moitra's approach. Based on joint work with Chao Liao, Pinyan Lu, and Chihao Zhang.

Bio: Heng Guo is a lecturer in the University of Edinburgh. He came to Edinburgh after spending a semester in Berkeley and a year in London as a postdoc. He completed his Ph.D. in the University of Wisconsin - Madison in 2015, which has won the EATCS Distinguished Dissertation award.

-----------------------------

Title：Tensors, computational complexity and tensor network states

Abstract：I will talk about two aspects of tensors in this talk. First I will introduce the connection between tensor rank and computational complexity of bilinear maps. According to this relation, the problem of computing the bilinear complexity of a bilinear map is equivalent to the problem of computing the rank of an order three tensor. I will introduce the state of the art along this direction. Then I will switch to tensor network states, which are special types of tensor decompositions, from mathematical point of view. I will start with some examples and introduce some of our most recent works on tensor network states.

Bio: 中科院數學與系統研究院：副研究員,  University of Chicago： 統計系博后（2015-2017）數學 Dickson Instructor （2012-2015） Texas A&M University (2007-2012) 研究興趣：應用代數幾何。特別對張量相關的問題感興趣，例如張量的分解，計算復雜度理論以及張量網狀態。

-----------------------------

Title: Efficient classical simulation of noisy quantum circuit

Abstract: Quantum circuit is believed to be hard to simulate by classical computers. In realistic situations, there is always noise, which makes the quantum gates imperfect. In this talk, I consider classical simulation of several different ensembles of quantum circuits without fault-tolerance, such that the strength of the noise is regarded as a constant (not scaling with the system size). The noise model we consider is mixture of Pauli errors which include depolarizing noise as a special case. We study this problem by combining tensor network representation and fourier analysis of boolean function. This exhibits that tensor network provides an elegant pictorial reasoning tool and unleashes the power of fourier transformation in analyzing noisy quantum systems. First, I will prove for most of random quantum circuits, the measurement statistics is very close (exponentially decay with the strength of noise and circuit depth) to uniform distribution. This questions complexity-theoretic foundation of quantum supremacy by chaotic quantum circuit. Second, I will prove for a large proportion (say 99%) of ideal “classical” gates + noisy single qubit gates, there exists a polynomial classical algorithm simulating the measurement result to any constant additive error (say 0.01). The “classical” gates can be Clifford gates, classical reversible gates, etc. Third, I will construct an example such that a large size noisy quantum circuit can be simulated by small scale quantum computers. Different from other effort along this direction, we consider a scenario without explicit restriction on the entanglement among different sub-systems. This result might be a step towards understanding the computational complexity of analog quantum simulation and designing classical algorithm for simulating more physical noisy quantum systems. The result also introduces a question: for which kind of quantum evolution, the “quantumness” is robust to noise from computational point of view.

-------------------------------

Title: Variable Version Lovasz Local Lemma: Beyond Shearer's Bound

Abstract: Lovasz Local Lemma is a tool for proving the existence of objects satisfying multiple constraints. A tight criterion under which the abstract version Lovasz Local Lemma (abstract-LLL) holds was given by Shearer decades ago. However, little is known about that of the variable version LLL (variable-LLL) where events are generated by independent random variables, though this model of events is applicable to almost all applications of LLL. We introduce a necessary and sufficient criterion for variable-LLL, in terms of the probabilities of the events and the event-variable graph specifying the dependency among the events. Based on this new criterion, we obtain boundaries for two families of event-variable graphs, namely, cyclic and treelike bigraphs. These are the first two non-trivial cases where the variable-LLL boundary is fully determined. Though it is \#P-hard in general to determine variable-LLL boundaries, we can to some extent decide whether a gap exists between a variable-LLL boundary and the corresponding abstract-LLL boundary. In particular, we show that the gap existence can be decided without solving Shearer's conditions or checking our variable-LLL criterion. Equipped with this powerful theorem, we show that there is no gap if the the event-variable graph is a tree-like, while gap appears if it is cyclic. The problem is almost completely solved except when the induced dependency graph is chordal, in which case we also get partial solutions. The talk is based on joint work with Kun He, Liang Li, Yuyi Wang, and Mingji Xia.

Short Bio: 劉興武，中科院計算技術研究所副研究員，Frontiers of Computer Science青年編委，研究方向為分布式計算系統理論。