Life with Physics

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...

The following problem description as well as the solution follows the paper by H. D. Friedman, et al. (1962). Problem: There are n seats in a row at a luncheonette and people sit down one at a time at random. They are unfriendly and so never sit next to one another (no moving over). What is the expected number of persons to sit down? Solution: Let the $E_n$ be the expected number of person to sit down when there are n consecutively seats. The first person randomly picks the ith seat, which gives the recursion: \begin{equation} E_n = 1 + \frac{1}{n}\sum_{i=1}^n \left(E_{i-2}+E_{n-i-1}\right)\,,\tag{1}\end{equation}with $E_{-1}=E_0=0$. What I learned from the paper is to solve the above recursion by generating function. For this purpose, we define the generating function $F(x)\equiv \sum_{n=1}^{\infty} E_n \,x^n$, and rewrite the recursion as $n\,E_n = n + 2\sum_{i=1}^{n-2} E_i$. We have \begin{equation}F'(x) = \sum_{n=1}^{\infty} n\, E_n \,x^{n-1}= \sum_{n=1}^{\infty} n\,x...

Problems: (1) Zero correlation does not imply independence. (2) For two marginally normal random variables, zero correlation does not imply independence. (3) Pairwise independence does not imply jointly independence. (4) For three events A, B, C: A is independent with B and A is independent with C. Is A independent with the intersection of B and C? (5) Convergence in distribution does not imply convergence in probability. (6) Convergence in probability does not imply almost sure convergence. Solution: (1) X: take values of -1, 0, +1 with equal probability. $Y=X^2$. (2) X is standard Gaussian. Let W = +1 or -1 with equal probability and W is independent with X. Define Y=WX. X and Y are standard Gaussians. They are uncorrelated but dependent. Note: Only for random variables with jointly Gaussian, zero correlation implies independence. (3) Throw two dices. A: sum is 7, B: get 3, C: get 4. (4) No. Throw a dice. A: get a even number, B: get 1 or 2, ...

Problems: Suppose a family has two children: (1) If the first child is a boy, what is the probability that the second child is a boy? (2) If one child is a boy, what is the probability that the other child is a boy? (3) If one child is a boy, you make a random guess of the boy's name and it happens that your guess is correct. Then what is the probability that other other child is a boy (assume two boys can have the same name and a girl cannot have a boy's name)? Solution: (1) 1/2. Independent events. (2) 1/3. There are three events with equal probability: (boy, boy), (boy, girl) and (girl, boy). Compared to (1), here the one boy can be either the first child or the second child. (3) Let $p$ be the probability that the random guess of the boy's name is correct. In general, $p<<1$, \begin{eqnarray}&&\mathbb{P}(\text{correct guess}|\text{two boys})=1-(1-p)^2=2p-p^2\approx 2p\,, \\ &&\mathbb{P}(\text{correct guess}|\text{one boy and one g...

We start by defining the column (or row) rank of a matrix as the maximum number of linearly independent columns (or rows) in the matrix. It is not obvious to me when I learned linear algebra that row rank and column rank are equal. Thanks to this equality, we can simply speaks of the rank of a matrix.    The proof of row rank = column rank:  Suppose the column rank of a matrix $\mathbf{A}\in \mathbb{R}^{m\times n}$ is $r$, we can make a linear expansion $\mathbf{A} = \mathbf{X}\mathbf{Y}$ where the $r$ columns of $\mathbf{X}\in \mathbb{R}^{m\times r}$ are linearly independent and $\mathbf{Y}\in \mathbb{R}^{r\times n}$ contains the expansion coefficients: $\mathbf{A}[:, j]=\sum_{k=1}^r \mathbf{X}[:, k]\,\mathbf{Y}[k, j]$. $\mathbf{A} = \mathbf{X}\mathbf{Y}$ can also be interpreted as a linear expansion of rows: $\mathbf{A}[i, :] = \sum_{k=1}^r \mathbf{X}[i, k]\mathbf{Y}[k, :]$. As a result, $\text{row rank}(\mathbf{A})\leq r = \text{column rank}(\mathbf{A})$. By app...