Quantum One-Way Communication can be Exponentially Stronger Than Classical Communication

被引：0
|
作者：
Klartag, Bo'az [1 ]
Regev, Oded [1 ]
机构：
[1] Tel Aviv Univ, Sch Math Sci, Tel Aviv, Israel
来源：
STOC 11: PROCEEDINGS OF THE 43RD ACM SYMPOSIUM ON THEORY OF COMPUTING | 2011年
关键词：
communication complexity; sampling; sphere; hypercontractive inequality; INEQUALITIES; COMPLEXITY;
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
In STOC 1999, Raz presented a (partial) function for which there is a quantum protocol communicating only O(log n) qubits, but for which any classical (randomized, boundederror) protocol requires poly(n) bits of communication. That quantum protocol requires two rounds of communication. Ever since Raz's paper it was open whether the same exponential separation can be achieved with a quantum protocol that uses only one round of communication. Here we settle this question in the affirmative.
引用
收藏
页码：31 / 40
页数：10
相关论文
共 50 条
  • [1] On relating one-way classical and quantum communication complexities
    Boddu, Naresh Goud
    Jain, Rahul
    Lin, Han-Hsuan
    QUANTUM, 2023, 7
  • [2] Exponential separation of quantum and classical one-way communication complexity
    Bar-Yossef, Ziv
    Jayram, T. S.
    Kerenidis, Iordanis
    SIAM JOURNAL ON COMPUTING, 2008, 38 (01) : 366 - 384
  • [3] New bounds on classical and quantum one-way communication complexity
    Jain, Rahul
    Zhang, Shengyu
    THEORETICAL COMPUTER SCIENCE, 2009, 410 (26) : 2463 - 2477
  • [4] Unbounded-error one-way classical and quantum communication complexity
    Iwama, Kazuo
    Nishimura, Harumichi
    Raymond, Rudy
    Yamashita, Shigeru
    AUTOMATA, LANGUAGES AND PROGRAMMING, PROCEEDINGS, 2007, 4596 : 110 - +
  • [5] COMMUNICATION - MORE THAN A ONE-WAY STREET
    不详
    UNESCO COURIER, 1977, (03) : 30 - 30
  • [6] Quantum one-way versus classical two-way communication in XOR games
    Abderramán Amr
    Ignacio Villanueva
    Quantum Information Processing, 2021, 20
  • [7] Quantum one-way versus classical two-way communication in XOR games
    Amr, Abderraman
    Villanueva, Ignacio
    QUANTUM INFORMATION PROCESSING, 2021, 20 (02)
  • [8] Limitations of quantum advice and one-way communication
    Aaronson, S
    19TH IEEE ANNUAL CONFERENCE ON COMPUTATIONAL COMPLEXITY, PROCEEDINGS, 2004, : 320 - 332
  • [9] A NEW EXPONENTIAL SEPARATION BETWEEN QUANTUM AND CLASSICAL ONE-WAY COMMUNICATION COMPLEXITY
    Montanaro, Ashley
    QUANTUM INFORMATION & COMPUTATION, 2011, 11 (7-8) : 574 - 591
  • [10] ONE-WAY COMMUNICATION
    DONOGHUE, D
    IRISH UNIVERSITY REVIEW, 1979, 9 (01) : 119 - 141
12345