| Speaker: | Ray Liu |
| Affiliation: | University of Waterloo |
| Room: | MC 6486 |
Abstract:
Quantum algorithms achieve speed-up in evaluating many functions that can never be achieved by classical ones; for instance, the famous Shor’s Algorithm and Grover’s Search. In recent years, quantum walk based algorithms were heavily studied. By adding a coin register, we can turn discrete-time random walk into discrete-time quantum walk, which in general achieves a quadratic speed-up. In this talk, we will see how we can evaluate functions by analysing the spectrum of the quantum walk. No prior knowledge of quantum computing is assumed.
| Speaker: | Xinrui Jia |
| Affiliation: | University of Waterloo |
| Room: | MC 6486 |
Abstract:
A recent paper by Delaram Kahrobaei and Vladimir Shpilrain describes a key exchange protocol using a semidirect product of groups/semigroups. We present the general protocol and the Diffie-Hellman key exchange as a special case of this protocol. When implemented with a non-commutative group/semigroup, this key exchange by Kahrobaei and Shpilrain can have advantages over Diffie-Hellman but care must be taken to avoid linear algebra attacks. Time permitting, we discuss the analysis of the security of the protocol under certain semigroups and our approach to finding new suitable semigroups. The authors suggest using a free nilpotent p-group to avoid these attacks.