Oh, Changhun and Noh, Kyungjoo and Fefferman, Bill and Jiang, Liang (2021) Classical simulation of lossy boson sampling using matrix product operators. Physical Review A, 104 (2). Art. No. 022407. ISSN 2469-9926. doi:10.1103/physreva.104.022407. https://resolver.caltech.edu/CaltechAUTHORS:20210826-202056783
![]() |
PDF
- Published Version
See Usage Policy. 1MB |
![]() |
PDF
- Accepted Version
See Usage Policy. 1MB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20210826-202056783
Abstract
Characterizing the computational advantage from noisy intermediate-scale quantum (NISQ) devices is an important task from theoretical and practical perspectives. Here, we numerically investigate the computational power of NISQ devices focusing on boson sampling, one of the well-known promising problems which can exhibit quantum supremacy. We study hardness of lossy boson sampling using matrix product operator (MPO) simulation to address the effect of photon loss on classical simulability using MPO entanglement entropy (EE), which characterizes a running time of an MPO algorithm. An advantage of MPO simulation over other classical algorithms proposed to date is that its simulation accuracy can be efficiently controlled by increasing an MPO's bond dimension. Notably, we show by simulating lossy boson sampling using an MPO that as an input photon number grows, its computational cost, or MPO EE, behaves differently depending on a loss scaling, exhibiting a different feature from that of lossless boson sampling. Especially when an output photon number scales faster than the square root of an input photon number, our study shows an exponential scaling of time complexity for MPO simulation. On the contrary, when an output photon number scales slower than the square root of an input photon number, MPO EE may decrease, indicating that an exponential time complexity might not be necessary.
Item Type: | Article | ||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Related URLs: |
| ||||||||||||||||||||||||||
ORCID: |
| ||||||||||||||||||||||||||
Additional Information: | © 2021 American Physical Society. Received 13 February 2021; revised 21 June 2021; accepted 15 July 2021; published 5 August 2021. We thank O. Howell, A. Seif, and R. Bassirian for interesting and fruitful discussions. C.O. and L.J. acknowledge support from the ARO (Grants No. W911NF-18-1-0020 and No. W911NF-18-1-0212), ARO MURI (Grant No. W911NF-16-1-0349), AFOSR MURI (Grant No. FA9550-19-1-0399), NSF (Grants No. EFMA-1640959, No. OMA-1936118, and No. EEC-1941583), NTT Research, and the Packard Foundation (Grant No. 2013-39273). B.F. acknowledges support from AFOSR (Grants No. YIP FA9550-18-1-0148 and No. FA9550-21-1-0008). This material is based upon work partially supported by the National Science Foundation under Grant No. CCF-2044923 (CAREER). We also acknowledge the University of Chicago's Research Computing Center for their support of this work. | ||||||||||||||||||||||||||
Group: | AWS Center for Quantum Computing | ||||||||||||||||||||||||||
Funders: |
| ||||||||||||||||||||||||||
Issue or Number: | 2 | ||||||||||||||||||||||||||
DOI: | 10.1103/physreva.104.022407 | ||||||||||||||||||||||||||
Record Number: | CaltechAUTHORS:20210826-202056783 | ||||||||||||||||||||||||||
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20210826-202056783 | ||||||||||||||||||||||||||
Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||||||||||||||||||||||
ID Code: | 110585 | ||||||||||||||||||||||||||
Collection: | CaltechAUTHORS | ||||||||||||||||||||||||||
Deposited By: | Tony Diaz | ||||||||||||||||||||||||||
Deposited On: | 26 Aug 2021 21:03 | ||||||||||||||||||||||||||
Last Modified: | 26 Aug 2021 21:03 |
Repository Staff Only: item control page