CQT CS Talk by Shengyu Zhang, The Chinese University of Hong Kong (CUHK)

Date/Time: Wednesday, 24 Sep at 2:00 pm

Venue: CQT Seminar Room, S15-03-15

Title: Fast quantum algorithms for Least Squares Regression and Statistic Leverage Scores

Abstract:

Least squares regression is the simplest and most widely used technique for solving overdetermined systems of linear equations $Ax = b$, where $A\in\RR^{n\times p}$ has full column rank and $b\in \RR^n$. Though there is a well known unique solution $x^*\in \RR^p$ to minimize the squared error $\|Ax - b\|_2^2$, the best classical algorithm to find $x^*$ takes time $\Omega(n)$, even for sparse and well-conditioned matrices $A$, a fairly large class of input instances commonly seen in practice. In this paper, we design an efficient quantum algorithm to generate a quantum state proportional to $\ket{x^*}$. The algorithm takes only $O(\log n)$ time for sparse and well-conditioned $A$.

When the condition number of $A$ is large, a canonical solution is to use regularization. We give efficient quantum algorithms for two regularized regression problems, including ridge regression and $\delta$-truncated SVD, with similar costs and solution approximation.

Given a matrix $A\in \RR^{n\times p}$ of rank $r$ with SVD $A = U\Sigma V^T$ where $U \in \RR^{n\times r}$, $\Sigma \in \RR^{r\times r}$ and $V\in \RR^{p \times r}$, the statistical leverage scores of $A$ are the squared row norms of $U$, defined as $s_i = \nor{U_i}_2^2$, for $i = 1,...,n$. The matrix coherence is the largest statistic leverage score. These quantities play an important role in many machine learning algorithms. The best classical algorithm to approximate these values runs in time $\Omega(np)$. In this work, we introduce an efficient quantum algorithm to approximate $s_i$ in time $O(\log n)$ when $A$ is sparse and the ratio between $A#39;s largest singular value and smallest non-zero singular value is constant. This gives an exponential speedup over the best classical algorithms. Different than previous examples which are mainly modern algebraic or number theoretic, this problem is linear algebraic. It is also different than previous quantum algorithms for solving linear equations and least squares regression, whose outputs compress the $p$-dimensional solution to a $\log(p)$-qubit quantum state.

Joint work with Yang Liu.

CQT PhD Thesis Oral Defence by Markus Baden

Date/Time: Friday, 26 Sep at 9:00 pm

Venue: CQT Level 3 Conference Room, S15-03-18

Title: Quantum optics with cavity-assisted Raman transition

Abstract: We demonstrate that cavity-assisted Raman transitions between hyperfine ground states are a flexible way to create effective atom-photon interactions. We use them to create an effective Tavis-Cummings model and an effective Dicke model. In both

situation we have full control over all model parameters. In the Tavis-Cummings

model we reach strong coupling and observe a normal mode splitting in the cavity

transmission around the dispersively shifted cavity resonance. In the Dicke model we

reach the regime of the phase transition and observe the onset of superradiant

scattering into the cavity above critical coupling.

CQT Colloquium by Gianni Blatter, ETH Zurich

Date/Time: Wednesday, 15 Oct at 4:00 pm

Venue: CQT Seminar Room, S15-03-15

Title: Matter and Light: sharing ideas and concepts in the quantum world

Abstract:

With the development of quantum engineering, the traditionally separated fields of condensed matter physics and quantum optics are exchanging ideas and concepts to their mutual benefit. In the first part of the talk, I will recap the development of electronic structure theory in materials from weak- to strong interactions and then discuss how ideas on strong correlations have penetrated into cold atomic physics and cavity optics in the last decade. In the second part I will discuss a reverse example, how ideas on entanglement, typically a realm of quantum optics, have started to penetrate into mesoscopic physics and define the new field of electronic optics