Life with Physics

 

When I first learned Andrew Ng's CS229 machine learning, I did not really understand KKT conditions in his lecture note 3 , in which KKT conditions are presented without proof and mixed with the content of Lagrangian duality. Recently, I occasionally read a blog which provides a more clear and intuitive illustration on KKT conditions. Let me try to rephase the argument in this blog. Lagrangian Multiplier KKT conditions are about the optimization under inequality constraints. So before jumping into KKT conditions, we should first recall the optimization under equality constraints. Let's consider the optimization problem \begin{eqnarray} \begin{split} \min_{x}&&\quad f(x) \\ \text{s.t.}&& \quad g(x)=0 \end{split}\tag{1}\end{eqnarray} The key insight is that if $x^*$ is the optimal solution of the problem (1), then \begin{eqnarray} \nabla f(x^*)&=&-\lambda\nabla g(x^*)\tag{2}\\ g(x^*)&=&0\tag{3}\end{eqnarray} for some $\lambda \in \mathbb{R}$. Ther...

The training dataset of SVM consists of $n$ training examples of the form $\left(x^{(i)}, y^{(i)}\right)$ for $i=1, \cdots, n$, where each ${x}^{(i)}$ is a $p$-dimensional input vector and $y^{(i)}$ is the corresponding label. Furthermore, there is a fixed feature map $\phi$ in SVM that maps an input vector $x$ to a feature vector $\phi(x)$. Such feature map is implicitly specified by a kernel in the dual formulation of SVM. The task of SVM is to find two parallel linear boundaries (hyperplanes) in the feature space by maximizing their margin for either binary classification or regression. SVM as binary classifier For binary classification, $y^{(i)}\in \{1, -1\}$ labels the class to which ${x}^{(i)}$ belongs. The task of SVM is to find two parallel hyperplanes in the feature space that separate the two classes.  Fig. 1: Two parallel hyperplanes in the feature space with the maximum margin for binary classification: (a) Linearly separable data: taken from wiki . (b) Non-linearl...

We introduced the HHL algorithm and its subroute quantum phase estimation (QPE) algorithm in this blog . Now we introduce two quantum versions of machine learning algorithms: quantum principal component analysis (qPCA) and quantum support vector machine (qSVM), which replies on QPE and HHL, respectively. Data Preparation Suppose we have $n$ data samples and each data sample has $p$ features, i.e., $\mathbf{x}^{(i)}\equiv[x_1^{(i)}, \cdots, x_p^{(i)}]^T$ for $i=1,\cdots, n$. To apply quantum algorithms, we encode each data sample $\mathbf{x}^{(i)}$ in a quantum state \begin{eqnarray}\mathbf{x}^{(i)}\equiv[x_1^{(i)}, \cdots, x_p^{(i)}]^T \quad\xrightarrow{p=2^m} \quad |\psi_i\rangle\equiv \frac{1}{\left|\left| \mathbf{x}^{(i)}\right|\right|_2}\sum_{\tau\in \{0,1\}^m}x_{\tau}^{(i)}|\tau\rangle\,.\tag{1}\end{eqnarray} To encode the entire dataset, we entangle the data state $|\psi_i\rangle$ with an auxiliary state $|i\rangle$ and form a pure state \begin{equation}|\psi\rangle\equiv\sum_{i=...

Background Quantum computing can bring exponential speedup over some classical algorithms. Most of the early-age algorithms are designed as proof of concept and thus lack of practical interests. Shor's algorithm for integer factorization is the first quantum algorithm that will bring practical applications: breaking the current RSA encryption  on the internet. However, implementing Shor's algorithm requires the manipulation of thousands of qubits, which is far beyond today's engineering capability. The breakthrough starts with the appearance of Harrow-Hassidim-Lloyd (HHL) algorithm in 2009, which solves linear equations in logarithmic time. Solving linear equations is of great importance in almost all the scientific and engineering disciplines. It is also an indispensable subroute in many machine learning algorithms. Besides its wide applications, implementing HHL algorithm only requires tens of qubits and thus seems feasible in the near future. Along with the rise of deep...

原文是对知乎上“ 当前量子计算技术前沿是什么水平 ”问题的回答，现已被删除，特此转载留档。原文中还有一些图片，网上只有纯文字版残留。非本人原创，完全转载，如有侵权，即刻删除。 王之鑫 耶鲁大学 应用物理系博士在读 更新（03-19-2018）：感谢大家三天来的关注和反馈。量子通信部分略有修改，一些细节语言更严谨了些。需要强调的是，实际条件下量子通信的安全性分析是一个复杂的研究方向，科学家们也一直在为减少实用量子通信的安全漏洞不懈努力。例如，诱骗态 (decoy state) 和测量装置无关量子密钥分发 (measurement-device-independent quantum key distribution) 弥补了第一代商用量子通信技术的两个重要安全漏洞。但是，绝对安全的量子通信在现实中是不存在的，使用了新技术的量子密码仍然存在其它安全漏洞。对此感兴趣的童鞋可以参考下面三篇综述长文： V. Scarani, et al. The security of practical quantum key distribution. Rev. Mod. Phys. 81, 1301 (2009) R. Alléaume, et al. Using quantum key distribution for cryptographic purposes: A survey. Theor. Comput. Sci. 560, 62 (2014) E. Diamanti, et al. Practical challenges in quantum key distribution. npj Quantum Information 2, 16025 (2016) 另外，为了避免误解，第八部分中关于中国互联网巨头“量子战略”的评论更具体了些，写清了“亩产十万斤”到底指什么。此段观点没有变化。 最后，出于自我保护，我将在知乎永久封笔。Addio! 本人坐标耶鲁大学，是 Devoret-Schoelkopf 超导量子计算实验室迄今唯一本科来自中国的博士生。 文章很长，分为九个独立的问题，可分别阅读： （一）量子是个啥？ （二）各种量子技术都是啥？ （三）量子计算机有啥用？ （四）量子计算机怎么做？ （五）当前量子计算实验研究的各路高手都是谁？ （六）量子计算到底难在哪？进展到...

Qubits  A qubit is a well-defined quantum two-level system with states $|0\rangle$ and $|1\rangle$. Unlike a classical bit that is either 0 or 1, a qubit can be in a superposition of both $|0\rangle$ and $|1\rangle$ as \begin{equation}|\text{qubit}\rangle\equiv\cos\frac{\theta}{2} |0\rangle +\sin\frac{\theta}{2} e^{i\phi}|1\rangle\,.\end{equation} Notes: Quantum states are the same up to an overall phase factor. To remove the ambiguity of the overall phase factor, we use the conversion that the coefficient in front of $|0\rangle$ is always a real positive number. $\phi$  is the relative phase difference between $|0\rangle$ and $|1\rangle$. Each qubit state can be one-to-one mapped to a point on the Bloch sphere . Note that the polar angle $\theta$ in the spherical coordinate system takes the value in $[0, \pi]$. To ensure the coefficient in front of $|0\rangle$ is always a real positive number, we parameterize the qubit state as $\frac{\theta}{2}$ rather than $\theta$. As...