1. Introduction

Harnessing the miraculous features of quantum physics, quantum computation based on well-designed quantum algorithms shows great advantages over their classical counterparts. Due to the power of quantum algorithms, e.g. Shor’s algorithm [1, 2], quantum simulation algorithm [3–7 ], the algorithm used to solve Simon’s problem [8–11 ], and the algorithm used to solve linear equations [12–14 ], quantum algorithms have drawn much attention. With these algorithms, the advantage of speed-up can be revealed with at least two qubits.

Recently, Gedik [15] proposed an interesting and simple quantum algorithm which gives an intuitive computational speed-up via only one qudit involved. The designed algorithm intends to determine the parity of a given permutation function of a set by performing the permutation operation only once, which shows a two-to-one speed-up ratio over the corresponding classical algorithm.

Linear optical system is a potential candidate to realize quantum computer. Due to its good scalability, easy-handling and high stability, it is a good candidate for implementing quantum algorithms. In this paper, we report an experimental demonstration of the algorithm operating on a single qudit with linear optical system. The algorithm can be generalized to higher-dimensional system with the same speed-up ratio.

2. Gedik’s algorithm

Gedik’s algorithm solves a black-box problem as followings: consider a d-dimensional set S = {0,1,…,d − 1} with d elements, the black box operating on the set acts as one of the 2d cyclic permutations, which maps the d inputs into d possible outputs. The cyclic permutations form a subset $\mathcal{C}$ of the set of all permutations. In the text below, when we say permutation, we mean an element of $\mathcal{C}$. Permutations can be summarized as functions with the form

In order to solve the problem with a quantum algorithm, the elements of a d-dimensional set S correspond to such orthogonal basis states {|0〉,…,|d − 1〉}, where | j〉 = {δ _{(0, j)},δ _{(1, j)},…,δ _{( d− 1,j)}}^T and δ _{( i,j )} = δ (i − j) is the Dirac-Delta function. The quantum algorithm contains the following three subroutines (see Fig. 1(a) for a four-dimensional case): (i) quantum Fourier transform (QFT) U_FT, (ii) permutation operation $U_{f_m^{\pm }}$, (iii) inverse QFT $U_{FT}^{†}$.

 

Fig. 1 The circuit model of Gedik’s algorithm. (a) The global circuit. The larger squares represent three subroutines of the algorithm, and M denotes for measurement. (b) Circuit for the permutation function of a four-dimensional qudit represented by two-qubit state. All the operations can be constructed by CNOT and X gates. The circuit for $U_{f_3^{+}}$ is designed to avoid introducing any extra single-qubit gate in front of CNOT gate, which may cause the time-distinguishable photons coming to the CNOT module.

Download Full Size | PDF

Subroutine (i) is to apply QFT [16] on the initial state of the quantum algorithm |ψ〉₀ = |1〉, which results in

The permutation operation

The final subroutine is to apply inverse QFT on the qudit, which results in the parity of the permutation. Simple calculation shows the final state depends the parity of the permutation. That is, if the permutation is clockwise (say the permutation with the form $U_{f_3^{+}}$), the algorithm ends up with

The two different outputs corresponding to two kinds of permutations are orthogonal.

Thus performing a projective measurement of the final state is able to determine the parity of the permutation. The permutation is clockwise (counterclockwise) if the output is |1〉 (|d − 1〉). One can successfully determine the parity of a given permutation by applying the permutation operation only once. It shows a speed-up over the classical algorithm, in which to evaluate the permutation function for at least two different inputs is necessary. Moreover, the output is deterministic and different outputs are orthogonal. Therefore the projective measurement ensures the probability of successfully getting the parity is unit for ideal quantum circuit.

In this paper, we demonstrate a proof-of-principle experiment of the algorithm for a four-dimensional qudit case with linear optical quantum circuit. The four orthogonal states |j〉 are represented by binary representation of two-qubit state, i.e., |0〉 := |00〉, |1〉 := |01〉, |2〉 := |10〉, |3〉 := |11〉 The first subroutine of the algorithm is to apply QFT to the state |1〉|, which yields

3. Experimental realization

In our experiment, the logic qubits |0〉 and |1〉 are encoded in the horizontal (|H〉) and vertical (|V〉) polarization states of single photons, respectively. The two-photon polarization states form four orthogonal bases of a qudit. To implement the quantum circuit shown in Fig. 1, we prepare pairs of photons via pumping a 0.5mm-thick nonlinear-β-barium-borate (BBO) crystal with a 400.8nm CW diode laser with 80mW of power through type-I spontaneous parametric down-conversion (SPDC). Two interference filters (IFs) are then used to restrict the bandwidth of photons to 3nm.

In the state preparation module, which has integrated the QFT, a polarization beam splitter (PBS) and wave plates (WPs) are used to initialize the two-photon state to be Eq. (3) (see Fig. 2). The permutation modules are constructed by the circuits shown in Fig. 1(b). Similar to the procedure in [18], the CNOT gate is constructed in an inherently stable architecture with two beam displacers (BDs) and three half wave plates (HWPs) (we name the architecture formed by those elements “CNOT submodule”). A CNOT gate with the second qubit the control qubit and the first qubit the target qubit can be implemented via the HWP_1,2,3 with certain setting angles shown in Table. 1. The X gate is implemented via removable HWP₄ and HWP₅ set at 45°. In order to keep the stability of the optical circuit, we do not remove the CNOT submodule when CNOT gate is not used for the permutation operations. Instead, we adopt a more stable and efficient method by tuning the angle of HWP₂ from 17.5° for the CNOT gate to 45° for two X gates on both photons. Whereas, the setting angles of HWP₁ and HWP₃ are fixed at 22.5° and −22.5°, respectively. Thus all the eight permutations can be realized via tuning the angle of HWP₂, and moving HWP₄ and HWP₅.

 

Fig. 2 Experimental setup. The pairs of photons are generated via type-I SPDC. The photons are tuned to be time indistinguishable and then incident into the optical computation circuit. The arrows show the direction of photon flow. There are three modules in the setup. (1) State preparation: HWPs and QWPs in front of the first PBS are used to prepare pairs of photons in the state |HV〉. Two HWPs and a QWP behind the first PBS are for preparing the state of Eq. (3). (2) Permutation operation: the CNOT submodule contains two BDs and three HWPs (HWP_{1 − 3}). One can implement a CNOT gate or X gates on each qubit via the three HWPs with certain setting angles shown in Table. 1. Tuning the angle of HWP₂ and moving HWP₄ and HWP₅ implement the eight permutation operations. (3) Measurement: WPs are used to apply semiclassical inverse QFT. After passing through PBS the photons are detected by APDs.

Download Full Size | PDF

Table 1. The setting angles of HWPs to realize different permutation operations, where \ denotes the corresponding HWP is removed from the optical circuit.

View Table

Before running the algorithm, we characterize the property of the optical quantum circuit. The two BDs form an interferometer with a high visibility 99.691 ± 0.004%. The photon pairs are prepared in the state |HV〉 and injected into the first BD. The angle of the HWP₂ is then tuned to be 22.5° for a Hong-Ou-Mandel (HOM) interferometer of the two photons [19]. We observe a HOM interference with a visibility 92.459 ± 0.372%. By preparing the pair of photons in the input state $(|H〉+|V〉)|V〉/\sqrt{2}$, after a CNOT gate the output state is $(|HV〉+|VH〉)/\sqrt{2}$, which is determined via quantum state tomography [20]. The fidelity [16] of the measured output state compared to its theoretical prediction achieves 89.180 ± 2.987%.

We have realized the algorithm for all the eight possible permutations of four-dimensional set by tuning the HWP between the two BDs and two removable HWPs on the output modes. The outputs are injected into PBSs for measurement, and collected into single mode fibers, with coupling efficiency higher than 65%. The photons are detected by avalanche photo-diodes (APDs) whose coincidence signals, monitored using commercially available counting logic with coincidence window 1.9ns. The detection efficiency of our APD at 801.6nm is about 30%. For each measurement, we record clicks for 10s, registering about 1100 (120) photon pairs for permutation operations realized without (with) CNOT gate. We characterize the outputs by measuring the probabilities of each computational basis for each permutation and the measured probabilities are shown in Fig. 3. The algorithm performed on the optical quantum circuit gives a probability of success 93.023 ± 2.015% on average.

 

Fig. 3 Experimental results. Eight different permutations for four-dimensional set are chosen as $U_{f_m^{\pm }}(m=0,1,2,3)$. The output of the measurement HV (VH) means the parity of the permutation is positive (negative). Error bars indicate the statistical uncertainty.

Download Full Size | PDF

4. Conclusion and discussion

We experimentally realized a quantum speed-up algorithm to determine the parity of permutation functions of four-dimensional set with only one query. The experiment has been performed in a photonic system which is ideal for probing of the boundary between classical and quantum efficiency in computing algorithms. The experimental results demonstrate the successful performance of the algorithm with the successful probability 93.023 ± 2.015% on average. Our experiment proves that a single qudit is sufficient to design an oracle-based algorithm which solves a black-box problem and demonstrates quantum speed-up over any classical approach.

NOTE: While we finished this experiment, we noticed that this algorithm has also been realized in nuclear magnetic resonance system [21,22].