Quantum Algorithms and its Application in Cryptography

Even since the introduction of quantum
computation to the computing world, many
practical quantum experiments have been
successfully carried out. By taking advantage
of the tremendous computing power of
quantum computers, Peter Shor has shown
that factor large numbers can be done in
polynomial time. Public key cryptosystems,
digital signature schemes as well as many
other schemes that depended on this
difficulty of factoring large numbers would
become vulnerable. On the other hand,perfect secure cryptographic key distribution
scheme based on quantum computing has
been developed. Indeed, quantum computing
will threaten the security of many classical
cryptographic schemes, but it can also make
classically infeasible computing tasks
become feasible. Quantum computing has
attracts the attentions of most leading
scholars and research institute in the world.
The main research targets of this project
are quantum automata theory, quantum
algorithms and quantum cryptography. By
studying the theoretical foundations of
quantum computing, we hope we can have a
better understanding of the power of
quantum computing and can design practical
and effective quantum algorithms. In
particular, we shall focus on what classically
infeasible cryptographic tasks might become
feasible using quantum computers. For
example, can we break AES (Advanced
Encryption Standard) efficiently using
quantum computers? We still do not know.
In particular, can we solve any NP-hard
problem with polynomial-time quantum
computation? (I.e., is NP a subset of QP?)
Next, we are also interested in what new
quantum objects might be created and
adopted to construct secure cryptographic
protocols that are impossible using classical
computation models.
We will investigate the possibility of
adopting quantum parallelism for fast
cryptanalysis. We will also study the
possibility of adopting the non-cloning
feature of quantum objects to design efficient
algorithms for quantum money. In addition,
we shall study what other quantum
phenomena (such as superposition,
entanglement, reversibility, etc.) might be
useful for quantum algorithm design. Under
this project, we expect to integrate the
research potential in the nation and
collaborate with leading researchers in the
world.