Demonstration of a Compiled Version of Shor’s Quantum Factoring Algorithm Using Photonic Qubits

We report an experimental demonstration of a complied version of Shor’s algorithm using four photonic qubits. We choose the simplest instance of this algorithm, that is, factorization of $N=15$ in the case that the period $r=2$ and exploit a simplified linear optical network to coherently implement the quantum circuits of the modular exponential execution and semiclassical quantum Fourier transformation. During this computation, genuine multiparticle entanglement is observed which well supports its quantum nature. This experiment represents an essential step toward full realization of Shor’s algorithm and scalable linear optics quantum computation.

Figure 1

Quantum circuit for the order-finding routine of Shor’s algorithm. (a) Outline of the quantum circuit. (b) Quantum circuit for $N=15$ and $a=11$. The MEF is implemented by two CNOT gates, and the QFT is implemented by Hadamard rotations and two-qubit conditional phase gates. The gate-labeling scheme denotes the axis about which the conditional rotation takes place and the angle of rotation. (c) The simplified linear optics network using HWPs and PBSs to implement the MEF circuit and the semiclassical version of the QFT circuit. The double lines denote classical information.

Figure 2

Experimental setup. Femtosecond laser pulses (394 nm, 120 fs, 76 MHz) pass through two BBO crystals to produce two pairs of entangled photons with an average count of $7.8\times {10}^4{\mathrm{s}}^{-1}$. Fine adjustments of the delays between path 2, 3, 4 are made by translation stages $\Delta d_2$ and $\Delta d_4$. We incorporate in front of each PBS a compensator (Comp.) to counter the additional phase shifts of the PBS. The final measurement results are then read out using polarizers and single-photon detectors.

Figure 3

Principle of three-photon interference and data of genuine triplet entanglement. (a) Hong-Ou-Mandel type [25] interference of three photons. Three $|+⟩$ polarized photons are directed to two PBSs from three spatial modes. As the PBSs transmit $H$ and reflect $V$ polarizations, a coincidence detection of three outputs can only originate from either the case that all photons are transmitted or all reflected. (b) Three-photon interference as a function of the temporal delay. Outside the coherent regime, the terms $|H{⟩}_2|H{⟩}_3|H{⟩}_4$ and $|V{⟩}_2|V{⟩}_3|V{⟩}_4$ are distinguishable. At the zero delay, an optimal superposition of $|H{⟩}_2|H{⟩}_3|H{⟩}_4$ and $|V{⟩}_2|V{⟩}_3|V{⟩}_4$ is achieved; thus, the $|+{⟩}_2|+{⟩}_3|+{⟩}_4$ events show a maximal enhancement while the $|+{⟩}_2|+{⟩}_3|-{⟩}_4$ events show a dip. The raw visibility is $0.75\pm 0.03$, which after subtraction of the contribution of the double pair emission can be improved to $0.88\pm 0.05$, indicating good spatial and temporal overlap have been achieved. This is, to our knowledge, the first observation of Hong-Ou-Mandel type interference which involves three photons from three different paths. (c) The multiphoton detection probabilities in the $H/V$ measurement basis. (d) Measured expectation value of the observables $XXX$, $XYY$, $YXY$, and $YYX$. The error bars denote 1 standard deviation, deduced from propagated Poissonian counting statistics of the raw detection events.

Figure 4

Experimental result of the output-state probabilities after application of the QFT on the first register. Each measurement takes 120 s and yields a maximum 270 fourfold coincidence counts for the $|00⟩$ projection.