[양자 컴퓨팅과 보안] 양자 알고리즘

양자 알고리즘

1. Grover’s algorithm

• 정렬되지 않은 데이터베이스에서 쓰이는 검색 알고리즘
• 루트N 시간 소요 (데이터 양이 많아질수록 효과가 뛰어남)
• 대칭키에서는 안전 → 암호키의 비트 수를 늘리면 깨뜨리는데에 수만년이 걸림
• 단계 별 내용 (ex. 입력 큐빗 : 2개, 정답 : 10)
  • • “위상(부호) 반전”을 통해 해답을 찾아내는 단계
    • 파울리 Z게이트 사용
    • 정답인 값 10의 부호가 - 로 변경
    • 결과물 : $\frac{1}{2} | 00 > +\frac{1}{2} | 01 >-\frac{1}{2} | 10 > +\frac{1}{2} | 11 >$해답 (Oracle 단계) 

 

 

• • 중첩 (Superposition 단계)
  • 아다마르 게이트를 통해 큐빗을 중첩 상태로 만드는 단계
  • 결과물 : $\frac{1}{2} | 00 > +\frac{1}{2} | 01 >+\frac{1}{2} | 10 > +\frac{1}{2} | 11 >$ 
  • 해답 (Oracle 단계)
    • “위상(부호) 반전”을 통해 해답을 찾아내는 단계
    • 파울리 Z게이트 사용
    • 정답인 값 10의 부호가 - 로 변경
    • 결과물 : $\frac{1}{2} | 00 > +\frac{1}{2} | 01 >-\frac{1}{2} | 10 > +\frac{1}{2} | 11 >$

 

 

• 증폭 (Diffuser 단계)
  • 원하는 해답의 부호가 -인 상태에서 “확률”을 높이기 위한 증폭 필요
  • “평균에 대한 반전” 을 이용 : L* = m - (L-m) = 2m - L

 

2. Shor’s algorithm

• 소인수분해 / 이산대수 암호를 빠르게 깨뜨림
• 암호 키의 비트 수와 상관 없이 빠르게 깨뜨림
• 공개키 암호가 깨지게되면 개인키까지 깨져 사용할 수 없게 됨
  •