Program
Invited Speakers
Accepted Talks
 Andris Ambainis and Janis Iraids. Provable Advantage for Quantum Strategies in Random Symmetric XOR Games
 Andris Ambainis, Jānis Iraids and Juris Smotrovs. Exact quantum query complexity of EXACT and THRESHOLD
 Salman Beigi, Jianxin Chen, Markus Grassl, Zhengfeng Ji, Qiang Wang and Bei Zeng. Symmetries of Codeword Stabilized Quantum Codes
 Gonzalo de La Torre Carazo, Chirag Dhara and Antonio Acín. Certifying the absence of apparent randomness under minimal assumptions
 Andrew M. Childs, Robin Kothari, Maris Ozols and Martin Roetteler. Easy and hard functions for the Boolean hidden shift problem
 Giulio Chiribella, Giacomo D'Ariano and Martin Roetteler. How many copies are needed for gate discrimination?
 Patrick Coles, Mario Berta and Stephanie Wehner. Entanglementassisted guessing of complementary measurement outcomes
 Alessandro Cosentino, Robin Kothari and Adam Paetznick. Dequantizing readonce quantum formulas
 Guillaume DuclosCianci and David Poulin. Kitaev's Z_dCode Thresholds Estimate via a Renormalization Group Decoder
 Guillaume DuclosCianci and Krysta Svore. Distillation of NonStabilizer States for Universal Quantum Computation
 Nathaniel Johnston. The Minimum Size of Qubit Unextendible Product Bases
 Joel Klassen, Jianxin Chen and Bei Zeng. Universal Entanglers for Bosonic and Fermionic Systems
 Greg Kuperberg. Another subexponentialtime quantum algorithm for the dihedral hidden subgroup problem
 Daniel Lercher, Géza Giedke and Michael M. Wolf. Superactivation for Gaussian channels requires squeezing
 Noah Linden, František Matúš, Mary Beth Ruskai and Andreas Winter. The Quantum Entropy Cone of Stabiliser States
 Anne Marin, Damian Markham and Simon Perdrix. Access structure in a graph in higher dimension and applications to secret sharing protocols
 Carl Miller and Yaoyun Shi. Optimal robust selftesting by binary nonlocal XOR games
 David Reeb and Michael M. Wolf. General microscopic proof of Landauer's Principle and finitesize improvements
 David Rosenbaum. Optimal Quantum Circuits for NearestNeighbor Architectures
 Kerem Halil Shah and Daniel Oi. Ancilla Driven Quantum Computation with arbitrary entangling strength
 Mark Wilde, Olivier LandonCardinal and Patrick Hayden. Towards efficient decoding of classicalquantum polar codes
 Yuxiang Yang and Giulio Chiribella. Is global asymptotic cloning state estimation?
 Kevin Zatloukal. Classical and Quantum Algorithms for Testing Equivalence of Group Extensions
Accepted Posters
 Sakineh Ashourisheikhi and Swarnamala Sirsi. Entanglement classes of Nqubits Mixed symmetric states
 Yuri Campbell and José Roberto Castilho Piqueira. Optimal Classical Hierarchical Correlation Quantification on Tripartite Mixed State Families
 Vanarsa Chiranjeevi, Indranil Chakrabarty and Kannan Srinathan. Fault tolerant establishment of Entanglement in arbitrary Quantum Networks
 Guanru Feng, Guofu Xu and Guilu Long. Experimental Realization of Nonadiabatic Holonomic Quantum Computation
 Christopher Granade, Christopher Ferrie, Nathan Wiebe and David Cory. Robust Online Hamiltonian Learning
 Matty Hoban, Joel Wallman, Hussain Anwar, Nairi Usher, Robert Raussendorf and Dan Browne. Does quantum speedup require quantum nonlocality?
 Xingtong Liu, Jian Wang, Chaojing Tang and Chen Zhang. Passive Error Rejecting Scheme for Qubit Transmission against Collective Noise
 Easwar Magesan and Paola Cappellaro. Experimentally efficient methods for estimating the performance of quantum measurements
 Carl Miller, Yaoyun Shi, Mary Wootters and Brett Hemenway. On optimal entanglement assisted oneshot classical communication
 Nikolay Nahimov and Dmitry Kravchenko. Grover's algorithm with faulty and nonfaulty marked items
 Alex Parent, Dmitri Maslov, Marc Burns and Jacob Parker. Quantum Circuit Viewer
 Gerardo PazSilva, Jason Dominy and Daniel Lidar. Quantum Control and the FaultTolerance threshold
 Katja Ried and Robert W. Spekkens. Generalized tomography for states and processes
 Akira Saitoh. Realistic cost for the model of coherent computing
 Hiroyasu Tajima. A New Version of the Second Law of Information Thermodynamics Using Entanglement Measure
 Amit Tribedi. QIT Measures in the vicinity of a Quantum Critical Point
 Peter Vrana, David Reeb, Daniel Reitzner and Michael M. Wolf. Faultignorant Quantum Search
Timetable
May 21, 2013 (Tuesday) 
08:00  09:00 
Registration 
08:30  09:00 
Breakfast 
09:00  09:40 
[invited talk] Thomas Vidick.
The Complexity of Entangled Games 
09:45  10:05 
Carl Miller and Yaoyun Shi.
Optimal robust selftesting by binary nonlocal XOR games 
10:10  10:30 
Andris Ambainis and Janis Iraids.
Provable Advantage for Quantum Strategies in Random Symmetric XOR Games 
10:30  11:00 
Coffee Break 
11:00  11:20 
Kevin Zatloukal.
Classical and Quantum Algorithms for Testing Equivalence of Group Extensions 
11:25  11:45 
Andrew M. Childs, Robin Kothari, Maris Ozols and Martin Roetteler.
Easy and hard functions for the Boolean hidden shift problem 
11:50  12:10 
Greg Kuperberg.
Another subexponentialtime quantum algorithm for the dihedral hidden subgroup problem 
12:10  14:00 
Lunch break 
14:00  14:40 
[invited talk] Jop Briët.
Entanglementassisted Zeroerror Sourcechannel Coding 
14:45  15:05 
David Reeb and Michael M. Wolf.
General microscopic proof of Landauer's Principle and finitesize improvements 
15:10  15:30 
Patrick Coles, Mario Berta and Stephanie Wehner.
Entanglementassisted guessing of complementary measurement outcomes 
15:30  16:00 
Coffee break 
16:00  16:20 
Salman Beigi, Jianxin Chen, Markus Grassl, Zhengfeng Ji, Qiang Wang and Bei Zeng.
Symmetries of Codeword Stabilized Quantum Codes 
16:25  16:50 
Mark Wilde, Olivier LandonCardinal and Patrick Hayden.
Towards efficient decoding of classicalquantum polar codes 
16:50  17:10 
Guillaume DuclosCianci and David Poulin.
Kitaev's Z_dCode Thresholds Estimate via a Renormalization Group Decoder 
May 22, 2013 (Wednesday) 
08:30  09:00 
Breakfast 
09:00  09:40 
[invited talk] Iordanis Kerenidis.
Quantum Communication Complexity 
09:45  10:05 
Andris Ambainis, Jānis Iraids and Juris Smotrovs.
Exact quantum query complexity of EXACT and THRESHOLD 
10:10  10:30 
David Rosenbaum.
Optimal Quantum Circuits for NearestNeighbor Architectures 
10:30  11:00 
Coffee break 
11:00  11:20 
Noah Linden, František Matúš, Mary Beth Ruskai and Andreas Winter.
The Quantum Entropy Cone of Stabiliser States 
11:25  11:45 
Daniel Lercher, Géza Giedke and Michael M. Wolf.
Superactivation for Gaussian channels requires squeezing 
11:50  12:10 
Giulio Chiribella, Giacomo D'Ariano and Martin Roetteler.
How many copies are needed for gate discrimination? 
12:10  14:00 
Lunch break 
14:00  14:40 
[invited talk] Aram Harrow.
Separable states, the unique games conjecture and monogamy of entanglement 
14:45  15:05 
Joel Klassen, Jianxin Chen and Bei Zeng.
Universal Entanglers for Bosonic and Fermionic Systems 
15:10  15:30 
Nathaniel Johnston.
The Minimum Size of Qubit Unextendible Product Bases 
15:35  15:55 
Guillaume DuclosCianci and Krysta Svore.
Distillation of NonStabilizer States for Universal Quantum Computation 
16:00  18:30 
Coffee Break, Rump Session, Poster Session 
18:30  
Banquet 
May 23, 2012 (Thursday) 
08:30  09:00 
Breakfast 
09:00  09:40 
[invited talk] Stephanie Wehner.
Twoparty Quantum Cryptography  Results and Challenges 
09:45  10:05 
Anne Marin, Damian Markham and Simon Perdrix.
Access structure in a graph in higher dimension and applications to secret sharing protocols 
10:10  10:30 
Alessandro Cosentino, Robin Kothari and Adam Paetznick.
Dequantizing readonce quantum formulas 
10:30  11:00 
Coffee break 
11:00  11:20 
Gonzalo de La Torre Carazo, Chirag Dhara and Antonio Acín.
Certifying the absence of apparent randomness under minimal assumptions 
11:25  11:45 
Yuxiang Yang and Giulio Chiribella.
Is global asymptotic cloning state estimation? 
11:50  12:10 
Kerem Halil Shah and Daniel Oi.
Ancilla Driven Quantum Computation with arbitrary entangling strength 
12:10  
Closing 
Abstracts of invited talks:
Jop Briët (CWI, Amsterdam):
Entanglementassisted Zeroerror Sourcechannel Coding
This talk is about the use of entanglement in the classical zeroerror sourcechannel coding problem. Here, Alice and Bob are connected by a noisy classical oneway communication channel and are given correlated inputs from a random source. Their goal is for Bob to learn Alice's input while using the channel as few times as possible. The stiff zeroerror constraint leads to beautiful connections to combinatorics (such as graph theory, the polynomial method and designs) and semidefinite programming (such as the celebrated Lovasz theta number). Our main result shows for the first time that shared entanglement can allow for an unbounded decrease in the asymptotic rate of classical sourcechannel codes.
Aram Harrow (MIT, Cambridge):
Separable states, the unique games conjecture and monogamy of entanglement
The quantum separability problemdetermining when a density matrix
is entangled or when it is separableis an old problem in quantum
information theory. Although solving this problem to accuracy
inversepolynomial in dimension is NPhard, only loose bounds are
known on the complexity of the constanterror case. In this talk, I
will describe some surprising connections between the quantum
separability problem and a major open problem in classical computer
science known as the unique games conjecture. Remarkably, even the
proposed solutions to both problems turn out to be essentially the
same, so that bounds on the monogamy of entanglement (aka de Finetti
theorems) can be used to analyze the performance of classical
algorithms. I will also describe conjectured monogamy bounds that are
an alternate route to resolving the unique games conjecture.
Based on 1205.4484 and 1210.6367.
Iordanis Kerenidis (CNRS  Université Paris DiderotParis 7, Paris):
Quantum Communication Complexity
Communication complexity studies how much classical or quantum communication is necessary to solve a distributed task. It has numerous applications in computer science, including in data structures, circuit lower bounds, streaming algorithms, VLSI design, etc. In this model, two parties, Alice with input x and Bob with input y, collaborate to solve some computational problem that depends on both x and y. Their goal is to do this with minimal communication. The superiority of quantum communication has been proven in various models of communication complexity. Namely, there exist distributed computational problems that can be resolved with an exponentially smaller communication overhead by agents who have the ability to communicate via a quantum channel rather than a classical one. In the first part of the talk, we will review some of these separations and their widerange applications, including for nonlocality, quantum cryptography, quantum extractors etc. We will then focus on the different lower bound techniques for classical and quantum communication complexity and their respective power. We will see how the study of Bell inequality violations enables us to recast some wellknown classical techniques in a more intuitive way and to prove new strong relations between communication and information complexity.
Thomas Vidick (MIT, Cambridge):
The Complexity of Entangled Games
Multiplayer games, from their use in cryptography to their role in the proof of the PCP theorem, play a central role in modern theoretical computer science. Players allowed to use entanglement can increase their odds of winning by exploiting its nonlocal correlations: how does it affect the properties of the game? What do games tell us about the fundamental strengths and limitations of entanglement? In this talk I will present some recent result on the complexity of entangled games. I will show that the class MIP*(3) of languages having threeprover entangled proof systems contains the class NEXP. This resolves a longstanding open question in quantum complexity by showing that entangledprover proof systems are no less powerful than their classical counterparts. Building upon this characterization I will also present some recent results showing that approximating the largest possible violation by quantum mechanics of a tripartite Bell correlation inequality, within a factor (2eps), is NPhard. Since the largest possible violation of a bipartite correlation inequality can be computed in polynomial time, this result shows a striking complexitytheoretic distinction between bipartite and tripartite inequalities.
Stephanie Wehner (National University of Singapore, Singapore):
Twoparty Quantum Cryptography  Results and Challenges
After long years of exchanging keys, Alice and Bob had a falling out and no longer trust each other. The goal of twoparty quantum cryptography is to enable them to nevertheless solve tasks in cooperation. A classic example of such a task is bit commitment. Unfortunately, it has long been known that even using quantum communication, we cannot implement bit commitment perfectly. Is this the end for Alice and Bob? In this talk we will review the impossible, the possible and a number of assumptions that lead to security for twoparty quantum cryptography. We will discuss some general properties of assumptions that yield security, and review some of the many exciting open problems in this area.
