Quantum Computing: HHL Algorithm

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 learning in the same time period, many big techs start to invest quantum computing after 2010. The goal is not to build a universal quantum computer, but a quantum processor running some specific algorithm such as HHL algorithm.

Problem Definition

Given a matrix $\mathbf{A}\in\mathbb{C}^{N\times N}$ and a vector $\mathbf{b}\in \mathbb{C}^N$, the problem is to find the solution $\mathbf{x}\in\mathbb{C}^N$ of the linear equations $\mathbf{A}\mathbf{x}=\mathbf{b}$. Without loss of generality, we assume that $\mathbf{A}$ is Hermitian: $\mathbf{A}=\mathbf{A}^{\dagger}$. If not, we solve the linear equations $\left[\begin{array}{cc} 0 & \mathbf{A}^{\dagger}\\ \mathbf{A} & 0\end{array}\right]\left[\begin{array}{c} \mathbf{x}\\ 0 \end{array}\right]=\left[\begin{array}{c} 0\\ \mathbf{b} \end{array}\right]$ instead.

Consider the case $N\equiv 2^n$ for simplicity. A quantum solver encodes the $N$ components of the classical vector $\mathbf{b}$ into a quantum state of $n=\log_2 N$ qubits (exponential compression): \begin{eqnarray}\mathbf{b}=[b_1, b_2, \cdots, b_N]^T\xrightarrow{N=2^n}|b\rangle = \sum_{\tau\in \{0,1\}^n} b_{\tau} | \tau\rangle_n\,,\end{eqnarray} assuming $\mathbf{b}$ is a unit vector for simplicity. The goal is to produce a quantum state $|x\rangle\equiv A^{-1}|b\rangle$ which encodes the components of the classical vector of the solution $\mathbf{x}$ as $|x\rangle=\sum_{\tau\in\{0,1\}^n}x_{\tau}|\tau\rangle_n$. More specific, since $\mathbf{A}$ is Hermitian, the corresponding operator has eigendecomposition $A=\sum_{j=1}^N \lambda_j|u_j\rangle\langle u_j|$. As a result, the goal is to generate a quantum state \begin{equation}|x\rangle=\sum_{j=1}^N\frac{\beta_j}{\lambda_j}|u_j\rangle \end{equation} with $\beta_j \equiv \langle u_j|b\rangle$.

Preliminary

Phase Factor in Binary Representation

For a positive integer $j \in [0, 2^n)$, we denote its binary representation by $j_1j_2\cdots j_{n}$. That is,  $j\equiv\sum_{l=1}^{n}j_l 2^{n-l}$ with $j_1, \cdots, j_n\in \{0, 1\}$. Furthermore, a quantum state $|j\rangle$ can be represented as the n-qubit state $|j\rangle_n\equiv |j_1\rangle|j_2\rangle\cdots|j_n\rangle$. Similarly, for a decimal $\phi\in [0, 1)$, we denote its binary representation by $0.\phi_1\phi_2\cdots \phi_n$. That is, $\phi\equiv\sum_{l=1}^n\phi_l2^{-l}$ with $\phi_1, \cdots, \phi_n\in \{0, 1\}$.

With the above notations, we have the phase factor in the binary representation:\begin{eqnarray}e^{2\pi i\frac{j}{2^{n+1-l}}}\,&=&e^{2\pi i \, 0.j_{l}\,\cdots j_n}\,,\tag{1}\\ e^{2\pi i\,2^{l-1}\,\phi}&=&e^{2\pi i \,0.\phi_{l}\,\cdots\phi_n}\,,\tag{2}\end{eqnarray} for $l=1, \cdots,n$, because of $2\pi$ phase periodicity.

Quantum Fourier Transformation (QFT)

Corresponding to the classical discrete Fourier transformation $y_k = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1}x_j e^{2\pi i\, jk/N}$, the so-called quantum Fourier transformation (QFT) acts on a quantum state as \begin{eqnarray}|j\rangle &\xrightarrow{\text{QFT}}& \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}e^{2\pi i\frac{jk}{N}}|k\rangle\,,\tag{3}\end{eqnarray} where $j$ and $k$ are integers in the range of $[0, N)$. 

Consider the case of $N\equiv 2^n$, we first write QFT in terms of binary digits $k\equiv\sum_{l=1}^n k_l2^{n-l}$ as \begin{eqnarray}|j\rangle_n&\xrightarrow{\text{QFT}}& \frac{1}{2^{n/2}}\sum_{k_1=0}^1\cdots\sum_{k_n=0}^1\prod_{l=1}^ne^{2\pi i\frac{jk_l}{2^l}} |k_l\rangle\nonumber\\&=&\frac{1}{2^{n/2}}\prod_{l=1}^n\sum_{k_l=0}^1e^{2\pi i\frac{jk_l}{2^l}}|k_l\rangle=\frac{1}{2^{n/2}}\prod_{l=1}^n \left(|0\rangle + e^{2\pi i\frac{j}{2^l}} |1\rangle\right)\,,\end{eqnarray} and then use the relation (1) for the final relation \begin{eqnarray} |j_1\rangle\cdots |j_n\rangle &\xrightarrow{\text{QFT}}&\frac{1}{2^{n/2}}\prod_{l=1}^n \left(|0\rangle + e^{2\pi i\,0.j_l\cdots j_n} |1\rangle\right)\,.\tag{4}\end{eqnarray} The product representation (4) can be viewed directly as another definition of QFT (3). 

To construct an efficient quantum circuit for QFT (4), we use the one-qubit Hadamard gate as well as the two-qubit controlled phase gate $R_l$ that produce a phase $e^{2\pi i /2^l}$ only on the state $|1\rangle|1\rangle$: $|0\rangle|j_i\rangle\rightarrow |0\rangle|j_i\rangle$ and $|1\rangle|j_i\rangle\rightarrow e^{2\pi i \frac{j_i}{2^l}} |1\rangle|j_i\rangle$. The circuit is shown in Fig. 1, which provides a $\Theta(n^2)$ quantum algorithm. In contrast, the best classical algorithm, FFT, has complexity $\Theta\left(n2^n\right)$. 

Fig. 1 Quantum circuit for quantum Fourier transformation. Taken from M. Nielson and I. Chuang's book "Quantum Computation and Quantum Information"

Quantum Phase Estimation (QPE)

Given an eigenstate $|\phi\rangle$ of an unitary operator (gate) $U$: $U|u\rangle=e^{2\pi i \phi}|u\rangle$, $0\leq\phi <1$, the problem of quantum phase estimation is to find the unknown value of $\phi$ to a certain precision.

The algorithm for quantum phase estimation can be summarized as follows: \begin{eqnarray} |u\rangle|0\rangle_n &\xrightarrow{I\otimes H^{\otimes n}}& \frac{1}{2^{n/2}}\sum_{k\in\{0,1\}^n}|u\rangle|k\rangle_n\\&\xrightarrow{\sum_{\tau\in\{0,1\}^n}\,\,\,U^{\tau}\otimes |\tau\rangle_n{}_n\langle \tau|}& \frac{1}{2^{n/2}}\sum_{k\in\{0,1\}^n}e^{2\pi i\phi k}|u\rangle|k\rangle_n\\&\xrightarrow{\text{QFT}^{\dagger}}&\frac{1}{2^n}\sum_{j\in\{0,1\}^n}\sum_{k\in\{0,1\}^n}e^{\frac{2\pi i k}{2^n}\,\left(2^n\phi-j\right)}|u\rangle|j\rangle_n\\&\xrightarrow{\text{Measurement}}& |u\rangle\left|\lfloor 2^n\phi\rceil\right\rangle_n\,,\tag{5}\end{eqnarray} where we create the superposition using the n-qubit Hadamard gate in the first line, apply the controlled-U operator $\sum_{\tau\in\{0,1\}^n}\,\,\,U^{\tau}\otimes |\tau\rangle_n{}_n\langle \tau|$ and the inverse quantum Fourier transformation in the second and third lines, and finally perform a measurement in the last line. Note that $0\leq\phi <1$, we denote by $\lfloor 2^n\phi\rceil$ the nearest integer around $2^n\phi$ in the last line. If $2^n\phi$ is an integer, i.e., $2^n\phi=\lfloor 2^n\phi\rceil$, the measurement leads to the state $|u\rangle\left|\lfloor 2^n\phi\rceil\right\rangle_n$ with probability 1; otherwise, with probability $\geq 4/\pi^2$.

To construct a quantum circuit for the quantum phase estimation algorithm (5), we introduce a two-qubit controlled-U gate $U$: $|0\rangle|u\rangle\rightarrow|0\rangle|u\rangle$ and $|1\rangle|u\rangle\rightarrow e^{2\pi i \phi}|1\rangle|u\rangle$. The circuit is shown in Fig. 2. The fundamental block of the circuit is \begin{eqnarray}|0\rangle|u\rangle\xrightarrow{H\otimes I}\frac{|0\rangle + |1\rangle}{\sqrt{2}}|u\rangle\nonumber&\xrightarrow{U^{2^{l-1}}} \frac{|0\rangle +e^{2\pi i\,2^{l-1} \phi} |1\rangle}{\sqrt{2}}|u\rangle=\frac{|0\rangle +e^{2\pi i\,0.\phi_{l}\,\cdots\phi_n} |1\rangle}{\sqrt{2}}|u\rangle\,,\end{eqnarray} where we use the relation (2) in the last step. The circuit is designed in a way such that the output state besides $|u\rangle$ is exactly the outcome of QFT (4):\begin{eqnarray}\frac{1}{2^{n/2}}\prod_{l=1}^n \left(|0\rangle + e^{2\pi i\,0.\phi_l\cdots \phi_n} |1\rangle\right)&\xrightarrow{\text{QFT}^{\dagger}}& |\phi_1\rangle\cdots |\phi_n\rangle \,,\end{eqnarray} where $\phi_1\phi_2\dots\phi_n$ is the binary representation of the integer $\lfloor 2^n\phi\rceil$ for $0\leq \phi < 1$.

Fig. 2 Quantum circuit for quantum phase estimation. QFT$^{\dagger}$ represents the inverse of the quantum circuit in Fig. 1. Taken and modified from M. Nielson and I. Chuang's book "Quantum Computation and Quantum Information"

Algorithm Summary

Given a prepared state $|b\rangle$ and the access to $A$, a high-level description of HHL algorithm is as follows:
  1. Quantum phase estimation: Since $A=\sum_{j=1}^N\lambda_j|u_j\rangle\langle u_j|$ is Hermitian, we can apply quantum phase estimation for the unitary operator $U=e^{iAt}$ and achieve the quantum state \begin{eqnarray}|b\rangle|0\rangle_n\equiv\sum_{j=1}^N \beta_j|u_j\rangle|0\rangle_n\xrightarrow{\text{QPE on } e^{iAt}}\sum_{j=1}^N\beta_j|u_j\rangle|\tilde{\lambda}_j\rangle\,,\end{eqnarray} where $|\tilde{\lambda}_j\rangle$ denotes a $n$-qubits state of binary representation of the value $\tilde{\lambda}_j\equiv \lambda_j\frac{t}{2\pi}$.
  2. Controlled rotation: we introduce a controlled rotation operation $R$ such that \begin{eqnarray}R\,|\lambda\rangle|0\rangle&=&\sqrt{1-\frac{C^2}{\lambda^2}}|\lambda\rangle|0\rangle+\frac{C}{\lambda}|\lambda\rangle|1\rangle\,,\\R\,|\lambda\rangle|1\rangle&=&-\frac{C}{\lambda}|\lambda\rangle|0\rangle+\sqrt{1-\frac{C^2}{\lambda^2}}|\lambda\rangle|1\rangle\,.\end{eqnarray} By introducing an additional ancilla qubit initialized to be $|0\rangle$ and applying the above controlled rotation, we achieve a quantum state \begin{eqnarray} \sum_{j=1}^N\beta_j|u_j\rangle|\tilde{\lambda}_j\rangle|0\rangle\xrightarrow{\text{controlled }R} \sum_{j=1}^N\beta_j|u_j\rangle|\tilde{\lambda}_j\rangle\left(\sqrt{1-\frac{C^2}{\tilde{\lambda}_j^2}}|0\rangle+\frac{C}{\tilde{\lambda}_j}|1\rangle\right)\,.\end{eqnarray}
  3. Inverse of the quantum phase estimation: \begin{eqnarray} \sum_{j=1}^N\beta_j|u_j\rangle|\tilde{\lambda}_j\rangle\left(\sqrt{1-\frac{C^2}{\tilde{\lambda}_j^2}}|0\rangle+\frac{C}{\tilde{\lambda}_j}|1\rangle\right)\xrightarrow{\text{QPE}^{\dagger}}\sum_{j=1}^N\beta_j|u_j\rangle|0\rangle_n\left(\sqrt{1-\frac{C^2}{\tilde{\lambda}_j^2}}|0\rangle+\frac{C}{\tilde{\lambda}_j}|1\rangle\right)\,.\end{eqnarray}
  4. Measurement of the ancilla qubit: \begin{eqnarray}\sum_{j=1}^N\beta_j|u_j\rangle|0\rangle_n\left(\sqrt{1-\frac{C^2}{\tilde{\lambda}_j^2}}|0\rangle+\frac{C}{\tilde{\lambda}_j}|1\rangle\right)\xrightarrow{\text{Measurement}}\sum_{j=1}^N\frac{\beta_j}{\tilde{\lambda}_j}|u_j\rangle|0\rangle_n|1\rangle\propto|x\rangle|0\rangle_n|1\rangle\,.\end{eqnarray} The algorithm succeeds If the measurement outcome is $|1\rangle$. 
The quantum circuit that implements the above four steps is shown in Fig. 3. 
Fig. 3 Quantum circuit for HHL algorithm. Taken from the paper D. Dervovic, et. al arXiv:1802.08227.

Remarks:
  1. In quantum phase estimation, one can only estimate a value $0\leq \phi < 1$ in the phase factore $e^{i2\pi \phi}$. To apply quantum phase estimation in the first step of HHL algorithm on unitary operator $e^{iAt}$, we have to choose the value $t$ such that all $\lambda t/2\pi\in [0, 1)$, which does require the prior knowledge of the eigenvalue bounds.
  2. The original HHL paper assumes that "the singular values of $A$ lie between $1/\kappa$ and 1", where $\kappa$ is the conditional number of $A$. In this case, we simply choose $t=2\pi$.
  3. The unitary operator $e^{iAt}$ used in the quantum phase estimation can be constructed using the techniques of Hamiltonian simulation.
  4. HHL algorithm does not involve any actual eigendecomposition. $A=\sum_{j=1}^N \lambda_j|u_j\rangle\langle u_j|$ and $|b\rangle=\sum_{j=1}^N\beta_j|u_j\rangle$ in the above algorithm description only serves the purpose to illustrate the correctness of the algorithm.
  5. If we define the controlled rotation as $R\,|\lambda\rangle|0\rangle=\frac{C}{\lambda}|\lambda\rangle|0\rangle+\sqrt{1-\frac{C^2}{\lambda^2}}|\lambda\rangle|1\rangle$, the algorithm still goes through but the final success flag of the ancilla qubit after measurement will become $|0\rangle$ which can not be distinguished from its initial state.
  6. How to implement the controlled rotation? No answers yet. Comments welcome! It looks like it requires the implementation of an operator to compute the reciprocal of eigenvalues as well as the controlled-$R_y$ operator $\sum_{\tau\in\{0,1\}^n}|\tau\rangle_n{}_n\langle\tau|e^{-i\tau\sigma_y}$.
  7. The output quantum state $|x\rangle$ is normalized and thus differs a normalization factor from the classical solution vector $\mathbf{x}$. The normalization factor comes from the measurement step as well as $||\mathbf{b}||_2$ if $\mathbf{b}$ is not a unit vector. How to find such normalization factor?  It is required to compute $\mathbf{x}^T\mathbf{O}\mathbf{x}$ by $\langle x|{O}|x\rangle$. No answers yet. Comments welcome! 
  8. More comments on the caveats of the algorithm can be found in this Nature paper.

Comments

Post a Comment

Popular posts from this blog

529 Plan

This post is for knowledge sharing only. It is not intended to be investment or tax advice. 529 Plans are tax-advantaged accounts specific for education saving: Contribution are made with after-tax dollars. Growth within the account is tax-free. Withdraw for qualified education expenses is also tax free. Roth IRA First 529 Plans are very similar to Roth IRA . But Roth IRA withdraw under  the 5-year rule  is tax free for any purpose. Therefore, unless for the state tax deduction in some states, it is always better to max out Roth IRA first (through backdoor and mega backdoor  for high income earners) before funding a 529 plan. Note: there is NO California state tax deduction for any 529 plan. 529 or Not? Here are some considerations in reality before funding a 529 plan: What if no qualified education expenses In the worst case that there will be no qualified education expenses, you can still take money out for non-qualified expenses, but you have to pay: federal income tax + 10% federa
Read more

How to offset W2 tax

This post is for knowledge sharing only. It is not intended to be tax or investment advice. 1. Contribute to pre-tax 401K and HSA As well known, pre-tax 401K and health saving account (HSA) are the only a few tax shelters for W2 workers.  2. Tax-loss harvesting If your total capital losses exceed your capital gains in a tax year, you can deduct up to \$3,000 (married filing jointly) from your ordinary income. If your losses are more than $3,000, you can carry over the remaining amount to future years, continuing to offset your income until all the losses are used up. A popular method to generate these deductible losses is  tax-loss harvesting . This involves selling a security at a loss to offset gains or reduce ordinary income, and optionally purchasing a similar, but not "substantially identical", security to avoid missing out on the market. However, be aware of the  wash-sale rule , which disallows claiming a loss if you buy the same or a substantially identical security
Read more

Health Saving Account (HSA)

This post is for knowledge sharing only. It is not intended to be investment or tax advice. Health saving account (HSA) is another tax-free investment account that is even better than Roth IRA . HSA offers three tax advantages: The contribution is tax deductible. Investment grows tax-free. Finally, withdrawals for qualified medical expenses are also tax-free. To fully utilizes the advantages, it is better to let the money stay and grow in HSA as long as possible. To achieve this, Do NOT use HSA money to cover the current medical expenses. Instead, save the receipts and ask for reimbursement in future year of withdrawal. Remarks: HSA does NOT have any CA state tax benefits. Both HSA enrollees and their spouse are NOT eligible to contribute to the general   flexible spending account (FSA) . One can have a HSA and  limited purpose FSA (LPFSA) at the same time. Unlike the general FSA, LPFSA can only cover vision and dental expenses. High Deduction v.s. HSA Saving To be eligible for HSA,
Read more