Review on the study of entanglement in quantum computation speedup

被引：46

作者：

ShengChao, Ding

Zhi, Jin ^{[1
]}

机构：

[1] Chinese Acad Sci, Inst Commun Technol, Beijing 100080, Peoples R China

[2] Chinese Acad Sci, Acad Math & Syst Sci, Beijing 100080, Peoples R China

[3] Grad Univ, Chinese Acad Sci, Beijing 100080, Peoples R China

来源：

CHINESE SCIENCE BULLETIN | 2007年 / 52卷 / 16期

基金：

中国国家自然科学基金;

关键词：

entanglement; quantum computation; speedup; simulation;

D O I：

10.1007/s11434-007-0324-8

中图分类号：

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

学科分类号：

07 ; 0710 ; 09 ;

摘要：

The role the quantum entanglement plays in quantum computation speedup has been widely disputed. Some believe that quantum computation's speedup over classical computation is impossible if entanglement is absent, while others claim that the presence of entanglement is not a necessary condition for some quantum algorithms. This paper discusses this problem systematically. Simulating quantum computation with classical resources is analyzed and entanglement in known algorithms is reviewed. It is concluded that the presence of entanglement is a necessary but not sufficient condition in the pure state or pseudo-pure state quantum computation speedup. The case with the mixed state remains open. Further work on quantum computation will benefit from the presented results.

引用

页码：2161 / 2166

页数：6

共 30 条

[1] Polynomial simulations of decohered quantum computers [J].

Aharonov, D ;

BenOr, M .

37TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 1996, :46-55

[2]

Ambainis A., 2000, Proceedings of the Thirty Second Annual ACM Symposium on Theory of Computing, P697, DOI 10.1145/335305.335403

[3] TELEPORTING AN UNKNOWN QUANTUM STATE VIA DUAL CLASSICAL AND EINSTEIN-PODOLSKY-ROSEN CHANNELS [J].

BENNETT, CH ;

BRASSARD, G ;

CREPEAU, C ;

JOZSA, R ;

PERES, A ;

WOOTTERS, WK .

PHYSICAL REVIEW LETTERS, 1993, 70 (13) :1895-1899

[4] Quantum computing without entanglement [J].

Biham, E ;

Brassard, G ;

Kenigsberg, D ;

Mor, T .

THEORETICAL COMPUTER SCIENCE, 2004, 320 (01) :15-33

[5] Entanglement monotone derived from Grover's algorithm [J].

Biham, O ;

Nielsen, MA ;

Osborne, TJ .

PHYSICAL REVIEW A, 2002, 65 (06) :623121-623127

[6]

Braunstein SL, 2002, QUANTUM INFORM COMPU, V2, P399

[7] Separability of very noisy mixed states and implications for NMR Quantum computing [J].

Braunstein, SL ;

Caves, CM ;

Jozsa, R ;

Linden, N ;

Popescu, S ;

Schack, R .

PHYSICAL REVIEW LETTERS, 1999, 83 (05) :1054-1057

[8] Ensemble quantum computing by NMR spectroscopy [J].

Cory, DG ;

Fahmy, AF ;

Havel, TF .

PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 1997, 94 (05) :1634-1639

[9] RAPID SOLUTION OF PROBLEMS BY QUANTUM COMPUTATION [J].

DEUTSCH, D ;

JOZSA, R .

PROCEEDINGS OF THE ROYAL SOCIETY OF LONDON SERIES A-MATHEMATICAL PHYSICAL AND ENGINEERING SCIENCES, 1992, 439 (1907) :553-558

[10] Quantum algorithms: entanglement-enhanced information processing [J].

Ekert, A ;

Jozsa, R .

PHILOSOPHICAL TRANSACTIONS OF THE ROYAL SOCIETY A-MATHEMATICAL PHYSICAL AND ENGINEERING SCIENCES, 1998, 356 (1743) :1769-1781

← 1 2 3 →