Experimental realization of quantum algorithm for solving linear systems of equations

Many important problems in science and engineering can be reduced to the problem of solving linear equations. The quantum algorithm discovered recently indicates that one can solve an $N$-dimensional linear equation in $O(logN)$ time, which provides an exponential speedup over the classical counterpart. Here we report an experimental demonstration of the quantum algorithm when the scale of the linear equation is $2\times 2$ using a nuclear magnetic resonance quantum information processor. For all sets of experiments, the fidelities of the final four-qubit states are all above 96%. This experiment gives the possibility of solving a series of practical problems related to linear systems of equations and can serve as the basis to realize many potential quantum algorithms.

Figure 1

Quantum circuit for implementation of the algorithm in the experiment. Here $r=2$ and $t_0=2\pi$, determining the precision and probability of the correct answer. The matrix forms of the single-qubit gates are $S=\left(\begin{array}{cc}1& 0\\ 0& i\end{array}\right)$, $H=\frac{1}{\sqrt{2}}\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right)$, $R_y\left(\theta \right)=\left(\begin{array}{cc}cos(\theta /2)& -sin(\theta /2)\\ sin(\theta /2)& cos(\theta /2)\end{array}\right)$. The vertical segments with “$\times$” mean swap operations.

Figure 2

Properties of the iodotrifiuoroethylene molecule. The chemical shifts and J-coupling constants (in Hz) are on and below the diagonal in the table, respectively. The chemical shifts are given with respect to reference frequencies of 376.47 MHz (fluorines) and 100.64 MHz (carbons) at 303.0 K. The molecule contains four weakly coupled spin half nuclei which are ${}^{13}\mathrm{C},{}^{19}{\mathrm{F}}_1,{}^{19}{\mathrm{F}}_2,{}^{19}{\mathrm{F}}_3$. The natural abundance of the sample with a single ${}^{13}\mathrm{C}$ is about $1\%$.

Figure 3

Pulse sequence of the experiment. The numbers that label the pulse symbols represent the time duration of the pulse in milliseconds. The symbols “C” and “F” represent the channels for carbon and fluorine atoms, respectively. The blue rectangular boxes in the figure represent gradient field pulses. The durations of the readout pulses differ from 0.4 to 20 ms.

Figure 4

Experimental spectrum and state tomography of the pseudopure state. (a) is the spectrum of ${}^{13}\mathrm{C}$ obtained by a $\pi /2$ readout pulse. The vertical axes have arbitrary units. (b) and (c) are the real and imaginary parts of the experimentally reconstructed density matrices of the pseudopure state, respectively. The rows and columns in (b) and (c) represent the standard computational basis in binary order, from $|0000\rangle$ to $|1111\rangle$. The fidelity of the whole PPS is 98.73$\%$.

Figure 5

Experimental ${}^{13}\mathrm{C}$ spectra of the final states after a $\pi /2$ readout pulse for three different $\vec{b}$, which are listed in Fig. 8. There are eight peaks for ${}^{13}\mathrm{C}$. Here we only show four of them related to the solution, and their intensities represent the respective probabilities of projecting the final state onto the states $|0011\rangle ,|0000\rangle ,|0001\rangle ,|0010\rangle$ from left to right. The other four peaks are almost zero, which are not shown here. The vertical axes have arbitrary but the same units. The numbers above the peaks are the relative intensity compared to the intensity of the peak of PPS. The experimentally measured, fitting, and ideal spectra are shown as the blue, red, and green curves, respectively.

Figure 6

Experimental reconstructed partial density matrices for the final states. (a)–(c) are real parts of experimentally reconstructed density matrices of the final states in the subspace where the first and the second qubits are in the $|00\rangle$ state, along with the theoretical expectations (d)–(f). The rows and columns represent the standard computational basis in binary order, from $|00\rangle$ to $|11\rangle$.

Figure 7

Experimental final state tomography. (a), (c), and (e) are the real parts of the state tomography of the experimental final states for experiments 1, 2, and 3, respectively, along with the theoretical expectations (b), (d), and (f). The rows and columns represent the standard computational basis in binary order, from $|0000\rangle$ to $|1111\rangle$. The fidelities of the experimental final states are 96.4$\%$, 96.6$\%$, and 96.7$\%$, respectively.

Figure 8

Experimental results of the quantum algorithm for solving the linear equations $A\vec{x}=\vec{b}$. ${\vec{x}}_{\mathrm{theory}}$ is the theoretical solution, ${\vec{x}}_{\mathrm{alg}}$ is the ideal solution obtained by the algorithm, and ${\vec{x}}_{exp}$ is the experimental solution obtained by quantum state tomography. Here $|\Delta x_i{|}_{\max }^{\mathrm{theory}}=|x_{\exp }^i-x_{\mathrm{theory}}^i{|}_{\max }$, $|\Delta x_i{|}_{\max }^{\mathrm{alg}}=|x_{\exp }^i-x_{\mathrm{alg}}^i{|}_{\max }$, and $|\Delta x_i{|}_{\max }^{}=|x_{\mathrm{alg}}^i-x_{\mathrm{theory}}^i{|}_{\max }$, where $x_{\exp }^i$, $x_{\mathrm{theory}}^i$, and $x_{\mathrm{alg}}^i$ are the $i$th elements of ${\vec{x}}_{\exp }$, ${\vec{x}}_{\mathrm{theory}}$, and ${\vec{x}}_{\mathrm{alg}}$, respectively. The fidelity in the table refers to the final state of the whole four-qubit system, and is measured between the experimental final state and the ideal algorithm expectation.