Skip to Content
Quantum Computation

Quantum Error Correction

2019-12-26Original-language archivelegacy assets may be incomplete
  • 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∈R{0,1}(4+δ)na,b\in_R\{0,1\}^{(4+\delta)n}
    • ∣ψ⟩=⊗k=1(4+δ)n∣ψak,bk⟩|\psi\rangle=\otimes_{k=1}^{(4+\delta)n}|\psi_{a_k,b_k}\rangle
      • ∣ψ0,0⟩=∣0⟩,∣ψ1,0⟩=∣1⟩,∣ψ0,1⟩=∣+⟩,∣ψ1,1⟩=∣−⟩|\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′∈R{0,1}(4+δ)nb'\in_R\{0,1\}^{(4+\delta)n}
      • bi′=0b'_i=0 measure ii-th bit at {∣0⟩,∣1⟩}\{|0\rangle,|1\rangle\}
      • bi′=1b'_i=1 measure ii-th bit at {∣+⟩,∣−⟩}\{|+\rangle,|-\rangle\}
    • Alice announce bb
    • Discard the bits where bb and b′b' differ
    • Together select a subset of nn bits
    • Announce these nn bits and compare
    • Information reconciliation
    • privacy amplification
      • Collision entrop: Hc(X)=−log⁡(∑xp(x)2)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\\backslashP
      • 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 年可用，解薛定谔方程

需要懂物理，理解 HH

Quantum Distribution Computation

量子分布计算，混合计算