Review on quantum advantages of sampling problems

被引:1
作者
Li Ying [1 ,2 ]
Han Ze-Yao [1 ,2 ]
Li Chao-Jian [2 ,3 ]
Lu Jin [1 ]
Yuan Xiao [2 ]
Wu Bu-Jiao [2 ]
机构
[1] Peking Univ, Sch Phys, Beijing 100871, Peoples R China
[2] Peking Univ, Ctr Frontiers Comp Studies, Beijing 100871, Peoples R China
[3] Guangdong Univ Technol, Sch Comp Sci & Technol, Guangzhou 510006, Peoples R China
基金
中国国家自然科学基金;
关键词
quantum advantages; random circuit sampling; Boson sampling; classical simulation; CLASSICAL SIMULATION; SUPREMACY; COMPUTATION; ALGORITHMS; COMPLEXITY;
D O I
10.7498/aps.70.20211428
中图分类号
O4 [物理学];
学科分类号
0702 ;
摘要
Exploiting the coherence and entanglement of quantum many-qubit states, quantum computing can significantly surpass classical algorithms, making it possible to factor large numbers, solve linear equations, simulate many-body quantum systems, etc., in a reasonable time. With the rapid development of quantum computing hardware, many attention has been drawn to explore how quantum computers could go beyond the limit of classical computation. Owing to the need of a universal fault-tolerant quantum computer for many existing quantum algorithms, such as Shor' s factoring algorithm, and considering the limit of near-term quantum devices with small qubit numbers and short coherence times, many recent works focused on the exploration of demonstrating quantum advantages using noisy intermediate-scaled quantum devices and shallow circuits, and hence some sampling problems have been proposed as the candidates for quantum advantage demonstration. This review summarizes quantum advantage problems that are realizable on current quantum hardware. We focus on two notable problems-random circuit simulation and boson sampling-and consider recent theoretical and experimental progresses. After the respective demonstrations of these two types of quantum advantages on superconducting and optical quantum platforms, we expect current and near-term quantum devices could be employed for demonstrating quantum advantages in general problems.
引用
收藏
页数:16
相关论文
共 75 条
[1]  
Aaronson S, 2019, ARXIV191012085QUANTP
[2]  
Aaronson S, 2011, ACM S THEORY COMPUT, P333
[3]  
Aaronson Scott, 2016, ARXIV161205903QUANTP
[4]  
[Anonymous], 2017, ARXIV171005867QUANTP
[5]  
Arrazola J M, 2017, ARXIV171207288QUANTP
[6]   Using Gaussian Boson Sampling to Find Dense Subgraphs [J].
Arrazola, Juan Miguel ;
Bromley, Thomas R. .
PHYSICAL REVIEW LETTERS, 2018, 121 (03)
[7]   Quantum approximate optimization with Gaussian boson sampling [J].
Arrazola, Juan Miguel ;
Bromley, Thomas R. ;
Rebentrost, Patrick .
PHYSICAL REVIEW A, 2018, 98 (01)
[8]  
Arute F, 2010, ARXIV201007965QUANTP
[9]  
Arute F, 2000, SCIENCE, V369, P1084
[10]   Quantum supremacy using a programmable superconducting processor [J].
Arute, Frank ;
Arya, Kunal ;
Babbush, Ryan ;
Bacon, Dave ;
Bardin, Joseph C. ;
Barends, Rami ;
Biswas, Rupak ;
Boixo, Sergio ;
Brandao, Fernando G. S. L. ;
Buell, David A. ;
Burkett, Brian ;
Chen, Yu ;
Chen, Zijun ;
Chiaro, Ben ;
Collins, Roberto ;
Courtney, William ;
Dunsworth, Andrew ;
Farhi, Edward ;
Foxen, Brooks ;
Fowler, Austin ;
Gidney, Craig ;
Giustina, Marissa ;
Graff, Rob ;
Guerin, Keith ;
Habegger, Steve ;
Harrigan, Matthew P. ;
Hartmann, Michael J. ;
Ho, Alan ;
Hoffmann, Markus ;
Huang, Trent ;
Humble, Travis S. ;
Isakov, Sergei V. ;
Jeffrey, Evan ;
Jiang, Zhang ;
Kafri, Dvir ;
Kechedzhi, Kostyantyn ;
Kelly, Julian ;
Klimov, Paul V. ;
Knysh, Sergey ;
Korotkov, Alexander ;
Kostritsa, Fedor ;
Landhuis, David ;
Lindmark, Mike ;
Lucero, Erik ;
Lyakh, Dmitry ;
Mandra, Salvatore ;
McClean, Jarrod R. ;
McEwen, Matthew ;
Megrant, Anthony ;
Mi, Xiao .
NATURE, 2019, 574 (7779) :505-+