Project #1: Quantum Algorithms and Complexity Theory
-
Develop new quantum algorithms based on quantum walks, and other
``unconventional'' quantum algorithmic paradigms.
-
Develop new algorithms based on quantum Fourier transforms for
problems with various symmetrical structures.
-
Develop the amplitude amplification algorithmic paradigm (and
explore its connections with quantum walks on dense graphs).
-
Seek more efficient methods for computing the QFT and various
arithmetic/number-theoretic computations.
-
Investigate the power of quantum interactive proof systems,
inlcuding classes such as quantum Merlin-Arthur, various
notions of quantum zero-knowledge, and multi-prover interactive
proof systems.
-
Prove new lower bounds on the complexity of problems in the
black-box model (one open question, among many, is: is quadratic
speedup the best possible for quantum algorithms computing
total functions?).
-
Determine new instances where quantum resources reduce
communication complexity, or give rise to nonlocality.
Project #2: Quantum Information Security
-
Investigate the relationship between the quantum and classical
versions of oblivious transfer.
-
Improve the threshold (the maximum number of cheaters tolerated)
for secure multiparty quantum computations.
(Also, investigate
versions of this problem that are based on computational notions
of security.)
-
Investigate candidates for quantum one-way functions, and trapdoor
one-way functions.
Project #3: Theory of Quantum Information Implementations
-
Develop the theories of generalized quantum error correction.
Investigate fine tuned noise models that pertain to
specific physical systems.
-
Further study the computational power of various models inspired
by physical systems, including systems with limited pure state
qubits and with restricted entanglement.
|
