Experimental Quantum Computing to Solve Systems of Linear Equations

Solving linear systems of equations is ubiquitous in all areas of science and engineering. With rapidly growing data sets, such a task can be intractable for classical computers, as the best known classical algorithms require a time proportional to the number of variables $N$. A recently proposed quantum algorithm shows that quantum computers could solve linear systems in a time scale of order $\log (N)$, giving an exponential speedup over classical computers. Here we realize the simplest instance of this algorithm, solving $2\times 2$ linear equations for various input vectors on a quantum computer. We use four quantum bits and four controlled logic gates to implement every subroutine required, demonstrating the working principle of this algorithm.

Figure 1

Quantum circuits for solving systems of linear equations. (a) Outline of the original quantum algorithm proposed in Ref. 11. The light gray blocks represent three basic subroutines of the algorithm. $U=\sum _{k=0}^{T-1}|k⟩⟨k|\otimes e^{iAk{t}_0/T}$, where $T=2^t$ with $t$ being the number of registers, and $t_0$ is chose as $2\pi$. $H$ is a Hadamard gate. $FT$ and $F{T}^{†}$ are the Fourier transformation and the inverse Fourier transformation [1], respectively. The controlled rotation $R$ evolves the system into the state $\sum _{j=1}^N{\beta }_j|u_j⟩|{\lambda }_j⟩(\surd (1-C^2/{\lambda }_j^2)|0⟩+(C/{\lambda }_j)|1⟩)$, where $C$ is a normalizing constant. The inverse phase estimation subroutine restores the register to $|0{⟩}^{\otimes n}$. Finally, the vector $\overrightarrow{x}$, the solution of the system of linear equations, can be obtained by conditioning on the measurement outcome of $|1⟩$ in ancilla qubit. (b) The optimized circuit with four qubits and four entangling gates (see main text for details). The two swap gates are canceled out.

Figure 2

Experimental setup. There are four key modules in the optical setup. (1) Qubit initialization: Ultraviolet laser pulses with a central wavelength of 394 nm, pulse duration of 120 fs, and a repetition rate of 76 MHz pass through two $\beta$-barium borate (BBO) crystals to produce two photon pairs. The four single photons are spatially separated by ${\mathrm{PBS}}_1$ and ${\mathrm{PBS}}_2$ and initialized using HWPs, with three of them in the state $|H{⟩}_i$, where $i$ denotes their spatial modes, and one in state $|b⟩$. Photon 1 is used as the input vector qubit and photon 4 is used as the ancilla. Photons 2 and 3 are used as the register qubits $R1$ and $R2$, respectively. (2) Phase estimation: The input qubit $|b⟩$ is mixed with the two register qubits on ${\mathrm{PBS}}_3$ and ${\mathrm{PBS}}_4$ to simulate the CNOT gates in Fig. 1b. (3) $R({\lambda }^{-1})$ rotation: An entanglement-based implementation of the two controlled unitary gates (see main text for details). (4) Inverse phase estimation: This is realized semiclassically by using measurement and classical feed forward. To achieve good spatial and temporal overlap, all photons are spectrally filtered (${\lambda }_{\mathrm{FWHW}}=3.2\mathrm{nm}$) and detected by fiber-coupled single-photon detectors ($D1,\dots ,D4$). The coincidence events are registered by a programmable multichannel coincidence unit.

Figure 3

Experimental results. Three different input vectors are chosen: (a) $|b_1⟩=(|H⟩+|V⟩)/\sqrt{2}$, (b) $|b_2⟩=(|H⟩-|V⟩)/\sqrt{2}$, and (c) $|b_3⟩=|H⟩$. The quantum algorithm is run to determine the the expectation value $⟨x|\widehat{M}|x⟩$, where $\widehat{M}$ is some operator. For each input state $|b⟩$, the theoretically predicted (gray bar on the left) and experimentally measured (red bar on the right) expectation values of the observables of the Pauli matrices $Z$, $X$, and $Y$ are presented. The output states are measured with a fidelity of 0.993(3), 0.825(13), and 0.836(16) for $|b_1⟩$, $|b_2⟩$, and $|b_3⟩$, respectively. The error bars denote one standard deviation, deduced from propagated Poissonian counting statistics of the raw detection events.