Difference between revisions of "Journal Club Winter 2013"

From Quantum Computing Theory Group
Jump to: navigation, search
(Created page with "This quarter we will be focusing on Quantum Information Theory not Quantum Expanders, but the editing is yet to be completed so until then, confusion shall reign. '''Place:'...")
 
 
(29 intermediate revisions by 3 users not shown)
Line 1: Line 1:
−
This quarter we will be focusing on Quantum Information Theory not Quantum Expanders, but the editing is yet to be completed so until then, confusion shall reign.  
+
This season we will be focusing on quantum information theory.  Classical information theory is ubiquitous in science and mathematics with applications ranging from characterizing ensembles of particles to answering how many bits can be sent reliably over a noisy channel.  It is even useful as an estimation technique for gauging the difficulty of a research problem. For instance, one may ask, how many bits are necessary to specify a quantum circuit acting on n bits(with bit flips Toffoli and Hadamard gates) and how does that compare to the number of bits required to specify a classical circuit(just bit flips and Tofolli gates)? This question already leads to a naive bound on the average quantum speed-up attainable over classical circuits, e.g. there isn't enough information in the specification of constant depth quantum circuits to characterize all reversible function on n-bits and so we conclude that there are deterministic functions that require more than constant quantum depth. Although this example is rather simple, it already gives the researcher some perspective about a very broad and difficult problem, that of finding quantum speed-ups. If classical information theory can quickly give us insight into the classical resources needed for a task, perhaps quantum information theory would be equally useful in giving us insight into the quantum resources needed for a quantum task?
  
−
'''Place:''' Fridays at 1:30pm in CSE 674 ("the Irish room").
+
'''Place and Time:''' Thursday at 2:45pm in the Cosman room(6C-442) or in cyberspace via Google Hangouts.
 
==Schedule==
 
==Schedule==
 
{|border="1"
 
{|border="1"
Line 8: Line 8:
 
!Date
 
!Date
 
|-
 
|-
−
|[http://theoryofcomputing.org/articles/v006a003/ Quantum Expanders: Motivation and Construction]
+
|[http://arxiv.org/abs/quant-ph/9511030 Concentrating Partial Entanglement with Local Operations] and [http://quantum.cs.washington.edu/wiki/uploads/f/fd/ConcentratingPartialEntanglement.pdf lecture notes]
−
|Isaac
+
|Kamil Michnicki
−
|March 30
+
|2/21
 
|-
 
|-
−
|[http://theoryofcomputing.org/articles/v006a003/ Continue Review]
+
|[http://arxiv.org/abs/quant-ph/0404076 Consequences and Limits of Nonlocal Strategies]
−
|Kamil
+
|Henry Yuen
−
|April 6
+
|2/28
 
|-
 
|-
−
|Continue Review
+
|Quantum [http://arxiv.org/abs/quant-ph/0703069 De Finetti Theorems] and [http://arxiv.org/abs/1210.6367 recent work]
−
|Kamil
+
|Aram Harrow
−
|April 13
+
|3/7
 
|-
 
|-
−
|[http://arxiv.org/abs/0709.1142 Quantum expanders from any classical Cayley graph expander]
+
|[http://arxiv.org/abs/1206.5236 Quantum Compiling]
−
|Kevin
+
|Vadym Kliuchnikov
−
|April 20
+
|3/14
 
|-
 
|-
−
|[http://arxiv.org/abs/0706.0556 Random Unitaries Give Quantum Expanders], [[:media:RandomUnitariesQuantumExpanders-QCJC-printout.pdf | Slides]]
+
|[http://arxiv.org/abs/quant-ph/0512247 Quantum state merging] with [http://arxiv.org/abs/quant-ph/0606225 background]
−
|Isaac
+
|Cedric Yen-Yu Lin
−
|April 27
+
|3/21
 
|-
 
|-
−
|[http://arxiv.org/abs/cond-mat/0701055 Quantum Expander States], [[:media:QuantumExpanderStates-QCJC.pdf‎ | Slides]]
+
|[http://arxiv.org/abs/0809.3019 Post-selection technique for quantum channels with applications to quantum cryptography]
−
|Isaac
+
|Shelby Kimmel
−
|May 11
+
|3/28
 
|-
 
|-
−
|[http://arxiv.org/abs/0804.0011 Classical and Quantum Tensor Product Expanders]
+
|[]
−
|Kevin
+
|????
−
|May 11
+
|4/4
 
|-
 
|-
−
|[http://arxiv.org/abs/0804.0011 TPEs and Solovay-Kitaev]
+
|[]
−
|Kevin
+
|Isaac Crosson
−
|May 25
+
|4/11
 
|-
 
|-
 +
|[]
 
|
 
|
−
|
+
|4/18
−
|Jun 1
 
 
|-
 
|-
 +
|[]
 
|
 
|
−
|
+
|4/25
−
|
 
−
|-
 
 
|}
 
|}
  
 
==Papers==
 
==Papers==
−
===Review and Introduction===
+
===General Background===
−
May 2010: '''Quantum Expanders: Motivation and Construction''' - Ben-Aroya, Schwartz, Ta-Shma<br/>
+
[http://arxiv.org/abs/1106.1445 From Classical to Quantum Shannon Theory] - A thorough and up-to-date (2012) free textbook by Mark Wilde. 
−
''"We define quantum expanders in a natural way and give two constructions of quantum expanders, both based on classical expander constructions."''<br/>
 
−
http://theoryofcomputing.org/articles/v006a003/
 
  
−
June 2003: '''Randomizing quantum states: Constructions and applications''' - Hayden, Leung, Shor, Winter<br/>
+
[http://www.youtube.com/user/classxteam#p/c/51268CD78FA180BF/0/yhvqwolUnHc Video lectures] by Thomas Cover on classical information theory.
−
''"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."''<br/>
 
−
http://arxiv.org/abs/quant-ph/0307104 ,  http://arxiv.org/abs/0802.4193
 
  
−
===Expander Constructions===
+
Nielson and Chuang, Quantum Computing and Quantum Information: Part III
−
Jun 2007: '''Random Unitaries Give Quantum Expanders''' - M. B. Hastings<br/>
 
−
''"We show that randomly choosing the matrices in a completely positive map from the unitary group gives a quantum expander. "''<br/>
 
−
http://arxiv.org/abs/0706.0556
 
  
−
Sep 2007: '''Quantum expanders from any classical Cayley graph expander''' - A. W. Harrow<br/>
+
===Papers===
−
''"We give a simple recipe for translating walks on Cayley graphs of a group G into a quantum operation on any irrep of G. "''<br/>
 
−
http://arxiv.org/abs/0709.1142 0709.1142
 
  
−
Apr 2008: '''Classical and Quantum Tensor Product Expanders''' - M. B. Hastings, A. W. Harrow<br/>
+
'''April 1996:''' [http://arxiv.org/abs/quant-ph/9604024 Mixed State Entanglement and Quantum Error Correction] - C. Bennett, D. DiVincenzo, J. Smolin, W. Wootters
−
''"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."''<br/>
 
−
http://arxiv.org/abs/0804.0011
 
  
−
Nov 2008: '''Efficient Quantum Tensor Product Expanders and k-designs''' - A. W. Harrow, R. A. Low<br/>
+
'''Sept 2003:''' [http://arxiv.org/abs/quant-ph/0309110 Secure key from bound entanglement] K. Horodecki, M. Horodecki, P. Horodecki, J. Oppenheim
−
''"we give an efficient construction of constant-degree, constant-gap quantum k-tensor product expanders."''<br/>
 
−
http://arxiv.org/abs/0811.2597
 
  
−
===Entanglement===
+
'''July 2004:''' [http://arxiv.org/abs/quant-ph/0407049 Aspects of generic entanglement] - P. Hayden, D. Leung, A. Winter
  
−
Sep 2004: '''Entanglement in Random Subspaces''' - Hayden<br/>
+
'''Dec 2005:''' [http://arxiv.org/abs/quant-ph/0512247 Quantum state merging and negative information] - M. Horodecki, J. Oppenheim, A. Winter
−
''"The selection of random subspaces plays a role in quantum information theory analogous to the role of random strings in classical information theory."''<br/>
 
−
http://arxiv.org/abs/quant-ph/0409157
 
  
−
July 2004: '''Aspects of generic entanglement''' - Hayden, Leung, Winter<br/>
+
'''June 2006:''' [http://arxiv.org/abs/quant-ph/0606225 The mother of all protocols: Restructuring quantum information's family tree] - A. Abeyesinghe, I. Devetak, P. Hayden, A. Winter
−
'"We study entanglement and other correlation properties of random states in high-dimensional bipartite systems."'<br/>
 
−
http://arxiv.org/abs/quant-ph/0407049
 
  
−
Jan 2007: '''Entropy and Entanglement in Quantum Ground States''' - M.B. Hastings<br/>
+
'''March 2007:''' [http://arxiv.org/abs/quant-ph/0703069 Symmetry implies independence] - R. Renner
−
'"We prove that there exist gapped one-dimensional local Hamiltonians such that the entropy is exponentially large in the correlation length"'<br/>
 
−
http://arxiv.org/abs/cond-mat/0701055
 
  
−
===Additional Topics===
+
'''Aug 2008:''' [http://arxiv.org/abs/0807.1338 The operational meaning of min- and max-entropy] - R. Koenig, R. Renner, C. Schaffner
  
−
Jun 2006: '''The mother of all protocols: Restructuring quantum information's family tree''' - Abeyesinghe, Devetak, Hayden, Winter<br/>
+
'''Sept 2008:''' [http://arxiv.org/abs/0809.3019 Post-selection technique for quantum channels with applications to quantum cryptography] - M. Christandl, R. Koenig, R. Renner
−
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<br/>
+
'''April 2009:''' [http://arxiv.org/abs/0904.0281 A Generalization of Quantum Stein's Lemma] - F. Brandao, M. Plenio
−
http://arxiv.org/abs/1010.3007
 
  
−
Oct 2009: '''Non-additivity of Renyi entropy and Dvoretzky's Theorem''' - Aubrun, Szarek, Werner<br/>
+
'''Dec 2009:''' [http://arxiv.org/abs/0912.5537 Quantum Reverse Shannon Theorem] - C. Bennett, I. Devetak, A. Harrow, P. Shor, A. Winter
−
http://arxiv.org/abs/0910.1189
 
  
−
Mar 2010: '''Hastings' additivity counterexample via Dvoretzky's theorem''' - Aubrun, Szarek, Werner<br/>
+
'''March 2010:''' [http://arxiv.org/abs/1003.4925 Hastings' additivity counterexample via Dvoretzky's theorem] - G. Aubrun, S. Szarek, E. Werner
−
http://arxiv.org/abs/1003.4925
 
  
−
Jun 2011: '''Entanglement thresholds for random induced states''' - Aubrun,  Szarek, Ye<br/>
+
'''March 2010:''' [http://arxiv.org/abs/1003.4994 Weak Decoupling Duality and Quantum Identification] - P. Hayden, A. Winter
−
http://arxiv.org/abs/1106.2264
 
  
−
Nov 2011: '''Towards the fast scrambling conjecture''' - Lashkari, Stanford, Hastings, Osborne, Hayden<br/>
+
'''Oct 2010:''' [http://arxiv.org/abs/1010.3007 From Low-Distortion Norm Embeddings to Explicit Uncertainty Relations and Efficient Information Locking] - O. Fawzi, P. Hayden, P. Sen
−
http://arxiv.org/abs/1111.6580
 
  
 
==Organizers==
 
==Organizers==
  
−
'''Organizer(1):''' [[User:Icrosson|Isaac Crosson]]
+
'''Organizer:''' [[User:kpm3|Kamil Michnicki]]
  
−
'''Organizer(2):''' [[User:kpm3|Kamil Michnicki]]
+
'''Wiki Page:''' [[User:Icrosson|Isaac Crosson]]
  
−
'''Faculty Advisor:''' [http://www.cs.washington.edu/homes/aram/ Aram Harrow]
+
'''Faculty Advisor:''' [http://www.mit.edu/~aram/ Aram Harrow]

Latest revision as of 19:32, 28 March 2013

This season we will be focusing on quantum information theory. Classical information theory is ubiquitous in science and mathematics with applications ranging from characterizing ensembles of particles to answering how many bits can be sent reliably over a noisy channel. It is even useful as an estimation technique for gauging the difficulty of a research problem. For instance, one may ask, how many bits are necessary to specify a quantum circuit acting on n bits(with bit flips Toffoli and Hadamard gates) and how does that compare to the number of bits required to specify a classical circuit(just bit flips and Tofolli gates)? This question already leads to a naive bound on the average quantum speed-up attainable over classical circuits, e.g. there isn't enough information in the specification of constant depth quantum circuits to characterize all reversible function on n-bits and so we conclude that there are deterministic functions that require more than constant quantum depth. Although this example is rather simple, it already gives the researcher some perspective about a very broad and difficult problem, that of finding quantum speed-ups. If classical information theory can quickly give us insight into the classical resources needed for a task, perhaps quantum information theory would be equally useful in giving us insight into the quantum resources needed for a quantum task?

Place and Time: Thursday at 2:45pm in the Cosman room(6C-442) or in cyberspace via Google Hangouts.

Schedule

Subject Speaker Date
Concentrating Partial Entanglement with Local Operations and lecture notes Kamil Michnicki 2/21
Consequences and Limits of Nonlocal Strategies Henry Yuen 2/28
Quantum De Finetti Theorems and recent work Aram Harrow 3/7
Quantum Compiling Vadym Kliuchnikov 3/14
Quantum state merging with background Cedric Yen-Yu Lin 3/21
Post-selection technique for quantum channels with applications to quantum cryptography Shelby Kimmel 3/28
[] ???? 4/4
[] Isaac Crosson 4/11
[] 4/18
[] 4/25

Papers

General Background

From Classical to Quantum Shannon Theory - A thorough and up-to-date (2012) free textbook by Mark Wilde.

Video lectures by Thomas Cover on classical information theory.

Nielson and Chuang, Quantum Computing and Quantum Information: Part III

Papers

April 1996: Mixed State Entanglement and Quantum Error Correction - C. Bennett, D. DiVincenzo, J. Smolin, W. Wootters

Sept 2003: Secure key from bound entanglement K. Horodecki, M. Horodecki, P. Horodecki, J. Oppenheim

July 2004: Aspects of generic entanglement - P. Hayden, D. Leung, A. Winter

Dec 2005: Quantum state merging and negative information - M. Horodecki, J. Oppenheim, A. Winter

June 2006: The mother of all protocols: Restructuring quantum information's family tree - A. Abeyesinghe, I. Devetak, P. Hayden, A. Winter

March 2007: Symmetry implies independence - R. Renner

Aug 2008: The operational meaning of min- and max-entropy - R. Koenig, R. Renner, C. Schaffner

Sept 2008: Post-selection technique for quantum channels with applications to quantum cryptography - M. Christandl, R. Koenig, R. Renner

April 2009: A Generalization of Quantum Stein's Lemma - F. Brandao, M. Plenio

Dec 2009: Quantum Reverse Shannon Theorem - C. Bennett, I. Devetak, A. Harrow, P. Shor, A. Winter

March 2010: Hastings' additivity counterexample via Dvoretzky's theorem - G. Aubrun, S. Szarek, E. Werner

March 2010: Weak Decoupling Duality and Quantum Identification - P. Hayden, A. Winter

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

Organizers

Organizer: Kamil Michnicki

Wiki Page: Isaac Crosson

Faculty Advisor: Aram Harrow

Retrieved from "http://quantum.cs.washington.edu/wiki/index.php?title=Journal_Club_Winter_2013&oldid=1578"