Some theoretical works on the quantum application, cryptanalysis, and computer system

Speaker  Byung-Soo Choi

Affiliation  Duke University

Host  Krysta Svore

Duration  01:22:46

Date recorded  6 June 2013

In this talk, I would like to discuss three research works. First, related to quantum applications, I would like to discuss the quantum partial search algorithms. Specifically, I will discuss how to generalize the single target block search case into the multiple target block search case. At the same time, I will show how to achieve sure success of the partial search. Second, related to quantum cryptanalysis, I would like to discuss how the quantum computer can be used for analyzing the Boolean functions, specially some secure properties. I will explain how Grover search algorithm can be used for analyzing the weight of Boolean functions where the weight is the ratio of solutions over the input. Its generalization for asymmetric case and multiple weights cases will be discussed. At the same time their optimality has been proved. Meanwhile for the actual secure primitives I will describe how the quantum computation can be used for resiliency checking problem. Third, related to quantum computer system, I would like to show an addition circuit on the 2D NTC architecture and their optimality. At the same time I will propose a way how to generated quantum LDPC code from any binary matrix. Also some current works on the layout and scheduling of logical tiles will be discussed. In each category, I will explain some future work. For example, quantum machine learning on the Boolean functions, quantum query/circuit complexities on the secure property checking, and the quantum error-correction code conversion methods will be touched.

©2013 Microsoft Corporation. All rights reserved.
> Some theoretical works on the quantum application, cryptanalysis, and computer system