Sample caching Markov chain Monte Carlo approach to boson sampling simulation

被引：6

作者：

Liu, Yong ^{[1
,2
]}

Xiong, Min ^{[1
,2
]}

Wu, Chunqing ^{[1
,2
]}

Wang, Dongyang ^{[1
,2
]}

Liu, Yingwen ^{[1
,2
]}

Ding, Jiangfang ^{[1
,2
]}

Huang, Anqi ^{[1
,2
]}

Fu, Xiang ^{[1
,2
]}

Qiang, Xiaogang ^{[1
,2
,3
]}

Xu, Ping ^{[1
,2
]}

Deng, Mingtang ^{[1
,2
]}

Yang, Xuejun ^{[1
,2
]}

Wu, Junjie ^{[1
,2
]}

机构：

[1] Natl Univ Def Technol, Coll Comp, Inst Quantum Informat, Changsha 410073, Peoples R China

[2] Natl Univ Def Technol, Coll Comp, State Key Lab High Performance Comp, Changsha 410073, Peoples R China

[3] AMS, Natl Innovat Inst Def Technol, Beijing 100071, Peoples R China

来源：

NEW JOURNAL OF PHYSICS | 2020年 / 22卷 / 03期

基金：

中国国家自然科学基金;

关键词：

boson sampling; quantum supremacy; Markov chain Monte Carlo; autocorrelation; sample caching; QUANTUM SUPREMACY;

D O I：

10.1088/1367-2630/ab73c4

中图分类号：

O4 [物理学];

学科分类号：

0702 ;

摘要：

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.

引用

页数：8

共 47 条

[11] Bayesian approach to Boson sampling validation [J].

Bentivegna, Marco ;

Spagnolo, Nicolo ;

Vitelli, Chiara ;

Brod, Daniel J. ;

Crespi, Andrea ;

Flamini, Fulvio ;

Ramponi, Roberta ;

Mataloni, Paolo ;

Osellame, Roberto ;

Galvao, Ernesto F. ;

Sciarrino, Fabio .

INTERNATIONAL JOURNAL OF QUANTUM INFORMATION, 2014, 12 (7-8)

[12] Characterizing quantum supremacy in near-term devices [J].

Boixo, Sergio ;

Isakov, Sergei, V ;

Smelyanskiy, Vadim N. ;

Babbush, Ryan ;

Ding, Nan ;

Jiang, Zhang ;

Bremner, Michael J. ;

Martinis, John M. ;

Neven, Hartmut .

NATURE PHYSICS, 2018, 14 (06) :595-600

[13] Average-Case Complexity Versus Approximate Simulation of Commuting Quantum Computations [J].

Bremner, Michael J. ;

Montanaro, Ashley ;

Shepherd, Dan J. .

PHYSICAL REVIEW LETTERS, 2016, 117 (08)

[14] Photonic Boson Sampling in a Tunable Circuit [J].

Broome, Matthew A. ;

Fedrizzi, Alessandro ;

Rahimi-Keshari, Saleh ;

Dove, Justin ;

Aaronson, Scott ;

Ralph, Timothy C. ;

White, Andrew G. .

SCIENCE, 2013, 339 (6121) :794-798

[15] UNDERSTANDING THE METROPOLIS-HASTINGS ALGORITHM [J].

CHIB, S ;

GREENBERG, E .

AMERICAN STATISTICIAN, 1995, 49 (04) :327-335

[16]

Clifford P, 2018, SODA'18: PROCEEDINGS OF THE TWENTY-NINTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P146

[17]

DURBIN J, 1971, BIOMETRIKA, V58, P1

[18]

Gagniuc Paul A, 2017, MARKOV CHAINS THEORY

[19] The permanent of a square matrix [J].

Glynn, David G. .

EUROPEAN JOURNAL OF COMBINATORICS, 2010, 31 (07) :1887-1891

[20] General-Purpose Quantum Circuit Simulator with Projected Entangled-Pair States and the Quantum Supremacy Frontier [J].

Guo, Chu ;

Liu, Yong ;

Xiong, Min ;

Xue, Shichuan ;

Fu, Xiang ;

Huang, Anqi ;

Qiang, Xiaogang ;

Xu, Ping ;

Liu, Junhua ;

Zheng, Shenggen ;

Huang, He-Liang ;

Deng, Mingtang ;

Poletti, Dario ;

Bao, Wan-Su ;

Wu, Junjie .

PHYSICAL REVIEW LETTERS, 2019, 123 (19)

← 1 2 3 4 5 →