Tight Bounds on the Convergence of Noisy Random Circuits to the Uniform Distribution
We study the properties of output distributions of noisy random circuits. We obtain upper and lower bounds on the expected distance of the output distribution from the “useless” uniform distribution. These bounds are tight with respect to the dependence on circuit depth. Our proof techniques also al...
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
American Physical Society
2022-12-01
|
| Series: | PRX Quantum |
| Online Access: | http://doi.org/10.1103/PRXQuantum.3.040329 |
| _version_ | 1811184150248423424 |
|---|---|
| author | Abhinav Deshpande Pradeep Niroula Oles Shtanko Alexey V. Gorshkov Bill Fefferman Michael J. Gullans |
| author_facet | Abhinav Deshpande Pradeep Niroula Oles Shtanko Alexey V. Gorshkov Bill Fefferman Michael J. Gullans |
| author_sort | Abhinav Deshpande |
| collection | DOAJ |
| description | We study the properties of output distributions of noisy random circuits. We obtain upper and lower bounds on the expected distance of the output distribution from the “useless” uniform distribution. These bounds are tight with respect to the dependence on circuit depth. Our proof techniques also allow us to make statements about the presence or absence of anticoncentration for both noisy and noiseless circuits. We uncover a number of interesting consequences for hardness proofs of sampling schemes that aim to show a quantum computational advantage over classical computation. Specifically, we discuss recent barrier results for depth-agnostic and/or noise-agnostic proof techniques. We show that in certain depth regimes, noise-agnostic proof techniques might still work in order to prove an often-conjectured claim in the literature on quantum computational advantage, contrary to what has been thought prior to this work. |
| first_indexed | 2024-04-11T13:08:21Z |
| format | Article |
| id | doaj.art-7fe7147790e8409bbd17a3f3f5301395 |
| institution | Directory Open Access Journal |
| issn | 2691-3399 |
| language | English |
| last_indexed | 2024-04-11T13:08:21Z |
| publishDate | 2022-12-01 |
| publisher | American Physical Society |
| record_format | Article |
| series | PRX Quantum |
| spelling | doaj.art-7fe7147790e8409bbd17a3f3f53013952022-12-22T04:22:39ZengAmerican Physical SocietyPRX Quantum2691-33992022-12-013404032910.1103/PRXQuantum.3.040329Tight Bounds on the Convergence of Noisy Random Circuits to the Uniform DistributionAbhinav DeshpandePradeep NiroulaOles ShtankoAlexey V. GorshkovBill FeffermanMichael J. GullansWe study the properties of output distributions of noisy random circuits. We obtain upper and lower bounds on the expected distance of the output distribution from the “useless” uniform distribution. These bounds are tight with respect to the dependence on circuit depth. Our proof techniques also allow us to make statements about the presence or absence of anticoncentration for both noisy and noiseless circuits. We uncover a number of interesting consequences for hardness proofs of sampling schemes that aim to show a quantum computational advantage over classical computation. Specifically, we discuss recent barrier results for depth-agnostic and/or noise-agnostic proof techniques. We show that in certain depth regimes, noise-agnostic proof techniques might still work in order to prove an often-conjectured claim in the literature on quantum computational advantage, contrary to what has been thought prior to this work.http://doi.org/10.1103/PRXQuantum.3.040329 |
| spellingShingle | Abhinav Deshpande Pradeep Niroula Oles Shtanko Alexey V. Gorshkov Bill Fefferman Michael J. Gullans Tight Bounds on the Convergence of Noisy Random Circuits to the Uniform Distribution PRX Quantum |
| title | Tight Bounds on the Convergence of Noisy Random Circuits to the Uniform Distribution |
| title_full | Tight Bounds on the Convergence of Noisy Random Circuits to the Uniform Distribution |
| title_fullStr | Tight Bounds on the Convergence of Noisy Random Circuits to the Uniform Distribution |
| title_full_unstemmed | Tight Bounds on the Convergence of Noisy Random Circuits to the Uniform Distribution |
| title_short | Tight Bounds on the Convergence of Noisy Random Circuits to the Uniform Distribution |
| title_sort | tight bounds on the convergence of noisy random circuits to the uniform distribution |
| url | http://doi.org/10.1103/PRXQuantum.3.040329 |
| work_keys_str_mv | AT abhinavdeshpande tightboundsontheconvergenceofnoisyrandomcircuitstotheuniformdistribution AT pradeepniroula tightboundsontheconvergenceofnoisyrandomcircuitstotheuniformdistribution AT olesshtanko tightboundsontheconvergenceofnoisyrandomcircuitstotheuniformdistribution AT alexeyvgorshkov tightboundsontheconvergenceofnoisyrandomcircuitstotheuniformdistribution AT billfefferman tightboundsontheconvergenceofnoisyrandomcircuitstotheuniformdistribution AT michaeljgullans tightboundsontheconvergenceofnoisyrandomcircuitstotheuniformdistribution |