Institute of Information Science, Academia Sinica

Events

Print

Press Ctrl+P to print from browser

A quantum algorithm for computing the unit group of an arbitrary-degree number field

:::

A quantum algorithm for computing the unit group of an arbitrary-degree number field

  • LecturerDr. Song Fang (Institute for Quantum Computing, University of Waterloo)
    Host: Kai-Min Chung
  • Time2014-12-15 (Mon.) 14:00 ~ 16:00
  • LocationAuditorium 106 at new IIS Building
Abstract

Quantum algorithms can sometimes solve problems exponentially faster than best known classical algorithms. I will give such an example in this talk.  Specifically, I will present an efficient quantum algorithm for computing the unit group of number fields of arbitrary degree. I will introduce the basics of number fields and a central problem in quantum computing called the hidden subgroup problem (HSP) . Then I will show how to reduce the problem of computing unit group to an instance of the HSP problem, and how to solve the HSP instance efficiently on a quantum computer. I will also discuss potential applications of our quantum algorithm in attacking (ideal) lattice based cryptography, which consists of many recent breakthroughs, e.g., fully homomorphic encryption and code obfuscation. Background in neither number fields nor quantum computing is required. 

Joint work with Kirsten Eisentraeger, Sean Hallgren and Alexei Kitaev. [STOC'14, QIP'15]

BIO

Song Fang is a postdoctoral fellow at the Institute for Quantum Computing and the Department of Combinatorics and Optimization at the University of Waterloo. His research interests lie in quantum computing, cryptography and more broadly complexity theory. He completed my PhD in 2013 in Computer Science and Engineering at Pennsylvania State University under the supervision of Sean Hallgren. Before coming to Penn State, He received his bachelor's degree from University of Science & Technology of China in 2008.