BosonSampling with lost photons
BosonSampling is an intermediate model of quantum computation where linear-optical networks are used to solve sampling problems expected to be hard for classical computers. Since these devices are not expected to be universal for quantum computation, it remains an open question of whether any error-...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
American Physical Society
2016
|
| Online Access: | http://hdl.handle.net/1721.1/100976 https://orcid.org/0000-0003-1333-4045 |
| _version_ | 1811088453661622272 |
|---|---|
| author | Aaronson, Scott Brod, Daniel J. |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Aaronson, Scott Brod, Daniel J. |
| author_sort | Aaronson, Scott |
| collection | MIT |
| description | BosonSampling is an intermediate model of quantum computation where linear-optical networks are used to solve sampling problems expected to be hard for classical computers. Since these devices are not expected to be universal for quantum computation, it remains an open question of whether any error-correction techniques can be applied to them, and thus it is important to investigate how robust the model is under natural experimental imperfections, such as losses and imperfect control of parameters. Here, we investigate the complexity of BosonSampling under photon losses, more specifically, the case where an unknown subset of the photons is randomly lost at the sources. We show that if k out of n photons are lost, then we cannot sample classically from a distribution that is 1/n[superscript Θ(k)] close (in total variation distance) to the ideal distribution, unless a BPP[superscript NP] machine can estimate the permanents of Gaussian matrices in n[superscript O(k)] time. In particular, if k is constant, this implies that simulating lossy BosonSampling is hard for a classical computer, under exactly the same complexity assumption used for the original lossless case. |
| first_indexed | 2024-09-23T14:02:07Z |
| format | Article |
| id | mit-1721.1/100976 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T14:02:07Z |
| publishDate | 2016 |
| publisher | American Physical Society |
| record_format | dspace |
| spelling | mit-1721.1/1009762022-10-01T18:45:11Z BosonSampling with lost photons Aaronson, Scott Brod, Daniel J. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Aaronson, Scott BosonSampling is an intermediate model of quantum computation where linear-optical networks are used to solve sampling problems expected to be hard for classical computers. Since these devices are not expected to be universal for quantum computation, it remains an open question of whether any error-correction techniques can be applied to them, and thus it is important to investigate how robust the model is under natural experimental imperfections, such as losses and imperfect control of parameters. Here, we investigate the complexity of BosonSampling under photon losses, more specifically, the case where an unknown subset of the photons is randomly lost at the sources. We show that if k out of n photons are lost, then we cannot sample classically from a distribution that is 1/n[superscript Θ(k)] close (in total variation distance) to the ideal distribution, unless a BPP[superscript NP] machine can estimate the permanents of Gaussian matrices in n[superscript O(k)] time. In particular, if k is constant, this implies that simulating lossy BosonSampling is hard for a classical computer, under exactly the same complexity assumption used for the original lossless case. National Science Foundation (U.S.) (Alan T. Waterman Award Grant 1249349) 2016-01-25T16:21:08Z 2016-01-25T16:21:08Z 2016-01 2015-11 2016-01-21T23:00:05Z Article http://purl.org/eprint/type/JournalArticle 1050-2947 1094-1622 http://hdl.handle.net/1721.1/100976 Aaronson, Scott, and Daniel J. Brod. "BosonSampling with lost photons." Phys. Rev. A 93, 012335 (January 2016). © 2016 American Physical Society https://orcid.org/0000-0003-1333-4045 en http://dx.doi.org/10.1103/PhysRevA.93.012335 Physical Review A Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. American Physical Society application/pdf American Physical Society American Physical Society |
| spellingShingle | Aaronson, Scott Brod, Daniel J. BosonSampling with lost photons |
| title | BosonSampling with lost photons |
| title_full | BosonSampling with lost photons |
| title_fullStr | BosonSampling with lost photons |
| title_full_unstemmed | BosonSampling with lost photons |
| title_short | BosonSampling with lost photons |
| title_sort | bosonsampling with lost photons |
| url | http://hdl.handle.net/1721.1/100976 https://orcid.org/0000-0003-1333-4045 |
| work_keys_str_mv | AT aaronsonscott bosonsamplingwithlostphotons AT broddanielj bosonsamplingwithlostphotons |