CQT CS Talk by Jianwei Li, Chinese Academy of Sciences, China

Title: Faster computing a short lattice basis

Date/Time: 21 Mar, 02:00 PM

Venue: CQT Level 3 Seminar Room, S15-03-15

Abstract: Given as input two integers a and b, Euclid's algorithm outputs the positive generator gcd(a,b) of the ideal aZ+bZ. Computing a lattice basis is a classical high-dimensional generalization of the gcd problem: given integer vectors a_1, ... , a_n \in Z^m, find a Z-basis of the lattice L={\sum_{i=1}^{n} x_{i}a_{i}, x_i \in Z} generated by the a_{i}'s. It is well-known that such a basis can be found in polynomial time: the fastest algorithm known is an algorithm computing the Hermite normal form (HNF). However such HNF algorithms are usually not suitable for the applications where the output basis is required to be ``short'', i.e. not much longer than the input vectors. In this talk, we will present an algorithm which computes a basis guaranteed to be ``short'' (namely, the size of the output basis does not increase the size of the input generators by more than a factor linear in the dimension), and whose asymptotical running time matches that of the best HNF algorithms: in fact, it reduces the problem to two well-chosen HNF computations. We will emphasise the intuitive idea behind our algorithm.

CQT Colloquium by Pedram Roushan, Google Inc., Santa Barbara, USA

Title: Superconducting qubits, the macroscopic atoms for building quantum processors

Date/Time: 28 Mar, 04:00 PM

Venue: CQT Level 3 Seminar Room, S15-03-15

Abstract:

Quantum theory, formed in the early part of the last century, has revolutionized our view on the nature of physical reality. More than half a century after its inception, a few great minds of physics, including Richard Feynman, predicted that the laws of quantum mechanics could give rise to a computing paradigm that is far superior to classical computing for certain tasks. Decades have passed since their great insight, but controlling fragile quantum systems well enough to implement even the most primitive quantum computer has proven difficult. A promising way of making quantum bits (qubits) is by using superconducting Josephson junctions. Devices made out of these junctions show quantum properties at the macroscopic level, providing advantages in controlling and connecting qubits. In this talk, I discuss the prospects and challenges in making quantum processors by using superconducting qubits. I report on our progress at Google and explain how qubits can be used to study problems at the core of statistical mechanics; in particular, we studied the signatures of transition from ergodic to the many-body localized state in a chain of 9 qubits.