# Journal Club Spring 2012

This quarter we will be focusing on Quantum Expanders and Randomized Constructions.

**Place:** Fridays at 1:30pm in CSE 674 ("the Irish room").

## Contents

## Schedule

Subject | Speaker | Date |
---|---|---|

Quantum Expanders: Motivation and Construction | Isaac | March 30 |

Continue Review | Kamil | April 6 |

Continue Review | Kamil | April 13 |

Quantum expanders from any classical Cayley graph expander | Kevin | April 20 |

Random Unitaries Give Quantum Expanders, Slides | Isaac | April 27 |

Quantum Expander States, Slides | Isaac | May 11 |

Classical and Quantum Tensor Product Expanders | Kevin | May 11 |

TPEs and Solovay-Kitaev | Kevin | May 25 |

Jun 1 | ||

## Papers

### Review and Introduction

May 2010: **Quantum Expanders: Motivation and Construction** - Ben-Aroya, Schwartz, Ta-Shma

*"We deﬁne quantum expanders in a natural way and give two constructions of quantum expanders, both based on classical expander constructions."*

http://theoryofcomputing.org/articles/v006a003/

June 2003: **Randomizing quantum states: Constructions and applications** - Hayden, Leung, Shor, Winter

*"The construction of a perfectly secure private quantum channel in dimension d is known to require 2 log d shared random key bits between the sender and receiver. We show that if only near-perfect security is required, the size of the key can be reduced by a factor of two."*

http://arxiv.org/abs/quant-ph/0307104 , http://arxiv.org/abs/0802.4193

### Expander Constructions

Jun 2007: **Random Unitaries Give Quantum Expanders** - M. B. Hastings

*"We show that randomly choosing the matrices in a completely positive map from the unitary group gives a quantum expander. "*

http://arxiv.org/abs/0706.0556

Sep 2007: **Quantum expanders from any classical Cayley graph expander** - A. W. Harrow

*"We give a simple recipe for translating walks on Cayley graphs of a group G into a quantum operation on any irrep of G. "*

http://arxiv.org/abs/0709.1142 0709.1142

Apr 2008: **Classical and Quantum Tensor Product Expanders** - M. B. Hastings, A. W. Harrow

*"We introduce the concept of quantum tensor product expanders. These are expanders that act on several copies of a given system, where the Kraus operators are tensor products of the Kraus operator on a single system."*

http://arxiv.org/abs/0804.0011

Nov 2008: **Efficient Quantum Tensor Product Expanders and k-designs** - A. W. Harrow, R. A. Low

*"we give an efficient construction of constant-degree, constant-gap quantum k-tensor product expanders."*

http://arxiv.org/abs/0811.2597

### Entanglement

Sep 2004: **Entanglement in Random Subspaces** - Hayden

*"The selection of random subspaces plays a role in quantum information theory analogous to the role of random strings in classical information theory."*

http://arxiv.org/abs/quant-ph/0409157

July 2004: **Aspects of generic entanglement** - Hayden, Leung, Winter

'"We study entanglement and other correlation properties of random states in high-dimensional bipartite systems."'

http://arxiv.org/abs/quant-ph/0407049

Jan 2007: **Entropy and Entanglement in Quantum Ground States** - M.B. Hastings

'"We prove that there exist gapped one-dimensional local Hamiltonians such that the entropy is exponentially large in the correlation length"'

http://arxiv.org/abs/cond-mat/0701055

### Additional Topics

Jun 2006: **The mother of all protocols: Restructuring quantum information's family tree** - Abeyesinghe, Devetak, Hayden, Winter

http://arxiv.org/abs/quant-ph/0606225

Oct 2010: **From Low-Distortion Norm Embeddings to Explicit Uncertainty Relations and Efficient Information Locking** - Fawzi, Hayden, Sen

http://arxiv.org/abs/1010.3007

Oct 2009: **Non-additivity of Renyi entropy and Dvoretzky's Theorem** - Aubrun, Szarek, Werner

http://arxiv.org/abs/0910.1189

Mar 2010: **Hastings' additivity counterexample via Dvoretzky's theorem** - Aubrun, Szarek, Werner

http://arxiv.org/abs/1003.4925

Jun 2011: **Entanglement thresholds for random induced states** - Aubrun, Szarek, Ye

http://arxiv.org/abs/1106.2264

Nov 2011: **Towards the fast scrambling conjecture** - Lashkari, Stanford, Hastings, Osborne, Hayden

http://arxiv.org/abs/1111.6580

## Organizers

**Organizer(1):** Isaac Crosson

**Organizer(2):** Kamil Michnicki

**Faculty Advisor:** Aram Harrow