Sample caching Markov chain Monte Carlo approach to boson sampling simulation
Boson sampling is a promising candidate for quantum supremacy. It requires to sample from a complicated distribution, and is trusted to be intractable on classical computers. Among the various classical sampling methods, the Markov chain Monte Carlo method is an important approach to the simulation...
| Main Authors: | , , , , , , , , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IOP Publishing
2020-01-01
|
| Series: | New Journal of Physics |
| Subjects: | |
| Online Access: | https://doi.org/10.1088/1367-2630/ab73c4 |
| _version_ | 1827872993798258688 |
|---|---|
| author | Yong Liu Min Xiong Chunqing Wu Dongyang Wang Yingwen Liu Jiangfang Ding Anqi Huang Xiang Fu Xiaogang Qiang Ping Xu Mingtang Deng Xuejun Yang Junjie Wu |
| author_facet | Yong Liu Min Xiong Chunqing Wu Dongyang Wang Yingwen Liu Jiangfang Ding Anqi Huang Xiang Fu Xiaogang Qiang Ping Xu Mingtang Deng Xuejun Yang Junjie Wu |
| author_sort | Yong Liu |
| collection | DOAJ |
| description | Boson sampling is a promising candidate for quantum supremacy. It requires to sample from a complicated distribution, and is trusted to be intractable on classical computers. Among the various classical sampling methods, the Markov chain Monte Carlo method is an important approach to the simulation and validation of boson sampling. This method however suffers from the severe sample loss issue caused by the autocorrelation of the sample sequence. Addressing this, we propose the sample caching Markov chain Monte Carlo method that eliminates the correlations among the samples, and prevents the sample loss at the meantime, allowing more efficient simulation of boson sampling. Moreover, our method can be used as a general sampling framework that can benefit a wide range of sampling tasks, and is particularly suitable for applications where a large number of samples are taken. |
| first_indexed | 2024-03-12T16:31:20Z |
| format | Article |
| id | doaj.art-4235efad9bcb425499def035ed544aac |
| institution | Directory Open Access Journal |
| issn | 1367-2630 |
| language | English |
| last_indexed | 2024-03-12T16:31:20Z |
| publishDate | 2020-01-01 |
| publisher | IOP Publishing |
| record_format | Article |
| series | New Journal of Physics |
| spelling | doaj.art-4235efad9bcb425499def035ed544aac2023-08-08T15:29:07ZengIOP PublishingNew Journal of Physics1367-26302020-01-0122303302210.1088/1367-2630/ab73c4Sample caching Markov chain Monte Carlo approach to boson sampling simulationYong Liu0https://orcid.org/0000-0003-0523-6816Min Xiong1Chunqing Wu2Dongyang Wang3Yingwen Liu4Jiangfang Ding5Anqi Huang6Xiang Fu7https://orcid.org/0000-0002-1365-8501Xiaogang Qiang8Ping Xu9Mingtang Deng10Xuejun Yang11Junjie Wu12https://orcid.org/0000-0001-5951-8988Institute for Quantum Information & State Key Laboratory of High Performance Computing, College of Computer, National University of Defense Technology, Changsha 410073, People's Republic of ChinaInstitute for Quantum Information & State Key Laboratory of High Performance Computing, College of Computer, National University of Defense Technology, Changsha 410073, People's Republic of ChinaInstitute for Quantum Information & State Key Laboratory of High Performance Computing, College of Computer, National University of Defense Technology, Changsha 410073, People's Republic of ChinaInstitute for Quantum Information & State Key Laboratory of High Performance Computing, College of Computer, National University of Defense Technology, Changsha 410073, People's Republic of ChinaInstitute for Quantum Information & State Key Laboratory of High Performance Computing, College of Computer, National University of Defense Technology, Changsha 410073, People's Republic of ChinaInstitute for Quantum Information & State Key Laboratory of High Performance Computing, College of Computer, National University of Defense Technology, Changsha 410073, People's Republic of ChinaInstitute for Quantum Information & State Key Laboratory of High Performance Computing, College of Computer, National University of Defense Technology, Changsha 410073, People's Republic of ChinaInstitute for Quantum Information & State Key Laboratory of High Performance Computing, College of Computer, National University of Defense Technology, Changsha 410073, People's Republic of ChinaInstitute for Quantum Information & State Key Laboratory of High Performance Computing, College of Computer, National University of Defense Technology, Changsha 410073, People's Republic of China; National Innovation Institute of Defense Technology , AMS, 100071 Beijing, People's Republic of ChinaInstitute for Quantum Information & State Key Laboratory of High Performance Computing, College of Computer, National University of Defense Technology, Changsha 410073, People's Republic of ChinaInstitute for Quantum Information & State Key Laboratory of High Performance Computing, College of Computer, National University of Defense Technology, Changsha 410073, People's Republic of ChinaInstitute for Quantum Information & State Key Laboratory of High Performance Computing, College of Computer, National University of Defense Technology, Changsha 410073, People's Republic of ChinaInstitute for Quantum Information & State Key Laboratory of High Performance Computing, College of Computer, National University of Defense Technology, Changsha 410073, People's Republic of ChinaBoson sampling is a promising candidate for quantum supremacy. It requires to sample from a complicated distribution, and is trusted to be intractable on classical computers. Among the various classical sampling methods, the Markov chain Monte Carlo method is an important approach to the simulation and validation of boson sampling. This method however suffers from the severe sample loss issue caused by the autocorrelation of the sample sequence. Addressing this, we propose the sample caching Markov chain Monte Carlo method that eliminates the correlations among the samples, and prevents the sample loss at the meantime, allowing more efficient simulation of boson sampling. Moreover, our method can be used as a general sampling framework that can benefit a wide range of sampling tasks, and is particularly suitable for applications where a large number of samples are taken.https://doi.org/10.1088/1367-2630/ab73c4boson samplingquantum supremacyMarkov chain Monte Carloautocorrelationsample caching |
| spellingShingle | Yong Liu Min Xiong Chunqing Wu Dongyang Wang Yingwen Liu Jiangfang Ding Anqi Huang Xiang Fu Xiaogang Qiang Ping Xu Mingtang Deng Xuejun Yang Junjie Wu Sample caching Markov chain Monte Carlo approach to boson sampling simulation New Journal of Physics boson sampling quantum supremacy Markov chain Monte Carlo autocorrelation sample caching |
| title | Sample caching Markov chain Monte Carlo approach to boson sampling simulation |
| title_full | Sample caching Markov chain Monte Carlo approach to boson sampling simulation |
| title_fullStr | Sample caching Markov chain Monte Carlo approach to boson sampling simulation |
| title_full_unstemmed | Sample caching Markov chain Monte Carlo approach to boson sampling simulation |
| title_short | Sample caching Markov chain Monte Carlo approach to boson sampling simulation |
| title_sort | sample caching markov chain monte carlo approach to boson sampling simulation |
| topic | boson sampling quantum supremacy Markov chain Monte Carlo autocorrelation sample caching |
| url | https://doi.org/10.1088/1367-2630/ab73c4 |
| work_keys_str_mv | AT yongliu samplecachingmarkovchainmontecarloapproachtobosonsamplingsimulation AT minxiong samplecachingmarkovchainmontecarloapproachtobosonsamplingsimulation AT chunqingwu samplecachingmarkovchainmontecarloapproachtobosonsamplingsimulation AT dongyangwang samplecachingmarkovchainmontecarloapproachtobosonsamplingsimulation AT yingwenliu samplecachingmarkovchainmontecarloapproachtobosonsamplingsimulation AT jiangfangding samplecachingmarkovchainmontecarloapproachtobosonsamplingsimulation AT anqihuang samplecachingmarkovchainmontecarloapproachtobosonsamplingsimulation AT xiangfu samplecachingmarkovchainmontecarloapproachtobosonsamplingsimulation AT xiaogangqiang samplecachingmarkovchainmontecarloapproachtobosonsamplingsimulation AT pingxu samplecachingmarkovchainmontecarloapproachtobosonsamplingsimulation AT mingtangdeng samplecachingmarkovchainmontecarloapproachtobosonsamplingsimulation AT xuejunyang samplecachingmarkovchainmontecarloapproachtobosonsamplingsimulation AT junjiewu samplecachingmarkovchainmontecarloapproachtobosonsamplingsimulation |