QIP 2009

The Twelfth Workshop on Quantum Information Processing
January 12-16, 2009

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