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

Full Article  |  PDF Article
OSA Recommended Articles
Experimental realization of a quantum quincunx by use of linear optical elements

Binh Do, Michael L. Stohler, Sunder Balasubramanian, Daniel S. Elliott, Christopher Eash, Ephraim Fischbach, Michael A. Fischbach, Arthur Mills, and Benjamin Zwickl
J. Opt. Soc. Am. B 22(2) 499-504 (2005)

Simplified proposal for realizing a multiqubit tunable phase gate in circuit QED

Wen-An Li and Yuan Chen
J. Opt. Soc. Am. B 34(7) 1560-1566 (2017)

References

  • View by:
  • |
  • |
  • |

  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]

2014 (3)

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]

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]

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]

2013 (4)

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]

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]

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]

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]

2009 (1)

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

2003 (1)

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]

2001 (2)

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

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]

1997 (2)

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

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

1996 (2)

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

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

1987 (1)

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]

1982 (1)

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

Aaronson, S.

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]

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).

Arkhipov, A.

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).

Arvind,

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]

Bell, B. A.

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]

Branning, D.

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]

Breyta, G.

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]

Broome, M. A.

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]

Cai, X. D.

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]

Çakmak, B.

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.

Cao, Y. D.

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]

Chen, H. W.

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]

Chen, M. C.

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]

Chuang, I. L.

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]

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

deAzevedo, E. R.

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.

Di Franco, C.

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]

Dogra, S.

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]

Dorai, K.

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]

Dove, J.

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]

Du, J. F.

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]

Fanchini, F. F.

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.

Fedrizzi, A.

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]

Feng, G. R.

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]

Feynman, R. P.

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

Gedik, Z.

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

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.

Griffiths, R. B.

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

Gu, M.

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]

Harrow, A. W.

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

Hassidim, A.

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

Hong, C. K.

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]

James, D. F. V.

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

Ju, C. Y.

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]

Kais, S.

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]

Kalasuwan, P.

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]

Karpat, G.

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.

Kwiat, P. G.

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

Li, L.

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]

Li, X. W.

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]

Liu, N. L.

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]

Lloyd, S.

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

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

Long, G. L.

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]

Long, Y.

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]

Lu, C. Y.

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]

Mandel, L.

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]

Munro, W. J.

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

Nielsen, M. A.

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

Niu, C. S.

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

O’Brien, J. L.

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]

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]

Ou, Z. Y.

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]

Pan, J.

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]

Pan, J. W.

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]

Peng, X. H.

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]

Pryde, G. J.

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]

Qin, W.

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]

Rahimi-Keshari, S.

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]

Ralph, T. C.

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]

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]

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]

Rarity, J. G.

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]

Sherwood, M. H.

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]

Shor, P.

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

Silva, I. A.

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.

Simon, D. R.

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

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.

Soares-Pinto, D. O.

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.

Steffen, M.

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]

Su, Z. E.

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]

Tame, M. S.

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]

Tang, Y. C.

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]

Vandersypen, L. M. K.

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]

Vidoto, E. L. G.

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.

Wadsworth, W. J.

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]

Weedbrook, C.

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]

White, A. G.

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]

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]

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

Yannoni, C. S.

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]

Zhou, X. Q.

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]

Zhu, M. J.

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]

Int. J. Theor. Phys. (1)

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

Nat. Photonics (1)

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]

Nature (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]

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]

Phys. Lett. A (1)

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]

Phys. Rev. A (3)

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

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]

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]

Phys. Rev. Lett. (5)

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

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]

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]

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]

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

Science (2)

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

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]

SIAM J. Comput. (2)

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

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

Other (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).

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.

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

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

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.

Cited By

OSA participates in Crossref's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (3)

Fig. 1
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.
Fig. 2
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 (HWP1 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 HWP2 and moving HWP4 and HWP5 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.
Fig. 3
Fig. 3 Experimental results. Eight different permutations for four-dimensional set are chosen as U f m ± ( 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.

Tables (1)

Tables Icon

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

Equations (7)

Equations on this page are rendered with MathJax. Learn more.

f m ± ( x ) = ( m ± x ) mod ( d )
| ψ 1 = 1 d k = 0 d 1 e 2 π i k / d | k .
U f m ± = j = 0 d 1 | ( m ± j ) m o d ( d ) j | .
| ψ 2 = 1 d k = 0 d 1 e 2 π i k / d | ( m ± k ) m o d ( d ) .
| ψ 3 + = e 2 π i m / d | 1 ,
| ψ 3 = e 2 π i ( d 1 ) m / d | d 1 .
( | 0 + i | 1 | 2 i | 3 ) / 2 ,

Metrics