Abstract

Boson sampling can provide strong evidence that the computational power of a quantum computer outperforms a classical one via currently feasible linear optics experiments. However, how to identify an actual boson sampling device against any classical computing imposters is an ambiguous problem due to the computational complexity class in which boson sampling lies. The certification protocol based on bosonic bunching fails to rule out the so-called mean-field sampling. We propose a certification scheme to distinguish the boson sampling from the mean-field sampling for any random scattering matrices chosen via the Harr measure. We numerically analyze our scheme and the influence of the imperfect input states caused by non-simultaneous arrival photons.

© 2016 Optical Society of America

Full Article  |  PDF Article
OSA Recommended Articles
Quantum fast Fourier transform and quantum computation by linear optics

Ronen Barak and Yacob Ben-Aryeh
J. Opt. Soc. Am. B 24(2) 231-240 (2007)

Sparsity-based recovery of three-photon quantum states from two-fold correlations

Dikla Oren, Yoav Shechtman, Maor Mutzafi, Yonina C. Eldar, and Mordechai Segev
Optica 3(3) 226-232 (2016)

Experimental pre-assessing of two-mode entanglement in Gaussian state mixing

Adriana Pecoraro, Daniela Buono, Gaetano Nocerino, Alberto Porzio, Stefano Olivares, and Matteo G. A. Paris
J. Opt. Soc. Am. B 34(2) 404-411 (2017)

References

  • View by:
  • |
  • |
  • |

  1. P. W. Shor, “Algorithms for quantum computation: discrete logarithms and factoring,” in Proceedings of the 35th Annual Symposium on Foundations of Computer Science (IEEE, 1994), pp. 124–134.
  2. P. W. Shor, “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,” SIAM Rev. 41, 303–332 (1999).
    [Crossref]
  3. M. A. Nielsen and I. L. Chuang, Quantum Computation and Information (Cambridge University, 2000).
  4. E. Martin-Lopez, A. Laing, T. Lawson, R. Alvarez, X. Q. Zhou, and J. L. O’Brien, “Experimental realization of Shor’s quantum factoring algorithm using qubit recycling,” Nat. Photonics 6, 773–776 (2012).
    [Crossref]
  5. S. Aaronson and A. Arkhipov, “The computational complexity of linear optics,” in Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing (STOC), New York, 2011, pp. 333–342.
  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. J. B. Spring, B. J. Metcalf, P. C. Humphreys, W. S. Kolthammer, X. M. Jin, M. Barbieri, A. Datta, N. Thomas-Peter, N. K. Langford, D. Kundys, J. C. Gates, B. J. Smith, P. G. R. Smith, and I. A. Walmsley, “Boson sampling on a photonic chip,” Science 339, 798–801 (2013).
    [Crossref]
  8. M. Tillmann, B. Dakic, R. Heilmann, S. Nolte, A. Szameit, and P. Walther, “Experimental boson sampling,” Nat. Photonics 7, 540–544 (2013).
    [Crossref]
  9. A. Crespi, R. Osellame, R. Ramponi, D. J. Brod, E. F. Galvao, N. Spagnolo, C. Vitelli, E. Maiorino, P. Mataloni, and F. Sciarrino, “Integrated multimode interferometers with arbitrary designs for photonic boson sampling,” Nat. Photonics 7, 545–549 (2013).
    [Crossref]
  10. J. Carolan, C. Harrold, C. Sparrow, E. Martín-López, N. J. Russell, J. W. Silverstone, P. J. Shadbolt, N. Matsuda, M. Oguma, M. Itoh, G. D. Marshall, M. G. Thompson, J. C. F. Matthews, T. Hashimoto, J. L. O’Brien, and A. Laing, “Universal linear optics,” Science 349, 711–716 (2015).
    [Crossref]
  11. K. R. Motes, A. Gilchrist, J. P. Dowling, and P. P. Rohde, “Scalable boson sampling with time-bin encoding using a loop-based architecture,” Phys. Rev. Lett. 113, 120501 (2014).
    [Crossref]
  12. Y. He, Z.-E. Su, H.-L. Huang, X. Ding, J. Qin, C. Wang, S. Unsleber, C. Chen, H. Wang, Y.-M. He, X.-L. Wang, C. Schneider, M. Kamp, S. Höfling, C.-Y. Lu, and J.-W. Pan, “Scalable boson sampling with a single-photon device,” arXiv:1603.04127 [quant-ph] (2016).
  13. P. P. Rohde and T. C. Ralph, “Error tolerance of the boson-sampling model for linear optics quantum computing,” Phys. Rev. A 85, 022332 (2012).
    [Crossref]
  14. A. P. Lund, A. Laing, S. Rahimi-Keshari, T. Rudolph, J. L. O’Brien, and T. C. Ralph, “Boson sampling from a Gaussian state,” Phys. Rev. Lett. 113, 100502 (2014).
    [Crossref]
  15. M. Bentivegna, N. Spagnolo, C. Vitelli, F. Flamini, N. Viggianiello, L. Latmiral, P. Mataloni, D. J. Brod, E. F. Galvãoand, A. Crespi, R. Ramponi, R. Osellame, and F. Sciarrino, “Experimental scattershot boson sampling,” Sci. Adv. 1, e1400255 (2015).
    [Crossref]
  16. C. Gogolin, M. Kliesch, L. Aolita, and J. Eisert, “Boson-sampling in the light of sample complexity,” arXiv:1306.3995v2 (2013).
  17. S. Aaronson and A. Arkhipov, “BosonSampling is far from uniform,” Quantum Inf. Comput. 14, 1383–1423 (2013).
  18. N. Spagnolo, C. Vitelli, M. Bentivegna, D. J. Brod, A. Crespi, F. Flamini, S. Giacomini, G. Milani, R. Ramponi, P. Mataloni, R. Osellame, E. F. Galvao, and F. Sciarrino, “Experimental validation of photonic boson sampling,” Nat. Photonics 8, 615–620 (2014).
    [Crossref]
  19. J. Carolan, D. A. MeineckeJasmin, P. J. Shadbolt, N. J. Russell, N. Ismail, K. Wörhoff, T. Rudolph, M. G. Thompson, J. L. O’Brien, J. C. F. Matthews, and A. Laing, “On the experimental verification of quantum complexity in linear optics,” Nat. Photonics 8, 621–626 (2014).
    [Crossref]
  20. J. Carolan, J. Meinecke, P. Shadbolt, N. J. Russell, N. Ismail, K. Wörhoff, T. Rudolph, M. Thompson, J. L. O’Brien, J. Matthews, and A. Laing, “Verifying quantum complexity in linear optical experiments,” in Conference on Lasers and Electro-Optics (Optical Society of America, 2014), paper FM2A.7.
  21. M. C. Tichy, K. Mayer, A. Buchleitner, and K. Mølmer, “Stringent and efficient assessment of boson-sampling devices,” Phys. Rev. Lett. 113, 020502 (2014).
    [Crossref]
  22. A. Crespi, R. Osellame, R. Ramponi, M. Bentivegna, F. Flamini, N. Spagnolo, N. Viggianiello, L. Innocenti, P. Mataloni, and F. Sciarrino, “Suppression law of quantum states in a 3D photonic fast Fourier transform chip,” Nat. Commun. 7, 10469 (2016).
    [Crossref]
  23. M. Jerrum, A. Sinclair, and E. Vigoda, “A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries,” in Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing (STOC), New York, 2001, pp. 712–721.
  24. M. C. Tichy, H. T. Lim, Y. S. Ra, F. Mintert, Y. H. Kim, and A. Buchleitner, “Four-photon indistinguishability transition,” Phys. Rev. A 83, 062111 (2011).
    [Crossref]

2016 (1)

A. Crespi, R. Osellame, R. Ramponi, M. Bentivegna, F. Flamini, N. Spagnolo, N. Viggianiello, L. Innocenti, P. Mataloni, and F. Sciarrino, “Suppression law of quantum states in a 3D photonic fast Fourier transform chip,” Nat. Commun. 7, 10469 (2016).
[Crossref]

2015 (2)

M. Bentivegna, N. Spagnolo, C. Vitelli, F. Flamini, N. Viggianiello, L. Latmiral, P. Mataloni, D. J. Brod, E. F. Galvãoand, A. Crespi, R. Ramponi, R. Osellame, and F. Sciarrino, “Experimental scattershot boson sampling,” Sci. Adv. 1, e1400255 (2015).
[Crossref]

J. Carolan, C. Harrold, C. Sparrow, E. Martín-López, N. J. Russell, J. W. Silverstone, P. J. Shadbolt, N. Matsuda, M. Oguma, M. Itoh, G. D. Marshall, M. G. Thompson, J. C. F. Matthews, T. Hashimoto, J. L. O’Brien, and A. Laing, “Universal linear optics,” Science 349, 711–716 (2015).
[Crossref]

2014 (5)

K. R. Motes, A. Gilchrist, J. P. Dowling, and P. P. Rohde, “Scalable boson sampling with time-bin encoding using a loop-based architecture,” Phys. Rev. Lett. 113, 120501 (2014).
[Crossref]

N. Spagnolo, C. Vitelli, M. Bentivegna, D. J. Brod, A. Crespi, F. Flamini, S. Giacomini, G. Milani, R. Ramponi, P. Mataloni, R. Osellame, E. F. Galvao, and F. Sciarrino, “Experimental validation of photonic boson sampling,” Nat. Photonics 8, 615–620 (2014).
[Crossref]

J. Carolan, D. A. MeineckeJasmin, P. J. Shadbolt, N. J. Russell, N. Ismail, K. Wörhoff, T. Rudolph, M. G. Thompson, J. L. O’Brien, J. C. F. Matthews, and A. Laing, “On the experimental verification of quantum complexity in linear optics,” Nat. Photonics 8, 621–626 (2014).
[Crossref]

M. C. Tichy, K. Mayer, A. Buchleitner, and K. Mølmer, “Stringent and efficient assessment of boson-sampling devices,” Phys. Rev. Lett. 113, 020502 (2014).
[Crossref]

A. P. Lund, A. Laing, S. Rahimi-Keshari, T. Rudolph, J. L. O’Brien, and T. C. Ralph, “Boson sampling from a Gaussian state,” Phys. Rev. Lett. 113, 100502 (2014).
[Crossref]

2013 (5)

S. Aaronson and A. Arkhipov, “BosonSampling is far from uniform,” Quantum Inf. Comput. 14, 1383–1423 (2013).

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. B. Spring, B. J. Metcalf, P. C. Humphreys, W. S. Kolthammer, X. M. Jin, M. Barbieri, A. Datta, N. Thomas-Peter, N. K. Langford, D. Kundys, J. C. Gates, B. J. Smith, P. G. R. Smith, and I. A. Walmsley, “Boson sampling on a photonic chip,” Science 339, 798–801 (2013).
[Crossref]

M. Tillmann, B. Dakic, R. Heilmann, S. Nolte, A. Szameit, and P. Walther, “Experimental boson sampling,” Nat. Photonics 7, 540–544 (2013).
[Crossref]

A. Crespi, R. Osellame, R. Ramponi, D. J. Brod, E. F. Galvao, N. Spagnolo, C. Vitelli, E. Maiorino, P. Mataloni, and F. Sciarrino, “Integrated multimode interferometers with arbitrary designs for photonic boson sampling,” Nat. Photonics 7, 545–549 (2013).
[Crossref]

2012 (2)

P. P. Rohde and T. C. Ralph, “Error tolerance of the boson-sampling model for linear optics quantum computing,” Phys. Rev. A 85, 022332 (2012).
[Crossref]

E. Martin-Lopez, A. Laing, T. Lawson, R. Alvarez, X. Q. Zhou, and J. L. O’Brien, “Experimental realization of Shor’s quantum factoring algorithm using qubit recycling,” Nat. Photonics 6, 773–776 (2012).
[Crossref]

2011 (1)

M. C. Tichy, H. T. Lim, Y. S. Ra, F. Mintert, Y. H. Kim, and A. Buchleitner, “Four-photon indistinguishability transition,” Phys. Rev. A 83, 062111 (2011).
[Crossref]

1999 (1)

P. W. Shor, “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,” SIAM Rev. 41, 303–332 (1999).
[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, “BosonSampling is far from uniform,” Quantum Inf. Comput. 14, 1383–1423 (2013).

S. Aaronson and A. Arkhipov, “The computational complexity of linear optics,” in Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing (STOC), New York, 2011, pp. 333–342.

Alvarez, R.

E. Martin-Lopez, A. Laing, T. Lawson, R. Alvarez, X. Q. Zhou, and J. L. O’Brien, “Experimental realization of Shor’s quantum factoring algorithm using qubit recycling,” Nat. Photonics 6, 773–776 (2012).
[Crossref]

Aolita, L.

C. Gogolin, M. Kliesch, L. Aolita, and J. Eisert, “Boson-sampling in the light of sample complexity,” arXiv:1306.3995v2 (2013).

Arkhipov, A.

S. Aaronson and A. Arkhipov, “BosonSampling is far from uniform,” Quantum Inf. Comput. 14, 1383–1423 (2013).

S. Aaronson and A. Arkhipov, “The computational complexity of linear optics,” in Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing (STOC), New York, 2011, pp. 333–342.

Barbieri, M.

J. B. Spring, B. J. Metcalf, P. C. Humphreys, W. S. Kolthammer, X. M. Jin, M. Barbieri, A. Datta, N. Thomas-Peter, N. K. Langford, D. Kundys, J. C. Gates, B. J. Smith, P. G. R. Smith, and I. A. Walmsley, “Boson sampling on a photonic chip,” Science 339, 798–801 (2013).
[Crossref]

Bentivegna, M.

A. Crespi, R. Osellame, R. Ramponi, M. Bentivegna, F. Flamini, N. Spagnolo, N. Viggianiello, L. Innocenti, P. Mataloni, and F. Sciarrino, “Suppression law of quantum states in a 3D photonic fast Fourier transform chip,” Nat. Commun. 7, 10469 (2016).
[Crossref]

M. Bentivegna, N. Spagnolo, C. Vitelli, F. Flamini, N. Viggianiello, L. Latmiral, P. Mataloni, D. J. Brod, E. F. Galvãoand, A. Crespi, R. Ramponi, R. Osellame, and F. Sciarrino, “Experimental scattershot boson sampling,” Sci. Adv. 1, e1400255 (2015).
[Crossref]

N. Spagnolo, C. Vitelli, M. Bentivegna, D. J. Brod, A. Crespi, F. Flamini, S. Giacomini, G. Milani, R. Ramponi, P. Mataloni, R. Osellame, E. F. Galvao, and F. Sciarrino, “Experimental validation of photonic boson sampling,” Nat. Photonics 8, 615–620 (2014).
[Crossref]

Brod, D. J.

M. Bentivegna, N. Spagnolo, C. Vitelli, F. Flamini, N. Viggianiello, L. Latmiral, P. Mataloni, D. J. Brod, E. F. Galvãoand, A. Crespi, R. Ramponi, R. Osellame, and F. Sciarrino, “Experimental scattershot boson sampling,” Sci. Adv. 1, e1400255 (2015).
[Crossref]

N. Spagnolo, C. Vitelli, M. Bentivegna, D. J. Brod, A. Crespi, F. Flamini, S. Giacomini, G. Milani, R. Ramponi, P. Mataloni, R. Osellame, E. F. Galvao, and F. Sciarrino, “Experimental validation of photonic boson sampling,” Nat. Photonics 8, 615–620 (2014).
[Crossref]

A. Crespi, R. Osellame, R. Ramponi, D. J. Brod, E. F. Galvao, N. Spagnolo, C. Vitelli, E. Maiorino, P. Mataloni, and F. Sciarrino, “Integrated multimode interferometers with arbitrary designs for photonic boson sampling,” Nat. Photonics 7, 545–549 (2013).
[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]

Buchleitner, A.

M. C. Tichy, K. Mayer, A. Buchleitner, and K. Mølmer, “Stringent and efficient assessment of boson-sampling devices,” Phys. Rev. Lett. 113, 020502 (2014).
[Crossref]

M. C. Tichy, H. T. Lim, Y. S. Ra, F. Mintert, Y. H. Kim, and A. Buchleitner, “Four-photon indistinguishability transition,” Phys. Rev. A 83, 062111 (2011).
[Crossref]

Carolan, J.

J. Carolan, C. Harrold, C. Sparrow, E. Martín-López, N. J. Russell, J. W. Silverstone, P. J. Shadbolt, N. Matsuda, M. Oguma, M. Itoh, G. D. Marshall, M. G. Thompson, J. C. F. Matthews, T. Hashimoto, J. L. O’Brien, and A. Laing, “Universal linear optics,” Science 349, 711–716 (2015).
[Crossref]

J. Carolan, D. A. MeineckeJasmin, P. J. Shadbolt, N. J. Russell, N. Ismail, K. Wörhoff, T. Rudolph, M. G. Thompson, J. L. O’Brien, J. C. F. Matthews, and A. Laing, “On the experimental verification of quantum complexity in linear optics,” Nat. Photonics 8, 621–626 (2014).
[Crossref]

J. Carolan, J. Meinecke, P. Shadbolt, N. J. Russell, N. Ismail, K. Wörhoff, T. Rudolph, M. Thompson, J. L. O’Brien, J. Matthews, and A. Laing, “Verifying quantum complexity in linear optical experiments,” in Conference on Lasers and Electro-Optics (Optical Society of America, 2014), paper FM2A.7.

Chen, C.

Y. He, Z.-E. Su, H.-L. Huang, X. Ding, J. Qin, C. Wang, S. Unsleber, C. Chen, H. Wang, Y.-M. He, X.-L. Wang, C. Schneider, M. Kamp, S. Höfling, C.-Y. Lu, and J.-W. Pan, “Scalable boson sampling with a single-photon device,” arXiv:1603.04127 [quant-ph] (2016).

Chuang, I. L.

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

Crespi, A.

A. Crespi, R. Osellame, R. Ramponi, M. Bentivegna, F. Flamini, N. Spagnolo, N. Viggianiello, L. Innocenti, P. Mataloni, and F. Sciarrino, “Suppression law of quantum states in a 3D photonic fast Fourier transform chip,” Nat. Commun. 7, 10469 (2016).
[Crossref]

M. Bentivegna, N. Spagnolo, C. Vitelli, F. Flamini, N. Viggianiello, L. Latmiral, P. Mataloni, D. J. Brod, E. F. Galvãoand, A. Crespi, R. Ramponi, R. Osellame, and F. Sciarrino, “Experimental scattershot boson sampling,” Sci. Adv. 1, e1400255 (2015).
[Crossref]

N. Spagnolo, C. Vitelli, M. Bentivegna, D. J. Brod, A. Crespi, F. Flamini, S. Giacomini, G. Milani, R. Ramponi, P. Mataloni, R. Osellame, E. F. Galvao, and F. Sciarrino, “Experimental validation of photonic boson sampling,” Nat. Photonics 8, 615–620 (2014).
[Crossref]

A. Crespi, R. Osellame, R. Ramponi, D. J. Brod, E. F. Galvao, N. Spagnolo, C. Vitelli, E. Maiorino, P. Mataloni, and F. Sciarrino, “Integrated multimode interferometers with arbitrary designs for photonic boson sampling,” Nat. Photonics 7, 545–549 (2013).
[Crossref]

Dakic, B.

M. Tillmann, B. Dakic, R. Heilmann, S. Nolte, A. Szameit, and P. Walther, “Experimental boson sampling,” Nat. Photonics 7, 540–544 (2013).
[Crossref]

Datta, A.

J. B. Spring, B. J. Metcalf, P. C. Humphreys, W. S. Kolthammer, X. M. Jin, M. Barbieri, A. Datta, N. Thomas-Peter, N. K. Langford, D. Kundys, J. C. Gates, B. J. Smith, P. G. R. Smith, and I. A. Walmsley, “Boson sampling on a photonic chip,” Science 339, 798–801 (2013).
[Crossref]

Ding, X.

Y. He, Z.-E. Su, H.-L. Huang, X. Ding, J. Qin, C. Wang, S. Unsleber, C. Chen, H. Wang, Y.-M. He, X.-L. Wang, C. Schneider, M. Kamp, S. Höfling, C.-Y. Lu, and J.-W. Pan, “Scalable boson sampling with a single-photon device,” arXiv:1603.04127 [quant-ph] (2016).

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]

Dowling, J. P.

K. R. Motes, A. Gilchrist, J. P. Dowling, and P. P. Rohde, “Scalable boson sampling with time-bin encoding using a loop-based architecture,” Phys. Rev. Lett. 113, 120501 (2014).
[Crossref]

Eisert, J.

C. Gogolin, M. Kliesch, L. Aolita, and J. Eisert, “Boson-sampling in the light of sample complexity,” arXiv:1306.3995v2 (2013).

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]

Flamini, F.

A. Crespi, R. Osellame, R. Ramponi, M. Bentivegna, F. Flamini, N. Spagnolo, N. Viggianiello, L. Innocenti, P. Mataloni, and F. Sciarrino, “Suppression law of quantum states in a 3D photonic fast Fourier transform chip,” Nat. Commun. 7, 10469 (2016).
[Crossref]

M. Bentivegna, N. Spagnolo, C. Vitelli, F. Flamini, N. Viggianiello, L. Latmiral, P. Mataloni, D. J. Brod, E. F. Galvãoand, A. Crespi, R. Ramponi, R. Osellame, and F. Sciarrino, “Experimental scattershot boson sampling,” Sci. Adv. 1, e1400255 (2015).
[Crossref]

N. Spagnolo, C. Vitelli, M. Bentivegna, D. J. Brod, A. Crespi, F. Flamini, S. Giacomini, G. Milani, R. Ramponi, P. Mataloni, R. Osellame, E. F. Galvao, and F. Sciarrino, “Experimental validation of photonic boson sampling,” Nat. Photonics 8, 615–620 (2014).
[Crossref]

Galvao, E. F.

N. Spagnolo, C. Vitelli, M. Bentivegna, D. J. Brod, A. Crespi, F. Flamini, S. Giacomini, G. Milani, R. Ramponi, P. Mataloni, R. Osellame, E. F. Galvao, and F. Sciarrino, “Experimental validation of photonic boson sampling,” Nat. Photonics 8, 615–620 (2014).
[Crossref]

A. Crespi, R. Osellame, R. Ramponi, D. J. Brod, E. F. Galvao, N. Spagnolo, C. Vitelli, E. Maiorino, P. Mataloni, and F. Sciarrino, “Integrated multimode interferometers with arbitrary designs for photonic boson sampling,” Nat. Photonics 7, 545–549 (2013).
[Crossref]

Galvãoand, E. F.

M. Bentivegna, N. Spagnolo, C. Vitelli, F. Flamini, N. Viggianiello, L. Latmiral, P. Mataloni, D. J. Brod, E. F. Galvãoand, A. Crespi, R. Ramponi, R. Osellame, and F. Sciarrino, “Experimental scattershot boson sampling,” Sci. Adv. 1, e1400255 (2015).
[Crossref]

Gates, J. C.

J. B. Spring, B. J. Metcalf, P. C. Humphreys, W. S. Kolthammer, X. M. Jin, M. Barbieri, A. Datta, N. Thomas-Peter, N. K. Langford, D. Kundys, J. C. Gates, B. J. Smith, P. G. R. Smith, and I. A. Walmsley, “Boson sampling on a photonic chip,” Science 339, 798–801 (2013).
[Crossref]

Giacomini, S.

N. Spagnolo, C. Vitelli, M. Bentivegna, D. J. Brod, A. Crespi, F. Flamini, S. Giacomini, G. Milani, R. Ramponi, P. Mataloni, R. Osellame, E. F. Galvao, and F. Sciarrino, “Experimental validation of photonic boson sampling,” Nat. Photonics 8, 615–620 (2014).
[Crossref]

Gilchrist, A.

K. R. Motes, A. Gilchrist, J. P. Dowling, and P. P. Rohde, “Scalable boson sampling with time-bin encoding using a loop-based architecture,” Phys. Rev. Lett. 113, 120501 (2014).
[Crossref]

Gogolin, C.

C. Gogolin, M. Kliesch, L. Aolita, and J. Eisert, “Boson-sampling in the light of sample complexity,” arXiv:1306.3995v2 (2013).

Harrold, C.

J. Carolan, C. Harrold, C. Sparrow, E. Martín-López, N. J. Russell, J. W. Silverstone, P. J. Shadbolt, N. Matsuda, M. Oguma, M. Itoh, G. D. Marshall, M. G. Thompson, J. C. F. Matthews, T. Hashimoto, J. L. O’Brien, and A. Laing, “Universal linear optics,” Science 349, 711–716 (2015).
[Crossref]

Hashimoto, T.

J. Carolan, C. Harrold, C. Sparrow, E. Martín-López, N. J. Russell, J. W. Silverstone, P. J. Shadbolt, N. Matsuda, M. Oguma, M. Itoh, G. D. Marshall, M. G. Thompson, J. C. F. Matthews, T. Hashimoto, J. L. O’Brien, and A. Laing, “Universal linear optics,” Science 349, 711–716 (2015).
[Crossref]

He, Y.

Y. He, Z.-E. Su, H.-L. Huang, X. Ding, J. Qin, C. Wang, S. Unsleber, C. Chen, H. Wang, Y.-M. He, X.-L. Wang, C. Schneider, M. Kamp, S. Höfling, C.-Y. Lu, and J.-W. Pan, “Scalable boson sampling with a single-photon device,” arXiv:1603.04127 [quant-ph] (2016).

He, Y.-M.

Y. He, Z.-E. Su, H.-L. Huang, X. Ding, J. Qin, C. Wang, S. Unsleber, C. Chen, H. Wang, Y.-M. He, X.-L. Wang, C. Schneider, M. Kamp, S. Höfling, C.-Y. Lu, and J.-W. Pan, “Scalable boson sampling with a single-photon device,” arXiv:1603.04127 [quant-ph] (2016).

Heilmann, R.

M. Tillmann, B. Dakic, R. Heilmann, S. Nolte, A. Szameit, and P. Walther, “Experimental boson sampling,” Nat. Photonics 7, 540–544 (2013).
[Crossref]

Höfling, S.

Y. He, Z.-E. Su, H.-L. Huang, X. Ding, J. Qin, C. Wang, S. Unsleber, C. Chen, H. Wang, Y.-M. He, X.-L. Wang, C. Schneider, M. Kamp, S. Höfling, C.-Y. Lu, and J.-W. Pan, “Scalable boson sampling with a single-photon device,” arXiv:1603.04127 [quant-ph] (2016).

Huang, H.-L.

Y. He, Z.-E. Su, H.-L. Huang, X. Ding, J. Qin, C. Wang, S. Unsleber, C. Chen, H. Wang, Y.-M. He, X.-L. Wang, C. Schneider, M. Kamp, S. Höfling, C.-Y. Lu, and J.-W. Pan, “Scalable boson sampling with a single-photon device,” arXiv:1603.04127 [quant-ph] (2016).

Humphreys, P. C.

J. B. Spring, B. J. Metcalf, P. C. Humphreys, W. S. Kolthammer, X. M. Jin, M. Barbieri, A. Datta, N. Thomas-Peter, N. K. Langford, D. Kundys, J. C. Gates, B. J. Smith, P. G. R. Smith, and I. A. Walmsley, “Boson sampling on a photonic chip,” Science 339, 798–801 (2013).
[Crossref]

Innocenti, L.

A. Crespi, R. Osellame, R. Ramponi, M. Bentivegna, F. Flamini, N. Spagnolo, N. Viggianiello, L. Innocenti, P. Mataloni, and F. Sciarrino, “Suppression law of quantum states in a 3D photonic fast Fourier transform chip,” Nat. Commun. 7, 10469 (2016).
[Crossref]

Ismail, N.

J. Carolan, D. A. MeineckeJasmin, P. J. Shadbolt, N. J. Russell, N. Ismail, K. Wörhoff, T. Rudolph, M. G. Thompson, J. L. O’Brien, J. C. F. Matthews, and A. Laing, “On the experimental verification of quantum complexity in linear optics,” Nat. Photonics 8, 621–626 (2014).
[Crossref]

J. Carolan, J. Meinecke, P. Shadbolt, N. J. Russell, N. Ismail, K. Wörhoff, T. Rudolph, M. Thompson, J. L. O’Brien, J. Matthews, and A. Laing, “Verifying quantum complexity in linear optical experiments,” in Conference on Lasers and Electro-Optics (Optical Society of America, 2014), paper FM2A.7.

Itoh, M.

J. Carolan, C. Harrold, C. Sparrow, E. Martín-López, N. J. Russell, J. W. Silverstone, P. J. Shadbolt, N. Matsuda, M. Oguma, M. Itoh, G. D. Marshall, M. G. Thompson, J. C. F. Matthews, T. Hashimoto, J. L. O’Brien, and A. Laing, “Universal linear optics,” Science 349, 711–716 (2015).
[Crossref]

Jerrum, M.

M. Jerrum, A. Sinclair, and E. Vigoda, “A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries,” in Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing (STOC), New York, 2001, pp. 712–721.

Jin, X. M.

J. B. Spring, B. J. Metcalf, P. C. Humphreys, W. S. Kolthammer, X. M. Jin, M. Barbieri, A. Datta, N. Thomas-Peter, N. K. Langford, D. Kundys, J. C. Gates, B. J. Smith, P. G. R. Smith, and I. A. Walmsley, “Boson sampling on a photonic chip,” Science 339, 798–801 (2013).
[Crossref]

Kamp, M.

Y. He, Z.-E. Su, H.-L. Huang, X. Ding, J. Qin, C. Wang, S. Unsleber, C. Chen, H. Wang, Y.-M. He, X.-L. Wang, C. Schneider, M. Kamp, S. Höfling, C.-Y. Lu, and J.-W. Pan, “Scalable boson sampling with a single-photon device,” arXiv:1603.04127 [quant-ph] (2016).

Kim, Y. H.

M. C. Tichy, H. T. Lim, Y. S. Ra, F. Mintert, Y. H. Kim, and A. Buchleitner, “Four-photon indistinguishability transition,” Phys. Rev. A 83, 062111 (2011).
[Crossref]

Kliesch, M.

C. Gogolin, M. Kliesch, L. Aolita, and J. Eisert, “Boson-sampling in the light of sample complexity,” arXiv:1306.3995v2 (2013).

Kolthammer, W. S.

J. B. Spring, B. J. Metcalf, P. C. Humphreys, W. S. Kolthammer, X. M. Jin, M. Barbieri, A. Datta, N. Thomas-Peter, N. K. Langford, D. Kundys, J. C. Gates, B. J. Smith, P. G. R. Smith, and I. A. Walmsley, “Boson sampling on a photonic chip,” Science 339, 798–801 (2013).
[Crossref]

Kundys, D.

J. B. Spring, B. J. Metcalf, P. C. Humphreys, W. S. Kolthammer, X. M. Jin, M. Barbieri, A. Datta, N. Thomas-Peter, N. K. Langford, D. Kundys, J. C. Gates, B. J. Smith, P. G. R. Smith, and I. A. Walmsley, “Boson sampling on a photonic chip,” Science 339, 798–801 (2013).
[Crossref]

Laing, A.

J. Carolan, C. Harrold, C. Sparrow, E. Martín-López, N. J. Russell, J. W. Silverstone, P. J. Shadbolt, N. Matsuda, M. Oguma, M. Itoh, G. D. Marshall, M. G. Thompson, J. C. F. Matthews, T. Hashimoto, J. L. O’Brien, and A. Laing, “Universal linear optics,” Science 349, 711–716 (2015).
[Crossref]

A. P. Lund, A. Laing, S. Rahimi-Keshari, T. Rudolph, J. L. O’Brien, and T. C. Ralph, “Boson sampling from a Gaussian state,” Phys. Rev. Lett. 113, 100502 (2014).
[Crossref]

J. Carolan, D. A. MeineckeJasmin, P. J. Shadbolt, N. J. Russell, N. Ismail, K. Wörhoff, T. Rudolph, M. G. Thompson, J. L. O’Brien, J. C. F. Matthews, and A. Laing, “On the experimental verification of quantum complexity in linear optics,” Nat. Photonics 8, 621–626 (2014).
[Crossref]

E. Martin-Lopez, A. Laing, T. Lawson, R. Alvarez, X. Q. Zhou, and J. L. O’Brien, “Experimental realization of Shor’s quantum factoring algorithm using qubit recycling,” Nat. Photonics 6, 773–776 (2012).
[Crossref]

J. Carolan, J. Meinecke, P. Shadbolt, N. J. Russell, N. Ismail, K. Wörhoff, T. Rudolph, M. Thompson, J. L. O’Brien, J. Matthews, and A. Laing, “Verifying quantum complexity in linear optical experiments,” in Conference on Lasers and Electro-Optics (Optical Society of America, 2014), paper FM2A.7.

Langford, N. K.

J. B. Spring, B. J. Metcalf, P. C. Humphreys, W. S. Kolthammer, X. M. Jin, M. Barbieri, A. Datta, N. Thomas-Peter, N. K. Langford, D. Kundys, J. C. Gates, B. J. Smith, P. G. R. Smith, and I. A. Walmsley, “Boson sampling on a photonic chip,” Science 339, 798–801 (2013).
[Crossref]

Latmiral, L.

M. Bentivegna, N. Spagnolo, C. Vitelli, F. Flamini, N. Viggianiello, L. Latmiral, P. Mataloni, D. J. Brod, E. F. Galvãoand, A. Crespi, R. Ramponi, R. Osellame, and F. Sciarrino, “Experimental scattershot boson sampling,” Sci. Adv. 1, e1400255 (2015).
[Crossref]

Lawson, T.

E. Martin-Lopez, A. Laing, T. Lawson, R. Alvarez, X. Q. Zhou, and J. L. O’Brien, “Experimental realization of Shor’s quantum factoring algorithm using qubit recycling,” Nat. Photonics 6, 773–776 (2012).
[Crossref]

Lim, H. T.

M. C. Tichy, H. T. Lim, Y. S. Ra, F. Mintert, Y. H. Kim, and A. Buchleitner, “Four-photon indistinguishability transition,” Phys. Rev. A 83, 062111 (2011).
[Crossref]

Lu, C.-Y.

Y. He, Z.-E. Su, H.-L. Huang, X. Ding, J. Qin, C. Wang, S. Unsleber, C. Chen, H. Wang, Y.-M. He, X.-L. Wang, C. Schneider, M. Kamp, S. Höfling, C.-Y. Lu, and J.-W. Pan, “Scalable boson sampling with a single-photon device,” arXiv:1603.04127 [quant-ph] (2016).

Lund, A. P.

A. P. Lund, A. Laing, S. Rahimi-Keshari, T. Rudolph, J. L. O’Brien, and T. C. Ralph, “Boson sampling from a Gaussian state,” Phys. Rev. Lett. 113, 100502 (2014).
[Crossref]

Maiorino, E.

A. Crespi, R. Osellame, R. Ramponi, D. J. Brod, E. F. Galvao, N. Spagnolo, C. Vitelli, E. Maiorino, P. Mataloni, and F. Sciarrino, “Integrated multimode interferometers with arbitrary designs for photonic boson sampling,” Nat. Photonics 7, 545–549 (2013).
[Crossref]

Marshall, G. D.

J. Carolan, C. Harrold, C. Sparrow, E. Martín-López, N. J. Russell, J. W. Silverstone, P. J. Shadbolt, N. Matsuda, M. Oguma, M. Itoh, G. D. Marshall, M. G. Thompson, J. C. F. Matthews, T. Hashimoto, J. L. O’Brien, and A. Laing, “Universal linear optics,” Science 349, 711–716 (2015).
[Crossref]

Martin-Lopez, E.

E. Martin-Lopez, A. Laing, T. Lawson, R. Alvarez, X. Q. Zhou, and J. L. O’Brien, “Experimental realization of Shor’s quantum factoring algorithm using qubit recycling,” Nat. Photonics 6, 773–776 (2012).
[Crossref]

Martín-López, E.

J. Carolan, C. Harrold, C. Sparrow, E. Martín-López, N. J. Russell, J. W. Silverstone, P. J. Shadbolt, N. Matsuda, M. Oguma, M. Itoh, G. D. Marshall, M. G. Thompson, J. C. F. Matthews, T. Hashimoto, J. L. O’Brien, and A. Laing, “Universal linear optics,” Science 349, 711–716 (2015).
[Crossref]

Mataloni, P.

A. Crespi, R. Osellame, R. Ramponi, M. Bentivegna, F. Flamini, N. Spagnolo, N. Viggianiello, L. Innocenti, P. Mataloni, and F. Sciarrino, “Suppression law of quantum states in a 3D photonic fast Fourier transform chip,” Nat. Commun. 7, 10469 (2016).
[Crossref]

M. Bentivegna, N. Spagnolo, C. Vitelli, F. Flamini, N. Viggianiello, L. Latmiral, P. Mataloni, D. J. Brod, E. F. Galvãoand, A. Crespi, R. Ramponi, R. Osellame, and F. Sciarrino, “Experimental scattershot boson sampling,” Sci. Adv. 1, e1400255 (2015).
[Crossref]

N. Spagnolo, C. Vitelli, M. Bentivegna, D. J. Brod, A. Crespi, F. Flamini, S. Giacomini, G. Milani, R. Ramponi, P. Mataloni, R. Osellame, E. F. Galvao, and F. Sciarrino, “Experimental validation of photonic boson sampling,” Nat. Photonics 8, 615–620 (2014).
[Crossref]

A. Crespi, R. Osellame, R. Ramponi, D. J. Brod, E. F. Galvao, N. Spagnolo, C. Vitelli, E. Maiorino, P. Mataloni, and F. Sciarrino, “Integrated multimode interferometers with arbitrary designs for photonic boson sampling,” Nat. Photonics 7, 545–549 (2013).
[Crossref]

Matsuda, N.

J. Carolan, C. Harrold, C. Sparrow, E. Martín-López, N. J. Russell, J. W. Silverstone, P. J. Shadbolt, N. Matsuda, M. Oguma, M. Itoh, G. D. Marshall, M. G. Thompson, J. C. F. Matthews, T. Hashimoto, J. L. O’Brien, and A. Laing, “Universal linear optics,” Science 349, 711–716 (2015).
[Crossref]

Matthews, J.

J. Carolan, J. Meinecke, P. Shadbolt, N. J. Russell, N. Ismail, K. Wörhoff, T. Rudolph, M. Thompson, J. L. O’Brien, J. Matthews, and A. Laing, “Verifying quantum complexity in linear optical experiments,” in Conference on Lasers and Electro-Optics (Optical Society of America, 2014), paper FM2A.7.

Matthews, J. C. F.

J. Carolan, C. Harrold, C. Sparrow, E. Martín-López, N. J. Russell, J. W. Silverstone, P. J. Shadbolt, N. Matsuda, M. Oguma, M. Itoh, G. D. Marshall, M. G. Thompson, J. C. F. Matthews, T. Hashimoto, J. L. O’Brien, and A. Laing, “Universal linear optics,” Science 349, 711–716 (2015).
[Crossref]

J. Carolan, D. A. MeineckeJasmin, P. J. Shadbolt, N. J. Russell, N. Ismail, K. Wörhoff, T. Rudolph, M. G. Thompson, J. L. O’Brien, J. C. F. Matthews, and A. Laing, “On the experimental verification of quantum complexity in linear optics,” Nat. Photonics 8, 621–626 (2014).
[Crossref]

Mayer, K.

M. C. Tichy, K. Mayer, A. Buchleitner, and K. Mølmer, “Stringent and efficient assessment of boson-sampling devices,” Phys. Rev. Lett. 113, 020502 (2014).
[Crossref]

Meinecke, J.

J. Carolan, J. Meinecke, P. Shadbolt, N. J. Russell, N. Ismail, K. Wörhoff, T. Rudolph, M. Thompson, J. L. O’Brien, J. Matthews, and A. Laing, “Verifying quantum complexity in linear optical experiments,” in Conference on Lasers and Electro-Optics (Optical Society of America, 2014), paper FM2A.7.

MeineckeJasmin, D. A.

J. Carolan, D. A. MeineckeJasmin, P. J. Shadbolt, N. J. Russell, N. Ismail, K. Wörhoff, T. Rudolph, M. G. Thompson, J. L. O’Brien, J. C. F. Matthews, and A. Laing, “On the experimental verification of quantum complexity in linear optics,” Nat. Photonics 8, 621–626 (2014).
[Crossref]

Metcalf, B. J.

J. B. Spring, B. J. Metcalf, P. C. Humphreys, W. S. Kolthammer, X. M. Jin, M. Barbieri, A. Datta, N. Thomas-Peter, N. K. Langford, D. Kundys, J. C. Gates, B. J. Smith, P. G. R. Smith, and I. A. Walmsley, “Boson sampling on a photonic chip,” Science 339, 798–801 (2013).
[Crossref]

Milani, G.

N. Spagnolo, C. Vitelli, M. Bentivegna, D. J. Brod, A. Crespi, F. Flamini, S. Giacomini, G. Milani, R. Ramponi, P. Mataloni, R. Osellame, E. F. Galvao, and F. Sciarrino, “Experimental validation of photonic boson sampling,” Nat. Photonics 8, 615–620 (2014).
[Crossref]

Mintert, F.

M. C. Tichy, H. T. Lim, Y. S. Ra, F. Mintert, Y. H. Kim, and A. Buchleitner, “Four-photon indistinguishability transition,” Phys. Rev. A 83, 062111 (2011).
[Crossref]

Mølmer, K.

M. C. Tichy, K. Mayer, A. Buchleitner, and K. Mølmer, “Stringent and efficient assessment of boson-sampling devices,” Phys. Rev. Lett. 113, 020502 (2014).
[Crossref]

Motes, K. R.

K. R. Motes, A. Gilchrist, J. P. Dowling, and P. P. Rohde, “Scalable boson sampling with time-bin encoding using a loop-based architecture,” Phys. Rev. Lett. 113, 120501 (2014).
[Crossref]

Nielsen, M. A.

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

Nolte, S.

M. Tillmann, B. Dakic, R. Heilmann, S. Nolte, A. Szameit, and P. Walther, “Experimental boson sampling,” Nat. Photonics 7, 540–544 (2013).
[Crossref]

O’Brien, J. L.

J. Carolan, C. Harrold, C. Sparrow, E. Martín-López, N. J. Russell, J. W. Silverstone, P. J. Shadbolt, N. Matsuda, M. Oguma, M. Itoh, G. D. Marshall, M. G. Thompson, J. C. F. Matthews, T. Hashimoto, J. L. O’Brien, and A. Laing, “Universal linear optics,” Science 349, 711–716 (2015).
[Crossref]

J. Carolan, D. A. MeineckeJasmin, P. J. Shadbolt, N. J. Russell, N. Ismail, K. Wörhoff, T. Rudolph, M. G. Thompson, J. L. O’Brien, J. C. F. Matthews, and A. Laing, “On the experimental verification of quantum complexity in linear optics,” Nat. Photonics 8, 621–626 (2014).
[Crossref]

A. P. Lund, A. Laing, S. Rahimi-Keshari, T. Rudolph, J. L. O’Brien, and T. C. Ralph, “Boson sampling from a Gaussian state,” Phys. Rev. Lett. 113, 100502 (2014).
[Crossref]

E. Martin-Lopez, A. Laing, T. Lawson, R. Alvarez, X. Q. Zhou, and J. L. O’Brien, “Experimental realization of Shor’s quantum factoring algorithm using qubit recycling,” Nat. Photonics 6, 773–776 (2012).
[Crossref]

J. Carolan, J. Meinecke, P. Shadbolt, N. J. Russell, N. Ismail, K. Wörhoff, T. Rudolph, M. Thompson, J. L. O’Brien, J. Matthews, and A. Laing, “Verifying quantum complexity in linear optical experiments,” in Conference on Lasers and Electro-Optics (Optical Society of America, 2014), paper FM2A.7.

Oguma, M.

J. Carolan, C. Harrold, C. Sparrow, E. Martín-López, N. J. Russell, J. W. Silverstone, P. J. Shadbolt, N. Matsuda, M. Oguma, M. Itoh, G. D. Marshall, M. G. Thompson, J. C. F. Matthews, T. Hashimoto, J. L. O’Brien, and A. Laing, “Universal linear optics,” Science 349, 711–716 (2015).
[Crossref]

Osellame, R.

A. Crespi, R. Osellame, R. Ramponi, M. Bentivegna, F. Flamini, N. Spagnolo, N. Viggianiello, L. Innocenti, P. Mataloni, and F. Sciarrino, “Suppression law of quantum states in a 3D photonic fast Fourier transform chip,” Nat. Commun. 7, 10469 (2016).
[Crossref]

M. Bentivegna, N. Spagnolo, C. Vitelli, F. Flamini, N. Viggianiello, L. Latmiral, P. Mataloni, D. J. Brod, E. F. Galvãoand, A. Crespi, R. Ramponi, R. Osellame, and F. Sciarrino, “Experimental scattershot boson sampling,” Sci. Adv. 1, e1400255 (2015).
[Crossref]

N. Spagnolo, C. Vitelli, M. Bentivegna, D. J. Brod, A. Crespi, F. Flamini, S. Giacomini, G. Milani, R. Ramponi, P. Mataloni, R. Osellame, E. F. Galvao, and F. Sciarrino, “Experimental validation of photonic boson sampling,” Nat. Photonics 8, 615–620 (2014).
[Crossref]

A. Crespi, R. Osellame, R. Ramponi, D. J. Brod, E. F. Galvao, N. Spagnolo, C. Vitelli, E. Maiorino, P. Mataloni, and F. Sciarrino, “Integrated multimode interferometers with arbitrary designs for photonic boson sampling,” Nat. Photonics 7, 545–549 (2013).
[Crossref]

Pan, J.-W.

Y. He, Z.-E. Su, H.-L. Huang, X. Ding, J. Qin, C. Wang, S. Unsleber, C. Chen, H. Wang, Y.-M. He, X.-L. Wang, C. Schneider, M. Kamp, S. Höfling, C.-Y. Lu, and J.-W. Pan, “Scalable boson sampling with a single-photon device,” arXiv:1603.04127 [quant-ph] (2016).

Qin, J.

Y. He, Z.-E. Su, H.-L. Huang, X. Ding, J. Qin, C. Wang, S. Unsleber, C. Chen, H. Wang, Y.-M. He, X.-L. Wang, C. Schneider, M. Kamp, S. Höfling, C.-Y. Lu, and J.-W. Pan, “Scalable boson sampling with a single-photon device,” arXiv:1603.04127 [quant-ph] (2016).

Ra, Y. S.

M. C. Tichy, H. T. Lim, Y. S. Ra, F. Mintert, Y. H. Kim, and A. Buchleitner, “Four-photon indistinguishability transition,” Phys. Rev. A 83, 062111 (2011).
[Crossref]

Rahimi-Keshari, S.

A. P. Lund, A. Laing, S. Rahimi-Keshari, T. Rudolph, J. L. O’Brien, and T. C. Ralph, “Boson sampling from a Gaussian state,” Phys. Rev. Lett. 113, 100502 (2014).
[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]

Ralph, T. C.

A. P. Lund, A. Laing, S. Rahimi-Keshari, T. Rudolph, J. L. O’Brien, and T. C. Ralph, “Boson sampling from a Gaussian state,” Phys. Rev. Lett. 113, 100502 (2014).
[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]

P. P. Rohde and T. C. Ralph, “Error tolerance of the boson-sampling model for linear optics quantum computing,” Phys. Rev. A 85, 022332 (2012).
[Crossref]

Ramponi, R.

A. Crespi, R. Osellame, R. Ramponi, M. Bentivegna, F. Flamini, N. Spagnolo, N. Viggianiello, L. Innocenti, P. Mataloni, and F. Sciarrino, “Suppression law of quantum states in a 3D photonic fast Fourier transform chip,” Nat. Commun. 7, 10469 (2016).
[Crossref]

M. Bentivegna, N. Spagnolo, C. Vitelli, F. Flamini, N. Viggianiello, L. Latmiral, P. Mataloni, D. J. Brod, E. F. Galvãoand, A. Crespi, R. Ramponi, R. Osellame, and F. Sciarrino, “Experimental scattershot boson sampling,” Sci. Adv. 1, e1400255 (2015).
[Crossref]

N. Spagnolo, C. Vitelli, M. Bentivegna, D. J. Brod, A. Crespi, F. Flamini, S. Giacomini, G. Milani, R. Ramponi, P. Mataloni, R. Osellame, E. F. Galvao, and F. Sciarrino, “Experimental validation of photonic boson sampling,” Nat. Photonics 8, 615–620 (2014).
[Crossref]

A. Crespi, R. Osellame, R. Ramponi, D. J. Brod, E. F. Galvao, N. Spagnolo, C. Vitelli, E. Maiorino, P. Mataloni, and F. Sciarrino, “Integrated multimode interferometers with arbitrary designs for photonic boson sampling,” Nat. Photonics 7, 545–549 (2013).
[Crossref]

Rohde, P. P.

K. R. Motes, A. Gilchrist, J. P. Dowling, and P. P. Rohde, “Scalable boson sampling with time-bin encoding using a loop-based architecture,” Phys. Rev. Lett. 113, 120501 (2014).
[Crossref]

P. P. Rohde and T. C. Ralph, “Error tolerance of the boson-sampling model for linear optics quantum computing,” Phys. Rev. A 85, 022332 (2012).
[Crossref]

Rudolph, T.

A. P. Lund, A. Laing, S. Rahimi-Keshari, T. Rudolph, J. L. O’Brien, and T. C. Ralph, “Boson sampling from a Gaussian state,” Phys. Rev. Lett. 113, 100502 (2014).
[Crossref]

J. Carolan, D. A. MeineckeJasmin, P. J. Shadbolt, N. J. Russell, N. Ismail, K. Wörhoff, T. Rudolph, M. G. Thompson, J. L. O’Brien, J. C. F. Matthews, and A. Laing, “On the experimental verification of quantum complexity in linear optics,” Nat. Photonics 8, 621–626 (2014).
[Crossref]

J. Carolan, J. Meinecke, P. Shadbolt, N. J. Russell, N. Ismail, K. Wörhoff, T. Rudolph, M. Thompson, J. L. O’Brien, J. Matthews, and A. Laing, “Verifying quantum complexity in linear optical experiments,” in Conference on Lasers and Electro-Optics (Optical Society of America, 2014), paper FM2A.7.

Russell, N. J.

J. Carolan, C. Harrold, C. Sparrow, E. Martín-López, N. J. Russell, J. W. Silverstone, P. J. Shadbolt, N. Matsuda, M. Oguma, M. Itoh, G. D. Marshall, M. G. Thompson, J. C. F. Matthews, T. Hashimoto, J. L. O’Brien, and A. Laing, “Universal linear optics,” Science 349, 711–716 (2015).
[Crossref]

J. Carolan, D. A. MeineckeJasmin, P. J. Shadbolt, N. J. Russell, N. Ismail, K. Wörhoff, T. Rudolph, M. G. Thompson, J. L. O’Brien, J. C. F. Matthews, and A. Laing, “On the experimental verification of quantum complexity in linear optics,” Nat. Photonics 8, 621–626 (2014).
[Crossref]

J. Carolan, J. Meinecke, P. Shadbolt, N. J. Russell, N. Ismail, K. Wörhoff, T. Rudolph, M. Thompson, J. L. O’Brien, J. Matthews, and A. Laing, “Verifying quantum complexity in linear optical experiments,” in Conference on Lasers and Electro-Optics (Optical Society of America, 2014), paper FM2A.7.

Schneider, C.

Y. He, Z.-E. Su, H.-L. Huang, X. Ding, J. Qin, C. Wang, S. Unsleber, C. Chen, H. Wang, Y.-M. He, X.-L. Wang, C. Schneider, M. Kamp, S. Höfling, C.-Y. Lu, and J.-W. Pan, “Scalable boson sampling with a single-photon device,” arXiv:1603.04127 [quant-ph] (2016).

Sciarrino, F.

A. Crespi, R. Osellame, R. Ramponi, M. Bentivegna, F. Flamini, N. Spagnolo, N. Viggianiello, L. Innocenti, P. Mataloni, and F. Sciarrino, “Suppression law of quantum states in a 3D photonic fast Fourier transform chip,” Nat. Commun. 7, 10469 (2016).
[Crossref]

M. Bentivegna, N. Spagnolo, C. Vitelli, F. Flamini, N. Viggianiello, L. Latmiral, P. Mataloni, D. J. Brod, E. F. Galvãoand, A. Crespi, R. Ramponi, R. Osellame, and F. Sciarrino, “Experimental scattershot boson sampling,” Sci. Adv. 1, e1400255 (2015).
[Crossref]

N. Spagnolo, C. Vitelli, M. Bentivegna, D. J. Brod, A. Crespi, F. Flamini, S. Giacomini, G. Milani, R. Ramponi, P. Mataloni, R. Osellame, E. F. Galvao, and F. Sciarrino, “Experimental validation of photonic boson sampling,” Nat. Photonics 8, 615–620 (2014).
[Crossref]

A. Crespi, R. Osellame, R. Ramponi, D. J. Brod, E. F. Galvao, N. Spagnolo, C. Vitelli, E. Maiorino, P. Mataloni, and F. Sciarrino, “Integrated multimode interferometers with arbitrary designs for photonic boson sampling,” Nat. Photonics 7, 545–549 (2013).
[Crossref]

Shadbolt, P.

J. Carolan, J. Meinecke, P. Shadbolt, N. J. Russell, N. Ismail, K. Wörhoff, T. Rudolph, M. Thompson, J. L. O’Brien, J. Matthews, and A. Laing, “Verifying quantum complexity in linear optical experiments,” in Conference on Lasers and Electro-Optics (Optical Society of America, 2014), paper FM2A.7.

Shadbolt, P. J.

J. Carolan, C. Harrold, C. Sparrow, E. Martín-López, N. J. Russell, J. W. Silverstone, P. J. Shadbolt, N. Matsuda, M. Oguma, M. Itoh, G. D. Marshall, M. G. Thompson, J. C. F. Matthews, T. Hashimoto, J. L. O’Brien, and A. Laing, “Universal linear optics,” Science 349, 711–716 (2015).
[Crossref]

J. Carolan, D. A. MeineckeJasmin, P. J. Shadbolt, N. J. Russell, N. Ismail, K. Wörhoff, T. Rudolph, M. G. Thompson, J. L. O’Brien, J. C. F. Matthews, and A. Laing, “On the experimental verification of quantum complexity in linear optics,” Nat. Photonics 8, 621–626 (2014).
[Crossref]

Shor, P. W.

P. W. Shor, “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,” SIAM Rev. 41, 303–332 (1999).
[Crossref]

P. W. Shor, “Algorithms for quantum computation: discrete logarithms and factoring,” in Proceedings of the 35th Annual Symposium on Foundations of Computer Science (IEEE, 1994), pp. 124–134.

Silverstone, J. W.

J. Carolan, C. Harrold, C. Sparrow, E. Martín-López, N. J. Russell, J. W. Silverstone, P. J. Shadbolt, N. Matsuda, M. Oguma, M. Itoh, G. D. Marshall, M. G. Thompson, J. C. F. Matthews, T. Hashimoto, J. L. O’Brien, and A. Laing, “Universal linear optics,” Science 349, 711–716 (2015).
[Crossref]

Sinclair, A.

M. Jerrum, A. Sinclair, and E. Vigoda, “A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries,” in Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing (STOC), New York, 2001, pp. 712–721.

Smith, B. J.

J. B. Spring, B. J. Metcalf, P. C. Humphreys, W. S. Kolthammer, X. M. Jin, M. Barbieri, A. Datta, N. Thomas-Peter, N. K. Langford, D. Kundys, J. C. Gates, B. J. Smith, P. G. R. Smith, and I. A. Walmsley, “Boson sampling on a photonic chip,” Science 339, 798–801 (2013).
[Crossref]

Smith, P. G. R.

J. B. Spring, B. J. Metcalf, P. C. Humphreys, W. S. Kolthammer, X. M. Jin, M. Barbieri, A. Datta, N. Thomas-Peter, N. K. Langford, D. Kundys, J. C. Gates, B. J. Smith, P. G. R. Smith, and I. A. Walmsley, “Boson sampling on a photonic chip,” Science 339, 798–801 (2013).
[Crossref]

Spagnolo, N.

A. Crespi, R. Osellame, R. Ramponi, M. Bentivegna, F. Flamini, N. Spagnolo, N. Viggianiello, L. Innocenti, P. Mataloni, and F. Sciarrino, “Suppression law of quantum states in a 3D photonic fast Fourier transform chip,” Nat. Commun. 7, 10469 (2016).
[Crossref]

M. Bentivegna, N. Spagnolo, C. Vitelli, F. Flamini, N. Viggianiello, L. Latmiral, P. Mataloni, D. J. Brod, E. F. Galvãoand, A. Crespi, R. Ramponi, R. Osellame, and F. Sciarrino, “Experimental scattershot boson sampling,” Sci. Adv. 1, e1400255 (2015).
[Crossref]

N. Spagnolo, C. Vitelli, M. Bentivegna, D. J. Brod, A. Crespi, F. Flamini, S. Giacomini, G. Milani, R. Ramponi, P. Mataloni, R. Osellame, E. F. Galvao, and F. Sciarrino, “Experimental validation of photonic boson sampling,” Nat. Photonics 8, 615–620 (2014).
[Crossref]

A. Crespi, R. Osellame, R. Ramponi, D. J. Brod, E. F. Galvao, N. Spagnolo, C. Vitelli, E. Maiorino, P. Mataloni, and F. Sciarrino, “Integrated multimode interferometers with arbitrary designs for photonic boson sampling,” Nat. Photonics 7, 545–549 (2013).
[Crossref]

Sparrow, C.

J. Carolan, C. Harrold, C. Sparrow, E. Martín-López, N. J. Russell, J. W. Silverstone, P. J. Shadbolt, N. Matsuda, M. Oguma, M. Itoh, G. D. Marshall, M. G. Thompson, J. C. F. Matthews, T. Hashimoto, J. L. O’Brien, and A. Laing, “Universal linear optics,” Science 349, 711–716 (2015).
[Crossref]

Spring, J. B.

J. B. Spring, B. J. Metcalf, P. C. Humphreys, W. S. Kolthammer, X. M. Jin, M. Barbieri, A. Datta, N. Thomas-Peter, N. K. Langford, D. Kundys, J. C. Gates, B. J. Smith, P. G. R. Smith, and I. A. Walmsley, “Boson sampling on a photonic chip,” Science 339, 798–801 (2013).
[Crossref]

Su, Z.-E.

Y. He, Z.-E. Su, H.-L. Huang, X. Ding, J. Qin, C. Wang, S. Unsleber, C. Chen, H. Wang, Y.-M. He, X.-L. Wang, C. Schneider, M. Kamp, S. Höfling, C.-Y. Lu, and J.-W. Pan, “Scalable boson sampling with a single-photon device,” arXiv:1603.04127 [quant-ph] (2016).

Szameit, A.

M. Tillmann, B. Dakic, R. Heilmann, S. Nolte, A. Szameit, and P. Walther, “Experimental boson sampling,” Nat. Photonics 7, 540–544 (2013).
[Crossref]

Thomas-Peter, N.

J. B. Spring, B. J. Metcalf, P. C. Humphreys, W. S. Kolthammer, X. M. Jin, M. Barbieri, A. Datta, N. Thomas-Peter, N. K. Langford, D. Kundys, J. C. Gates, B. J. Smith, P. G. R. Smith, and I. A. Walmsley, “Boson sampling on a photonic chip,” Science 339, 798–801 (2013).
[Crossref]

Thompson, M.

J. Carolan, J. Meinecke, P. Shadbolt, N. J. Russell, N. Ismail, K. Wörhoff, T. Rudolph, M. Thompson, J. L. O’Brien, J. Matthews, and A. Laing, “Verifying quantum complexity in linear optical experiments,” in Conference on Lasers and Electro-Optics (Optical Society of America, 2014), paper FM2A.7.

Thompson, M. G.

J. Carolan, C. Harrold, C. Sparrow, E. Martín-López, N. J. Russell, J. W. Silverstone, P. J. Shadbolt, N. Matsuda, M. Oguma, M. Itoh, G. D. Marshall, M. G. Thompson, J. C. F. Matthews, T. Hashimoto, J. L. O’Brien, and A. Laing, “Universal linear optics,” Science 349, 711–716 (2015).
[Crossref]

J. Carolan, D. A. MeineckeJasmin, P. J. Shadbolt, N. J. Russell, N. Ismail, K. Wörhoff, T. Rudolph, M. G. Thompson, J. L. O’Brien, J. C. F. Matthews, and A. Laing, “On the experimental verification of quantum complexity in linear optics,” Nat. Photonics 8, 621–626 (2014).
[Crossref]

Tichy, M. C.

M. C. Tichy, K. Mayer, A. Buchleitner, and K. Mølmer, “Stringent and efficient assessment of boson-sampling devices,” Phys. Rev. Lett. 113, 020502 (2014).
[Crossref]

M. C. Tichy, H. T. Lim, Y. S. Ra, F. Mintert, Y. H. Kim, and A. Buchleitner, “Four-photon indistinguishability transition,” Phys. Rev. A 83, 062111 (2011).
[Crossref]

Tillmann, M.

M. Tillmann, B. Dakic, R. Heilmann, S. Nolte, A. Szameit, and P. Walther, “Experimental boson sampling,” Nat. Photonics 7, 540–544 (2013).
[Crossref]

Unsleber, S.

Y. He, Z.-E. Su, H.-L. Huang, X. Ding, J. Qin, C. Wang, S. Unsleber, C. Chen, H. Wang, Y.-M. He, X.-L. Wang, C. Schneider, M. Kamp, S. Höfling, C.-Y. Lu, and J.-W. Pan, “Scalable boson sampling with a single-photon device,” arXiv:1603.04127 [quant-ph] (2016).

Viggianiello, N.

A. Crespi, R. Osellame, R. Ramponi, M. Bentivegna, F. Flamini, N. Spagnolo, N. Viggianiello, L. Innocenti, P. Mataloni, and F. Sciarrino, “Suppression law of quantum states in a 3D photonic fast Fourier transform chip,” Nat. Commun. 7, 10469 (2016).
[Crossref]

M. Bentivegna, N. Spagnolo, C. Vitelli, F. Flamini, N. Viggianiello, L. Latmiral, P. Mataloni, D. J. Brod, E. F. Galvãoand, A. Crespi, R. Ramponi, R. Osellame, and F. Sciarrino, “Experimental scattershot boson sampling,” Sci. Adv. 1, e1400255 (2015).
[Crossref]

Vigoda, E.

M. Jerrum, A. Sinclair, and E. Vigoda, “A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries,” in Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing (STOC), New York, 2001, pp. 712–721.

Vitelli, C.

M. Bentivegna, N. Spagnolo, C. Vitelli, F. Flamini, N. Viggianiello, L. Latmiral, P. Mataloni, D. J. Brod, E. F. Galvãoand, A. Crespi, R. Ramponi, R. Osellame, and F. Sciarrino, “Experimental scattershot boson sampling,” Sci. Adv. 1, e1400255 (2015).
[Crossref]

N. Spagnolo, C. Vitelli, M. Bentivegna, D. J. Brod, A. Crespi, F. Flamini, S. Giacomini, G. Milani, R. Ramponi, P. Mataloni, R. Osellame, E. F. Galvao, and F. Sciarrino, “Experimental validation of photonic boson sampling,” Nat. Photonics 8, 615–620 (2014).
[Crossref]

A. Crespi, R. Osellame, R. Ramponi, D. J. Brod, E. F. Galvao, N. Spagnolo, C. Vitelli, E. Maiorino, P. Mataloni, and F. Sciarrino, “Integrated multimode interferometers with arbitrary designs for photonic boson sampling,” Nat. Photonics 7, 545–549 (2013).
[Crossref]

Walmsley, I. A.

J. B. Spring, B. J. Metcalf, P. C. Humphreys, W. S. Kolthammer, X. M. Jin, M. Barbieri, A. Datta, N. Thomas-Peter, N. K. Langford, D. Kundys, J. C. Gates, B. J. Smith, P. G. R. Smith, and I. A. Walmsley, “Boson sampling on a photonic chip,” Science 339, 798–801 (2013).
[Crossref]

Walther, P.

M. Tillmann, B. Dakic, R. Heilmann, S. Nolte, A. Szameit, and P. Walther, “Experimental boson sampling,” Nat. Photonics 7, 540–544 (2013).
[Crossref]

Wang, C.

Y. He, Z.-E. Su, H.-L. Huang, X. Ding, J. Qin, C. Wang, S. Unsleber, C. Chen, H. Wang, Y.-M. He, X.-L. Wang, C. Schneider, M. Kamp, S. Höfling, C.-Y. Lu, and J.-W. Pan, “Scalable boson sampling with a single-photon device,” arXiv:1603.04127 [quant-ph] (2016).

Wang, H.

Y. He, Z.-E. Su, H.-L. Huang, X. Ding, J. Qin, C. Wang, S. Unsleber, C. Chen, H. Wang, Y.-M. He, X.-L. Wang, C. Schneider, M. Kamp, S. Höfling, C.-Y. Lu, and J.-W. Pan, “Scalable boson sampling with a single-photon device,” arXiv:1603.04127 [quant-ph] (2016).

Wang, X.-L.

Y. He, Z.-E. Su, H.-L. Huang, X. Ding, J. Qin, C. Wang, S. Unsleber, C. Chen, H. Wang, Y.-M. He, X.-L. Wang, C. Schneider, M. Kamp, S. Höfling, C.-Y. Lu, and J.-W. Pan, “Scalable boson sampling with a single-photon device,” arXiv:1603.04127 [quant-ph] (2016).

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]

Wörhoff, K.

J. Carolan, D. A. MeineckeJasmin, P. J. Shadbolt, N. J. Russell, N. Ismail, K. Wörhoff, T. Rudolph, M. G. Thompson, J. L. O’Brien, J. C. F. Matthews, and A. Laing, “On the experimental verification of quantum complexity in linear optics,” Nat. Photonics 8, 621–626 (2014).
[Crossref]

J. Carolan, J. Meinecke, P. Shadbolt, N. J. Russell, N. Ismail, K. Wörhoff, T. Rudolph, M. Thompson, J. L. O’Brien, J. Matthews, and A. Laing, “Verifying quantum complexity in linear optical experiments,” in Conference on Lasers and Electro-Optics (Optical Society of America, 2014), paper FM2A.7.

Zhou, X. Q.

E. Martin-Lopez, A. Laing, T. Lawson, R. Alvarez, X. Q. Zhou, and J. L. O’Brien, “Experimental realization of Shor’s quantum factoring algorithm using qubit recycling,” Nat. Photonics 6, 773–776 (2012).
[Crossref]

Nat. Commun. (1)

A. Crespi, R. Osellame, R. Ramponi, M. Bentivegna, F. Flamini, N. Spagnolo, N. Viggianiello, L. Innocenti, P. Mataloni, and F. Sciarrino, “Suppression law of quantum states in a 3D photonic fast Fourier transform chip,” Nat. Commun. 7, 10469 (2016).
[Crossref]

Nat. Photonics (5)

N. Spagnolo, C. Vitelli, M. Bentivegna, D. J. Brod, A. Crespi, F. Flamini, S. Giacomini, G. Milani, R. Ramponi, P. Mataloni, R. Osellame, E. F. Galvao, and F. Sciarrino, “Experimental validation of photonic boson sampling,” Nat. Photonics 8, 615–620 (2014).
[Crossref]

J. Carolan, D. A. MeineckeJasmin, P. J. Shadbolt, N. J. Russell, N. Ismail, K. Wörhoff, T. Rudolph, M. G. Thompson, J. L. O’Brien, J. C. F. Matthews, and A. Laing, “On the experimental verification of quantum complexity in linear optics,” Nat. Photonics 8, 621–626 (2014).
[Crossref]

E. Martin-Lopez, A. Laing, T. Lawson, R. Alvarez, X. Q. Zhou, and J. L. O’Brien, “Experimental realization of Shor’s quantum factoring algorithm using qubit recycling,” Nat. Photonics 6, 773–776 (2012).
[Crossref]

M. Tillmann, B. Dakic, R. Heilmann, S. Nolte, A. Szameit, and P. Walther, “Experimental boson sampling,” Nat. Photonics 7, 540–544 (2013).
[Crossref]

A. Crespi, R. Osellame, R. Ramponi, D. J. Brod, E. F. Galvao, N. Spagnolo, C. Vitelli, E. Maiorino, P. Mataloni, and F. Sciarrino, “Integrated multimode interferometers with arbitrary designs for photonic boson sampling,” Nat. Photonics 7, 545–549 (2013).
[Crossref]

Phys. Rev. A (2)

P. P. Rohde and T. C. Ralph, “Error tolerance of the boson-sampling model for linear optics quantum computing,” Phys. Rev. A 85, 022332 (2012).
[Crossref]

M. C. Tichy, H. T. Lim, Y. S. Ra, F. Mintert, Y. H. Kim, and A. Buchleitner, “Four-photon indistinguishability transition,” Phys. Rev. A 83, 062111 (2011).
[Crossref]

Phys. Rev. Lett. (3)

M. C. Tichy, K. Mayer, A. Buchleitner, and K. Mølmer, “Stringent and efficient assessment of boson-sampling devices,” Phys. Rev. Lett. 113, 020502 (2014).
[Crossref]

A. P. Lund, A. Laing, S. Rahimi-Keshari, T. Rudolph, J. L. O’Brien, and T. C. Ralph, “Boson sampling from a Gaussian state,” Phys. Rev. Lett. 113, 100502 (2014).
[Crossref]

K. R. Motes, A. Gilchrist, J. P. Dowling, and P. P. Rohde, “Scalable boson sampling with time-bin encoding using a loop-based architecture,” Phys. Rev. Lett. 113, 120501 (2014).
[Crossref]

Quantum Inf. Comput. (1)

S. Aaronson and A. Arkhipov, “BosonSampling is far from uniform,” Quantum Inf. Comput. 14, 1383–1423 (2013).

Sci. Adv. (1)

M. Bentivegna, N. Spagnolo, C. Vitelli, F. Flamini, N. Viggianiello, L. Latmiral, P. Mataloni, D. J. Brod, E. F. Galvãoand, A. Crespi, R. Ramponi, R. Osellame, and F. Sciarrino, “Experimental scattershot boson sampling,” Sci. Adv. 1, e1400255 (2015).
[Crossref]

Science (3)

J. Carolan, C. Harrold, C. Sparrow, E. Martín-López, N. J. Russell, J. W. Silverstone, P. J. Shadbolt, N. Matsuda, M. Oguma, M. Itoh, G. D. Marshall, M. G. Thompson, J. C. F. Matthews, T. Hashimoto, J. L. O’Brien, and A. Laing, “Universal linear optics,” Science 349, 711–716 (2015).
[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]

J. B. Spring, B. J. Metcalf, P. C. Humphreys, W. S. Kolthammer, X. M. Jin, M. Barbieri, A. Datta, N. Thomas-Peter, N. K. Langford, D. Kundys, J. C. Gates, B. J. Smith, P. G. R. Smith, and I. A. Walmsley, “Boson sampling on a photonic chip,” Science 339, 798–801 (2013).
[Crossref]

SIAM Rev. (1)

P. W. Shor, “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,” SIAM Rev. 41, 303–332 (1999).
[Crossref]

Other (7)

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

S. Aaronson and A. Arkhipov, “The computational complexity of linear optics,” in Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing (STOC), New York, 2011, pp. 333–342.

C. Gogolin, M. Kliesch, L. Aolita, and J. Eisert, “Boson-sampling in the light of sample complexity,” arXiv:1306.3995v2 (2013).

P. W. Shor, “Algorithms for quantum computation: discrete logarithms and factoring,” in Proceedings of the 35th Annual Symposium on Foundations of Computer Science (IEEE, 1994), pp. 124–134.

Y. He, Z.-E. Su, H.-L. Huang, X. Ding, J. Qin, C. Wang, S. Unsleber, C. Chen, H. Wang, Y.-M. He, X.-L. Wang, C. Schneider, M. Kamp, S. Höfling, C.-Y. Lu, and J.-W. Pan, “Scalable boson sampling with a single-photon device,” arXiv:1603.04127 [quant-ph] (2016).

J. Carolan, J. Meinecke, P. Shadbolt, N. J. Russell, N. Ismail, K. Wörhoff, T. Rudolph, M. Thompson, J. L. O’Brien, J. Matthews, and A. Laing, “Verifying quantum complexity in linear optical experiments,” in Conference on Lasers and Electro-Optics (Optical Society of America, 2014), paper FM2A.7.

M. Jerrum, A. Sinclair, and E. Vigoda, “A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries,” in Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing (STOC), New York, 2001, pp. 712–721.

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 (4)

Fig. 1.
Fig. 1. Simulation of boson sampling, mean-field sampling, coherent-state sampling, and classical sampling for (a) two photons with input state S=(0,1,1,0), and (b) three photons with input state S=(0,1,1,1,0). Both cases run over 100 Harr-random matrices and are sampled 100 times for each matrix.
Fig. 2.
Fig. 2. Simulation of boson sampling and mean-field sampling with the test state ST=(1,1,1,1). Each panel represents a different choice of a Harr-random unitary matrix. For each choice of unitary matrix, 10,000 samples are taken. For this quantity of samples, the maximum standard deviation of the number of samples is 50. There are cases in each panel for which the number of events sampled deviate between the two cases by 5 to 10 standard deviations.
Fig. 3.
Fig. 3. Simulation of boson sampling and mean-field sampling with the input state S=(0,1,1,0). We chose four random matrices by the Harr measure and sampled them 10,000 times for each matrix. The same expected variation as in Fig. 2 applies to these data.
Fig. 4.
Fig. 4. Simulation of boson sampling, classical sampling, partially distinguishable boson sampling, and mean-field sampling with the input state S=(1,1,1). Four randomly chosen matrices are displayed, with 10,000 samples for each case. We chose the coefficients for the Fock basis state in Eq. (16) to be identical, i.e., 16, as there are 6 Fock basis states in this example. In terms of two-photon interference, this is equivalent to having a 50% probability of finding that the input particles were indistinguishable.

Equations (16)

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

SB=|s1,s2,,sN=j=1N(a^j)sjsj!|0=(a1)s1(a2)s2(aN)sNs1!s2!sN!|0,
S^a^jS^=k=1NΛk,ja^k,
PB(TB;SB,Λ)=|Permanent(A)|2i=1Nsi!ti!,
PD(TD;SD,Λ)=Permanent(Ω)i=1Nsi!ti!,
|ψ=1np=1neiθpa^jp|0,
S^|ψ=1np=1neiθpS^a^jpS^|0=1nk=1Np=1neiθpΛk,jpa^jp|0.
pk=1n|p=1neiθpΛk,jp|2.
PMf(TMf;SMf,Λ)=(nt1)(nt1t2)(tNtN)p1t1p2t2pNtN=n!nnl=1Ntl!k=1N|p=1neiθpΛk,jp|2tk=n!nnl=1Ntl!q=1n|p=1neiθpΛkq,jp|2.
P˜Mf(TMf;SMf,Λ)=02πdθ12π02πdθn2πPMf(TMf;SMf,Λ)=n!nnl=1Ntl!q=1np=1n|Λkq,jp|2.
S^SCs=exp(12j=1N|αj|2)exp(k=1Nj=1NeiχjαjΛk,ja^k)|0.
S^SCs=k=1Nexp(12|j=1NeiχjαjΛk,j|2)exp(j=1NeiχjαjΛk,ja^k)|0=k=1Nexp(12|j=1NeiχjαjΛk,j|2)nk=0(j=1NeiχjαjΛk,j)nknk!|nk.
PCs(TCs;SCs,Λ)=exp(k=1N|j=1NeiχjαjΛk,j|2)k=1N|j=1NeiχjαjΛk,j|2tktk!.
P˜Cs(TCs;SCs,Λ)=exp(k,j=1N|αjΛk,j|2)k=1N(j=1N|αjΛk,j|2)tktk!.
P˜Mf(TMf;ST,Λ)=n!nnk=1Ntk!.
a^jr=k=1jrCr,ka^jr,tk,
|SB=a^j1,t1k2=12k3=13kn=1nr=2nCr,kra^jr,tkr|0.

Metrics