CaltechAUTHORS
  A Caltech Library Service

Classical simulation of lossy boson sampling using matrix product operators

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

[img] PDF - Published Version
See Usage Policy.

1MB
[img] 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:
URLURL TypeDescription
https://doi.org/10.1103/physreva.104.022407DOIArticle
https://arxiv.org/abs/2101.11234arXivDiscussion Paper
ORCID:
AuthorORCID
Oh, Changhun0000-0003-2002-1928
Noh, Kyungjoo0000-0002-6318-8472
Fefferman, Bill0000-0002-9627-0210
Jiang, Liang0000-0002-0000-9342
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:
Funding AgencyGrant Number
Army Research Office (ARO)W911NF-18-1-0020
Army Research Office (ARO)W911NF-18-1-0212
Army Research Office (ARO)W911NF-16-1-0349
Air Force Office of Scientific Research (AFOSR)FA9550-19-1-0399
NSFEFMA-1640959
NSFOMA-1936118
NSFEEC-1941583
NTT ResearchUNSPECIFIED
David and Lucile Packard Foundation2013-39273
Air Force Office of Scientific Research (AFOSR)FA9550-18-1-0148
Air Force Office of Scientific Research (AFOSR)FA9550-21-1-0008
NSFCCF-2044923
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