中央研究院 資訊科學研究所

活動訊息

友善列印

列印可使用瀏覽器提供的(Ctrl+P)功能

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

  • 講者Song Fang 博士 (Institute for Quantum Computing, University of Waterloo)
    邀請人:鐘楷閔
  • 時間2014-12-15 (Mon.) 14:00 ~ 16:00
  • 地點資訊所新館106演講廳
摘要

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.