Quantum sampling problems, BosonSampling and quantum supremacy
10.1038/s41534-017-0018-2
Crossref journal-article
Springer Science and Business Media LLC
npj Quantum Information (297)
Abstract

AbstractThere is a large body of evidence for the potential of greater computational power using information carriers that are quantum mechanical over those governed by the laws of classical mechanics. But the question of the exact nature of the power contributed by quantum mechanics remains only partially answered. Furthermore, there exists doubt over the practicality of achieving a large enough quantum computation that definitively demonstrates quantum supremacy. Recently the study of computational problems that produce samples from probability distributions has added to both our understanding of the power of quantum algorithms and lowered the requirements for demonstration of fast quantum algorithms. The proposed quantum sampling problems do not require a quantum computer capable of universal operations and also permit physically realistic errors in their operation. This is an encouraging step towards an experimental demonstration of quantum algorithmic supremacy. In this paper, we will review sampling problems and the arguments that have been used to deduce when sampling problems are hard for classical computers to simulate. Two classes of quantum sampling problems that demonstrate the supremacy of quantum algorithms are BosonSampling and Instantaneous Quantum Polynomial-time Sampling. We will present the details of these classes and recent experimental progress towards demonstrating quantum supremacy in BosonSampling.

Bibliography

Lund, A. P., Bremner, M. J., & Ralph, T. C. (2017). Quantum sampling problems, BosonSampling and quantum supremacy. Npj Quantum Information, 3(1).

Authors 3
  1. A. P. Lund (first)
  2. Michael J. Bremner (additional)
  3. T. C. Ralph (additional)
References 60 Referenced 137
  1. Preskill, J. Quantum computing and the entanglement frontier. Preprint at arXiv:1203.5813 (2012).
  2. Terhal, B. M. & DiVincenzo, D. P. Quantum information and computation. 4, 134–145. Preprint at arXiv:quant-ph/0205133 (2004). (10.26421/QIC4.2-5)
  3. Papadimitriou C. Computational Complexity, (AddisonWesley, 1994).
  4. Bremner, M. J., Jozsa, R. & Shepherd, D. J. Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy. Proc. R. Soc. A 467, 459–472. Preprint at arXiv:1005.1407 (2011). (10.1098/rspa.2010.0301)
  5. Aaronson, S., Arkhipov, A. The Computational Complexity of Linear Optics. Theory Comput. 4, 143–252. Preprint at arXiv:1011.3245 (2013). (10.4086/toc.2013.v009a004)
  6. Tillmann, M. et al. Experimental boson sampling. Nat. Photon. 7, 540–544 (2013). (10.1038/nphoton.2013.102) / Nat. Photon. by M Tillmann (2013)
  7. Spring, J. B. et al. Boson sampling on a photonic chip. Science 339, 798–801 (2013). (10.1126/science.1231692) / Science by JB Spring (2013)
  8. Crespi, A. et al. Integrated multimode interferometers with arbitrary designs for photonic boson sampling. Nat. Photon. 7, 545–549 (2013). (10.1038/nphoton.2013.112) / Nat. Photon. by A Crespi (2013)
  9. Barz, S., Fitzsimons, J. F., Kashefi, E. & Walther, P. Experimental verification of quantum computation. Nat. Phys. 9, 727–731 (2013). (10.1038/nphys2763) / Nat. Phys. by S Barz (2013)
  10. Broome, M. A. et al. Photonic boson sampling in a tunable circuit. Science 339, 794–798 (2013). (10.1126/science.1231440) / Science by MA Broome (2013)
  11. Spagnolo, N. et al. Efficient experimental validation of photonic boson sampling against the uniform distribution. Nat. Photon. 8, 615 (2014). (10.1038/nphoton.2014.135) / Nat. Photon. by N Spagnolo (2014)
  12. Bremner, M. J., Montanaro, A. & Shepherd, D. J. Average-Case Complexity Versus Approximate Simulation of Commuting Quantum Computations. Phys. Rev. Lett. 117, 080501. Preprint at arXiv:1504.07999 (2016). (10.1103/PhysRevLett.117.080501)
  13. Boixo, S. et al. Characterizing quantum supremacy in near-term devices. Preprint at arXiv:1608.00263 (2016).
  14. Aaronson, S. & Chen, L. Complexity-theoretic foundations of quantum supremacy experiments. Preprint at arXiv:1612.05903 (2016).
  15. Montanaro, A. Quantum algorithms: an overview. npj Quantum Inf. 2, 15023. Preprint at arXiv:1511.04206 (2016). (10.1038/npjqi.2015.23)
  16. Shor, P. W. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM J. Comput. 26, 1484–1509. Preprint at arXiv:quant-ph/9508027v2 (1997). (10.1137/S0097539795293172)
  17. Stockmeyer, L. J. The polynomial-time hierarchy. Theor. Comput. Sci. 3, 1–22 (1976). (10.1016/0304-3975(76)90061-X)
  18. Fortnow, L. & Rogersr, J. Thirteenth Annual IEEE Conference on Computational Complexity Preprint at arXiv:cs/9811023.(1998)
  19. Fenner, S., Green, F., Homer, S. & Pruim, R. Determining acceptance possibility for a quantum computation is hard for the polynomial hierarchy. Proc. R. Soc. A 455, 3953–3966 (1999). Preprint at arXiv:quant-ph/9812056. (10.1098/rspa.1999.0485) / Proc. R. Soc. A by S Fenner (1999)
  20. Toda, S. PP is as Hard as the Polynomial-Time Hierarchy. SIAM J. Comput. 20, 865–877 (1991). (10.1137/0220053)
  21. Stockmeyer, L. J. The complexity of approximate counting. Proc. ACM STOC. 83, 118–126 (1983). (10.1145/800061.808740)
  22. Morimae, T., Fujii, K. & Fitzsimons, J. Hardness of Classically Simulating the One-Clean-Qubit Model. Phys. Rev. Lett. 112, 130502. Preprint at arXiv:1312.2496. (2014). (10.1103/PhysRevLett.112.130502)
  23. Jozsa, R. & Van den Nest, M. Classical simulation complexity of extended Clifford circuits. Quantum Inf. Comput. 14, 633-648 (2014). Preprint at arXiv:1305.6190. (10.26421/QIC14.7-8-7)
  24. Bouland, A, Mančinska, L, & Zhang, X. Complexity classification of two-qubit commuting hamiltonians. Preprint at arXiv:1602.04145 (2016).
  25. Reck, M., Zeilinger, A., Bernstein, H. J. & Bertani, P. Experimental realization of any discrete unitary operator. Phys. Rev. Lett. 73, 58 (1994). (10.1103/PhysRevLett.73.58)
  26. Valiant, L. G. The complexity of computing the permanent. Theor. Comput. Sci. 8:189–201, (1979). (10.1016/0304-3975(79)90044-6)
  27. Rohde, P. P. & Ralph, T. C. Error tolerance of the boson-sampling model for linear optics quantum computing. Phys. Rev. A 85, 022332 (2012). (10.1103/PhysRevA.85.022332)
  28. Aaronson, S. & Brod, D. J. BosonSampling with lost photons. Phys. Rev. A 93, 012335 (2016). (10.1103/PhysRevA.93.012335)
  29. Leverrier, A. & Garcia-Patron, R. Analysis of circuit imperfections in bosonsampling. Quantum Inf. Comput. 15, 489–512 (2015). (10.26421/QIC15.5-6-8)
  30. Arkhipov, A. BosonSampling is robust against small errors in the network matrix. Phys. Rev. A 92, 062326 (2015). (10.1103/PhysRevA.92.062326)
  31. Rahimi-Keshari, S., Ralph, T. C. & Caves, C. M. Sufficient Conditions for Efficient Classical Simulation of Quantum Optics. Phys. Rev. X 6, 021039 (2016). (10.1103/PhysRevX.6.021039)
  32. Aaronson, S. & Arkhipov, A. Bosonsampling is far from uniform. Quantum Inf. Comput. 14, 1383–1423 (2014). No. 15-16. / Quantum Inf. Comput. by S Aaronson (2014)
  33. Carolan, J. et al. On the experimental verification of quantum complexity in linear optics. Nat. Photon. 8, 621–626 (2014). (10.1038/nphoton.2014.152) / Nat. Photon. by J Carolan (2014)
  34. Crespi, A. et al. Suppression law of quantum states in a 3D photonic fast Fourier transform chip. Nat. Commun. 7, 10469 (2016). (10.1038/ncomms10469)
  35. Lund, A. P. et al. Boson Sampling from a Gaussian state. Phys. Rev. Lett. 113, 100502 (2014). (10.1103/PhysRevLett.113.100502) / Phys. Rev. Lett. by AP Lund (2014)
  36. Bentivegna, M., et al. Experimental scattershot boson sampling. Sci. Adv. 1(3), e1400255 (2015). (10.1126/sciadv.1400255)
  37. Latmiral, L., Spagnolo, N. & Sciarrino, F. Towards quantum supremacy with lossy scattershot boson sampling. New. J. Phys. 18, 113008 (2016). (10.1088/1367-2630/18/11/113008)
  38. Carolan, J. et al. Universal linear optics. Science 349, 711 (2015). (10.1126/science.aab3642) / Science by J Carolan (2015)
  39. Motes, K. R., Gilchrist, A., Dowling, J. P. & Rohde, P. P. Scalable Boson Sampling with Time-Bin Encoding Using a Loop-Based Architecture. Phys. Rev. Lett. 113, 120501 (2014). (10.1103/PhysRevLett.113.120501)
  40. Yu, H. et al. Scalable boson sampling with a single-photon device. Preprint at arXiv:1603.04127 (2016)
  41. Loredo, J. C. et al. BosonSampling with single-photon Fock states from a bright solid-state source. Preprint at arXiv:1603.00054 (2016). (10.1103/PhysRevLett.118.130503)
  42. Laibacher, S. & Tamma, V. From the Physics to the Computational Complexity of Multiboson Correlation Interference. Phys. Rev. Lett. 115, 243605 (2015). (10.1103/PhysRevLett.115.243605)
  43. Tamma, V. & Laibacher, S. Multi-boson correlation sampling. Quantum Inf. Process. 15, 1241–1262 (2016). (10.1007/s11128-015-1177-8)
  44. Barkhofen, S. et al. Driven Boson Sampling. Phys. Rev. Lett. 118, 020502 (2017). (10.1103/PhysRevLett.118.020502)
  45. Fefferman, B. & Umans, C. The power of quantum fourier sampling. Preprint at arXiv:1507.05592 (2015).
  46. Shepherd, D. & Bremner, M. J. Temporally unstructured quantum computation. Proc. R. Soc. A 465, 1413–1439. Preprint at arXiv:0809.0847 (2009). (10.1098/rspa.2008.0443)
  47. Fujii, K. & Morimae, T. Quantum commuting circuits and complexity of Ising partition functions. Preprint at arXiv:1311.2128 (2013).
  48. Goldberg, L. A. & Guo, H. The complexity of approximating complex-valued Ising and Tutte partition functions. Preprint at arXiv:1409.5627 (2014).
  49. Bremner, M. J., Montanaro, A., & Shepherd, D. J. Achieving quantum supremacy with sparse and noisy commuting quantum computations. Preprint at arXiv:1610.01808 (2016) (10.22331/q-2017-04-25-8)
  50. Xun, G., Wang, S.-T. & Duan, L.-M. Quantum supremacy for simulating A translation-invariant ising spin model. Phys. Rev. Lett. 118, 040502 (2017). (10.1103/PhysRevLett.118.040502) / Phys. Rev. Lett. by G Xun (2017)
  51. Douce, T. et al. Continuous-Variable Instantaneous Quantum Computing is Hard to Sample. Phys. Rev. Lett. 118, 070503 (2017). (10.1103/PhysRevLett.118.070503)
  52. Fujii, K. & Tamate, S. Computational quantum-classical boundary of noisy commuting quantum circuits. Scientific Reports. 6, 25598. Preprint at arXiv:1406.6932 (2016). (10.1038/srep25598)
  53. Tichy, M. C., Mayer, K., Buchleitner, A. & Mølmer, K. Stringent and Efficient Assessment of Boson-Sampling Devices. Phys. Rev. Lett. 113, 020502 (2014). (10.1103/PhysRevLett.113.020502)
  54. Walschaers, M. et al. Statistical benchmark for BosonSampling. New J. Phys. 18, 032001 (2016). (10.1088/1367-2630/18/3/032001)
  55. Hangleiter, D., Kliesch, M., Schwarz, M., Eisert, J. Direct certification of a class of quantum simulations. Quantum Sci. Technol. 2, 015004 (2017). (10.1088/2058-9565/2/1/015004)
  56. Aolita, L., Gogolin, C., Kliesch, M. & Eisert, J. Reliable quantum certification of photonic state preparations. Nat. Commun. 6, 8498 (2015). (10.1038/ncomms9498)
  57. Farhi, E. & Harrow, A. Quantum supremacy through the quantum approximate optimization algorithm. Preprint at arXiv:1602.07674.(2016).
  58. Huh, J. et al. Boson sampling for molecular vibronic spectra. Nat. Photon. 9, 615 (2015). (10.1038/nphoton.2015.153)
  59. Motes, K. R. et al. Linear Optical Quantum Metrology with Single Photons: Exploiting Spontaneously Generated Entanglement to Beat the Shot-Noise Limit. Phys. Rev. Lett. 114, 170802 (2015). (10.1103/PhysRevLett.114.170802)
  60. Nikolopoulos, G. M. & Brougham, T. Decision and function problems based on boson sampling. Phys. Rev. A 94, 012315 (2016). (10.1103/PhysRevA.94.012315)
Dates
Type When
Created 8 years, 4 months ago (April 5, 2017, 5:46 a.m.)
Deposited 2 years, 8 months ago (Dec. 22, 2022, 8:43 p.m.)
Indexed 5 days, 9 hours ago (Aug. 21, 2025, 1:38 p.m.)
Issued 8 years, 4 months ago (April 13, 2017)
Published 8 years, 4 months ago (April 13, 2017)
Published Online 8 years, 4 months ago (April 13, 2017)
Funders 0

None

@article{Lund_2017, title={Quantum sampling problems, BosonSampling and quantum supremacy}, volume={3}, ISSN={2056-6387}, url={http://dx.doi.org/10.1038/s41534-017-0018-2}, DOI={10.1038/s41534-017-0018-2}, number={1}, journal={npj Quantum Information}, publisher={Springer Science and Business Media LLC}, author={Lund, A. P. and Bremner, Michael J. and Ralph, T. C.}, year={2017}, month=apr }