| A detailed description (in PostScript
format) can be found here. What follows is
a brief overview of the research areas.
Quantum algorithms and complexity
theory
Quantum algorithms
The polynomial-time algorithm of Peter Shor for factoring integers on a
quantum computer suggests that quantum computers are fundamentally more
powerful than their classical counterparts. This quantum algorithm
employs inherently non-classical operations, such as the quantum
Fourier transform. Another quantum algorithm (due to Lov Grover)
permits generic searches to be performed quadratically faster than with
classical algorithms, employing a technique called amplitude
amplification. Our work in this area of research includes
investigations of further applications of quantum Fourier
transforms and amplitude amplification techniques, as well as the
development of new algorithmic techniques, such as those based on
quantum walks and adiabatic methods.
Lower bounds
Many quantum algorithms can be
expressed within a black-box framework, where one is given a black-box
computing an unknown function and the goal is to determine some global
property of the function. Lower bounds on the query complexity of such
problems provide useful guidance about the prospects of various
algorithmic techniques. We are exploring new versions of the so-called
quantum
adversary method, in order to broaden the number of problems that it
applies
to.
Communication complexity
This is the study of communication costs associated with
various distributed systems. It turns out that quantum information
enables us to dramatically reduce the communication costs of certain
distributed
problems, and we are continuing to explore such scenarios. Also, the
non-local effects that arise from
entangled systems (a.k.a. Bell inequality violations) are an important
feature of quantum information, and they fit
naturally within this framework.
Quantum interactive proof
systems
Interactive proof systems generalize the standard notion of a proof, by
permitting interaction between a "verifier" and a "prover", and
allowing the verifier to be a
probabilistic procedure (that may err). Such notions have been very
fruitful within the context of classical complexity theory and
cryptography. Quantum analogues of these systems have been studied and
shown to have increased expressive power. There are further questions
about their expressive power, and about other issues, such as quantum
notions of zero knowledge, that are under investigation.
Quantum
communication and information
security
Key distribution protocols
Quantum information appears to have very important consequences for the
field of cryptography. There are efficient quantum algorithms that
break most of the currently-known public-key cryptosystems. Moreover,
the "BB84" quantum key distribution protocol due to Charles Bennett and
Gilles Brassard provides an alternate cryptographic framework, where
security can be attained by basic properties of the laws of physics,
rather than computational assumptions.
The goal in quantum key distribution is for two parties to set up a
private key in the presence of an eavesdropper. The assumption is that
the parties have a quantum channel whose content is accessible to the
eavesdropper, as well as a classical channel whose content the
eavesdropper has full read-only access to. (The latter channel can be
simulated by authentication using short
private keys.) Since quantum
key distribution protocols were first proposed in 1984, many questions
about their security have been investigated. Although secure "in
principle", several issues remain about their security when implemented
with current (imperfect) devices, and about efficiency issues. One
recently-proposed idea that is being further investigated employs
"decoy states" to detect eavesdropping.
This appears to yield security while significantly surpassing many
experimental real-world
performances reported in the recent literature. We are also
establishing
results concerning the composability of quantum key
distribution schemes, showing that they are secure enough to be used
along with any other application, provided an appropriate
security criteria is chosen and be satisfied.
Multiparty quantum
communication protocols
There are several multi-party cryptographic problems
whose feasibility in the setting of quantum
information is of interest, such as coin-flipping, data hiding, and
notions of bit commitment (where two separated "provers" are present).
Cryptographic consequences
of measure concentration
The one-time pad is perhaps the simplest and most basic cryptographic
construction: two parties can use a number of secret shared random bits
as key to securely encrypt and decrypt a message of the same length. An
analogous construction exists in the quantum realm, with the twist that
the number of bits of key required to perfectly encrypt the message is
now twice the length of the message
itself. Using a randomized construction exploiting measure
concentration in high dimensions, it was shown that this extra factor
of
two disappears entirely if tiny deviations from perfect secrecy are
allowed. We are using similar techniques to study the cryptographic
power of
a shared Cartesian reference frame, a type of physical information that
cannot be established by any amount of discussion.
Theory of quantum
information implementations
Quantum error correction
All implementations of quantum information processing are likely to
include errors in one form or another. We are exploring new
methodologies for quantum error correction for more general types of
noise than were
previously known.
<>
Physical models of quantum
information
<>We are implementing specific quantum information
processing devices, and analyzing the noise that occurs with them. We
are also considering physical processes as a source of inspiration for
new quantum algorithms (for, example, we have discovered non-trivial
algorithms that compute using highly mixed states by considering issues
that arise in the context of nuclear magnetic resonance
implementations).
<>
Quantum
information theory and entanglement
theory
Entanglement theory
We are investigating issues related to the problem of "distilling" pure
entangled states from noisy ones.
Quantum Shannon theory
We are continuing to study properties of various
quantum channels, and how they may be used to reliably communicate.
Pseudorandom quantum
operations
We are exploring various techniques for constructing various types of
"pseudo-random" quantum operations, which have properties similar to
truly random unitary operations (sampled according to the Haar measure,
which is computationally not feasible for large scale systems). These
have applications ranging from simplifying the effective behavior of
quantum channels, to data hiding.
|
