## See home page for slides for talks!
**Invited Talks**
- Andrew Childs (Waterloo)
*Universal computation by quantum walk*
In some of the earliest work on quantum mechanical computers, Feynman showed how to implement universal quantum computation by the dynamics of a time-independent Hamiltonian. I show that this remains possible even if the Hamiltonian is restricted to be a sparse matrix with all entries equal to 0 or 1, i.e., the adjacency matrix of a low-degree graph. Thus quantum walk can be regarded as a universal computational primitive, with any desired quantum computation encoded entirely in some underlying graph. The main idea of the construction is to implement quantum gates by scattering processes
- Avinatan Hassidim (Jerusalem)
*Multi Prover Interactive Proofs with Communicating Provers *
We introduce a variant of Quantum Multi Prover Interactive Proofs (QMIP), where the provers do not share entanglement, the communication between the verifier and the provers is quantum, but the provers are unlimited in the classical communication between them. At first, this model may seem very weak, as provers who exchange information seem to be equivalent in power to a single prover. This in fact is not the case - we show that any language in NEXP can be recognized in this model efficiently, with just two provers and two rounds of communication, with a constant completeness-soundness gap.
The main idea is not to bound the information the provers exchange with each other, as in the classical case, but rather to prove that any "cheating" strategy employed by the provers has constant probability to diminish the entanglement between the verifier and the provers by a constant amount. Detecting such reduction gives us the soundness proof. Similar ideas and techniques may help help with other models of Quantum MIP, including the dual question, of non communicating provers with unlimited entanglement.
Joint work with Michael Ben-Or and Haran Pilpel
- Matt Hastings (LANL)
*Area Laws for Quantum Many-Body Systems: Gapped One-Dimensional Systems Are in NP*
One of the basic problems in physics is approximating the ground state energy of a quantum many-body system. For arbitrary choice of local interactions, this problem is extremely difficult, even in one dimension where Aharonov, Gottesman, and Kempe and Irani showed that this problem is QMA-complete. However, many of the quantum ground states encountered in practice have a limited amount of entanglement. As I will explain, this makes it possible to efficiently represent the ground state of these systems on a classical computer. In the important case that the Hamiltonian has a spectral gap, I will explain a recent proof of an "area law" which bounds the entanglement entropy. This result implies that a certain promise problem for approximating the ground state energy of gapped one-dimensional Hamiltonians is in NP, while a similar problem for approximating the adiabatic evolution of such systems is in P.
*A Counter-example to Additivity*
There are four different additivity conjectures in quantum information theory, all of which were shown to be equivalent by Shor in 2004. These include the additivity of the Holevo capacity for sending classical information over a quantum channel, and the additivity of the minimum output entropy of a quantum channel. These conjectures relate to whether or not entanglement between different inputs to a quantum channel is useful to increase classical capacity or reduce output entropy. I will present a counter-example to the minimum output entropy conjecture, which implies that all of these additivity conjectures are false. The counter-example is based on a random construction of a channel with a large environment dimension and an even larger system dimension. I will relate this channel to recent work on quantum expanders, and I will propose a slightly weaker additivity conjecture which would give us a two-letter formula for capacity of channels invariant under complex conjugation.
- Charles Marcus (Harvard)
*Holding Quantum Information in Electron Spins*
This talk will review recent progress in the control of single electron spins in quantum dots. In GaAs, progress has been rapid, but may ultimately be limited by hyperfine coupling of electrons to nuclear spins of the host lattice [1]. It appears, though, that a variant on dynamic nuclear polarization can help reduce the hyperfine field fluctuations [2]. An alternative is to move out of GaAs, and consider materials with zero nuclear spin, where obviously hyperfine coupling is absent [3,4]. Work along both of these directions will be discussed. Research Supported by ARO/iARPA, the Department of Defense, and the NSF.
[1] A. C. Johnson, J. R. Petta, J. M. Taylor, A. Yacoby, M. D. Lukin, C. M. Marcus, M. P. Hanson, and A. C. Gossard, *Triplet-singlet spin relaxation via nuclei in a double quantum dot*, Nature **435**, 925 (2005); J. R. Petta, A. C. Johnson, J. M. Taylor, E. A. Laird, A. Yacoby, M. D. Lukin, C. M. Marcus, M. P. Hanson, and A. C. Gossard, *Coherent manipulation of coupled electron spins in semiconductor quantum dots*, Science **309**, 2180 (2005).
[2] D. J. Reilly, J. M. Taylor, J. R. Petta, C. M. Marcus, M. P. Hanson, and A. C. Gossard, *Suppressing spin qubit dephasing by nuclear state preparation*, Science **321**, 817-821 (2008).
[3] Y. J. Hu, H. O. H. Churchill, D. J. Reilly, J. Xiang, C. M. Lieber, and C. M. Marcus, *A Ge/Si heterostructure nanowire-based double quantum dot with integrated charge sensor*, Nature Nanotechnology **2**, 622-625 (2007);
[4] H. O. H. Churchill, A. J. Bestwick, J. W. Harlow, F. Kuemmeth, D. Marcos, C. H. Stwertka, S. K. Watson, and C. M. Marcus, *Electron-nuclear interaction in 13 C nanotube double quantum dots*, arXiv:0811.3239 (2008).
- Lluis Masanes (Barcelona)
*Device-independent security in QKD*
This talk is about secret key distribution from correlations that violate Bell inequalities. A security proof can be obtained from the assumption that arbitrarily-fast signaling between different subsystems is impossible. This assumption is imposed at the level of the outcome probabilities given the choice of observables, therefore, the scheme remains secure in situations where the honest parties distrust their quantum apparatuses.
- Graeme Smith (IBM, TJ Watson)
*Quantum Communication With Zero-Capacity Channels*
Communication over a noisy quantum channel introduces errors in the transmission that must be corrected. A fundamental bound on quantum error correction is the quantum capacity, which quantifies the amount of quantum data that can be sent. I will show how two quantum channels, each with a transmission capacity of zero, can have a nonzero capacity when used together. This unveils a rich structure in the theory of quantum communications, and points towards several new questions about communication and information in the physical world. This is work done jointly with Jon Yard.
## **Contributed Talks**
Note: the order in which papers are listed is not significant.
TEN 30-MINUTE TALKS
Amnon Ta-Shma. *Short seed extractors against quantum storage*
Fernando Brandao and Martin Plenio. *Quantum Stein's Lemma for
Correlated States and Asymptotic Entanglement Transformations*
Sandy Irani. *Ground States Entanglement in One Dimensional
Translationally-Invariant Quantum Systems*
Andris Ambainis. *Quantum algorithms are at most polynomially
faster than classical for any symmetric function*
Sergey Bravyi and Barbara Terhal. *A no-go theorem for a
two-dimensional self-correcting quantum memory based on stabilizer
codes*
Jop Briet, Harry Buhrman and Ben Toner. *A generalized
Grothendieck inequality and entanglement in XOR games*
Dmitry Gavinsky. *Classical Interaction Cannot Replace Quantum
Nonlocality*
Richard Cleve, Daniel Gottesman, Michele Mosca, Rolando Somma and
David Yonge-Mallo. *Efficient discrete-time simulations of
continuous-time quantum query algorithms*
Patrick Hayden and Andreas Winter. *The Fidelity Alternative and
Quantum Measurement Simulation*
Jean-Pierre Tillich. * Quantum Tornado codes*
TWENTY-TWO 20-MINUTE TALKS
Robert Koenig, Renato Renner and Christian Schaffner. *The
Operational Meaning of Min- and Max-Entropy *
Panos Aliferis and John Preskill. *Fault-tolerant quantum
computing against highly biased noise *
Tsuyoshi Ito, Hirotada Kobayashi and Keiji Matsumoto. *Oracularization and Two-Prover One-Round Interactive Proofs
against Nonlocal Strategies*
Robert Koenig, Ben Reichardt and Guifre Vidal. *Exact entanglement
renormalization for string-net models *
Ashley Montanaro and Tobias Osborne. *Quantum boolean functions *
Bill Rosgen. *Distinguishability of Random Unitary Channels *
Aram Harrow and Richard Low. *Efficient Quantum Tensor Product
Expanders and k-designs *
Avraham Ben-Aroya and Amnon Ta-Shma. *Approximate quantum error
correction for correlated noise *
Steve Flammia, David Gross, Jens Eisert, Michael Bremner, Andreas
Winter and Caterina Mora. *Most quantum states are useless for
measurement-based quantum computation *
Dmitry Gavinsky.* Predictive Quantum Learning *
Norbert Schuch and Frank Verstraete. *Interacting electrons,
Density Functional Theory, and Quantum Merlin Arthur *
Norbert Schuch, J. Ignacio Cirac and Frank Verstraete. *The
computational difficulty of finding MPS ground states *
Jens Eisert and David Gross. *Lieb Robinson bounds and "supersonic
quantum communication" *
Dan Shepherd and Michael Bremner. *Instantaneous Quantum
Computation *
Scott Aaronson and John Watrous. *Closed Timelike Curves Make
Quantum and Classical Computing Equivalent *
John Smolin and Graeme Smith.* Can non-private channels transmit
quantum information? *
Dejan Dukaric, Manuel Forster, Severin Winkler and Stefan Wolf. *On Non-Locality Distillation*
Dave Bacon, Wim van Dam and Alexander Russell. *Analyzing Quantum
Circuits Using the Least Action Principle *
Matthias Christandl, Dejan Dukaric, Robert Koenig, and Renato Renner. *Postselection-technique with applications to quantum cryptography and
the parallel repetition problem*
Gilles Brassard, Louis Salvail and Alain Tapp. *Key Distribution
and Oblivious Transfer à la Merkle*
Bryan Eastin and Emanuel Knill. *Restrictions on Transversal
Encoded Quantum Gate Sets *
Yi-Kai Liu. *Quantum Algorithms using the Curvelet Transform*
## **Posters**
- Dibwe Pierrot Musumbu and Francesco Petruccione.
*Quantum Walks and the Dispersion Relation in One Dimensional Many-particle System on Lattice*
- Arturo Fernandez, Andrei Klimov, Carlos Muñoz and Carlos Saavedra.
*Optimal quantum state reconstruction for cold trapped ions*
- Sevag Gharibian.
*Strong NP-Hardness of the Quantum Separability Problem*
- Yong Zhang.
*Quantum Error Correction Codes Via Jones Unitary Braid Representations at q=i*
- Berihu Gebrehiwot, Stefano Olivares and Matteo G A Paris.
*Bayesian estimation of qubit gates*
- Hang Dinh and Alexander Russell.
*Quantum and Randomized Lower Bounds for Local Search on Vertex-Transitive Graphs*
- Hui Khoon Ng and Lorenza Viola.
* Generalized entanglement as a unifying framework for fermionic entanglement*
- Masahito Hayashi.
* Universal coding for classical-quantum channel*
- Masahito Hayashi.
*Universal approximation of multi-copy states and universal quantum lossless data compression*
- Masahito Hayashi.
*Optimal ratio between phase basis and bit basis in QKD*
- Koji Azuma, Masato Koashi and Nobuyuki Imoto.
*Accessing genuinely quantum information without causing disturbance*
- Soojoon Lee, Jinhyoung Lee and Jaewan Kim.
*Any multipartite entangled state violating Bell inequality can be distilled for almost all bipartite splits*
- Jim Harrington, Mark Wilde and Todd Brun.
*Closed timelike curves enable perfect state distinguishability*
- Christopher Portmann and Akinori Kawachi.
*On the Power of Quantum Encryption Keys*
- Debbie Leung and Graeme Smith.
*Continuity of a quantum channel's capacities*
- Wim van Dam and Qingqing Yuan.
*Quantum Online Memory Checking*
- Masahito Hayashi.
*Discretization of group symmetric LOCC-detection*
- Masahito Hayashi.
*Group theoretical study of LOCC-detection of maximally entangled state using hypothesis testing*
- Dong Pyo Chi, Jeong Woon Choi, Kabgyun Jeong, Jeong San Kim, Taewan Kim and Soojoon Lee.
*Monogamy equality in $2\otimes 2 \otimes d$ quantum systems*
- Dong Pyo Chi, Jeong Woon Choi, Jeong San Kim, Taewan Kim and Soojoon Lee.
* Quantum states for perfectly secure secret sharing*
- Go Kato.
*Quantum cloning of qubits with orthogonal states as hints*
- Hari Krovi and Martin Roetteler.
*An Efficient Quantum Algorithm for the Hidden Subgroup Problem over Weyl-Heisenberg Groups*
- Min-Hsiu Hsieh and Mark Wilde.
*The Classically-Enhanced Father Protocol*
- Marco Tomamichel, Renato Renner and Roger Colbeck.
*A Quantum Asymptotic Equipartition Property*
- Koji Nuida, Gen Kimura, Takayuki Miyadera and Hideki Imai.
*On Minimum-Error State Discrimination Problems in Generic Probability Models*
- Anne Broadbent, Joseph Fitzsimons and Elham Kashefi.
*Universal Blind Quantum Computation*
- Daniel Nagaj.
*Railroad Switch: From Circuits to Hamiltonians*
- Andris Ambainis, Kazuo Iwama, Masaki Nakanishi, Harumichi Nishimura, Rudy Raymond, SEIICHIRO TANI and Shigeru Yamashita.
*Average/Worst-Case Gap of Quantum Query Complexities*
- Sebastien Gambs.
*Quantum classification*
- Vlad Gheorghiu, Shiang Yong Looi and Robert B. Griffiths.
*Location of quantum information in additive quantum codes*
- Jeong San Kim, Anirban Das and Barry Sanders.
*Entanglement monogamy of multipartite higher-dimensional quantum systems using convex-roof extended negativity*
- Yingkai Ouyang, Debbie Leung and Man Hong Yung.
*A More Accurate Measurement Model for Fault Tolerant Quantum Computing*
- Ivan Kassal, Stephen Jordan, Peter Love, Masoud Mosheni and Alan Aspuru-Guzik.
*Quantum simulation of chemical dynamics.*
- Salman Beigi.
*NP vs QMAlog(2)*
- Hiroshi Imai and Masahito Hayashi.
*Fourier Analytic Approach to Phase Estimation*
- Anil Shaji, Alexandre Tacla, Animesh Datta, Sergio Boixo, Steve Flammia, Carlton Caves and Matthew Davis.
*Quantum metrology from an information theory perspective*
- Cedric Beny, Achim Kempf and David Kribs.
*Quantum error correction for infinite-dimensional Hilbert spaces*
- Peng Xue.
*Quantum Computing with Dangling Bonds on a Silicon Surface*
- Nicolas Menicucci, Steve Flammia and Olivier Pfister.
*One-Way Quantum Computing in the Optical Frequency Comb*
- Andris Ambainis, Debbie Leung, Laura Mancinska and Maris Ozols.
*Quantum Random Access Codes with Shared Randomness*
- Andrew Childs, Debbie Leung, Laura Mancinska and Maris Ozols.
*Characterization of Universal 2-qubit Hamiltonians*
- Frédéric Dupuis.
*The capacity of quantum channels with side information at the transmitter*
- Marco Piani, Matthias Christandl, Pawel Horodecki and Caterina-Eloisa Mora.
*Broadcast copies reveal quantumness of bipartite correlations*
- Geza Toth and Juan Jose Garcia-Ripoll.
*Efficient algorithm for multi-qudit twirling for ensemble quantum computation*
- Elad Eban, Dorit Aharonov and Michael Ben-Or.
*Interactive Proofs For Quantum Computations*
- Joseph Fitzsimons.
*Quantum repetition encodings*
- Or Sattath, Dorit Aharonov, Michael Ben-Or and Fernando Brandao.
*The Pursuit for Uniqueness: Extending Valiant-Vazirani Theorem to the Probabilistic and Quantum Settings*
- David Menzies and Sarah Croke.
*Approximating quantum operations using weak values*
- Rolando Somma, Sergio Boixo, Howard Barnum and Emanuel Knill.
*Quantum Computing through decoherence and Quantum Simulated Annealing*
- William Matthews, Stephanie Wehner and Andreas Winter.
*Distinguishability of quantum states under restricted families of measurements*
- Peter Shor, Graeme Smith, John Smolin and Bei Zeng.
*Quantum error correction via codes over GF(3)*
- Raisa Karasik, Karl-Peter Marzlin, Barry Sanders and Birgitta Whaley.
*Avoiding irreversible dynamics in quantum Markovian systems*
- Steve Flammia, Stephen Bartlett, David Gross and Rolando Somma.
*Heralded polynomial-time quantum state tomography*
- Jing Shu, Xu-Bo Zou, Yun-Feng Xiao and Guangcan Guo.
*Quantum phase gate of photonic qubits in cavity QED system*
- Lin Chen and Yi-Xin Chen.
*Rank three bipartite entangled states are distillable*
- Milos Drezgic, Andrew Hines, Mohan Sarovar and Shankar Sastry.
* Complete Characterization of Mixing Time for the Continuous Quantum Walk on the Hypercube with Subspace Projection Decoherence Model*
- Seth Merkel, Gavin Brennen, Poul Jessen and Ivan Deutsch.
*Quantum Control of Hyperfine Spins with Coherent Electromagnetic Fields*
- Eric Chitambar and Runyao Duan.
*Nonlocal Entanglement Transformations Achievable by Separable Operations*
- Gregory Crosswhite and Dave Bacon.
*The Great Hunt for Small Subsystem Codes*
- Brian Mischuck, Ivan Deutsch and Poul Jessen.
*Control of Atomic Wave Functions in Optical Lattices*
- Alina Vasilieva and Ruben Agadzanyan.
*Quantum Query Algorithms for AND, OR and MAJORITY Boolean Functions*
- Paul Skrzypczyk, Nicolas Brunner and Sandu Popescu.
* Emergence of quantum correlations from non-locality swapping*
- Ligong Wang and Renato Renner.
*One-Shot Classical Capacities of Quantum Channels*
- Michael Frey.
*Quantum Fisher Information Associated with the Qudit Depolarizing Channel*
- Loïck Magnin, Nicolas J. Cerf and Frédéric Magniez.
*Quantum Bit-Commitment with Continuous-Variables*
- Yasuhito Kawano and Hiroshi Sekegawa.
*Producing Quantum Circuits of the Extended Clifford Group*
- Prabha Mandayam Doddamane and David Poulin.
*Approximate quantum error correction*
- Mayer Landau.
*Convex Roof Calculations of the Entanglement of Harmonic Oscillators Interacting Only Via a Reservoir*
- Yoritoshi Adachi, Takashi Yamamoto, Masato Koashi and Nobuyuki Imoto.
* Passive-decoy quantum key distribution with pseudo-single-photon sources*
- Michael Frey and Michael Steiner.
*Stern-Gerlach Measurement with External Coupling*
- Toshiki Ide.
*Violation of a local uncertainty relation in a photon telecloning*
- Hugue Blier and Alain Tapp.
*A Quantum Characterization of NP*
- Olivier Landon-Cardinal and Richard MacKenzie.
*Decoherence of a quantum reference frame*
- Michael Zwolak.
*Representing continuum environments*
- Gabriela Lemos and Fabricio Toscano.
*Can a chaotic environment with few degrees of freedom produce decoherence?*
- Vincent Nesme, Holger Vogts, David Gross and Reinhard Werner.
*Index theory for one-dimensional quantum walks and cellular automata*
- Paul M. Asling.
*The Wigner rotation and entanglement for photons in an arbitrary gravitational field*
Home | Photos | Submissions | Posters | Program | Talks | Dates | Committees
Participants | Location | Area Activities | Travel | Previous QIPs | Support |