Quantum computational supremacy

被引：542

作者：

Harrow, Aram W. ^{[1
]}

Montanaro, Ashley ^{[2
]}

机构：

[1] MIT, Ctr Theoret Phys, Cambridge, MA 02139 USA

[2] Univ Bristol, Sch Math, Bristol BS8 1TW, Avon, England

来源：

NATURE | 2017年 / 549卷 / 7671期

基金：

英国工程与自然科学研究理事会; 美国国家科学基金会;

关键词：

COMPLEXITY;

D O I：

10.1038/nature23458

中图分类号：

O [数理科学和化学]; P [天文学、地球科学]; Q [生物科学]; N [自然科学总论];

学科分类号：

07 ; 0710 ; 09 ;

摘要：

The field of quantum algorithms aims to find ways to speed up the solution of computational problems by using a quantum computer. A key milestone in this field will be when a universal quantum computer performs a computational task that is beyond the capability of any classical computer, an event known as quantum supremacy. This would be easier to achieve experimentally than full-scale quantum computing, but involves new theoretical challenges. Here we present the leading proposals to achieve quantum supremacy, and discuss how we can reliably compare the power of a classical computer to the power of a quantum computer.

引用

页码：203 / 209

页数：7

共 56 条

[41] Threshold values of random K-SAT from the cavity method [J].

Mertens, S ;

Mézard, M ;

Zecchina, R .

RANDOM STRUCTURES & ALGORITHMS, 2006, 28 (03) :340-373

[42] Hardness of Classically Simulating the One-Clean-Qubit Model [J].

Morimae, Tomoyuki ;

Fujii, Keisuke ;

Fitzsimons, Joseph F. .

PHYSICAL REVIEW LETTERS, 2014, 112 (13)

[43] Retrieving the ground state of spin glasses using thermal noise: Performance of quantum annealing at finite temperatures [J].

Nishimura, Kohji ;

Nishimori, Hidetoshi ;

Ochoa, Andrew J. ;

Katzgraber, Helmut G. .

PHYSICAL REVIEW E, 2016, 94 (03)

[44]

Papadimitriou C., 1994, Computational complexity

[45] Sufficient Conditions for Efficient Classical Simulation of Quantum Optics [J].

Rahimi-Keshari, Saleh ;

Ralph, Timothy C. ;

Caves, Carlton M. .

PHYSICAL REVIEW X, 2016, 6 (02)

[46] Temporally unstructured quantum computation [J].

Shepherd, Dan ;

Bremner, Michael J. .

PROCEEDINGS OF THE ROYAL SOCIETY A-MATHEMATICAL PHYSICAL AND ENGINEERING SCIENCES, 2009, 465 (2105) :1413-1439

[47]

SHOR PW, 1994, AN S FDN CO, P124

[48]

Spagnolo N, 2014, NAT PHOTONICS, V8, P615, DOI [10.1038/NPHOTON.2014.135, 10.1038/nphoton.2014.135]

[49] General Rules for Bosonic Bunching in Multimode Interferometers [J].

Spagnolo, Nicolo ;

Vitelli, Chiara ;

Sansoni, Linda ;

Maiorino, Enrico ;

Mataloni, Paolo ;

Sciarrino, Fabio ;

Brod, Daniel J. ;

Galvao, Ernesto F. ;

Crespi, Andrea ;

Ramponi, Roberta ;

Osellame, Roberto .

PHYSICAL REVIEW LETTERS, 2013, 111 (13)

[50] Boson Sampling on a Photonic Chip [J].

Spring, Justin B. ;

Metcalf, Benjamin J. ;

Humphreys, Peter C. ;

Kolthammer, W. Steven ;

Jin, Xian-Min ;

Barbieri, Marco ;

Datta, Animesh ;

Thomas-Peter, Nicholas ;

Langford, Nathan K. ;

Kundys, Dmytro ;

Gates, James C. ;

Smith, Brian J. ;

Smith, Peter G. R. ;

Walmsley, Ian A. .

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

← 1 2 3 4 5 6 →