量子计算

Quantum Error Correction

2019-12-26 08:00 CST
2019-12-26 10:13 CST
CC BY-NC 4.0
  • Vernam cipher/ One-time pad: 绝对安全(信息论安全),Eve 做任何计算
    • 加密前后概率分布需一样
    • Theorem: the secret key has to be as long as the message
  • 密码学安全:Eve 在多项式时间内无法得到任何有效信息
  • DH Key Exchange: 离散对数问题,量子计算机下不安全
  • Information reconciliation
    • Condition: flipped bits $\leq\delta$ fraction of bits
    • Goal: Alice and Bob
    • Error encoding code
  • BB84 QKD protocol
    • $a,b\in_R{0,1}^{(4+\delta)n}$
    • $|\psi\rangle=\otimes_{k=1}^{(4+\delta)n}|\psi_{a_k,b_k}\rangle$
      • $|\psi_{0,0}\rangle=|0\rangle,|\psi_{1,0}\rangle=|1\rangle,|\psi_{0,1}\rangle=|+\rangle,|\psi_{1,1}\rangle=|-\rangle$
    • Bob announce achievement
    • Bob $b'\in_R{0,1}^{(4+\delta)n}$
      • $b'_i=0$ measure $i$-th bit at ${|0\rangle,|1\rangle}$
      • $b'_i=1$ measure $i$-th bit at ${|+\rangle,|-\rangle}$
    • Alice announce $b$
    • Discard the bits where $b$ and $b'$ differ
    • Together select a subset of $n$ bits
    • Announce these $n$ bits and compare
    • Information reconciliation
    • privacy amplification
      • Collision entrop: $H_c(X)=-\log(\sum_xp(x)^2)$
  • QKD 应用
    • 京沪干线
    • 墨子号卫星
  • Q Monkey
    • 基于长时间保存量子态
  • Post-Quantum Cryptography
    • 经典密码学
    • 单向函数设计时对付量子计算机
    • 替换大数分解
      • Lattice-based: 理论完善(量子计算难)
      • Multivariate
      • Hash-based
      • Code-based
      • Supersingular elliptic curve isogeney
    • NIST: Post-Quantum Cryptography Standardization
  • Delegated Q. Computation
    • 验证对方是量子计算机
      • Factor $\in$ BQP$\backslash$P
      • only 1000 quib
      • Factor 上万比特
    • 协议要求
      • honest: complete
      • dishonest: user is able to detect
      • (Bonus) does not learn anything
    • 08: 2台
    • 18: 1台

Quantum Simulation

近 5-10 年可用,解薛定谔方程

需要懂物理,理解 $H$

Quantum Distribution Computation

量子分布计算,混合计算