Quantum pseudo-telepathy

被引：132

作者：

Brassard, G ^{[1
]}

Broadbent, A ^{[1
]}

Tapp, A ^{[1
]}

机构：

[1] Univ Montreal, Dept IRO, Montreal, PQ H3C 3J7, Canada

来源：

FOUNDATIONS OF PHYSICS | 2005年 / 35卷 / 11期

关键词：

entanglement; nonlocality; Bell's theorem; quantum information processing; quantum communication complexity; pseudo-telepathy;

D O I：

10.1007/s10701-005-7353-4

中图分类号：

O4 [物理学];

学科分类号：

0702 ;

摘要：

Quantum information processing is at the crossroads of physics, mathematics and computer science. It is concerned with what we can and cannot do with quantum information that goes beyond the abilities of classical information processing devices. Communication complexity is an area of classical computer science that aims at quantifying the amount of communication necessary to solve distributed computational problems. Quantum communication complexity uses quantum mechanics to reduce the amount of communication that would be classically required. Pseudo-telepathy is a surprising application of quantum information processing to communication complexity. Thanks to entanglement, perhaps the most nonclassical manifestation of quantum mechanics, two or more quantum players can accomplish a distributed task with no need for communication whatsoever, which would be an impossible feat for classical players. After a detailed overview of the principle and purpose of pseudo-telepathy, we present a survey of recent and not-so-recent work on the subject. In particular, we describe and analyse all the pseudo-telepathy games currently known to the authors.

引用

页码：1877 / 1907

页数：31

共 55 条

[11]

BOYER M, 2004, ARXIVQUANTPH0408090

[12]

Brassard G, 2005, QUANTUM INF COMPUT, V5, P275

[13]

Brassard G, 2003, LECT NOTES COMPUT SC, V2748, P1

[14] Quantum communication complexity [J].

Brassard, G .

FOUNDATIONS OF PHYSICS, 2003, 33 (11) :1593-1616

[15] Cost of exactly simulating quantum entanglement with classical communication [J].

Brassard, G ;

Cleve, R ;

Tapp, A .

PHYSICAL REVIEW LETTERS, 1999, 83 (09) :1874-1877

[16]

BRASSARD G, 2005, QUANTUM INF COMP, V5

[17]

BROADBENT A, 2004, THESIS U MONTREAL

[18]

Buhrman H., 1998, Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, P63, DOI 10.1145/276698.276713

[19] Combinatorics and quantum nonlocality -: art. no. 047903 [J].

Buhrman, H ;

Hoyer, P ;

Massar, S ;

Röhrig, H .

PHYSICAL REVIEW LETTERS, 2003, 91 (04)

[20]

BUHRMAN H, 2004, COMMUNICATION JAN

← 1 2 3 4 5 6 →