1
Preliminaries: quantum and algebraic background
2
Communication models
3
Magic lower bounds from communication complexity
▶
3.1
Computation and communication models
3.2
Lower bounds on magic gate count from communication complexity
▶
Bounds from parity decision trees
3.3
Lower bounds for concrete unitary operators
4
Communication upper bounds from magic depth
▶
4.1
The private simultaneous message passing model and NLQC
4.2
Transforming \(\mathsf{Q}\| ^{*}\) protocols into \(\mathsf{PSM}^{*}\) protocols
4.3
Separating \(\mathsf{R}\| ^{*}\) and \(\mathsf{R}\)
Dependency graph
Magic and Communication Complexity
Girish, May, Parham, Yuen (blueprint)
1
Preliminaries: quantum and algebraic background
2
Communication models
3
Magic lower bounds from communication complexity
3.1
Computation and communication models
3.2
Lower bounds on magic gate count from communication complexity
Bounds from parity decision trees
3.3
Lower bounds for concrete unitary operators
4
Communication upper bounds from magic depth
4.1
The private simultaneous message passing model and NLQC
4.2
Transforming \(\mathsf{Q}\| ^{*}\) protocols into \(\mathsf{PSM}^{*}\) protocols
4.3
Separating \(\mathsf{R}\| ^{*}\) and \(\mathsf{R}\)