Experimental Demonstration of a Compiled Version of Shor’s Algorithm with Quantum Entanglement

Shor’s powerful quantum algorithm for factoring represents a major challenge in quantum computation. Here, we implement a compiled version in a photonic system. For the first time, we demonstrate the core processes, coherent control, and resultant entangled states required in a full-scale implementation. These are necessary steps on the path towards scalable quantum computing. Our results highlight that the algorithm performance is not the same as that of the underlying quantum circuit and stress the importance of developing techniques for characterizing quantum algorithms.

Figure 1

(a) Conceptual circuit for the order-finding routine of Shor’s algorithm for number $N$ and co-prime $C$ [13]. The argument and function registers are bundles of $n$ and $m$ qubits; the nested order-finding structure uses $U|y⟩=|Cy\mathrm{mod}N⟩$, where the initial function-register state is $|y⟩=1$. The algorithm is completed by logical measurement of the argument register, and reversing the order of the argument qubits. (b,c) Implementation of (a) for $N=15$ and $C=4$, 2, respectively; the unitaries are decomposed into controlled-swap gates (CSWAP), marked as $X$; controlled-phase gates are marked by dots; $H$ and $T$ represent Hadamard and $\pi /8$ gates. Many gates are redundant, e.g., the second gate in (b), the first and second gates in (c). (d,e) Partially-compiled circuits of (b,c), replacing CSWAP by controlled-not gates. n.b. (e) is equivalent to the $N=15$ $C=7$ circuit in Ref. 14. (f,g) Fully-compiled circuits of (d,e), by evaluating ${log}_C[C^x\mathrm{mod}N]$ in the function-register.

Figure 2

Experimental schematic. (a) Forward (F1, F2) and backward (B1,B2) photons pairs are produced via parametric down-conversion [22]. (b,c) Linear-optical circuits for order-2 and order-4 finding algorithms, with inputs from (a)  labeled; the letters on the detectors refer to the Fig. 1 qubits. (d,e) Physical optical circuits for (b,c), replacing the classical interferometers with partially polarizing beam splitters.

Figure 3

Algorithm outputs given by measured argument-register density matrices. The diagonal elements are the logical output probabilities. (a) Order-2 algorithm. The fidelity with the ideal state is $F=99.9\pm 0.3\%$, the linear entropy is $S_L=100\pm 1\%$ [27]. Combined with the redundant qubit, the logical probabilities are $\{P_{00},P_{10}\}=\{52,48\}\pm 3\%$. (b) Order-4 algorithm, $F=98.5\pm 0.6\%$ and $S_L=98.1\pm 0.8\%$. The logical probabilities are $\{P_{000},P_{010},P_{100},P_{110}\}=\{27,23,24,27\}\pm 2\%$. Real parts shown, imaginary parts are less than 0.6%.

Figure 4

Measured density matrices of the state of both registers after modular exponentiation. (a) Order-2 circuit. The ideal state is locally equivalent to a GHZ state: we find $F_{\mathrm{GHZ}}=59\pm 4\%$. The state is partially mixed, $S_L=62\%\pm 4\%$, and entangled, violating the optimal GHZ entanglement witness $W_{\mathrm{GHZ}}=1/2-F_{\mathrm{GHZ}}=-9\pm 4\%$ [31]. (b) Order-4 circuit. Measured fidelity with the ideal state, a tensor product of two Bell-states, is $F=68\pm 3\%$. The state is partially mixed, $S_L=52\pm 4\%$, and entangled, with tangles of the component Bell-States of $41\pm 5\%$ and $33\pm 5\%$. Real parts shown, imaginary parts are, respectively, less than 7% and 4%. The fidelity of the four-qubit state (b) is higher than the three-qubit state (a), chiefly because the latter requires nonclassical interference of photons from independent sources, which suffer higher distinguishability, lowering gate performance [28, 32, 33].

Figure 5

Measured function-register probabilities after modular exponentiation, conditioned on logical measurement of the argument-register $M_x$. There is a high correlation between the registers: (a) Order-2 circuit, $\{P_{01},P_{10}\}=\{83\pm 4\%,59\pm 5\%\}$; (b) Order-4 circuit, $\{P_{00},P_{01},P_{10},P_{11}\}=\{87\pm 3\%,84\pm 4\%,82\pm 5\%,67\pm 6\%\}$.