Abstract to come later.
In this talk ramifications of the quantum source coding problem, as introduced by Schumacher, are discussed: after presenting the original setting and result, I present recent work (with H. Barnum, P. Hayden and R. Jozsa) showing that in "blind" coding situations qubits cannot be saved beyond Schumacher's limit by using a free classical side channel, unless the quantum source ensembles exhibits orthogonality. Then I go on to discuss results obtained together with P. Hayden and R. Jozsa during the last months regarding the case of "visible" coding: there it is natural to consider the function characterizing the tradeoff between classical and quantum bits. We were able to give a single-letter expression for this function. I will also discuss examples and applications of this result.
We present a new bound for the $p$-norm of an output state from the half-noisy product channel $I \times \Phi$, where $I$ is the identity and $\Phi$ is the phase-damping channel. This bound leads to a proof that the maximal $p$-norm of the product channel $\Omega \times \Psi$ is multiplicative when $\Omega$ is a completely arbitrary channel, and $\Psi$ is any unital qubit channel. Consideration of behavior near $p=1$ provides entropy bounds which establish the additivity of minimal entropy and of the Holevo capacity for this same class of product channels. Possible extensions of the result to other cases are discussed.
We present lower bounds for the resources required for remote state preparation for any ensemble of pure states that span the input Hilbert space. In particular, if the protocol (1) uses only forward communication, (2) prepares an exact copy of the states deterministically, (3) but otherwise provides Bob with no extra information about the prepared states, then the protocol can be modified to require from Alice only a copy of the states to be prepared. As the modification requires no extra resources, Alice's knowledge of the state does not enable resource trade-off, and lower bounds for teleportation are applicable to remote state preparation. This also proves Lo's conjecture [PRA 62 (2000) 012313] under the conditions stated above.
In this talk I explain three different sets of physical resources sufficient
to do universal quantum computation. In particular, I discuss how to do
quantum computation by projective measurements and quantum memory, how
to do quantum computation with any entangling two-body Hamiltonian, and
how to do quantum computation with a fault-tolerant set of quantum gates,
using the Solovay-Kitaev theorem.
The notion of (classical) zero-knowledge proof systems has been studied extensively. In the quantum case, however, even the first step of giving a cryptographically satisfying definition for quantum zero-knowledge presents a formidable challenge. In this talk I will discuss a very simple and straightforward definition for quantum zero-knowledge proof systems that is not intended to be cryptographically satisfying, but rather is intended as a tool for investigating the complexity-theoretic properties of quantum interactive proof systems. The definition gives rise to a complexity class QSZK (quantum statistical zero-knowledge) that has several properties that are also possessed by the analogous classical complexity class SZK, including closure under complement and the existence of natural complete promise problems.
We consider quantum counterparts of classical random walks on the line, with Hadamard transforms instead of random coin flips. For the walk on the unbounded line, we show that it spreads quadratically faster than the classical walk. (The expected distance from the origin after t steps is \Theta(t), instead of \Theta(\sqrt{t}).) For quantum walks on semi-infinite line and a finite segment of the line (with absorbing boundaries on one or both sides), we study the probabilities of the walk ending at the boundary and show that these probabilities have unusual properties very different from the classical case. We also show some bounds on the convergence time for quantum walks on general graphs. Joint work with Dorit Aharonov, Eric Bach, Julia Kempe, Ashwin Nayak, Umesh Vazirani, Ashvin Vishvanath and John Watrous.
We consider a spin 1/2 system on the honeycomb lattice. The interactions between nearest neighbors are of XX, YY, or ZZ type, depending on the direction of the link. A phase diagram in the space of coupling parameters is studied; two phases with anyonic excitation are identified. This model can be used as an implementation of error-protected quantum memory..
We present a new computational model, where quantum information processing consists entirely of one-qubit measurements on an entangled resource state (1).
An example of such a resource state is the cluster state (2). By the measurements, the entanglement of the cluster state is exploited and turned into (quantum) correlations, which are used for logical processing.
The measurements on a cluster state can be used to simulate any quantum logic circuit, but other, more efficient ways of information processing are possible. For cirquits in the Clifford group, for example, which are important for encoding, all measurements can be performed in a single time step (3).
Cluster state can be created efficiently in any system with a quantum Ising-type interaction between two-state particles in a lattice configuration.
This is joint work with Robert Raussendorf and Daniel E. Browne.
(1) PRL 86, 5188 (2001); http://arxiv.org/abs/quant-ph0010033.
(2) PRL 86, 910 (2001); http://arxiv.org/abs/quant-ph/0004051.
(3) http://arxiv.org/abs/quant-ph/0108118.
http://www.theorie.physik.uni-muenchen.de/~briegel
Abstract to come later.
One of the central concepts of modern cryptography is the idea of a public key protocol, in which the same public key is distributed to many people, some of whom may be untrustworthy, without compromising the security of the scheme. Public keys offer a number of advantages over private keys, which become insecure if obtained by an enemy. In particular, public keys are much easier to distribute to their intended recipients, since they do not need to be protected against enemy access. While quantum key distribution also handles this problem by allowing the users to detect eavesdropping, it cannot help two people who do not already share a small amount of private key. In addition, quantum key distribution does not obviously share another advantage of public key protocols: they can be used to perform tasks beyond the traditional domain of private key cryptography. One such task is the digital signature, which protects a signed message against forgery. Anyone who has a copy of the public key can verify the message, so the recipient of a digital signature can later prove in court that it was correctly signed, if need be. I will describe a quantum digital signature protocol which serves as a model for combining the advantages of public keys with unconditional security. The price is that the public keys must now be quantum states, which are more difficult to handle than classical keys and must have limited distribution.
I describe protocols which enable the recipient of a quantum state to
assure herself that the state has come unaltered from a sender with whom
she has previously shared secret classical key. For an m-qubit quantum
message, a scheme with failure probability no greater than 2^-s has private
key of length 2m + O(s), which is asymptotically optimal. The relationship
between authentication, encryption, and quantum key distribution will also
be discussed. This is joint work with Claude Crepeau, Daniel Gottesman,
Adam Smith and Alain Tapp.
Classically a property P has a property tester if there exists a probabilistic
algorithm that given an input x only asks a small number of bits of x and
distinguishes the cases as to whether x has property P and x has large
Hamming distance from all y that have property P (i.e. x is far from having
property P). We define a similar notion of quantum property testing and
show that there exist languages with quantum property testers but no good
classical testers. We also show there exist languages which require a large
number of queries even for quantumly testing. This is joint work with Lance
Fortnow, Ilan Newman and Hein R\"ohrig.
Reductions play an important role in complexity-based cryptography.
A notable example is the so-called Goldreich-Levin Theorem, which is a
reduction from the computational problem of inverting a one-way function
to the problem of predicting a particular bit associated with that function.
We show that the quantum version of this reduction can be quantitatively
more efficient than the classical version. We also show that, using the
Goldreich-Levin Theorem, a quantum bit (or qubit) commitment scheme that
is perfectly binding and computationally concealing can be obtained from
any quantum one-way permutation. This is joint work with Mark Adcock.
Abstract to come later
Abstract to come later
Quantum particles can be used for communicating spatial directions between
two observers that do not share a common reference frame. We show that
when the emitter's signal is represented by the orbit of a group, then
the optimal detection method is not in general a covariant measurement.
It may in fact be advantageous for the receiver to use a different group
followed by an indirect estimation method: first, an ordinary measurement
provids redundant data; the latter are then used for a nonlinear optimal
identification of the signal.
We consider a refinement of distillable entanglement: for a given state
$\rho$ (or $n$ copies of such a state), and a given output dimension $K$,
what is the greatest fidelity with which $\rho$ can be converted to a maximally
entangled state of dimension $K$? In the case of p.p.t. (positive partial
transpose) operations, this fidelity of distillation can be expressed as
the solution to a certain semidefinite program. The theory of semidefinite
programming thus leads to a number of interesting consequences; moreover,
in particularly symmetric cases (e.g., multiple copies of isotropic or
Werner states), the semidefinite program reduces to a linear program, and
is therefore particularly tractable. In the case of antisymmetric Werner
states, we can explicitly solve the linear program, and thus obtain the
p.p.t. distillable entanglement of these states.
A classical bit may be hidden in an N-partite quantum system, when quantum
communication between the N partners is restricted, but arbitrary local
operations and arbitrary classical communication is allowed. The encoding
is done by preparing one of two orthogonal multipartite states. For decoding
we assume that the N parties are partitioned into subsets within each of
which quantum communication is available. By judicious choice of hiding
states a rich variety of hiding scenarios can be realized, differing in
the partitions which can or cannot retrieve the hidden bit. Following a
suggestion by DiVincenzo, Terhal and Leung, the states used in this work
are invariant under $U^{\otimes N}$-rotations, and permutations.