Quantum multiparty communication complexity and circuit lower bounds

被引:1
|
作者
Kerenidis, Iordanis [1 ]
机构
[1] LRI Univ Paris 11, CNRS, Paris, France
关键词
PROTOCOLS;
D O I
10.1017/S0960129508007263
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We define a quantum model for multiparty communication complexity and prove a simulation theorem between the classical and quantum models. As a result, we show that if the quantum k-party communication complexity of a function f is Omega(n/2(k)), its classical k-party communication is Omega(n/2(k/2)). Finding such an f would allow us to prove strong classical lower bounds for k >= log n players and make progress towards solving a major open question about symmetric circuits.
引用
收藏
页码:119 / 132
页数:14
相关论文
共 50 条
  • [31] Communication complexity and lower bounds on multilective computations
    Hromkovic, J
    RAIRO-INFORMATIQUE THEORIQUE ET APPLICATIONS-THEORETICAL INFORMATICS AND APPLICATIONS, 1999, 33 (02): : 193 - 212
  • [32] Circuit lower bounds collapse relativized complexity classes
    Beigel, R
    Maciel, A
    FOURTEENTH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY, PROCEEDINGS, 1999, : 222 - 226
  • [33] Multiparty Communication Complexity and Threshold Circuit Size of AC0
    Beame, Paul
    Huynh-Ngoc, Dang-Trinh
    2009 50TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE: FOCS 2009, PROCEEDINGS, 2009, : 53 - 62
  • [34] Lower bounds on the complexity of simulating quantum gates
    Childs, AM
    Haselgrove, HL
    Nielsen, MA
    PHYSICAL REVIEW A, 2003, 68 (05):
  • [35] MULTIPARTY COMMUNICATION COMPLEXITY AND THRESHOLD CIRCUIT SIZE OF AC0
    Beame, Paul
    Huynh, Trinh
    SIAM JOURNAL ON COMPUTING, 2012, 41 (03) : 484 - 518
  • [36] The multiparty communication complexity of exact-T:: improved bounds and new problems
    Beigel, Richard
    Gasarch, William
    Glenn, James
    MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2006, PROCEEDINGS, 2006, 4162 : 146 - 156
  • [37] A geometric approach to quantum circuit lower bounds
    Nielsen, MA
    QUANTUM INFORMATION & COMPUTATION, 2006, 6 (03) : 213 - 262
  • [38] Lower Bounds in Communication Complexity Based on Factorization Norms
    Linial, Nati
    Shraibman, Adi
    RANDOM STRUCTURES & ALGORITHMS, 2009, 34 (03) : 368 - 394
  • [39] Lower Bounds in Communication Complexity Based on Factorization Norms
    Linial, Nati
    Shraibman, Adi
    STOC 07: PROCEEDINGS OF THE 39TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING, 2007, : 699 - 708
  • [40] Property Testing Lower Bounds Via Communication Complexity
    Blais, Eric
    Brody, Joshua
    Matulef, Kevin
    2011 IEEE 26TH ANNUAL CONFERENCE ON COMPUTATIONAL COMPLEXITY (CCC), 2011, : 210 - 220