TQC 2013
General Information Scope Submissions Registration Program Committees Travel and Local Info

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. Entanglement-assisted guessing of complementary measurement outcomes
  • Alessandro Cosentino, Robin Kothari and Adam Paetznick. Dequantizing read-once quantum formulas
  • Guillaume Duclos-Cianci and David Poulin. Kitaev's Z_d-Code Thresholds Estimate via a Renormalization Group Decoder
  • Guillaume Duclos-Cianci and Krysta Svore. Distillation of Non-Stabilizer 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 subexponential-time quantum algorithm for the dihedral hidden subgroup problem
  • Daniel Lercher, Géza Giedke and Michael M. Wolf. Super-activation 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 self-testing by binary nonlocal XOR games
  • David Reeb and Michael M. Wolf. General microscopic proof of Landauer's Principle and finite-size improvements
  • David Rosenbaum. Optimal Quantum Circuits for Nearest-Neighbor Architectures
  • Kerem Halil Shah and Daniel Oi. Ancilla Driven Quantum Computation with arbitrary entangling strength
  • Mark Wilde, Olivier Landon-Cardinal and Patrick Hayden. Towards efficient decoding of classical-quantum 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 N-qubits 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 one-shot classical communication
  • Nikolay Nahimov and Dmitry Kravchenko. Grover's algorithm with faulty and non-faulty marked items
  • Alex Parent, Dmitri Maslov, Marc Burns and Jacob Parker. Quantum Circuit Viewer
  • Gerardo Paz-Silva, Jason Dominy and Daniel Lidar. Quantum Control and the Fault-Tolerance 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. Fault-ignorant 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 self-testing 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 subexponential-time quantum algorithm for the dihedral hidden subgroup problem
12:10 - 14:00 Lunch break
14:00 - 14:40 [invited talk] Jop Briët.
Entanglement-assisted Zero-error Source-channel Coding
14:45 - 15:05 David Reeb and Michael M. Wolf.
General microscopic proof of Landauer's Principle and finite-size improvements
15:10 - 15:30 Patrick Coles, Mario Berta and Stephanie Wehner.
Entanglement-assisted 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 Landon-Cardinal and Patrick Hayden.
Towards efficient decoding of classical-quantum polar codes
16:50 - 17:10 Guillaume Duclos-Cianci and David Poulin.
Kitaev's Z_d-Code 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 Nearest-Neighbor 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.
Super-activation 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 Duclos-Cianci and Krysta Svore.
Distillation of Non-Stabilizer 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.
Two-party 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 read-once 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):
Entanglement-assisted Zero-error Source-channel Coding

This talk is about the use of entanglement in the classical zero-error source-channel coding problem. Here, Alice and Bob are connected by a noisy classical one-way 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 zero-error 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 source-channel codes.


Aram Harrow (MIT, Cambridge):
Separable states, the unique games conjecture and monogamy of entanglement

The quantum separability problem---determining when a density matrix is entangled or when it is separable---is an old problem in quantum information theory. Although solving this problem to accuracy inverse-polynomial in dimension is NP-hard, only loose bounds are known on the complexity of the constant-error 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 Diderot-Paris 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 wide-range applications, including for non-locality, 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 well-known 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 three-prover entangled proof systems contains the class NEXP. This resolves a long-standing open question in quantum complexity by showing that entangled-prover 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 (2-eps), is NP-hard. Since the largest possible violation of a bipartite correlation inequality can be computed in polynomial time, this result shows a striking complexity-theoretic distinction between bipartite and tripartite inequalities.


Stephanie Wehner (National University of Singapore, Singapore):
Two-party 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 two-party 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 two-party 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.


| General Information | Scope | Submissions | Registration | Program | Committees | Travel and Local Info|