Quantum Computer Runs The Most Practically Useful Quantum Algorithm

Chao-Yang Lu (left) and Jian-Wei Pan (right) 












Authors: Chao-Yang Lu and Jian-Wei Pan

Affiliation: Hefei National Laboratory for Physical Sciences at Microscale and Department of Modern Physics, University of Science and Technology of China, Hefei, China.

Over the past three decades, the promise of exponential speedup using quantum computing has spurred a world-wide interest in quantum information. To date, there are three most prominent quantum algorithms that can achieve this exponential speedup over classical computers. Historically, the first one is quantum simulation of complex systems proposed by Feynman in 1980s [1]. The second one is Shor’s algorithm (1994) for factoring large numbers [2] – a killer program to break the widely used RSA cryptographic codes.

Very recently, the third one came as a surprise. Harrow, Hassidim and Lloyd (2009) showed that quantum computers can offer an exponential speedup for solving systems of linear equations [3]. As the problem of solving linear equations is ubiquitous in virtually all areas of science and engineering (such as signal processing, economics, computer science, and physics), it would be fair to say that this might be the most practically useful quantum algorithm so far.

Fig.1: An optimized circuit with four qubits and four entangling gates for solving 2x2 systems of linear equations.

Demonstration of the powerful algorithms in a scalable quantum system has been considered as a milestone toward quantum computation. While the first two have been realized previously [4,5,6], the realization the new quantum algorithm had remained a challenge. Recently, we report the first demonstration of the quantum linear system algorithm, through testing the simplest meaningful instance: solving 2×2 linear equations on a photonic quantum computer [7], in parallel with Walther’s group who also presented results on arXiv [8]. To demonstrate the algorithm, we have implemented a quantum circuit (see Fig.1) with four quantum bits and four controlled logic gates, which is among the most sophisticated quantum circuit to date.

Fig.2: Experimental setup. It consists of (1) Qubit initialization, (2) Phase estimation, (3) R rotation, (4) Inverse phase estimation.

An illustration of our experimental set-up is shown in Fig.2. The four quantum bits are from four single photons generated using a nonlinear optical process called spontaneous parametric down-conversion (where a short, intense ultraviolet laser shines on a crystal and, with a tiny probability, an ultraviolet photon can split into two correlated infrared photons). The quantum information is encoded with the polarization of the single photons, which can be initialized and manipulated using wave plates, and readout using polarizers and single-photon detectors [9].

In the experiment, it is also necessary to implement four sets of photon-photon controlled logic gates – that is, the quantum state of a single photon controls that of another independent single photon. These gates are realized by optical networks consisting of polarizing beam splitters, half wave plates, Sagnac interferometer, and post-selection measurement.

Fig.3: Experimental results. For each input state, the experimentally measured (red bar) expectation values of the observables of the Pauli matrices are compared to the theoretically prediction (gray bar).

We have implemented the algorithm for various input vectors. We characterize the output by measuring the expectation values of the Pauli observables Z, X, and Y. Figure 3 shows both the ideal (gray bar) and experimentally obtained (red bar) expectation values for each observable. To compare how close our experimental results match ideal outcome, we compute the output state fidelities, which give 0.993(3), 0.825(13) and 0.836(16) for the three input vectors, respectively.

To solve more complicated linear and differential equations [10], we are trying to develop new techniques, including experimental manipulation of more photonic qubits, higher brightness multi-photon sources, and more efficient two-photon logic gates. So far, we have the ability to control up to eight individual single photons [11] and ten hyper-entangled quantum bits [12]. Creating a larger-scale circuit would involve more quantum bits. Two parallel pathways are being undertaken in our group. One is to climb up to ten-photon entanglement, and the other way is to exploit more degrees freedom of a single photon thus using it more efficiently. The near-future goal is to control 10 to 20 photonic quantum bits. The enhanced capability would allow us to test more complicated quantum algorithms.

References: 
[1] Richard P. Feynman, “Simulating physics with computers”. International Journal of Theoretical Physics, 21, 467 (1982). Abstract.
[2] P. Shor, “Algorithms for quantum computation: discrete logarithms and factoring” in Proc. 35th Annu. Symp. on the Foundations of Computer Science, edited by S. Goldwasser (IEEE Computer Society Press, Los Alamitos, California, 1994), p. 124–134. Abstract.
[3] Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd, “Quantum algorithm for linear systems of equations”. Physical Review Letters, 
103, 150502 (2009). Abstract.
[4] Chao-Yang Lu, Daniel E. Browne, Tao Yang, and Jian-Wei Pan, “Demonstration of a compiled version of Shor’s quantum factoring algorithm using photonic qubits”. Physical Review Letters, 99, 250504 (2007). Abstract.
[5] B.P. Lanyon, T. Weinhold, N. Langford, M. Barbieri, D. James, A. Gilchrist, and A. White, “Experimental demonstration of a compiled version of Shor’s algorithm with quantum entanglement”. Physical Review Letters, 99, 250505 (2007). Abstract.
[6] Chao-Yang Lu, Wei-Bo Gao, Otfried Gühne, Xiao-Qi Zhou, Zeng-Bing Chen, Jian-Wei Pan, “Demonstrating Anyonic Fractional Statistics with a Six-Qubit Quantum Simulator”. Physical Review Letters, 102, 030502 (2009). Abstract.
[7] X.-D. Cai, C. Weedbrook, Z.-E. Su, M.-C. Chen, Mile Gu, M.-J. Zhu, Li Li, Nai-Le Liu, Chao-Yang Lu, and Jian-Wei Pan, “Experimental Quantum Computing to Solve Systems of Linear Equations”. Physical Review Letters, 110, 230501 (2013). Abstract.
[8] Stefanie Barz, Ivan Kassal, Martin Ringbauer, Yannick Ole Lipp, Borivoje Dakic, Alán Aspuru-Guzik, Philip Walther, “Solving systems of linear equations on a quantum computer”. arXiv:1302.1210v1. Abstract.
[9] Jian-Wei Pan, Zeng-Bing Chen, Chao-Yang Lu, Harald Weinfurter, Anton Zeilinger, Marek Żukowski, “Multiphoton entanglement and interferometry”. Review of Modern Physics, 84, 777 (2012). Abstract.
[10] Dominic W. Berry, “Quantum algorithms for solving linear differential equations”. arXiv:1010.2745. Abstract.
[11] Xing-Can Yao, Tian-Xiong Wang, Ping Xu, He Lu, Ge-Sheng Pan, Xiao-Hui Bao, Cheng-Zhi Peng, Chao-Yang Lu, Yu-Ao Chen, Jian-Wei Pan, “Observation of eight-photon entanglement”. Nature Photonics, 6, 225. Abstract.
[12] Wei-Bo Gao, Chao-Yang Lu, Xing-Can Yao, Ping Xu, Otfried Gühne, Alexander Goebel, Yu-Ao Chen, Cheng-Zhi Peng, Zeng-Bing Chen, Jian-Wei Pan, “Experimental demonstration of a hyper-entangled ten-qubit Schrödinger cat state”. Nature Physics, 6, 331 - 335 (2010). Abstract.