【课程知识点总结】密码学中的量子计算基础

1 minute read

Published:

持续更新至课程结束。最后更新于 2021-10-07

2021 年秋季研一课程笔记,开课地点为雁栖湖。课程内容较为前沿,很有意思,之前接触的不多,本科仅仅只学过量子力学,因此开文记录主要知识点。

0. 参考书目与课程大纲

参考书目

课程大纲

教学目标
    本课程的目的是使信息安全研究生深入了解量子计算的基本理论,掌握Shor算法、Grover算法等经典量子算法,以及量子密码分析领域的最新科研动态,培养研究生的学习兴趣与研究能力,为将来的发展做好准备。
    
章节目录
    第一章 量子计算基础 2学时 黄震宇
    第1节 量子计算历史
    第2节 量子计算的数学基础
    第二章 谱分解定理与量子力学基本假设 2学时 黄震宇
    第1节 谱分解定理
    第2节 量子力学基本假设的数学模型
    第三章 量子测量与单比特量子门 2学时 黄震宇
    第1节 量子测量与海森堡不确定性原理
    第2节 单比特量子门与量子比特的旋转
    第四章 多量子比特门 2学时 黄震宇
    第1节 受控门
    第2节 酉变换的通用实现
    第五章 通用量子门集 2学时 黄震宇
    第1节 单比特量子变换的逼近
    第2节 经典计算的量子实现
    第六章 基本量子算法 2学时 黄震宇
    第1节 量子并行与Deutsch-Jozsa算法
    第2节 Simon算法
    第七章 量子傅里叶变换及其应用 2学时 黄震宇
    第1节 量子傅里叶变换
    第2节 相位估计
    第八章 RSA算法的量子攻击 2学时 黄震宇
    第1节 RSA算法与求阶问题
    第2节 Shor算法
    第九章 量子搜算算法 2学时 黄震宇
    第1节 Grover算法
    第2节 量子搜索问题的复杂度
    第十章 基于量子算法的对称密码分析 2学时 黄震宇
    第1节 改进的Simon算法及其成功率
    第2节 基于Simon算法的密码分析
    

1. 历史与数学基础

  • 历史

    • 1990 Deutsch-Jozsa algorithm

    • Yao 证明了量子电路模型等价于量子图灵机模型

    • 1993 Shor 算法,量子傅里叶变换,指数级降到多项式

    • 1997 Grover 算法,对称密码密钥长度需要加倍

    • 其他:Simon 算法等等

  • 对叠加态的基本认识

    • 经典计算机与量子计算机、比特与量子比特、寄存器与量子寄存器

    • 叠加态、叠加态的测量、测量后的坍缩、复数域上的概率问题

    • Stern-Gerlach 实验

    • 只测量第一个量子比特情况下第二个量子比特概率

    • Einstein-Podolsky-Rosen paradoxEPR 佯谬

    • Bell

    • 叠加态与纠缠态

    • 一个叠加态保存了 $2^n$ 位的信息

  • 什么是量子计算

  • Hilbert 空间:定义了内积和范数的有限维复线性空间

    • 左矢 bra 与右矢 ket

    • 1939 年引入 Dirac 符号,即 Bra-Ket 符号

    • 内积与范数的性质

    • 张量积、外积、结合律

    • Hilbert 空间的扩充

  • Bloch Sphere

2. 谱分解定理与量子力学基本假设

  • 谱分解定理

    • Hermitian 方阵、规范方阵、酉方阵

    • 特征值、特征向量与相似对角化

    • 谱分解定理及其推导:任一规范方阵,均酉相似于一个对角阵

  • 量子力学的基本假设

    • 假设一:量子系统的描述

    • 假设二:演化可由酉变换描述

    • 假设三:复合系统状态空间是分量状态空间的张量积

    • 假设四:关于量子测量

3. 量子测量与量子门

  • 量子测量

    • 对复合系统的测量

    • 纠缠态

    • 投影测量、投影算子、投影测量的期望

    • 密度矩阵主要用来描述不确定的系统、纯态与混合态

    • 海森堡不确定性原理、对易子与反对易子

  • 量子门

    • Pauli 门、相位门、$\frac{\pi}{8}$ 门

    • Hadamard

    • Bloch Sphere 上的旋转


声明:本文采用 CC BY-NC-SA 4.0 授权。

This work is licensed under a CC BY-NC-SA 4.0.