Complexity-theoretic foundations of BosonSampling with a linear number of modes
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913745291182080 |
|---|---|
| author | Bouland, Adam Brod, Daniel Datta, Ishaun Fefferman, Bill Grier, Daniel Hernandez, Felipe Oszmaniec, Michal |
| author_facet | Bouland, Adam Brod, Daniel Datta, Ishaun Fefferman, Bill Grier, Daniel Hernandez, Felipe Oszmaniec, Michal |
| contents | BosonSampling is the leading candidate for demonstrating quantum computational advantage in photonic systems. While we have recently seen many impressive experimental demonstrations, there is still a formidable distance between the complexity-theoretic hardness arguments and current experiments. One of the largest gaps involves the ratio of {particles} to modes -- all current hardness evidence assumes a dilute regime in which the number of linear optical modes scales at least quadratically in the number of particles. By contrast, current experiments operate in a saturated regime with a linear number of modes. In this paper we bridge this gap, bringing the hardness evidence for experiments in the saturated regime to the same level as had been previously established for the dilute regime. This involves proving a new worst-to-average-case reduction for computing the Permanent which is robust to both large numbers of row repetitions and also to distributions over matrices with correlated entries. We also apply similar arguments to give evidence for hardness of Gaussian BosonSampling in the saturated regime. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_00286 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Complexity-theoretic foundations of BosonSampling with a linear number of modes Bouland, Adam Brod, Daniel Datta, Ishaun Fefferman, Bill Grier, Daniel Hernandez, Felipe Oszmaniec, Michal Quantum Physics Computational Complexity BosonSampling is the leading candidate for demonstrating quantum computational advantage in photonic systems. While we have recently seen many impressive experimental demonstrations, there is still a formidable distance between the complexity-theoretic hardness arguments and current experiments. One of the largest gaps involves the ratio of {particles} to modes -- all current hardness evidence assumes a dilute regime in which the number of linear optical modes scales at least quadratically in the number of particles. By contrast, current experiments operate in a saturated regime with a linear number of modes. In this paper we bridge this gap, bringing the hardness evidence for experiments in the saturated regime to the same level as had been previously established for the dilute regime. This involves proving a new worst-to-average-case reduction for computing the Permanent which is robust to both large numbers of row repetitions and also to distributions over matrices with correlated entries. We also apply similar arguments to give evidence for hardness of Gaussian BosonSampling in the saturated regime. |
| title | Complexity-theoretic foundations of BosonSampling with a linear number of modes |
| topic | Quantum Physics Computational Complexity |
| url | https://arxiv.org/abs/2312.00286 |