## Abstract

Quantum algorithm acts as an important role in quantum computation science, not only for providing a great vision for solving classically unsolvable problems, but also due to the fact that it gives a potential way of understanding quantum physics. We experimentally realize a quantum speed-up algorithm with a single qudit via linear optics and prove that even a single qudit is enough for designing an oracle-based algorithm which can solve a certain problem twice faster than any classical algorithm. The algorithm can be generalized to higher-dimensional systems with the same two-to-one speed-up ratio.

© 2015 Optical Society of America

## 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 2*d* 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

*x ∈ S*,

*m*= 0,1,..

*d*− 1. The permutations can be classified as clockwise or counterclockwise according to whether the function has the form ${f}_{m}^{+}(x)$ or ${f}_{m}^{-}(x)$. Such property corresponds to the parity of the permutation function. For

*d*is even (odd), the parity of clockwise or counterclockwise permutation is positive (negative) or negative (positive). For a given permutation, the task of the algorithm is to determine whether it is clockwise or counterclockwise, and therefore to determine the parity. Classically, one needs to evaluate the permutation function at least twice for different inputs. Whereas in Gedik’s algorithm, with a single qudit we show that performing the function only once is enough.

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*, (ii) permutation operation ${U}_{{f}_{m}^{\pm}}$, (iii) inverse QFT ${U}_{FT}^{\u2020}$.

_{FT}Subroutine (i) is to apply QFT [16]
on the initial state of the quantum algorithm
|*ψ*〉_{0} = |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

otherwise, the counterclockwise permutation ${U}_{{f}_{m}^{-}}$ makes the algorithm concluding withThe 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

*X*) gates (see Fig. 1(b)). Finally, the inverse QFT module is realized in a semiclassical way [13, 17]. Instead of fabricating an inverse QFT circuit with controlled two-qubit gate [16], this semiclassical method requires only single-qubit gates performed together with the feedback of classical signals.

## 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_{4} and HWP_{5} 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_{2} from 17.5° for the CNOT gate to 45° for two
*X* gates on both photons. Whereas, the setting angles of
HWP_{1} and HWP_{3} are fixed at 22.5° and
*−*22.5°, respectively. Thus all the eight permutations can
be realized via tuning the angle of HWP_{2}, and moving
HWP_{4} and HWP_{5}.

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_{2} 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\u3009+|V\u3009)|V\u3009/\sqrt{2}$, after a CNOT gate the output state is
$(|HV\u3009+|VH\u3009)/\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.

## 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].

## Acknowledgments

We thank J. S. Xu and K. Sun for simulating discussions. This work has been supported by the National Natural Science Foundation of China under Grant Nos. 11174052 and 11474049, the Open Fund from the State Key Laboratory of Precision Spectroscopy of East China Normal University, and the CAST Innovation fund.

## References and links

**1. **P. Shor, “Polynomial-time algorithms for prime
factorization,” SIAM J. Comput. **26**(5), 1484
(1997). [CrossRef]

**2. **L. M. K. Vandersypen, M. Steffen, G. Breyta, C. S. Yannoni, M. H. Sherwood, and I. L. Chuang, “Experimental realization of Shor’s
quantum factoring algorithm using nuclear magnetic
resonance,” Nature **414**, 883–887
(2001). [CrossRef]

**3. **R. P. Feynman, “Simulating physics with
computers,” Int. J. Theor. Phys. **21**, 467 (1982). [CrossRef]

**4. **S. Lloyd, “Universal quantum
simulators,” Science **273**, 1073 (1996). [CrossRef] [PubMed]

**5. **S. Aaronson and A. Arkhipov, “The computational complexity of linear
optics,” Proc. ACM Symposium on Theory of
computing, San Jose, CA pp.
333–342
(2011).

**6. **M. A. Broome, A. Fedrizzi, S. Rahimi-Keshari, J. Dove, S. Aaronson, T. C. Ralph, and A. G. White, “Photonic boson sampling in a tunable
circuit,” Science **339**, 794–798
(2013). [CrossRef]

**7. **X. Q. Zhou, P. Kalasuwan, T. C. Ralph, and J. L. O’Brien, “Calculating unknown eigenvalues with
a quantum algorithm,” Nat. Photonics ,
**7**, 223–228
(2013). [CrossRef]

**8. **D. R. Simon, in Proceedings of the 35th IEEE Symposium
on Foundations of Computer Science, Santa
Fe, 1994 (IEEE Computer
Society, Washington,
DC, 1994), pp.
116–123.

**9. **D. R. Simon, “On the power of quantum
computation,” SIAM J. Comput. **26**, 1474–1483
(1997). [CrossRef]

**10. **M. S. Tame, B. A. Bell, C. Di Franco, W. J. Wadsworth, and J. G. Rarity, “Experimental realization of a one-way
quantum computer algorithm solving simon’s problem,”
Phys. Rev. Lett. **113**,
200501 (2014). [CrossRef]

**11. **Y. Long, G. R. Feng, Y. C. Tang, W. Qin, and G. L. Long, “NMR realization of adiabatic quantum
algorithms for the modified Simon problem,”
Phys. Rev. A **88**,
012306 (2013). [CrossRef]

**12. **A. W. Harrow, A. Hassidim, and S. Lloyd, “Quantum algorithm for linear systems
of equations,” Phys. Rev. Lett. **103**, 150502
(2009). [CrossRef] [PubMed]

**13. **X. D. Cai, C. Weedbrook, Z. E. Su, M. C. Chen, M. Gu, M. J. Zhu, L. Li, N. L. Liu, C. Y. Lu, and J. W. Pan, “Experimental quantum computing to
solve systems of linear equations,” Phys. Rev.
Lett. **110**, 230501
(2013). [CrossRef] [PubMed]

**14. **J. Pan, Y. D. Cao, X. W. Li, C. Y. Ju, H. W. Chen, X. H. Peng, S. Kais, and J. F. Du, “Experimental realization of quantum
algorithm for solving linear systems of equations,”
Phys. Rev. A **89**,
022313 (2014). [CrossRef]

**15. **Z. Gedik, “Computational speed-up with a single
qutrit,”
arXiv:1403.5861.

**16. **M. A. Nielsen and I. L. Chuang, *Quantum Computation and Quantum
Information* (Cambridge
University, 2000).

**17. **R. B. Griffiths and C. S. Niu, “Semiclassical Fourier Transform for
quantum computation,” Phys. Rev.
Lett. **76**, 3228
(1996). [CrossRef] [PubMed]

**18. **J. L. O’Brien, G. J. Pryde, A. G. White, T. C. Ralph, and D. Branning, “Demonstration of an all-optical
quantum controlled-NOT gate,” Nature **426**, 264–267
(2003). [CrossRef]

**19. **C. K. Hong, Z. Y. Ou, and L. Mandel, “Measurement of subpicosecond time
intervals between two photons by interference,”
Phys. Rev. Lett. **59**,
2044 (1987). [CrossRef] [PubMed]

**20. **D. F. V. James, P. G. Kwiat, W. J. Munro, and A. G. White, “Measurement of
qubits,” Phys. Rev. A **64**, 052312 (2001). [CrossRef]

**21. **I. A. Silva, E. L. G. Vidoto, D. O. Soares-Pinto, E. R. deAzevedo, B. Çakmak, G. Karpat, F. F. Fanchini, and Z. Gedik, “Computational speed-up in a single qudit NMR
quantum information processor,”
arXiv:1406.3579.

**22. **S. Dogra, Arvind, and K. Dorai, “Determining the parity of a
permutation using an experimental NMR qutrit,”
Phys. Lett. A **378**,
3452–3456 (2014). [CrossRef]