Life with Physics

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

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