n the powerftchnfor 1way uantumcation complexity Shengyu Zhang The Chinese University of Hong Kong
Shengyu Zhang The Chinese University of Hong Kong
Algorithms Circuit Ib Info.theory 0 Streaming Algorithms Quantum Communication crypto Computing O0 Complexity" VLSI Data games Structures Question:What's the largest gap between classical and quantum communication complexities?
Quantum Computing Communication Complexity Question: What’s the largest gap between classical and quantum communication complexities? Algorithms Info. theory crypto games … Circuit lb Streaming Algorithms VLSI Data Structures …
Communication complexity [Yao79]Two parties,Alice and Bob,jointly compute a function f(x,y)with x known only to Alice and y only to Bob. Alice Bob f(x,y) f(xy) Communication complexity:how many bits are needed to be exchanged?
Communication complexity • [Yao79] Two parties, Alice and Bob, jointly compute a function f(x,y) with x known only to Alice and y only to Bob. • Communication complexity: how many bits are needed to be exchanged? Alice Bob f(x,y) f(x,y) x y
Various protocols ·Deterministic:D(f 。Randomized:R(f -A bounded error probability is allowed. -Private or public coins?Differ by +O(log n). Quantum:Q(f) -A bounded error probability is allowed. -Assumption:No shared Entanglement. (Does it help？Open.)
Various protocols • Deterministic: D(f) • Randomized: R(f) – A bounded error probability is allowed. – Private or public coins? Differ by ±O(log n). • Quantum: Q(f) – A bounded error probability is allowed. – Assumption: No shared Entanglement. (Does it help? Open.)
Communication complexity: one-way model X Alice Bob f(x,y) One-way:Alice sends a message to Bob. -D1(⑤，R1(⑤，Q1(⑤
Communication complexity: one-way model • One-way: Alice sends a message to Bob. --- D1 (f), R1 (f), Q1 (f) Alice Bob x y f(x,y)