2020년 8월 30일 일요일

Google, "TIMELY: RTT-based Congestion Control for the Datacenter" 직역

작성중인 글입니다.

이 글은 Google의 "TIMELY: RTT-based Congestion Control for the Datacenter"[1] 논문의 직역입니다. 제 이해 수준에 따라 오역되거나, 단어 선정이 어색할 수 있습니다. 본문의 인용[#]은 제 글의 인용 안에 숫자를 바꿔 포함하거나 불필요 판단시 생략하며, 그림은 재도식할 때까지 당분간만 논문을 캡쳐하여 포함하고 직역 완료 후 재도식 하겠습니다.

요약

데이터 센터 전송은 낮은 메시지 전송 지연과 높은 처리량을 목표로 한다. 우리는 스위치의 피드백을 필요로 하지 않고, 호스트에서 측정한 왕복 시간인 단순한 패킷 지연이 효과적인 혼잡 신호임을 보인다. 첫 번째, 우리는 NIC[2] 하드웨어의 발전이 RTT[3]를 마이크로초 정확도로 측정 가능하다는 것과, 이러한 RTT는 스위치 큐잉을 추정하기에 충분하다는 것을 보인다. 그 다음 우리는 높은 대역폭을 전송하는 동안 낮은 패킷 지연을 유지하기 위해, TIMELY가 어떻게 RTT 변화도(gradient)를 사용하여 전송률[4]을 조절할 수 있는 지를 서술한다. 우리는 OS 우회 능력을 가진 NIC들을 통해 동작하는 호스트 소프트웨어에 우리의 설계를 구현한다. 우리는 Clos 네트워크 토폴로지[5] 상의 수백 대까지의 머신의 실험을 사용하여, 이것이 탁월한 성능을 제공하는 것을 보인다. OS를 우회하는 메시지에 TIMELY를 켜면 PFC[6]의 fabric[7]에서 회선 처리량에 9배 근접하게 유지하여 꼬리 지연(tail latency)[8]을 99 퍼센트 감소시킨다. 우리의 시스템은 또한 꼬리 지연을 13배 감소하여, 최적화된 커널에서 수행되는 DCTPC[9]를 능가한다. 우리가 아는 한, TIMELY 는 데이터 센터를 위한 첫 번째 지연-기반 혼잡 제어 프로토콜이며, Vegas 와 같은 이전의 지연-기반 기법보다 작은 규모의 RTT신호를 가지더라도 (NIC 의 offload[10] 를 통해) 그 목적을 달성한다.

1. 서문

(3, 4, 5번 섹션 작성 후 작성)

2. 데이터 센터에서 혼잡 신호로서의 RTT 값

(3, 4, 5번 섹션 작성 후 작성)

3. TIMELY 프레임워크

TIMELY는 현실에서 사용되는 전송 프로토콜과 독립적인 전송률(rate) 제어 프레임워크를 제공한다. 그림6은 그 세 가지 구성, 1) 네트워크 혼잡을 감시하는 RTT 측정, 2) RTT 신호를 목표 송신율(sending rates)들로 변환하는 계산 엔진, 그리고 3) 목표 전송률을 달성하기 위해 세그먼트 사이에 지연을 입력하는 제어 엔진을 보인다. 우리는 NIC 하드웨어 지원으로 호스트 소프트웨어에 TIMLEY를 구현하고, 각 flow의 독립적인 개체(instance)를 실행한다.

그림6. TIMELY 개요

3.1. RTT 측정 엔진

우리는 수신자가 명시적으로 새로운 데이터에 ACK로 응답하면 RTT를 추출하는 전통적인 전송을 가정한다. 우리는 그림7과 같이 RTT를 정의하며, 다수의 패킷으로 구성된 세그먼트가 하나의 버스트[11]로 전송되고, 수신자에 의해 한 단위로 ACK 응답되는 메시지의 타임라인을 보인다. 

그림7. 완료 시간에서 RTT 구하기

하나의 완료 이벤트는 데이터 세그먼트를 위한 하나의 ACK를 수신하여 생성되고, ACK 수신 시간을 포함한다. 첫 번째 패킷이 전송된 시간부터 ACK를 수신한 시간까지가 완료 시간(completion time)으로 정의된다. TCP와는 다르게, 1-2 패킷당 RTT보다는 패킷 집합을 위한 하나의 RTT가 있다. 지연 구성 요소는 1) 일반적으로 64 KB까지의 세그먼트의 모든 패킷을 진송하는 직렬화 지연, 2) 세그먼트와 데이터 센터를 건너 전파하는 ACK의 왕복 배선 지연, 3) ACK를 생성하는 수신자의 회송 시간(turnaround time), 그리고 4) 양방향에서 겪는 스위치의 큐잉 지연이 있다. 우리는 RTT를 전파(propagation)와 큐잉 지연 구성요소 만으로 정의한다. 첫번째 구성요소는 NIC의 회선 전송률(line rate)와 세그먼트 크기의 결정론적 함수이다. 우리는 전체 소요 시간에서 이를 계산하고 차감하므로, TIMELY의 전송률 계산 엔진에 입력되는 RTT는 세그먼트의 크기에 독립적이다. 세 번째 구성요소는 우리의 NIC 기반 ACK 구성에서 충분히 영(0)에 가까우므로 무시할 수 있다. 남아있는 구성요소 중 두 번째는 스위치에서 패킷 기반의 저장과 전달 행동을 포함하는 전파 지연이다. 이는 최소 RTT이고, 주어진 flow에서 고정된다. 오직 마지막 구성요소인 큐잉 지연이 RTT에서 변동을 일으키며, 이것이 우리가 혼잡 탐색하기 위해 집중하는 것이다. 요약하면, 호스트A(그림7에서 보이는)에서 실행하는 TIMELY는 RTT 를 다음과 같이 계산한다.


맥락적으로, 10Gbps 네트워크에서 64 KB의 직렬화(serialization)는 51㎲가 걸리고, 전파는 10-100 ㎲의 범위일 것이며, 1500 B 큐잉은 1.2 ㎲가 걸린다. 우리는 세그먼트 RTT를 정밀하게 측정하기 위한 두 형태의 NIC지원을 의존하며, 다음과 같이 기술한다.

ACK 타임스템프 우리는 NIC가 완료 타임스템프, tcompletion을 지원하도록 요구한다. 그림 2에서 보였다시피, OS 타임스탬프는 스케쥴링과 인터럽트들과 같은 변동을 겪으므로, 쉽게 혼잡 신호를 모호하게 할 수 있다. tsend는 NIC에 세그먼트가 전달되기 바로 직전에 호스트 소프트웨어가 읽은 NIC의 하드웨어 시간이다.

즉각적인 ACK 생성 우리는 NIC 기반의 ACK 생성을 요구하여 수신자 측의 회송(turnaround) 시간을 무시할 수 있다. 하나의 대안은 타임스탬프를 사용하여, 호스트의 처리 지연으로 인한 ACK 회송 지연을 측정하는 것이다. 우리는 이 선택을 피하였는 데, 이는 증가하는 전송 회선 형식(argumenting transport wire formats)이 이 명시적인 차이를 포함하도록 요구할 수도 있기 때문이다. 

다행히, 일부 현대적인 NIC들은 하나 또는 두 기능을 제공하고, 우리의 요구사항인 세그먼트 ACK에 타임스탬프를 찍는 메시징 구현이 자연스럽게 만족한다. RDMA 문맥 안에서 TIMELY 의 특정 구현은 섹션5 에서 기술된다. 우리는 NIC의 일괄처리 행동(batching behavior), 새 데이터의 수신에 대해 정확하게 연결되는 ACK, 그리고 ACK 회송시간의 보상에 대한 주의 깊은 적용으로 우리의 설계가 더 일반적으로 TCP에 적용될 수 있다고 믿는다.

3.2. 전송률 계산 엔진

이 구성요소는 섹션 4에서 기술된 우리의 RTT 기반 혼잡 제어 알고리즘을 구현한다. 전송률 계산 엔진의 인터페이스는 단순하다. 각 종료 이벤트마다 RTT 측정 엔진은 마이크로 초의 RTT를 전송률 계산 엔진에 제공한다. 이는 단순히 입력을 요구하지만, NIC 에서 발생한 지연과 같은 추가적인 시간 정보도 유용할 수 있다. 패킷 레벨 동작의 요구사항은 없으며, 우리는 일반적인 동작에서 NIC offload 때문에 하나의 완료 이벤트의 세그먼트 크기는 64 KB까지라고 예상한다. 전송률 계산 엔진은 매 종료 이벤트마다 혼잡 제어 알고리즘을 실행하고, flow를 위한 최신화된 목표 전송률을 산출한다.

3.3. 전송률 제어 엔진

메시지가 송신될 준비가 되었을 때, 전송률 제어 엔진은 전송을 위해 이를 세그먼트들로 쪼개고, 각 세그먼트를 순서대로 스케쥴러로 보낸다. 실행시간 효율성을 위해, 우리는 단일 스케쥴러를 구현하여 모든 flow를 처리한다. 스케쥴러는 세그먼트 크기, flow 전송률(전송률 계산 엔진에 의해 제공된), 그리고 적절한 전송 수준(pacing) 지연을 가진 현재 세그먼트의 전송 시간을 계산하기 위한 마지막 전송 시간을 사용한다. 세그먼트는 이후 스케쥴러의 우선순위 큐에 배치된다. 과거의 전송 시간들을 가진 세그먼트들은 라운드-로빈[12] 방식으로 서비스가 제공된다. 미래 전송 시간을 가진 세그먼트들은 큐에 대기한다. 전송 수준 지연(pacing delay)이 경과된 후, 전송률 제어 엔진은 세그먼트를 NIC으로 전달하여 패킷의 burst 로 즉시 전송되도록 한다. 데이터는 우선 64 KB 세그먼트들로 묶이고(batched), 이어서 스케쥴러가 두 묶인 세그먼트들 사이에 삽입하기 위한 전송 수준 지연을 계산한다. 64 KB는 최대 일괄처리 크기이며, 요구사항이 아님을 주의한다. 예를 들어, 임의의 주어진 시간에 교환할 작은 메시지만을 가진 한 flow 의 세그먼트 크기는 64 KB보다 작을 것이다. 우리는 나중에 64 KB보다 작은 세그먼트 크기들에 대한 결과도 나타낸다.
  TIMELY는 NIC offload 의 광범위한 사용으로 주어지는 트래픽 burst들을 통해 더 나은 제어를 제공하므로 윈도우 기반 보다는 전송률 기반이다. 대역폭-지연 결과물(product)은 데이터센터에서 작은 수의 패킷 버스트들이다. 예를 들어, 10 Gbps에서 51㎲가 하나의 64 KB 메시지이다. 이 체제에서(In this regime), 패킷 전송들에 세밀한 제어를 제공하지 않는다. 특정 목표 전송률을 명시하여 버스트들 간의 차이를 직접 제어하는 것이 더 쉽다. 안전 장치(safegurad)로서, 우리는 두드러진(outstanding) 데이터의 양을 하나의 고정된 최악의 경우의 한계로 제한한다.

4. TIMELY 혼잡 제어

우리의 혼잡 제어 알고리즘은 전송률 계산 엔진에서 수행된다. 이 섹션에서 우리는 우리의 환경과 주요 성능 측정 기준(key performance metrics)에 이어서, 우리의 변화도 기반 접근과 알고리즘을 기술한다.

4.1. 측정 기준과 설정

데이터 센터 네트워크 환경은 높은 대역폭과 낮은 지연 경로들에서 밀접하게 연결된(tightly-coupled) 형태의 계산으로부터 많은 폭발적인(bursty) 메시지 작업량으로 특정된다. 이는 여러모로 전통적인 넓은 영역의 인터넷의 반대이다. 대역폭은 풍부하고, flow 완료 시간(예를 들어, 원격 프로시저 호출(RPC))은 우선적인 관심사이다. 짧은 RPC들에게, 최소한의 완료 시간은 전파와 직렬화의 지연에 의해 결정된다. 그러므로, 우리는 RTT를 낮게 유지하기 위해 모든 큐잉 지연의 최소화를 시도한다. 꼬리 지연은 하나의 작은 패킷 조각이라도 늦게 되면 어플리케이션 성능을 떨어뜨리므로 중요하다. 일관된 낮은 지연은 낮은 큐잉 지연과 거의 영(0)에 가까운 패킷 손실을 암시한다. 더 긴 RPC들은 공유된 네트워크를 가로지르는 더 많은 데이터를 전송하는 데 걸리는 시간 때문에 더 큰 완료 시간들을 가질 것이다. 추가되는 시간을 낮게 유지하기 위해서, 우리는 반드시 높은 통합 처리량(high aggregate throughput)을 유지하여 모든 flow 에 도움을 주고, 대략적인 공정성을 유지하여 하나의 flow도 불리하지 않아야 한다(no one flow is penalized).
  평가를 위한 우리의 첫 번째 측정 기준은 꼬리(99 퍼센트의) RTT와 통합 처리량으로, 이들은 얼마나 빠르게 우리가 짧고 긴 RPC 들을 완료하는 지를 (어느정도의 공정성을 가정하며)결정한다. 패킷의 RTT 와 처리량에 충돌이 있는 경우, 우리는 작은 량의 대역폭을 희생하는 댓가로 RTT 가 낮게 유지되는 것을 선호한다. 왜냐하면 처음부터 대역폭은 풍부하고, 증가하는 RTT는 직접적으로 짧은 전송의 완료 시간에 영향을 주기 때문이다. 이 효과에서, 우리는 처리량 / 지연 곡선을 타고 어느 지점에서 꼬리 지연을 용납할 수 없는 지를 찾는다. 두 번째 측정 기준은 공성성과 손실이다. 우리는 이를 자세히 연구하기 보다는 양쪽을 확인하여 알린다. 마지막으로, 우리는 더 높은 평균보다는 안정적인 설계를 선호하지만, 예측 가능한 성능의 댓가를 위한 동요(oscillating)는 허용한다.

4.2. 지연 변화도 접근

FAST TCP 와 Compound TCP 와 같은 지연 기반 혼잡 제어 알고리즘들은 TCP Vagas 의 중대한 작업(seminal work)에 의해 영감을 받았다. 이들은 기준선 이상으로 증가하는 RTT 를 혼선의 지표(indicative)로 해석한다. 만약 지연이 더 증가하여 버퍼 점유가 병목 큐 근처의 일부 미리 정의된 한계점(threshold)에서 유지되면 그들은 송신율을 줄인다. 그러나, Kelly 등은 반복(loop) 지연 제어 시간보다 입력 시간(in time)이 짧을 때 큐 크기를 제어하는 것이 불가능하다고 주장한다. 이것이 경쟁하는 트래픽으로 인해 10 Gbps 링크를 통해 64 KB 메시지가 최소 51㎲ 이거나 상당히 더 높아질 수 있으며, 반면에 한 패킷의 큐잉 지연이 1㎲인 데이터 센터의 경우이다. 이런 환경에 있는 어떠한 알고리즘이 할 수 있는 최선(the most)은 큐 점유의 분산을 제어하는 것이다. 큐 크기의 제어가 가능하다고 해도, 다수의 큐가 병목이 될 수 있는 데이터 센터를 위한 한계점을 선택하는 것은 악의적으로 어려운 튜닝 문제이다.
  TIMELY's 의 혼잡 제어기는 높은(standing) 큐를 유지하는 대신에, 큐잉의 시간에 관한 파생물 또는 지연 변화도에 반응하여 낮은 지연을 달성한다. 이것은 우리가 큐잉 지연의 변화를 나타내는 RTT들의 차이점을 정확하게 측정할 수 있기 때문에 가능하다. RTT들의 증가로 인한 양수의 지연 변화도는 큐의 증가를 나타내고, 반대로 음수의 변화도는 큐의 감소를 나타낸다. 이 변화도를 이용하여, 우리는 높은 큐가 생성될 때까지 기다리지 않고 큐 증가에 반응할 수 있다. 이 전략이 우리가 낮은 지연을 달성하도록 돕는다.
  지연 변화도는 병목 큐에서 전송률 부조화의 대리인이다. 우리는 단지 큐 크기들에 기반한 명시적 피드백보다 더 좋은 안정성과 융합된 속성들이 가지는 전송률의 부조화에서 명시적 피드백을 찾은 RCP, XCP, PI, 그리고 QCN 에서 영감을 받았다. 후자일 수록 덜 정확하게 큐가 제어되도록 할 수 있다. 중요한 차이점은 이전의 컨트롤러들은 네트워크의 큐에서 동작하지만, TIMELY 는 종단 간(end to end)의 지연 변화도를 사용하여 유사한 이익을 달성한다.
  우리가 가정한 모델은 N 개의 종단 호스트가 전체 전송률 y(t)로 처리율(drain rate) C 를 가진 병목 큐로 데이터를 전송한다. 즉, 외부 전송률(outgoing rate)은 ≤ C 이다. 우리는 병목 큐를 통하는 큐잉 지연을 q(t) 로 표시한다. 만약 y(t) > C 이면, 이 큐가 생성하는 전송률은 (y(t) - C)이다. 왜냐하면 규잉된 데이터가 C 의 속도로 처리(drain)되므로, 큐잉 지연 변화도는 dq(t) / dt = (y(t) - C) / C 로 주어진다. 이 변화도는 무차원(dimensionless)이다. 이 것은 y(t) > C 이면 양수이고, 얼마나 빠르게 큐가 높아지는 중(building)인지 신호를 준다. y(t) < C 일 때 음수의 변화도는 얼마나 빠르게 큐가 빠져나가는 중(draining)인지 신호를 준다. 그러므로, RTT 신호들을 통해 측정된 지연 변화도는 병목에서의 전송률 부조화의 지표로 행동한다. 이 논리는 네트워크에 제로가 아닌 큐가 있는 동안 유지된다. 제로 큐가 있거나, 큐의 크기가 변하지 않을 때, 측정된 변화도 역시 제로다. TIMLEY는 총합의 유입(incoming) 전송률 y(t)를 처리율(drain rate)인 C에 맞추려 노력하여, ((y(t) - C) / C) = (dq(t) / dt) = (d(RTT) / dt) 의 측정된 오류의 비율로 연결당 전송율(per-connection rate) R(t)에 적응(adapt)시킨다.

4.3. 주요 알고리즘


알고리즘 1은 우리의 혼잡 제어 알고리즘의 의사코드이다. TIMLEY 는 각 연결에서 단일 전송률 R(t)를 유지하고 매 완료 이벤트마다 RTT 표본을 사용하여 이를 갱신한다. 이것은 처리량을 가용한 대역폭에 가깝도록 유지하기 위해 다듬어진(smoothed) 지연 변화도를 오류 신호로 사용하여 변화도 추적, 전송율 조정을 적용(employ)한다. 추가적으로, 우리는 사용할 수 없거나(under utilization), 과도하게 높은 패킷 지연의 극단적인 경우를 찾고 대응하기 위한 한계점(threshold) 를 사용한다. 그림8은 두 한계점들과 변화도 구간을 보여준다.

그림8. 상ㆍ하 RTT 한계점과 변화도 추적 구간

RTT가 명목상(nominal) 운영 범위 안에 있을 때, 변화도 추적 알고리즘은 RTT 표본들로부터 지연 변화도를 계산하고 이를 송신율를 조정하는 데 사용한다.

지연 변화도 계산하기. 우리는 NIC를 사용하는 정확한 RTT 측정에 의존한다. 지연 변화도를 계산하기 위해서, TIMELY는 두 개의 연속된 RTT 표본 사이의 차이를 계산한다. 우리는 이를 최소 RTT 로 나눠서 이 차이를 표준화하고, 무차원 양(dimensionless quantity)을 획득한다. 실제로는, 최소 RTT 의 정확한 값은 중요하지 않으며, 왜냐하면 우리는 큐가 증가하고 있는 지 감소하고 있는 지만을 결정하기 때문이다. 그래서 우리는 미리 알 수 있는 데이터센터 네트워크의 회선 전파 지연을 나타내는 고정된 값을 사용한다. 마지막으로, 우리는 이 결과를 EWMA 필터[13]에 보낸다. 이 필터는 우리가 큐의 전체적인 상승과 하락의 경향을 탐지할 수 있도록 하며, 반면에 혼잡을 나타내지 않는 작은 큐의 변동(fluctuation)은 무시한다.

전송률 계산하기. 다음, TIMELY는 일반화된 변화도를 사용하여 연결의 목표 전송률을 갱신한다. 만약 변화도가 음수 또는 영과 같으면, 네트워크는 총 수신률을 따라갈 수 있고, 그러므로 더 높은 전송률을 위한 여지가 있다. 이 경우, TIMELY 는 연결의 추가적인 증가 R = R + δ 를 수행하여 더 많은 대역폭을 조사하고, 여기에서 δ 는 대역폭 추가 증가 상수이다. 변화도가 양수이면, 전체 전송률은 네트워크 용량(capacity)보다 크다. 그러므로, TIMELY는 변화도 인수로 측량(scaled)한 증가하는 전송률의 감소 β 를 수행한다.


전체 수신과 송신 전송률을 기반하는 지연 변화도 신호는 혼잡한 경로와 함께 모든 연결에 공통적이다. 잘 알려진 AIMD[14] 속성은 우리의 알고리즘이 모든 연결에서 공정성을 확보하는 것을 보장한다.
  지연 변화도가 일반적인 동작에서는 효과적이지만, 상당히 불리하거나 높은 지연의 상태들에서는 더 공격적인 반응이 필요하다. 다음 우리는 어떻게 TIMELY가 이러한 상황을 탐지하고 반응하는 지를 논한다.

낮은 RTT 기준점 Tlow의 필요성. 우리의 알고리즘을 위한 이상적인 환경은 패킷들이 완벽하게 보조를 맞추는 것이다. 그러나, 현실적인 설정에서, TIMELY 전송률은 64KB 까지 커질 수 있는 세그먼트 단위로 강요된다. 이 큰 분할은 네트워크에서 일시적인(transient) 대기열을 초래하는 패킷 버스트들을 초래하므로, 때때로 충돌이 있을 때 RTT 가 치솟는다(spikes). 신경쓰지 않으면, 핵심 알고리즘은 갑작스런 RTT 의 치솟음으로 인한 양수의 변화도를 탐지할 것이고, 불필요하게 혼잡을 추측하고 속도를 늦춘다(back-off). 우리는 낮은 기준점 Tlow을 이용하여 RTT의 치솟음을 거름(filter)으로써 이 행동을 회피한다. 지연 변화도 기반의 조정(adjustment)은 기준점보다 큰 RTT 표본들로 시작된다. 더 큰 메시지는 더 많은 폭발적인(bursty) 큐 점유를 초래하므로, Tlow는 네트워크에서 사용되는 세그먼트 크기의 (비선형) 증가함수이다. 우리는 우리의 평가에서 이 효과를 연구하였으며, 또한 호스트에서 어떻게 정밀하게 속도를 조절하는 것이 폭발성(burstiness)를 줄일 수 있는 지와 낮은 기준점의 필요성을 보인다.

높은 RTT 기준점 Thigh의 필요성. 핵심 변화도 알고리즘은 매우 작은 큐를 만드는 동안에 병목 처리량에 가깝도록 유지한다. 그러나, 이론적으로, 큐가 높고, 고정된 수준으로 유지되는 동안 변화도가 제로에 머무를 수 있다. 이 염려를 없애기 위해, Thigh는 허용할 수 있는 종단 간 네트워크 큐 지연, 다시 말해 꼬리 지연의 상위 경계로서의 역할을 한다. 이는 지연이 증가할 때 변화도와 무관하게 전송률을 줄이는 방법을 제공하고, 우리가 알고있는 특정을 가진 데이터 센터 환경에서 동작하기 때문에 가능한 보호이다. 만약 측정된 RTT 가 Thigh보다 높으면, 우리는 전송률을 곱수로(multiplicatively) 줄인다.


우리는 매끄러운(smoothed) RTT 보다 순각적인(instantaneous) 것을 사용했다는 것에 주의한다. 이 것이 일상적이지 않게 보일 수 있지만, 우리는 과도하게 큰 하나의 RTT 가 혼잡을 알린다고 자신하고, 우리의 우선순위는 낮은 패킨 지연의 유지와 손실 회피이므로, 이에 반응하여 느리게 할 수 있다. 우리는 평균 RTT 를 혼잡 기준으로 반응하려 노력하였지만, 피드백 루프에서의 추가 지연 때문에 패킷 지연을 손상시키는 것을 발견하였다. 평균이 상승하고, 혼잡 제어가 전송률을 낮출 때, 네트워크에서 큐잉 지연은 이미 증가하였다. 우리의 발견은 평균적인 큐의 길이가 RED QAM[15] 을 떨어뜨린다는 이론적인 분석을 제어를 통해 보여준 [16]와 일치한다. 우리는 6번 단원에서 어떻게 Thigh가 처리량-지연 상충 곡선에서 우리를 올바르게 태워주는 지를 보인다.

빠른 수렴을 위한 과민한 증가. ㄷㄷㄷㄷ

[2] Network Interface Card
[3] Round Trip (delay) Time, 왕복 (지연)시간
[4] 본문의 rate 와 pace 를 직역하면 모두 '속도'이다. 의미의 차이를 고려하여, rate 는 '전송률', pace 는 pacing 을 포함하여 '전송 수준'으로 번역한다.
[5] 1952년 찰스 클로스가 처음 공식화하였으며, 모든 leaf switch 는 모든 spine 과 연결되어, leaf 간 통신의 hop 수는 2로 고정된다. 세부 내용은 아래 내용 참고. 특히 그림을 보자.
[6] Priority-based Flow Control
[7] 직역하면 직물, 천 등인데, 데이터 센터 내부의 Clos 네트워크의 다른 이름으로 이해된다. 
[8] 데이터가 네트워크 MTU(또는 PDU)로 분할(segmentation) 되었을 때 뒷 부분의 데이터 도착이 지연되는 것을 의미하는 것으로 이해된다.
[9] Data Center TPC : 데이터센터의 트래픽을 위한 프로토콜이며, RFC 8257 이다.
[10] CPU가 처리하지 않고, NIC가 직접 처리하는 작업량으로 이해된다. 세부 정보는 아래 블로그들 참고.
[11] Burst. 직역하면 파열, 한바탕 터뜨림이다. 물리적 송수신 단위로 이해된다.
[12] 줄여서 RR 스케쥴링. 시분할 시스템의 선정형 스케쥴링으로, 세그먼트들 사이에 우선순위를 두지 않고, 순서대로 시간단위(Time Quantum)로 처리하는 방식. 세부 내용은 위키 참고.
[13] Exponentially Weighted Moving Average 의 약자로, 지수적으로 가중된 이동 평균으로 번역할 수 있다. 노이즈 처리와 관련된 고성능 필터로 이해된다. 아래 참고.
[14] TCP 혼잡 제어 알고리즘으로, Addive Increase Multiplicative Decrease 의 약자이다. Network 의 상태가 좋아서 보내는 양을 증가시킬 때는 천천히, 반대로 감소시킬 때는 급격히 줄인다는 의미이다. 출처는 아래 블로그.
[15] TODO
[16] C. Hollot, V. Misra, D. Towsley, and W.-B. Gong. A control theoretic analysis of RED. In IEEE Infocom '01.

2020년 8월 12일 수요일

"양자 컴퓨팅 입문" 요약 - 1장. 복소수, 벡터 공간, 디랙 표기법

작성중인 글입니다.

1.1 복소수

양자 컴퓨팅을 이해하려면 복소수의 성질을 어느 정도 알아야 한다. 복소수는 실수와 허수라는 두 가지 기수(fundamental numbers)로 이뤄지고, 이차 방정식의 해가 될 수 있다. 복소수 c 는 다음과 같다. 

c = a + bi

위 식에서 a 와 b 는 실수고, i 는 √(-1) 이다. 숫자 a 는 c 의 실수부, 숫자 b는 c 의 허수부이며, 다음과 같이 표현할 수 있다.

a = c 의 실수부 = Re(a + bi)
b = c 의 허수부 = Im(a + bi) [1]

실수와 허수는 복소수의 부분집합이며, Re(a + bi) = 0 이면 c 는 순허수, Im(a + bi) = 0 이면 c 는 실수이다. 0 의 경우, 0 = 0 + 0i 이므로 실수이자, 순허수이다.

그림 1.1 복소평면

복소 평면(complex plane)은 실수부 a 를 x 좌표로, 허수부 b 를 y 좌표로 하는 점으로 표시한다.  수평축은 실수축(real axis), 수직축은 허수축(imaginary axis)이라고 한다.

복소수의 크기(magnitude) 및 길이(length)는 피타고라스 정리를 이용하여, 실수부와 허수부를 제곱해 더한 값의 제곱근으로 구할 수 있다.

|c| = √(a²+ b²)

복소수 i²= -1 이라는 점만 염두하면, 연산 규칙은 다음과 같다.

덧셈 : (a + bi) + (b + di) = (a + c) + (b + d)i
곱셈 : (a + bi) x (b + di) = ac + adi + bci - bd = (ac + bd) + (ad + bc)i
나눗셈[2] : (a + bi) / (c + di) = ((ac + bd) + (bc - ad)i) / (c2 + d2)

1.2 켤레복소수

복소수 c 의 켤레복소수는 허수부의 부호를 치환하며, c* 로 표기한다.

c* = a - bi

복소 평면에서는 실수축을 기준으로 반사한 복소수이다.

그림 1.2 켤레복소수

대수식의 결레복소수는 다음 세 가지 관계를 이용한다.

1. 합의 켤레는 켤레의 합과 같다. 즉, (a + b)* = a* + b*
2. 곱의 켤레는 켤레의 곱과 같다. 즉, (ab)* = a*b*
3. 켤레의 켤레는 원래의 복소수다[3]. 즉, (a*)* = a

복소수 c = a + bi 의 법(modulus) 또는 절댓값(absolute value)는 |c| 로 표기하며, 복소 평면의 원점에서 점 c 까지의 거리이다. 자연스럽게, |c| 는 c 에 대응하는 벡터의 길이가 된다.

c 의 절댓값 제곱(square modulus)은 |c|² 로 표기하며, c 와 켤레복소수 c* 의 곱이다. cc* = |c|² 은 실수이며, 양의 값임을 아래와 같이 보일 수 있다.

cc* = (a + bi)(a - bi) = a² + b² = (√(a² + b²))(√(a² + b²)) = |c|²

복소수의 절댓값은 크기라고도 하며, 다음과 같이 표현한다.

|c| = √(cc*) = √(a² + b²)

c 의 절댓값 제곱과 c² 은 같지 않다는 점에 유의한다. c = a + bi 이므로, c² 은 다음과 같다.

c² = (a² - b²) + (2ab)i

절대값 제곱은 항상 양의 실수인 반면, 제곱은 일반적으로 복소수가 된다. 

1.3. 벡터 공간

벡터 공간 V 는 벡터인 원소, 그리고 스칼라인 원소의 집합인 체(field) F 와 두 가지 연산, 벡터 덧셈과 스칼라 곱으로 이뤄진다. 체는 a 와 b 가 F 에 속하면 a + b, a - b, ab, a/b 또한 F 에 속하는 성질을 지닌 스칼라의 집합이다(a/b 에서 b ≠ 0 을 가정).

1. 벡터 덧셈 : V 의 어떤 두 벡터 u 와 v 를 취해 u + v 라는 제 3의 벡터를 산출하며, 다음의 조건을 따른다.
  1. 닫힘성 : u + v 는 V 에 속하는 벡터다.
  2. 교환성 : u + v = v + u
  3. 결합성 : (u + v) + w = u + (v + w)
  4. 항등원 : V 의 모든 u 에 대해 (u + 0) = u 인 영 벡터 0 이 있다.
  5. 역원 : V 의 모든 u 에 대해 -u 라고 표기하며, u + (-u) = 0 인 벡터가 있다.
2. 스칼라 곱셈 : F 의 스칼라 c 와 V 의 벡터 v를 취해 V 에 속하는 새로운 벡터 cv 를 산출하며, 다음의 조건을 만족한다.
  1. 닫힘성 : cv는 V 에 속한다.
  2. 분배성1 : c(u + v) = cu + cv // 스칼라 값이 분배
  3. 분배성2 : (c + d)u = cu + du // 벡터가 분배됨
  4. 결합성 : c(du) = (cd)u
  5. 항등원 : 1(u) = u
예를 들어, 복소 벡터 공간 Cⁿ 의 두 복소 벡터 X와 Y 가 있다고 하자.

X = (x₁, x₂, ..., xn), Y = (y₁, y₂, ..., yn)

덧셈 연산은 아래와 같이 성분 별로 더한다.

X + Y = (x₁ + y₁, x₂ + y₂, ..., xn + yn)

곱셈 연산은 각 성분 X(또는 Y)에 복소수 c 를 곱해준다.

c(X) = (cx₁,  cx₂, ..., cxn)

1.4 기저 집합

고전 물리학이 3차원 공간의 위치를 직교하는 세 축 x, y, z 좌표로 결정하듯이, 유사한 개념으로 양자역학에는 상태 벡터(state vector)로 표현하며, 이때 기저 집합(basis set)을 이용한다. 어떤 벡터 공간


[1] 허수는 영어로 Imaginary number 이다. 실수는 Real number.
[2] 허수부의 부호를 반대로 하는 켤레 복소수 c - di 를 분자와 분모에 곱한다. 즉, ((a + bi) / (c + di)) x ((c - di) / (c - di)) 를 정리한다. 이 과정을 '분모의 실수화'라고 한다. 출처는 아래 블로그.
https://mathbang.net/305
[3] 처음 값으로 돌아오는 성질을 연산의 역원이라고 하며, 암호학에서 암호문이 평문으로 돌아가도록 하는 중요한 성질이다.

2020년 8월 11일 화요일

"양자 컴퓨팅 입문" 요약 - 시작하는 글


이 글은 위 사진의 "양자 컴퓨팅 입문 - 간결하게 배우는 양자 컴퓨팅(파라그 랄라 지음, 이태휘 옮김, 2020년 1월 30일 발행)" 을 공부하는 글입니다. 공부 중인 분야이므로, 제 이해도에 따라 원문의 내용이 변질(?)될 수 있습니다.

이전에 보았던 "양자비트와 양자암호"와 비교하여 책의 두꼐는 비슷하지만, 수식이 많습니다. 옮긴이께서는 "양자 컴퓨팅의 기초를 이해하는 데 필요한 양자역학과 대수학 내용을 모두 포함하면서도 필요한 내용만 간결하게 담으려고 시도했다" 라고 합니다. 제가 잘 이해한다면, 박사과정으로 양자보안 연구를 시작하는 저에게 많은 도움이 될 것이라 생각합니다.

본문의 출처는 거의 위 책이므로 별도의 인용부호는 생략하며, 제 소견 등은 나무위키 스타일 또는 각주[#]로 추가할 예정입니다.

2020년 8월 5일 수요일

Introduction

이성민(Sungmin Lee)


Email : lee@sungmin.net
Office : 서울특별시 관악구 관악로1 서울대학교 제1공학관(301동) 5층 554-1호[1]
  1. History
    1. '20.07 ~ 현재, 서울대학교 컴퓨터공학부 인터넷 융합 및 보안 연구실 박사과정
    2. '14.07 ~ '20.07, LG전자 Mobile Communication(MC) 연구소 Platform Security Senior developer[2]
    3. '12.07 ~ '14.07, 연세대학교 신촌캠퍼스 컴퓨터과학과 석사 과정(졸업)
    4. '07.03 ~ '12.06, 육군 정보 장교[3]
    5. '03.03 ~ '07.02, 인하대학교 컴퓨터공학과 학사 과정(졸업)

  2. Records
    1. Android open source project contributor[4]
    2. LG전자 사내 암호학 강사 및 Security 관련 세미나 발표 다수[5]
    3. KAIST 정보전자연구소, LG전자-KAIST S/W Security Specialist 과정[6] 수료
    4. Cousera, University of Maryland College Park, S/W Security 과정 수료[7]
    5. 정보보안기사 등 컴퓨터 관련 자격증 다수[8]
    6. '12년 하반기 LG전자 산학장학생
    7. '08년 육군 정보학교, 초급 장교 과정(OBC) 수료
    8. '07년 특전사 교육단, 지상 침투 과정 수료
    9. '07년 육군 보병학교, 초급 장교 과정(OBC) 특수전(특공, 수색, 특전)반 수료
    10. '04년 육군 장학생

  3. Publication
    1. "A Mitigation Scheme of DoS Attacks against IEEE 802.11i Using Dynamic MAC Address", EECS 2013
[2] LG 모바일 원격 잠금해제(Remote Unlock), Android Enterprise, Factory Reset Protection, Key Store, H/W backed Key Master, H/W backed Gate Keeper, VPN, CertInstaller, etc
[3] 대위 만기 전역(ROTC 45기 + 군장학생 복무연장)
[5] LG그룹사 교육 플랫폼 '러닝넷'의 "Cryptographic Terminologies of Android Compatibility and Definition Document(CDD)" 오프라인 강의, "침투테스트" MC Security 팀세미나 발표 등
[6] '19.06.17-'19.07.19, 오프라인, https://csrc.kaist.ac.kr/content?menu=123
[8] 정보처리기사, 컴퓨터그래픽스 운용기능사, 컴퓨터 활용능력 1급, 프레젠테이션 1급, 워드프로세서 1급 등.

2020년 7월 29일 수요일

NIST, "Report on Post-Quantum Cryptography" 직역

이 글은 2016년 NIST 에서 공개한 NISTIR 8105, "Report on Post-Quantum Cryptography", Lily Chen et al[1] 을 공부하는 글입니다. 번역기를 사용하지 않고, 제 번역 능력과 이해도에 따라 단어 선정이나 글의 흐름이 매끄럽지 않을 수 있습니다. 본문의 인용부호[#]는 순서를 조정하여 포함하거나, 불필요하다고 판단하면 생략합니다.

(NIST의 ITL 소개 생략)

요약

최근 몇 년간, 양자 현상 기술을 활용하여 전통적인 컴퓨터는 처리할 수 없거나 어려운 계산 문제들을 푸는 기계인 양자 컴퓨터에 대한 상당한 연구가 있었다. 만약 큰 규모의 양자 컴퓨터가 개발되면, 현재 사용 중인 다수의 공개키 암호체계를 깰 수 있을 것이다. 이는 인터넷 등에서 이뤄지는 디지털 커뮤니케이션의 기밀성과 무결성을 심각하게 훼손한다. 양자 후 암호(또는 양자-내성 암호라 불림)의 목적은 양자 및 전통 컴퓨터 양쪽에서 안전한 암호 체계를 개발하는 것이며, 현존하는 네트워크 및 프로토콜과 연동할 수 있어야 한다. 이 내부 보고서는 현재 양자 계산과 양자 후 암호의 상태에 대한 NIST의 이해를 공유하고, 이 세계로 나아가기 위한 NIST 의 첫 계획을 요약한다. 또한 이 보고서는 새로운 암호 기반으로의 전환이 가지는 어려움(challenge)을 식별하고, 유관 기관(agencies)들이 암호화 민첩성(crypto agility)[2]에 집중해야 하는 필요성을 강조한다.

(Keywords, Table of Contents 생략)

1. 서문

지난 30년 간, 공개키 암호는 우리의 전 세계적 디지털 커뮤니케이션 기반의 필수적인 요소가 되었다. 이 네트워크들은 모바일 폰, 인터넷 거래, 소셜 네트워크와 클라우드 컴퓨팅과 같이 우리의 경제, 우리의 보안, 그리고 우리의 삶의 방식에 중요한 다양한(plethora) 앱들을 지원한다. 이러한 연결된 세계에서, 개인, 기업, 그리고 정부의 안전한 통신 능력은 가장 중요한 요소이다.

대다수 우리의 가장 중요한(crucial) 통신 프로토콜들은 주로 세 개의 핵심적인 암호학적 기능들, 즉 공개키 암호화, 전자 서명, 그리고 키 교환에 의존한다. 현재, 이 기능들은 디피-헬만 키 교환, RSA 암호체계, 그리고 타원 곡선 암호체계를 주로 사용하여 구현된다. 이들의 보안은 다양한 군(group)에서 정수 인수분해 또는 이산 로그 문제와 같은 특정 수의 이론적 문제의 어려움에 의존한다.

1994년, 벨 연구소의 피터 쇼어는 물질의 물리학적 특성과 에너지를 활용하여 계산을 수행하는 양자 컴퓨터가 이 문제들을 효율적으로 풀 수 있고[3], 이를 통해 그 가정[4]을 기반으로 하는 모든 공개키 암호체계가 무력화됨을 보였다. 따라서, 충분히 강력한 양자 컴퓨터는 현재 통신 형태 - 키 교환에서 암호화와 디지털 인증 - 를 위험하게 할 것이다.

양자 컴퓨터가 특정 문제들을 전통 컴퓨터보다 빠르게 푸는 데 활용될 수 있다는 발견은 양자 계산에 대한 흥미를 엄청나게 고무시켰다. 양자 복잡성(complexity)은 전통적인 복잡성과 근본적으로 다른가? 큰 규모의 양자 컴퓨터는 언제 개발될 것인가? 양자 계산과 전통 계산의 공격(adversary) 양쪽 모두에 저항(resist)하는 방법이 있는가? 연구자들은 이 문제에 대해 고민하고 있다.

쇼어의 발견 이후 20년 동안, 양자 알고리즘의 이론은 상당히 발전했다. 지수적 속도 증가(exponential speedup)를 달성하는 양자 알고리즘들이 물리학 모의실험(physics simulation), 정수론(number theory), 그리고 위상수학(topology)에 관련된 문제들에서 발견되었다. 그럼에도, 양자 계산의 지수적 속도 증가를 받아들이는 문제들의 목록은 상대적으로 적게 유지되었다. 반면에, 검색(searching), 충돌 탐지(collision finding), 그리고 부울 공식의 정리(evaluation of Boolean formulae)에 관련된 넓은 집합의 문제들에서 더 적당한(modest) 속도 증가가 개발되었다. 특히, 그로버의 검색 알고리즘은 비구조화된 검색 문제들(unstructured search problems)에서 두 제곱적 속도 증가(quadratic speedup)을 제공한다. 이러한 속도 증가가 암호학적 기술을 쇠태(obsolete)시키지는 않지만, 더 큰 키 길이(size)의 필요성에 영향을 줄 수 있으며, 대칭키의 경우도 포함된다. 표1은 큰 큐모의 양자 컴퓨터가 AES 와 RSA 같은 일반적인 암호 알고리즘에 미치는 영향의 요약을 보여준다. 어느 정도까지 양자 발전이 진행될 수 있는 지와, 양자 모델과 전통 모델 간의 실현 가능성(feasibility)의 차이(gap)가 얼마나 넓은 지는 알려져 있지 않다.

표1. 주요 암호 알고리즘에 대한 양자 컴퓨팅의 영향

큰 규모의 양자 컴퓨터가 언제 만들어질 것인지라는 질문은 복잡하고 논란의 여지가 있다. 과거에는 큰 규모를 가진 양자 컴퓨터의 물리적 가능성이 명확하지 않았으나, 이제 많은 과학자들은 단지 거대한 공학적 어려움이 있을 뿐이라고 믿고 있다. 심지어 일부 전문가들은 다음 20년 정도 안에 현재 사용되고 있는 모든 공개키 기법을 근본적으로 깰 수 있는 충분히 큰 양자 컴퓨터가 만들어질 것이라고 예상한다[5]. 우리의 현재 공개키 암호 기반이 전개되는 데에 거의 20년이 걸렸다. 현재 널리 쓰이는 암호 체계가 그들의(their?) 양자 컴퓨팅을 저항하는 반대측(counterparts)으로 원활하고, 안전하게 이동(migration)하도록 보장하기 위해서는 상당한 노력이 소요된다. 그러므로, 우리는 양자 컴퓨팅 시대가 도래하는 정확한 시간을 추정할 수 있을 지와 관계없이, 지금 반드시 우리의 정보 보안 체계가 양자 컴퓨팅에 저항할 수 있도록 준비를 시작해야 한다.

하나의 큰 다국적 공동체가 새로운 양자-내성의 원시적 특성들(primitives)을 활용하여, 우리의 공개키 기반이 온전하게(intact) 유지되기를 바라며, 미래 양자 컴퓨팅에서의 정보 보안 이슈를 다루기 위해 나타났다. 학계에서는, 이 새로운 과학을 "양자 후 암호(Post-Quantum Cryptography)"라는 이름으로 탄생시켰다(bears). 2006년에 시작된 PQCrypto 는 이 분야의 활발한 연구를 위한 자체 학술대회(conference)이다. 국가 기금(funding) 단체들로부터 상당한 지원을 받아왔으며, 가장 눈에 띄는 국가는 일본과 유럽으로, 유럽 연합의 PQCrypto 와 SAFEcrypto 프로젝트, 그리고 일본의 CREST Crypto-Math 프로젝트가 있다.

이러한 노력들이 기초 연구의 진보를 이끌고, 현실 세계에서 양자 후 암호체계의 발전을 위한 길을 다지고(paving) 있다. 지난 몇 면간, 산업과 표준 단체들은 이 분야에서 각자의 활동을 시작했으며, 2013년 부터 유럽 통신 표준원(ETSI, European Telecommunication Standards Institute)은 세 번의 "양자-안전 암호(Quantum-Safe Cryptography)" 토론회(workshop)를 개최했고, 2015년 NIST 는 정부, 산업, 학계에서 140명 이상이 참석한 "양자 후 세계의 사이버보안(Cybersecurity in a Post-Quantum World)" 토론회를 개최하였다.

NIST는 비정부 보안 연방 정보 체계의 보호를 위한 지침과 표준을 개발하는 넓은 책임의 부분으로 양자 후 암호 표준화의 고유한 역할을 가진다. AES와 같은 많은 NIST 표준들이 학계와 산업계의 폭넓은 참여를 통해 개발되었으며, 효과적인 방안으로 널리 적용되었다. 양자 후 암호의 NIST 표준화는 유사한 유익을 제공할 것이다.

이 모든 소식(sources)들을 고려할 때, 양자-내성 기술을 개발하는 노력이 격렬해지는 것(intensifying)은 명확하다. 동등하게, 새로운 양자 후 공개키 암호가 표준화될 필요성과 동반되는 투자가 시급한 것도 명확하다. 이 다국적 양자 후 암호 공동체에 NIST 암호 표준이 관여하여 전 세계의 학계와 다른 표준 단체들에게 동의를 받는(endorsed) 것은 중요하다. 이 내부 보고서는 양자 계산과 양자 후 암호에 대한 NIST 의 현재 이해와 우리가 앞으로 나아갈 계획의 개요를 공유한다.

2. 양자-내성 암호의 개요

오늘날 공개키 암호의 가장 중요한 사용은 전자 서명과 키 생성이다. 표1에서 언급하였듯이, 큰 규모의 양자 컴퓨터의 개발(construction)은 많은 공개키 암호체계를 불안하게 할 것이다. 특히, RSA와 같이 정수 인수분해의 어려움을 기반으로 하는 것들과 이산 로그 문제의 어려움을 기반으로 하는 것들도 포함한다. 반대로, 대칭 키 체계에 대한 영향은 급격하지않다. 그로버의 알고리즘은 전통적인 컴퓨터에서의 검색 알고리즘과 비교하여 양자 컴퓨터에서 두 제곱(quadratic)적 속도 증가를 제공한다. 우리는 그로버의 알고리즘이 어떤 실질적 관계가 있을지는 잘 모르지만, 만약 그렇다면, 보안을 유지하기 위해 키 길이를 두 배로 늘리는 것이 적당하다. 게다가, 검색 알고리즘의 지수적 속도 증가는 불가능함이 보여졌으므로[6], 양자 시대에도 대칭 알고리즘과 해시 함수는 사용 가능할 것이라고 제안한다.

결과적으로, 전통 컴퓨터와 양자 컴퓨터 양쪽에서 공격에 저항한다고 믿어지는 알고리즘의 탐색은 공개키 알고리즘에 집중되었다. 이 단원에서, 우리는 제안된 양자 후 원시적 특성들의 주요 집단(family)의 개요를 간단하게 설명한다. 이 집단은 격자(lattices), 코드, 그리고 다변수 다항식(multivariate polynomials)과 다른 일부(handful of others)를 기반으로 하는 것들을 포함한다. 추가 정보는 [7, 8]을 보라.

격자-기반 암호 : 격자 문제 기반의 암호체계는 몇 가지 이유로 새로운 관심을 받아왔다. 흥미로운 새 응용들(완전 동형 암호화(fully homomorphic encryption)[9], 코드 난독화, 그리고 속성 기반 암호화[10] 등)이 격자 기반 암호를 사용하여 가능해졌다. 대부분의 격자-기반 키 성립(establishment) 알고리즘들이 상대적으로 단순하고, 효율적이며, 고도의 병렬화가 가능하다. 또한, 일부 격자-기반 체계의 보안은 평균적인 경우가 아닌 최악의 경우의 강도 가정에서도 증명 가능하게 안전하다. 반면에, 알려진 암호문 해독 기법에 대해 격자 기법들의 정확한 보안성을 추측하기 어렵다는 것이 증명되었다. 

코드-기반 암호 : 1978년, McEliece cryptosystem 에서 처음 제안하였고, 아직까지 깨지지 않았다. 그동안, 오류 보정 코드를 기반하는 다른 체계들이 제안되었다. 꽤 빠르지만, 대부분의 코드-기반 원시적 특성들은 매우 큰 키 길이를 가지고 있다. 키 길이를 줄이기 위한 시도로 더 구조적인 코드를 소개하는 다양한 변형들이 소개되었으나, 일부 제안에서는 추가된 구조가 공격을 성공하게 하였다. 코드-기반 서명을 위한 제안들이 일부 있었으나, 코드-기반 암호는 암호화 기법에 더 성공적으로 여겨진다.

다변수 다항식 암호 : 이 기법들은 유한체(finite fields) 의 다변수 다항식의 체계를 푸는 어려움에 기반한다. 몇몇 다변수 암호체계가 지난 몇 십년간 제안되었으며, 다수는 깨져 있다[11]. 다변수 암호화 기법을 위한 제안들이 일부 있었으나, 다변수 암호는 역사적으로 서명을 위한 접근법으로 더 성공적이었다.

해시-기반 서명 : 해시-기반 서명은 해시 함수를 사용하여 생성된 전자 서명이다. 그들의 보안은, 심지어 양자 공격에 대해서도, 잘 이해된다. 더 효율적인 해시-기반 서명 기법의 다수는 서명자가 반드시 이전에 서명한 메시지의 정확한 개수를 기록해야 하는 결점을 가지고 있고, 기록의 어떠한 오류라도 불안정을 초래한다. 이 기법들의 다른 결점은 오직 제한된 횟수의 서명만 생성할 수 있다는 것이다. 제한된 서명 횟수를 효율적으로 증가시키는 것이 가능하지만, 서명의 크기를 증가시킨다.

기타 - 위 집단에 포함되지 않는 다양한 체계가 제안되었다. 그 중 하나는 초단수 타원 곡선(supersingular elliptic curves)[12] 상의 등원사상들(isogenies)[13]의 계산을 기반으로 한다. 타원 곡선 상의 이산 로그 문제는 쇼어의 알고리즘으로 효율적으로 풀릴 수 있으나, 초단수 타원 곡선 상의 등원사상 문제에는 유사한 양자 공격이 알려지지 않았다. 기타 다른 제안들, 예를 들어 
꼬임군(braid groups)[14] 안에서 공액 탐색(conjugacy search) 문제[15]와 관련된 문제들은 그들의 보안이 얼마나 자신이 있는 지에 대한 충분한 분석이 이뤄지지 않았다.

현재 알려진 어떤 알고리즘도 오늘날 사용하고 있는 알고리즘을 큰 수정 없이 대체(drop-in replacement)할 수 있을 것이라고 보이지는 않는다(improbable). 아마 우리가 극복해야하는 어려움은 대부분의 양자-내성 알고리즘이 그들이 대체할 알고리즘보다 키가 길다는 것이다. 이는 TLS, IKE 와 같은 다양한 인터넷 프로토콜의 변화를 요구할 것이다. 이로 인해, 위 방법들은 반드시 조심스럽게 고려되어야 한다.

우리는 위에 언급된 제안들 중 어느 것도 모든 양자 공격에 대해 보안을 보장한다고 보지 않는다는 것을 강조(note)한다. 이 기법들을 깨는 새로운 양자 알고리즘이 발견될 수 있다. 그러나, 이는 오늘의 상태와 유사하다. 대부분의 대칭 키 암호체계의 보안이 증명되었지만, 이 증명들은 증명되지 않은 가정을 기반으로 한다. 그러므로, 알려진 공격의 결여는 현재 사용하는 공개키 암호의 보안성을 정당화하는 데 사용된다. 그럼에도, NIST는 위의 제안된 양자 후 알고리즘 중 하나가 오늘날의 사용을 위해 권고되기 전에 더 많은 연구와 분석이 필요하다고 생각한다. 이들은 오늘날 전개된 알고리즘들 만큼 암호학적 공동체로부터 검증(scrutiny)을 받지 않았다. 하나의 예외는 보안성이 널리 알려진 해시-기반 서명이다. 디지털 코드 서명, 해시-기반 서명과 같은 특정 어플리케이션은 앞으로 몇년 동안은 잠재적으로 표준화될 수 있을 것이다.

3. 양자 컴퓨팅 하드웨어의 발전

대규모의 양자 컴퓨터의 개발 가능성에 대한 연구는 피터 쇼어가 1994년에 정수 인수분해를 위한 다항-시간 양자 알고리즘을 발견한 후 진지하게 시작되었다. 그 당시에는, 양자 컴퓨팅이 근본적으로 측정 가능할 수 있을 지가 명확하지 않았다. 많은 선도적인 전문가들은 양자 상태가 너무 취약하고, 오류가 누적되어 큰 규모의 계산이 실현되지 않을 것이라고 추측하였다. 이 상황은 1990년대 후반에 양자 오류 보정 코드와 기준점 정리(threshold theorems)[16]들이 개발되면서 바뀌었다. 이 기준점 정리들은 만약 고정된 기준점 아래로 양자 컴퓨터의 각 논리 게이트("양자 게이트")의 오류율을 낮출 수 있다면, 양자 계산 실행 동안에 오류 보정 과정을 포함시켜서 임의의 긴 양자 계산이 믿을 수 있고, 결함을 포용하는(fault-tolerant) 방법으로 수행될 수 있다는 것을 보인다[17].

몇 년동안, 실험과학자(experimentalists)들은 각 양자 게이트의 오류율을 서서히 낮추며 개선된 하드웨어를 개발하였다. 동시에, 이론과학자(theorists)들은 더 높은 결함 포용 기준을 산출하는 새로운 양자 오류 보정 방법들을 개발했다. 최근에, 일부 실험과학자들은 이온 트랩과 초전도체 회로를 사용하여 가장 높은 이론적 결함 허용(약 1%)보다 명목상(nominally) 낮은 보편적인 양자 게이트들의 집합을 입증하였다[18, 19]. 이는 정부와 산업계 모두 투자를 증가하도록 고무시킨 대단한 이정표(milestone)이다. 하지만, 오늘날 일부 큐비트와 관련된 연구실 재현에서 수십만 또는 수백만의 물리 큐비트로 부호화되는 수천 개의 논리 큐비트와 관련된 대규모 양자 컴퓨터로의 이동은 상당히 장기적인 노력이 요구되는 것은 자명하다.

일반적인 목적의 디지털 양자 컴퓨터를 개발하는 것과 병행하여, 양자 강화기(annealer, 예를들면 D-Wave 기계), 아날로그 양자 모의실험기, 그리고 보손 표본화 기기(boson sampling devices)와 같은 특수한 목적을 가진 양자 아날로그 컴퓨터를 개발하려는 노력이 있다. 이 기기 중 일부는 디지털 양자 컴퓨터보다 큐비트의 수가 매우 크게 증가되었다. 그러나, 그들의 특수한 본성(specialized nature)으로 인해, 이 아날로그 양자 기기들은 암호문 해독(cryptanalysis)과의 관련성이 믿어지지 않는다.

4. 이후 방향

더 강한 암호의 필요가 전통 및 양자 컴퓨팅 기술 양쪽에서의 진보에 의해 이끌어진다. 전통적인 공격들에 대한 보안을 유지하기 위해, NIST는 이미 80 비트 보안을 제공하는 알고리즘과 키 길이를 112 또는 128 비트의 보안을 제공하는 키 길이와 알고리즘으로 권고를 전환하였다[20]. 양자 공격에 대한 보안을 제공하기 위해, NIST 는 새로운 양자 후 암호체계로의 더 어려운 전환을 용이하게 해야 할 것이다.

언제 측정할 수 있는 양자 컴퓨터가 가용해질지는 명확하지 않다. 하지만, 과거와 지금, 양자 컴퓨터를 개발하고 있는 연구자들은 2030년까지 약 10억 달러의 예산으로 2000비트의 RSA를 수 시간내에 깰 수있는 양자컴퓨터가 만들어질 수 있을 것이라고 추정하고 있다[21]. 이는 NIST 가 현재 표준화한 암호체계에 대한 심각한 장기 위협이다.

상기 예측과 전통 컴퓨터를 사용하여 이 암호체계들을 깨는 비용을 비교하는 것은 유용하다.  2011-2013년에 단계적으로 퇴출된 80비트 또는 그 미만의 보안을 제공하는 암호체계는 가장 위험하다. 이들은 현재 수만에서 수억달러의 비용 범위 안에서 깨질 수 있다. 112비트의 보안을 제공하는 암호체계는 당분간 안전하게 유지될 것이다. 이들은 아마 수십억 달러로 30 에서 40년 안에 깨질 것이다(전통 컴퓨터를 사용하여). 

그러므로, 112비트에서 128비트(또는 이상)로의 전환은 아마도 현존하는 암호체계에서 양자 후 암호체계로 전환하는 것보다 덜 긴급할 것이다. 이 양자 후 전환은 많은 근본적인 어려움들을 야기한다.

이전의 약한 암호에서 강한 암호로의 전환은 전통 컴퓨터의 공격에 대한 시간 복잡성을 기반으로 하는 알고리즘의 보안을 측정하는 보안 비트 패러다임을 기반으로 하였다.(예를 들어, 전통 컴퓨터가 128비트 보안 키를 무차별 대입 공격으로 찾는 데에 필요한 시간과 자원만큼 공격이 어렵다면, 이 알고리즘은 128비트의 보안을 가지고 있다고 말한다.) NIST SP 800-57 파트1[22]은 2016년 1월까지 NIST 에 의해 표준화된 알고리즘들을 80, 112, 128, 192, 그리고 256 비트의 보안으로 분류한다. 나아가 80비트 보안 레벨은 더이상 충분히 안전하지 않다고 여기며, 112비트 보안 레벨은 2031년까지 단계적으로 퇴출되어야 한다고 권고한다.

불행하게도, 보안 비트 패러다임은 양자 암호분석을 대항하는 알고리즘의 보안에 고려되지 않는다. 이는 우리의 양자-내성 암호로의 전환 가이드에 부적합하다. 아직 키 길이가 양자 공격에 대항하는 적용할만한 보안 레벨을 제공할 지에 대한 합의된 관점이 없다. 대칭 키에 대해서, 하나의 단순한 경험론은 두 제곱적 성능 증가를 달성하는 그로버의 알고리즘을 보완하기 위해 키 길이를 두배로 하는 것이다. 하지만, 양자 계산 하드웨어의 개발은 전통 하드웨어의 개발보다 훨씬 비용이 클 것이므로, 이 권고도 지나치게 보수적이다. 동시에, 이 권고는 더 복잡한 양자 공격들의 가능성을 고려하지 않았다[23, 24, 25]. 우리의 양자 암호 해독의 이해는 여전히 제한되며, 이 분야의 더 많은 연구가 시급히 필요하다.

양자 후 암호를 위한 표준의 개발은 양자-내성 기법들의 분석을 위한 상당한 자원이 필요할 것이며, NIST 가 표준화하기 위해 선택한 알고리즘을 확신하기 위해서는 상당한 공공의 참여가 필요할 것이다. 양자 계산 하드웨어 발전의 이정표들과 국가 안전 보장국(NSA, National Security Agency)의 최근 그들의 Suite B 지침의 변경[26]으로 인해, 최근 양자 계산과 양자-내성 암호 분야에 대한 관심은 증가되고 있다. 이는 연구 공동체에게 실질적인 양자 컴퓨팅이 정말로 임박하기 전에 다시 오지 않을 수 있는 참여 기회를 제공한다. 결론적으로, NIST는 지금 양자-내성 암호로의 전환을 준비하기 위해 시작하는 중이다.

NIST는 양자 후 암호를 표준화하는 노력을 시작하기 위해 다음의 단계를 밟고 있다. NIST는 양자-내성 공개키 암호 표준을 위한 예비(preliminary) 측정 기준을 명시할 계획이다. 이 기준은 보안과 성능 요구사항들을 포함할 것이다. 기준 초안은 2016년에 공개 의견을 위해 공개될 것이며, 올해 말 안에 완성되기를 기대하고 있다. 이 때, NIST는 양자-내성 공개키 암호, 전자 서명, 그리고 키 교환 알고리즘들의 제안을 받기 시작할 것이다. NIST는 표준화를 위해 이 기능들을 각각 제공하는 최소 하나를 선택하려 한다. NIST 는 고려되어야 하는 알고리즘들의 최종 제출일을 2017년 하반기로 선택할 것이며, 이 제안들은 표준이되기 전에 3~5년의 공개 검증을 허용할 것이다.

이 절차는 AES[27]와 SHA3[28]의 표준화를 이끈 절체들과 많은 공통점을 가질 것이지만, 경쟁이 아니다. NIST는 이 역할을 시의 적절하고 투명하게 공동체의 합의를 달성하는 절차의 관리로 여긴다. 이상적으로, 여러 알고리즘들이 "좋은 선택(good choices)"으로 나타날 것이다. NIST는 각 범주에서 표준화를 위해 하나 또는 이상을 선택할 수 있다. 이 관점에서, NIST의 양자-내성 공개키 암호 표준화 절차는 진행 중인 블록 암호 모드 개발 절차[29]와 유사할 것이다. 

양자-내성 공개키 암호의 표준들이 사용 가능해지면, NIST는 현존하는 표준들에 대한 양자 컴퓨터의 급박한 위협을 재평가할 것이며, 결과에 따라 영향을 받는 표준들을 반대(deprecated)하거나 철회(withdraw)하는 결정을 할 수 있다. 따라서 유관 기관들은 반드시 현재부터 빠르면 10년 안에 이 알고리즘들을 완전히 전환활 수 있도록 준비해야 한다. 현재 표준화된 공개키 알고리즘의 대체는 아직 준비되지 않았지만, 암호화 민첩성의 유지는 필수(imperative)이다. 새로운 양자-내성 알고리즘이 표준화될 때까지, 유관 기관들은 반드시 현재 NIST 표준에 명시된 권고하는 알고리즘들의 사용을 계속해야 한다.

(Appendix A - References 생략.. 하지만 번호를 바꿔서 거의 다 포함됨)

[2] 암호화 민첩성(Crypto-agility)은 시스템 인프라에 큰 변화를주지 않으면 서 새로운 암호화 기본 요소 및 알고리즘의 신속한 적응을 지원하는 정보 보안 시스템 설계의 실무 패러다임이라고 한다. 출처는 아래 위키.
[3] P. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete
Logarithms on a Quantum Computer, SIAM J. Comput., 26 (5), 1997, pp.
[4] 앞 문장에서 언급된, 유한체 이산대수의 소인수 분해 또는 이산 로그 문제의 어려움.
[5] M. Mosca, Cybersecurity in an era with quantum computers: will we be ready? IACR Cryptology ePrint Archive Report 2015/1075, 2015. http://eprint.iacr.org/2015/1075.
[6] C. H. Bennett, E. Bernstein, G. Brassard, and U. Vazirani, Strengths and weaknesses of quantum computing, SIAM J. Comput., 26 (5), 1997, pp.1510–1523. http://dx.doi.org/10.1137/s0097539796300933
[7] European Telecommunications Standards Institute White Paper No. 8, Quantum Safe Cryptography and Security: An Introduction, Benefits, Enablers and Challenges, June 2015. https://portal.etsi.org/Portals/0/TBpages/QSC/Docs/Quantum_Safe_Whitepaper_1_0_0.pdf
[8] R. Perlner and D. Cooper, Quantum resistant public key cryptography: a survey, In Proc. of IDtrust, ACM, 2009, pp. 85-93. http://dx.doi.org/10.1145/1527017.1527028
[9] 우선, 동형 암호는 암호문끼리 연산이 가능한 암호. 복호화하지 않아도 통계적 처리가 가능하여 민감한 정보(ex. 생체정보) 처리에 유용하다. 동형 암호는 암호문간 연산이 반복되면 노이즈가 발생하여 횟수 제한이 있지만, Bootstrapping 과정을 통해 연산 횟수 제한을 없앨 수 있는 암호화 방식을 완전 동형 암호라고 부른다. 출처는 아래 LG CNS 공식 블로그.
https://blog.lgcns.com/2045
[10] 사용자의 개인키와 암호문이 속성(예를 들어, 살고 있는 국가)에 의존성을 가지며, 속성이 일치해야만 복호화 가능한 암호.. 라고 소개하는 위키는 아래 주소. 공부가 필요함.
https://en.wikipedia.org/wiki/Attribute-based_encryption#cite_note-1
[11] V. Dubois, P. Fouque, A. Shamir and J. Stern, Practical cryptanalysis of SFLASH, Advances in Cryptology — CRYPTO 2007, Lecture Notes in Comput. Sci. 4622, Springer-Verlag, 2007, pp. 1–12. http://dx.doi.org/10.1007/978-3-540-74143-5_1.
[13] 단수형은 isogeny 이며, 금융보안원의 "금융부문 암호기술 활용 가이드", 2019 1월, 에서 '등원사상' 이라는 용어를 사용한다. 역시 공부가 필요하다. http://www.fsec.or.kr/common/proc/fsec/bbs/147/fileDownLoad/1794.do
[14] 위상수학에서 주어진 개수의 실을 꼬은 모양으로 구성된 군이며, 대칭군의 일반화라고 한다. 공부가 필요하다.. https://ko.wikipedia.org/wiki/%EA%BC%AC%EC%9E%84%EA%B5%B0_(%EC%9C%84%EC%83%81%EC%88%98%ED%95%99)
[15] 켤레 탐색 문제. 그룹 G 에 속한 원소 g 에 대해 h=x^{-1}gx 를 만족하는 그룹 G 안에 있는 x 를 찾는 문제 ...공부하자... 다음 논문의 abstract 참고함. https://arxiv.org/abs/math/0411644
[16] J. Preskill, Reliable Quantum Computers, Proc. Roy. Soc. London A, 454, 1998, pp. 385–410. http://dx.doi.org/10.1098/rspa.1998.0167
[17] D. Lidar, T. Brun, eds., Quantum Error Correction, Cambridge University Press, 2013. http://dx.doi.org/10.1017/cbo9781139034807
[18] R. Barends, J. Kelly, A. Megrant, A. Veitia, D. Sank, E. Jeffrey, Y. Chen, B. Chiaro, J. Mutus, C. Neil, Superconducting quantum circuits at the surface
code threshold for fault tolerance, Nature 508 (7497), 2014, pp. 500–503. http://dx.doi.org/10.1038/nature13171
[19] T.P. Harty, D.T.C. Allcock, C.J. Balance, L. Guidoni, H.A. Janacek, N.M. Linke, D.N. Stacey, D.M. Lucas, High-Fidelity Preparation, Gates, Memory, and Readout of a Trapped-Ion Quantum Bit, Phys. Rev. Lett. 113 (22), 2014. http://dx.doi.org/10.1103/PhysRevLett.113.220501
[20] NIST Special Publication (SP) 800-131A Revision 1, Transitions: Recommendation for Transitioning the Use of Cryptographic Algorithms and Key Lengths, National Institute of Standards and Technology, Gaithersburg,
Maryland, November 2015, 23pp. http://dx.doi.org/10.6028/nist.sp.800-131ar1
[21] M. Mariantoni, Building a Superconducting Quantum Computer, Invited Talk PQCrypto 2014, October 2014 Waterloo, Canada. https://www.youtube.com/watch?v=wWHAs--HA1c
[22] NIST Special Publication (SP) 800-57 Part 1 Revision 4, Recommendation for Key Management – Part 1: General, National Institute of Standards and Technology, Gaithersburg, Maryland, January 2016, 160pp. http://dx.doi.org/10.6028/NIST.SP.800-57pt1r4
[23] P. Campbell, M. Groves, D. Shepherd, Soliloquy: A Cautionary Tale, ETSI Workshop on Quantum-Safe Cryptography, 2014. https://docbox.etsi.org/workshop/2014/201410_CRYPTO/S07_Systems_and_Attacks/S07_Groves_Annex.pdf
[24] M. Kaplan, G. Leurent, A. Leverrier, M. Naya-Plasencia, Quantum Differential and Linear Cryptanalysis, arXiv preprint ArXiv: 1510.05836, 2015. http://arxiv.org/abs/1510.05836
[25] H. Kuwakado, M. Morii, Quantum distinguisher between the 3-round Feistel cipher and the random permutation, In Proc. of 2010 IEEE International Symposium on Information Theory (ISIT), IEEE, 2010, pp. 2682-2685. http://dx.doi.org/10.1109/isit.2010.5513654
[26] National Security Agency, Cryptography Today, report, August 2015. https://www.nsa.gov/ia/programs/suiteb_cryptography/ [accessed 4/20/2016]. Also at: https://www.iad.gov/iad/programs/iad-initiatives/cnsasuite.cfm 둘 다 링크 깨진 것 같아요..
[27] NIST, AES Competition [Web page], http://csrc.nist.gov/archive/aes/
[28] NIST, SHA-3 Competition [Web page], http://csrc.nist.gov/groups/ST/hash/sha-3/

2020년 7월 23일 목요일

IBM, "양자 계산의 양자 우월성" 직역

이 글은 IBM 공식 블로그에서 2019년 10월에 발표한 "Quantum Computing on Quantum Supremacy", Edwin Pednault et al[1] 을 공부하는 글입니다. 번역기를 사용하지 않고, 현재 공부 중인 도메인이라 단어 선정이나 글의 흐름이 매끄럽지 않을 수 있습니다. 논문의 그림은 IBM 에서 공개한 링크로 대체합니다.

양자 컴퓨터는 고전 모의 실험의 한계에 접근하기 시작했고, 우리에게 성능 측정 과정과 그 모의 실험들이 얼마나 어려운 지를 묻는 것을 지속하는 일은 중요하다. 이는 흥미로운 과학적 질문이다.

양자 컴퓨팅의 최근의 진보는 두 53-큐비트 프로세스들이다. 하나는 IBM 의 우리 그룹에서 나왔고, 하나는 구글이 네이처 저널에서 출간된 논문으로 기술한 기기이다. 이 논문에서, 그들의 기기는 "양자 우월성"을 달성(reach)하였고, "최신 전통 슈퍼컴퓨터는 동등한 작업을 수행하는 데 대략 일만년이 필요할 것"이라고 한 것은 논쟁이 된다. 우리는 같은 작업의 이상적인 모의 실험이 훨신 큰 충실도로 전통적인 시스템에서 2.5일 안에 수행될 수 있음을 주장한다. 이는 사실 보수적이며, 최악의 경우의 추정이고, 우리는 추가 정제(refinement)를 통해 전통적인 모의 실험 비용이 상당히 줄어들 수 있다고 기대한다.

왜냐하면 2012년 존 프레스킬(John Preskill)[2]이 제안했던 "양자 우월성" 용어의 원래 의미가 기술하는 점은 양자 컴퓨터는 할 수 있는 일이나, 전통 컴퓨터는 할 수 없는 일이고, 이 기준(threshold)이 만족되지 않았다.

"양자 우월성"의 특별한 개념은 어떤 가용한 고전 컴퓨터로도 모의실험이 실현 불가능한 크기의 임의 양자 회로의 실행을 기반으로 한다. 특히, 논문은 53-큐비트 양자 프로세서의 계산 실험으로, 깊이 20의 두 큐비트 게이트 양자 회로, 430개의 두-큐비트와 1,113개의 단일-큐비트 게이트, 0.2%의 예상 총합 충실도(fidelity)를 인상적으로 구현한다. 그들의 전통 모의 실험 추정치인 만년은 불가능할(would be prohibitive) 슈뢰딩거 타입 모의 실험에서 전체 상태 벡터를 저장하는 작업에 필요한 RAM 메모리 관찰을 기반으로 하고, 시간과 공간의 상호관계(trade-off)인 슈뢰딩거-파인만 모의실험에 의존(resort)할 필요가 있다.

"양자 우월성"의 개념은 얽힘과 중첩에 대한 직접적인 접근과 같은 양자 컴퓨터의 고유 자원(resources)을 소개한다. 반면에, 전통적인 컴퓨터도 메모리 계층, 고정밀 계산 하드웨어, 다양한 소프트웨어 자산, 방대한 알고리즘 기반의 지식 등 그들 고유의 자원을 가지고 있으며, 이 능력들은 양자 컴퓨터와 전통 컴퓨터를 비교할 때 중요한 영향을 미친다.

그들이 전통적인 컴퓨터와의 비교를 생성할 때, 그들은 진보적인 모의실험의 평행성, 빠르고 오류가 없는 계산, 방대하게 통합된 RAM 에 의존하였으나, 많은(plentiful) 디스크 저장에 대한 충분한 설명은 실패하였다. 반면에, 우리의 슈뢰딩거 스타일 전통 모의실험 접근법은 상태 벡터를 저장하고 조작하기 위한 RAM 과 하드디스크 공간 양쪽을 사용한다. 우리의 모의 실험 기술(methodology)에 적용된 성능 강화 기법(techniques)은 회로 분할(circuit partitioning), 텐서 수축 지연(tensor contraction deferral), 게이트 병합과 일괄 처리(gate aggregation and batching), 집단적 통신의 섬세한 편성(careful orchestration of collective communication)과, 복합(hybrid) 노드의 CPU 및 GPU 구성요소 위에서 수행되는 계산과 발생하는 통신을 일치(overlap)시키기 위한 더블 버퍼링과 캐시 블로킹과 같은 잘 알려진 최적화 기법들이 포함되어 있다. 추가적은 세부사항은 "깊이 54큐비트 시카모어 회로의 모의 실험을 위한 2차 저장소 활용"[3]에서 볼 수 있다.


우리의 모의실험 접근은 전통 세계에서 양자 세계로 직접 전송하지 않는 다수의 멋진 속성들을 특징으로 한다. 예를 들어, 한번 전통적으로 계산되고 나면, 전체 상태 벡터는 자유롭게 여러 번 접근될 수 있다. 우리의 모의 실험 기법의 실행시간은 회로 깊이에 대해 대략 선형적으로 증가하며(scales), 제한된 얽힘 시간에 의한 것과 같은 제약(limits)을 부여하지 않는다. 새롭고 더 나은 전통 하드웨어, 전통 하드웨어를 더 효율적으로 활용하기 위한 코드 최적화, 흥미로운 우월성 모의 실험 류를 실행하기 위한 GPU 직접 통신 활용(leveraging)의 가능성은 말할 것도 없이(not to mention) 우리의 모의 실험을 상당히 가속시킬 것이다.

양자 시스템을 만드는 일은 과학과 공학의 공적(feat)이고 그들의 성능 측정은 엄청난(formidable) 도전이다. 구글의 실험은 53-큐비트 기기에서 최신 게이트 충실도를 보여주는 초전도체 기반 양자 컴퓨팅의 진보에 대한 훌륭한 재현이지만, 양자 컴퓨터가 전통 컴퓨터를 넘는 "우월성"의 증거로 보여서는 안된다.

IBM에 있는 우리가 "양자 우월성"이라는 용어가 어디로 가는 지에 관심을 가지는 것은 양자 공동체에 잘 알려져 있다. 일부 논란이 있는 분야에 대한 조리있는 반박과 자연스러운 반영 양쪽을 포함하여, 이 용어의 기원은 Quanta 매거진에서 John Preskill 의 사려깊은 기사[4]에서 최근에 논의되었다. Preskill 교수는 "이 용어가 이미 과장된 양자 기술의 상태에 대한 보고를 악화시키며", "백인 우월 주의(white supremacy)와 연관하여, 불쾌한(repugnant) 정치적 입장을 유발한다"고 설명하여 공동체에서 제기된 이 용어에 대한 두 주요한 반대를 요약하였다.

둘 다 민감한 반대이다. 그리고 우리는 "우월성" 용어가 (이를 적절한 문맥에 넣을 수 있는 드문(rarified) 양자 컴퓨팅 전문가들의 세계의 바깥에서) 거의 모두에게 오해되고 있다는 것을 추가할 것이다. "양자 우월성 달성"의 일부 변형을 포함하는 헤드라인을 인쇄하는 것은 거의 저항하기 어렵지만, 이는 필연적으로 일반 대중을 오해시킨다. 먼저, 위에서 언급하였듯이, 이 용어의 목적이 가지는 가장 엄격한 정의를 만족시키지 못한다. 하지만 더욱 근본적으로, 양자 컴퓨터는 절대로 전통 컴퓨터를 더 "우월"하게 지배할 수 없으며, 각각은 그들의 고유한 능력을 가지므로, 되려 이들과 협력(concert)하여 동작할 것이다.

위에서 언급한 이유들과, "양자 우월성" 용어가 널리 오해되고 있으며, 계속 증가되고 있는 혼선을 초래하고 있다는 풍부한 증거를 우리가 이미 가지고 있으므로, 우리는 공동체에게, 처음으로, 적절한 성능 측정 기준(metric)의 복잡한 환경 때문에 전통 컴퓨터가 할 수 없는 일을 수행했다는 양자 컴퓨터는 상당한 의구심(a large dose of skepticism)을 가지고 다뤄줄 것을 촉구한다.

사회에 긍정적인 영향을 주는 양자를 위해, 이 사전 작업(task ahead)은 재현 가능하고 믿을 수 있는 넓은 배열의 양자 시연, 알고리즘, 그리고 프로그램들을 구현할 수 있는 더 강력하고 프로그래밍 가능한 양자 컴퓨팅 시스템을 만들고 널리 접근 가능하도록 지속한다. 이는 양자 컴퓨터가 실현되는 현실적인 해결책으로 가는 유일한 길이다.

마지막 생각. 양자 컴퓨팅의 개념은 물리학자, 공학자와 컴퓨터과학자들을 포함하는 새로운 세대의 과학자들에게 근본적으로 정보 기술의 지형(landspace)을 바꾸도록 고무하고(inspiring) 있다. 만약 당신이 이미 양자 컴퓨팅의 변경(frontier)을 앞으로 밀고 있다면, 그 추진력을 계속하자. 그리고 만약 당신이 이 분야가 새롭다면, 와서 공동체에 합류하라. 앞으로 나아가 진짜 양자 컴퓨터에서 당신의 첫번째 프로그램을 오늘 실행[5]하라.

최고는 아직 오직 않았다.

[2] https://en.wikipedia.org/wiki/John_Preskill 파인만씨와 어떤 관계신지..
[3] "Leveraging Secondary Storage to Simulate Deep 54-qubit Sycamore Circuits", Edwin Pednault et al, https://arxiv.org/abs/1910.09534

2020년 4월 8일 수요일

구글, "프로그래밍 가능한 초전도체 프로세서를 이용하는 양자 우월성" 직역


이 글은 Nature 학술지에서 2019년 10월에 발표한 Google 의 'Quantum supremacy using a programmable superconducting processor, Frank Arute et al'[1] 논문을 공부하는 글입니다. 번역기를 사용하지 않고, 현재 공부중인 도메인이라, 단어 선정이나 글의 흐름이 매끄럽지 않을 수 있습니다. 논문의 그림 등은 Nature 에서 인터넷에 공개한 링크로 대체합니다.

요약

양자 컴퓨터의 전망(promise)은 특정 계산 작업들이 양자 프로세서 위에서 전통적인 프로세서보다 기하급수적으로 빠르게 수행될 수 있다는 것이다. 근본적인 어려움은 기하급수적으로 넓은 계산 범위(space)에서 양자 알고리즘들을 실행할 수 있는 높은 충실도(fidelity)[2]의 프로세서를 만드는 일이다. 여기에서 우리는 53 큐비트의 양자 상태를 생성하므로 253 (약 1016) 차원의 계산 상태 공간을 생성하며, 프로그래밍이 가능한 초전도체 큐비트를 가진 프로세서의 사용을 알린다. 반복된 실험을 통한 측정치들을 우리는 전통적인 시뮬레이션을 사용하여 검증한 확률 분산 결과로 시험했다. 우리의 시카모어(Sycamore) 프로세서는 하나의 양자 회로 연산을 백만번 수행하는 데 약 200초가 소요되었으며, 이는 우리의 성능 측정 결과가 현재 최신의 전통 슈퍼컴퓨터로 만년 정도 걸리는 작업과 동등함을 의미한다. 모든 알려진 고전 알고리즘들과 비교하여 이러한 극적인 성능 증가는 특정 계산 작업에 대한 양자 우월성의 실험적인 실현이며, 상당히 기대되는 계산 패러다임을 예고한다.

본문

1980년대 초반 리처드 파인만은 전통 컴퓨터에서 커다란 양자 계를 흉내내는 일은 기하급수적으로 비용이 크며, 양자컴퓨터가 물리학과 화학의 문제들을 해결할 수 있는 효과적인 도구가 될 것이라고 제안하였다. 파인만의 비전을 실현하는 것은 상당히 실험적이고 이론적인 도전을 요구한다. 첫 번째, 양자 가속(quantum speedup)을 제공하는 충분히 낮은 에러 비율로 양자 시스템이 충분히 거대한 (힐베르트) 계산 공간에서 계산을 수행할 수 있는가? 두 번째, 우리가 전통 컴퓨터로는 어려우나, 양자 컴퓨터로는 쉬운 문제를 정할 수 있는가? 우리는 두 문제를 초전도체 큐비트 프로세서의 성능 지표 작업(benchmark task)를 계산하여 대처한다. 우리의 실험은 양자 우월성과 전면적인(full-scale) 양자 계산의 이정표를 달성한다.

이 이정표에 도달하기 위해, 우리는 양자 가속이 현실 세계에서 달성 가능하고, 어떤 숨겨진 물리학 법칙에 의해서도 방해받지 않음을 보인다. 또한 양자 우월성은 중급 잡음 양자(NISQ, noisy intermediate-scale quantum) 기술의 시대를 알린다. 우리가 시현한 벤치마크 작업은 증명 가능한 임의의 숫자를 생성하는 즉각적인 어플리케이션을 가지고 있다. 이 새로운 계산 능력을 위한 다른 초기 사용은 최적화, 기계 학습, 재료 과학과 화학을 포함할 것이다. 그러나, 양자 컴퓨팅의 전체적인 전망(예를 들어, 인수 분해를 위한 쇼어의 알고리즘 사용)을 실현하는 것은 여전히 공학적인 오류 내성 큐비트를 위한 기술적 도약을 요구한다.

양자 우월성을 달성하기 위해, 우리는 오류 정정을 위한 길을 여는 다수의 기술적 진보를 만들었다. 우리는 2차원 큐비트 배열에 걸쳐 동시에 실행될 수 있는 빠르고, 높은 충실도의 게이트를 개발했다. 우리는 부품과 시스템 레벨에서 교차 불확실성 지수(cross entropy benchmarking)라는 강력하고 새로운 도구를 이용하여 프로세서의 성능을 측정하고 기록하였다. 마지막으로, 우리는 부품 단위 충실도들을 사용하여 전체 시스템의 성능을 정확히 예측하였으며, 나아가 시스템이 큰 규모로 커질 때에 양자 정보가 예상한대로 행동하는 것을 보인다.

적절한 계산 작업

양자 우월성을 증명하기 위해, 우리는 우리의 양자 프로세서와 최신식 전통 컴퓨터가 의사 난수 양자 회로의 결과를 표본화(sampling)하는 작업을 비교한다. 난수 회로들은 구조를 가지지 않으므로 제한된 계산의 어려움을 허용하여 성능 측정을 위한 적절한 선택이다. 우리는 단일 큐비트와 두 큐비트의 논리적 연산들의 반복 적용을 통해 하나의 큐비트 집합이 얽히도록 회로를 설계한다. 양자 회로 결과물의 표본은 {0000101, 1011100, ...} 과 같은 비트 문자열의 집합을 생성한다. 양자 간섭에 의해, 비트 문자열의 분산 확률은 레이저 분산에서 빛의 간섭에 의해 생성되는 반점 강도 패턴(speckled intensity pattern)[3]과 유사하므로, 일부 비트 문자열은 다른 문자열들보다 발생할 확률이 높다. 전통적으로 이러한 확률 분포의 계산은 큐비트의 수(넓이)와 게이트의 주기(깊이)가 증가할수록 기하급수적으로 어려워진다.

우리는 양자 프로세서를 소위 교차 불확실성 지수로 불리는 방법을 사용하여 적절하게 동작중인지를 검증하며, 이는 각 비트 문자열이 얼마나 자주 실험적으로 관측되는 지를 전통 컴퓨터에서 모의 실험하여 계산된 이상적인 대응 확률과 비교한다. 주어진 회로에서, 우리는 측정된 비트 문자열 {xi} 를 수집하고 선형 교차 불확실성 지수 충실도(보충 정보 단원을 보라)를 계산하며, 이는 우리가 측정한 비트 문자열의 모의 실험된 확률의 평균이다.

FXEB = 2n<P(xi)>i  - 1 (1)

위 식에서 n 은 큐비트들의 수이며, P(xi) 는 이상적인 양자 회로에서 계산된 비트 문자열 xi 의 확률이고, 평균은 관측된 비트 문자열보다 높다. 직관적으로, FXEB 는 우리가 얼마나 자주 높은 확률의 비트 문자열을 추출(sample)했는 지와 연관된다. 양자 회로에 오류가 없을 때, 확률들의 분산은 기하급수적(보충 정보 단원를 보라)이고, 이 분산의 표본화(sampling)는 FXEB = 1 을 만들 것이다. 반면에, 균등 분포에서의 표본화는 <P(xii = 1 / 2ⁿ 을 줄 것이고, FXEB = 0 을 만들 것이다. 0과 1 사이의 FXEB 값은 회로가 동작하는 동안 오류가 없는 확률에 일치하였다. 확률들 P(xi)는 반드시 전통적으로 모의 실험된 양자 회로에서 얻어야 하며, FXEB 의 계산은 양자 우월성의 체제에서 다루기 어렵다. 그러나 특정 회로 간소화로 우리는 깊고 넓은 양자 회로들로 동작하는 전체적인 운영 프로세서의 양적 충실도 측정 추정치들(quantitative fidelity estimates)을 얻을 수 있다.

우리의 목표는 전통적인 비용 계산으로 엄두가 나지 않을 정도로 큰 문제를 위한 만족스러운 넓이와 깊이를 가진 회로에서 충분히 높은 FXEB 를 얻는 것이다. 우리의 논리 게이트들은 불완전하고 우리가 만들고자 하는 양자 상태들은 오류에 민감하여 어려운 작업이다. 알고리즘의 과정에서 하나의 비트 또는 위상 플립은 반점 패턴을 전체적으로 뒤섞으며, 무효 충실도(zero fidelity)에 가까운 결과를 초래한다.(보충 정보 단원을 보라). 그러므로, 양자 우월성을 주장하기 위해 우리는 충분히 낮은 오류율로 프로그램을 실행하는 양자 프로세서가 필요하다.

높은 충실도의 프로세서 만들기

우리는 54개 초전도체 전하 큐비트(transmon[4])를 2차원으로 배열하여 구성된 '시카모어'로 불리는 양자 프로세서를 설계하였으며, 각 큐비트는 사각 격자에서 가장 가까운 네 이웃과 가변적으로 결합된다. 이 연결성은 표면 코드를 사용한 오류 수정의 상위 호환(forward-compatible)을 위해 선택되었다. 이 기기의 진보를 처리하는 핵심 시스템은 단순 격리 상태 뿐만 아니라 많은 큐비트들이 동시 게이트 연산을 수행하는 현실적인 계산을 수행하는 동안에도 단일 그리고 두 큐비트 연산들의 높은 충실도를 달성한다. 우리는 아래에서 가장 중요한 것들을 논한다. 보충 정보 단원도 보라.

초전도체 회로에서, 전도 전자들은 전류와 전압이 양자 기계적으로 작용하여 거시적인(macroscopic) 양자 상태로 단순화된다. 우리의 프로세서는 5-7 GHz 에서 공명하는 비선형 초전도체 공명체로 생각될 수 있는 전하 큐비트들을 이용한다. 큐비트는 공명하는 회로의 가장 낮은 2개의 양자 고유 상태로 인코딩된다. 각 전하 큐비트(transmon)는 두 개의 제어를 갖는다. 하나는 큐비트를 흥분시키는 마이크로파, 하나는 주파수를 맞추는 자기 흐름 제어이다. 각 큐비트는 큐비트의 상태를 읽는 데 사용하는 선형 공명체에 연결된다. 그림1과 같이, 각 큐비트는 새로운 조절 가능한 커플러(coupler)를 사용하여 이웃하는 큐비트들과 연결된다. 우리의 커플러 설계는 완전히 분리된 상태에서 40MHz 까지 빠르게 큐비트와 큐비트가 연결되도록 조절(tune)할 수 있게 한다. 하나의 큐비트는 제대로 동작하지 않았으므로, 기기는 53개의 큐비트와 86개의 커플러를 사용한다.

그림1. 시카모어 프로세서. a, 54 큐비트의 사각 배열(회색)을 보여주며, 각각은 이웃하는 4개의 커플러(파랑색)에 연결되어 있다. 동작할 수 없는 큐비트는 윤곽선만 있다. b, 시카모어 칩의 사진

프로세서는 금속화와 조셉슨 접합[5]을 위해 알루미늄을 사용하며, 두 개의 실리콘 웨이퍼 사이의 충돌 방지(bump-bond)를 위해 인듐을 사용하여 조립되었다. 칩은 초전도체 회로 보드에 와이어본딩[6] 되었으며, 모호한 열 에너지를 큐비트 에너지 이하로 줄이기 위해 희석(dilution) 냉장고 안에서 20 mK 이하로 냉각되었다. 프로세서는 필터와 감쇄기(attenuator)를 통해 제어 신호를 종합하는 실온(room-temperature) 전자기기에 연결되었다. 모든 큐비트들의 상태는 주파수 다중화 기법(frequency-multiplexing technique) 을 사용하여 동시에 읽을 수 있다. 우리는 극저온 증폭기(cryogenic amplifier)의 두 단계를 사용하여, 1GHz 의 8비트 신호로 증폭(boost)하고, 실온에서 디지털 방식으로 역다중화하였다. 종합하면, 우리는 양자 프로세서의 완전한 제어를 위해 277개의 디지털-아날로그 변환기(1GHz 에서 14비트)를 편성한다.

우리는 큐비트-큐비트 커플링이 켜지지 않았을 때의 큐비트 주파수와 공명하는 25-ns 의 마이크로파 파동을 운용(driving)하여 단일 큐비트 게이트들을 실행시킨다. 파동은 더 높은 전하 큐비트 상태들로의 전이를 최소화하도록 조형되었다. 게이트의 성능은 2레벨 시스템 결함, 떠도는(stray) 마이크로파 모드, 배선(lines)과 읽기(readout) 공명기를 제어하는 커플링, 떠도는 큐비트간 여분의 커플링, 유동 잡음(flux noise), 그리고 파동 왜곡(pulse distortions)에 의해 주파수마다 상당히 가변적이다. 그러므로 우리는 오류 메커니즘을 완화하기 위해 단일 큐비트 연산 주파수를 최적화한다.

우리는 단일 큐비트 게이트 성능을 상기 기술한 교차 불확실성 지수 기법을 사용하여 측정하여, 단일 큐비트 레벨(n=1)로 줄이고, 단일 큐비트 게이트 동안 발생하는 오류의 확률을 측정한다. 각 큐비트 위에 우리는 임의로 선택된 게이트에 변수 m을 적용하고, 많은 횟수의 평균적인 FXEB 를 측정한다. m 이 커질수록 오류값이 쌓이고 평균 FXEB가 감쇠(decay)한다. 우리는 이 감쇠를 [1-e₁ / (1 - 1/D²)]으로 모델링하고, 여기에서 e₁ 은 파울리 오류 확률(Pauli error probability)[7]이다. 상태(힐베르트) 공간 차원 조건인 D=2ⁿ은 이 경우에는 2와 같으며, 오류를 가진 상태들을 이상적인 상태로 덮어쓰는 감극 모델(depolarizing model)을 교정한다. 이 절차는 임의 성능 측정(randomized benchmarking)의 전형적인 기법과 더 유사하지만, 클리포드 게이트 방지 집합(non-Cliffored-gate[8] sets)을 지원하고, 결맞음 제어 오류로부터 결맞지 않은 오류를 분리할 수 있다. 우리는 모든 큐비트에 단일 큐비트 게이트를 동시에 실행하는 실험을 반복하였으며, 그림2와 같이 오류 확률이 아주 조금 상승하는 것을 보임으로써 우리의 기기가 낮은 마이크로파 잡음을 가짐을 입증한다.

그림2. 시스템 전체의 파울리 및 측정 오류 a, 파울리 오류들(검정, 초록, 파랑)의 통합 분포도(실증적 누적 분산 함수, ECDF), 격리된 큐비트들로 측정(점선)과 모든 큐비트들이 동시에 동작한 경우(진한선). 각 분포의 중앙 값은 세로축의 0.50에서 발생. 평균 값은 아래에 나타냄. b, 프로세서 설계에 위치한 단일과 두 큐비트의 파울리 오류들 e₁(격자들) 과 e₂(막대들)을 보여주는 히트맵. 보여지는 값은 모든 큐비트가 동시에 동작할 때이다.

우리는 큐비트들의 교환(swap) 여기 상태를 허용하는 20MHz 의 공명 및 전환과 12ns 의 커플링 전환(turning on)을 이웃하는 큐비트들에 일으켜서 두 큐비트의 iSWAP 류[9]의 얽힘을 수행한다. 그 동안, 큐비트들은 더 높은 레벨의 전하 큐비트(transmon)에서 발생한 제어된 위상(controlled-phase, CZ) 상호작용 단계를 거친다. 각 큐비트 쌍의 두 큐비트 게이트 주기 궤적(frequency trajectories)은 단일 큐비트 연산 주기의 최적화에서 고려된 같은 오류 메커니즘을 완화하도록 최적화되었다.

두 큐비트 게이트를 규정하고 성능을 측정하기 위해, 우리는 두 큐비트 회로를 m 번 순환 (cycles) 실행하였으며, 각 순환은 고정된 두 큐비트 게이트가 뒤따르는 각 두 큐비트에서 임의로 선택한 단일 큐비트 게이트를 포함한다. FXEB 를 비용 함수로 사용하면 두 큐비트  단위(unitary)의 매개변수(parameter)들(예를 들어, iSWAP 와 CZ 상호작용의 양)은 같음을 알 수 있다. 이 최적화 이후에, 우리는 m 의 FXEB 감쇠에서 순환별 오류 e2c를 추출하고 두 단일 게이트 오류 e1를 차감하여 두 큐비트 오류 e2를 격리한다. 우리는 0.36% 의 e2 평균을 식별한다. 또한, 같은 절차를 동시에 동작하는 전체 배열의 두 큐비트 회로에 반복한다. 분산 이동(dispersive shift)과 혼선(crosstalk)과 같은 효과를 단위 매개변수에 최신화한 후, 우리는 e2의 평균값 0.62% 를 식별한다.

전체 실험에서, 우리는 모든 쌍들의 표준적인 게이트보다는, 동시 동작 중 각 쌍의 두 큐비트 단위를 측정하는 방법으로 양자 회로를 생성하였다. 전형적인 두 큐비트 게이트는 전체 CZ 의 1/6 로 전체 iSWAP 을 수행한다. 전혀 개별적으로 조정되지 않은 게이트들은 증명의 보편성을 제한한다. 한 가지는 구성 가능한데, 예를 들어, 1 큐비트 게이트들에서 제어된 NOT (controlled-NOT, CNOT) 게이트들과 모든 주어진 쌍의 고유한 2큐비트 게이트들의 둘이다. CZ 또는 √iSWAP 과 같은 높은 충실도의 '교과서 게이트'들의 구현은 작업이 진행중이다.

마지막으로, 표준 분산 측정(standard dispersive measurement)를 사용하는 큐비트 읽기(readout) 성능을 측정하였다. 0과 1 상태들의 평균을 초과하는 측정 오류는 그림 2a 에서 보인다. 또한 우리는 각 큐비트의 상태를 0 또는 1로 임의로 준비하고 올바른 결과의 확률을 모든 큐비트에서 측정하여, 모든 큐비트가 동시에 동작할 때의 오류도 측정하였다. 우리는 동시 읽기가 단지 각 큐비트 측정의 오류들을 적당히 증가시킨다는 것을 알아내었다.

개별 게이트들과 읽기의 오류율을 찾은 후에, 우리는 모든 게이트의 오류 없는 연산의 확률과 측정의 산출물(product)로 양자 회로의 충실도를 모델링할 수 있다. 우리의 가장 큰 임의 양자 회로는 53개의 큐비트와 1,113개의 단일 큐비트 게이트와 430개의 두 큐비트 게이트를 가지고, 각 큐비트의 측정 기능을 가지며, 우리가 예측하는 전체 충실도는 0.2% 이다. 이 충실도는 반드시 수백만번의 측정으로 해결될 수 있어야 하는 데, 왜냐하면 FXEB 의 불확실성은 1 / √Ns이고, 여기에서 Ns는 표본들의 수이기 때문이다. 우리 모델은 얽힘이 커질수록 시스템이 단일 또는 두 큐비트 레벨에서 우리가 측정한 오류 위에 추가 오류 원인을 더하지 않는 것을 가정한다. 다음 단원에서 우리는 이 가설이 얼마나 잘 유지(holds up)되는 지를 볼 것이다.

우월 체제에서의 충실도 추정

우리의 의사 난수 양자 회로 생성을 위한 게이트 서열(sequence)은 그림3에서 보인다. 알고리즘의 한 순환은 모든 큐비트에서 {√X, √Y, √Z} 중 임의로 선택된 단일 큐비트 게이트와 이어서 큐비트 쌍에서의 두 큐비트 게이트의 적용으로 구성된다. '우월성 회로'를 구성하는 게이트 서열은 계산 복잡도와 전통적인 어려움을 위해 필요한 고도의 얽힘 상태를 생성하기 위해 요구되는 회로 깊이를 최소화하도록 설계되었다.

그림3. 양자 우월성 회로의 제어 연산들. a, 우리의 실험에서 사용된 양자 회로 예시의 표본. 모든 순환은 각각의 단일 및 두 큐비트 게이트들의 계층(layer)을 포함한다. 단일 큐비트들은 W = (X + Y) / √2 일 때 {√X, √Y, √W} 에서 임의로 선택되며, 게이트들은 순차적으로 반복하지 않는다. 두 큐비트 게이트의 서열은 타일 무늬에 따라 선택되며, 각 큐비트들은 가장 가깝게 이웃한 네 큐비트들과 순차적으로 커플링한다. 커플러는 네개의 부분 집합(ABCD)로 나뉘고, 각각은 음영색과 대응하는 전체 배열(array)에 걸쳐 동시에 실행된다. 여기에 우리는 처리하기 어려운 서열(반복되는 ABCDCDAB)을 보인다. 또한 우리는 다른 커플러 부분 집합들을 단순화할 수 있는 서열(반복되는 EFGHEFGH, 보이지 않음)과 함께 사용하여 전통적인 컴퓨터에서 모의할 수 있도록 한다. b, 단일 그리고 두 큐비트 게이트들을 위한 제어 신호의 파형

비록 우리는 우월 체제에서 FXEB 를 계산할 수 없지만, 회로의 복잡도를 줄이기 위해 세 변수를 사용하여 이를 추정할 수 있다. '부분(patch) 회로' 에서, 우리는 두 큐비트게이트의 한 조각(slice, 두 큐비트 게이트 전체의 수에서 작은 파편(fraction))을 제거하고, 회로를 공간적으로 격리된, 큐비트의 서로 통신할 수 없는 부분 둘로 나눈다. 이후 우리는 부분의 충실도들의 곱으로 전체 충실도를 계산하며, 각각은 쉽게 계산될 수 있다. '생략된(elided) 회로'에서, 우리는 조각을 따라 첫 두 큐비트의 파편만을 제거하여 부분들의 얽힘을 허용하고, 모의 실험 가능성을 유지하면서 전체 실험을 더 가깝게 흉내낸다. 마지막으로, 우리는 우리의 우월 회로와 같은 게이트의 수를 가진 전체 '검증(verification) 회로'를 실행할 수 있지만, 전통적으로 더 쉽게 모의하도록 다른 두 큐비트 게이트 서열의 패턴을 갖는다. (보충 정보 단원을 보라). 세 변수들 사이의 비교는 우리의 시스템 충실도 추적을 허용하여, 우리는 우월 체제에 접근한다.

그림 4a에서 보는 것과 같이, 우리는 먼저 검증회로의 부분과 생략된 버전이 53개의 큐비트까지의 전체 검증 회로와 같은 충실도를 생성하는지 확인한다. 각 데이터 지점에서, 우리는 전형적으로 10개의 예제(instance) 회로에서 Ns = 5 x 106 개의 샘플을 수집하며, 여기에서 예제들은 각 순환에서 단일 큐비트 게이트들의 선택만 다를 뿐이다. 또한 우리는 단일 그리고 두 큐비트 게이트들의 측정(보충 정보 단원을 보라)과 오류가 없는 확률을 곱해서 계산된, 예측한 FXEB 를 보인다. 계산 복잡도와 얽힘에서 거대한 차이에도 불구하고, 예측된, 부분과 생략된 충실도 모두는 전체회로에 대응하는 충실도와 좋은 일치(agreement)를 보인다. 생략된 회로들이 더 복잡한 회로의 충실도를 정확하게 추정하는 데 사용될 수 있다는 점은 우리에게 확신을 준다.

그림4. 양자 우월성 입증. a, 성능 측정 방법의 검증. 부분과 생략 그리고 전체 검증회로의 FXEB 는 측정된 비트 문자열과 전통적인 모의 실험에서 측정된 대응 확률에서 계산된다. 여기에, 두 큐비트 게이트는 합리적인 시간 안에 n = 53, m = 14 를 도출하도록 모의될 수 있는 전체 회로의 서열과 단순화할 수 있는 타일링으로 적용된다. 각 데이터 지점은 10개의 구분된 양자 회로 예시들의 평균이며, 각 회로는 그들의 단일 큐비트 게이트가 다르다.(n = 39, 42, 32 은 두 예시들만 모의되었다). 각 n 에서, 각 예시들은 0.5 - 2.5 백만회 실험에서 샘플을 추출하였다. 검정선은 단일 그리고 두 큐비트 게이트와 측정 오류를 기반으로 예상된 FXEB를 보인다. 모든 4개 곡선의 가까운 일치는, 그들의 거대한 복잡성 차이에도 불구하고, 우월 체제예서 충실도를 추정하기 위해 삭제된 회로의 사용을 정당화한다. b, 우월 체제에서 추정하는 FXEB. 여기에 두 큐비트 게이트는 모의 실험을 어렵게 하기 위해서 간소화되지 않은 타일링과 서열이 적용되었다. 가장 크게 생략된 데이터(n = 53, m = 20, 전체 Ns = 3천만)에서, 우리는 평균 FXEB > 0.1% 와 5∂ 신뢰도(confidence) 를 발견하였으며, 여기에서 ∂ 는 체계적(systematic)이고 통계적인 불확실성(uncertainties) 모두를 포함한다. 모의되지 않고 획득한 전체 회로에 대응하는 데이터는 통계적으로 유사하게 상당한 충실도를 보여줄 것으로 예상된다. m = 20 에서, 양자 프로세서로 백만개의 표본을 얻는 데 200초가 걸렸으며, 반면에 백만개의 코어로 전통적인 표본 추출에서 동일한 충실도는 만년이 걸릴 것이고, 충실도를 측정은 수백만년이 걸릴 것이다.

충실도가 직접적으로 검증될 수 있는 가장 큰 회로는 53개 큐비트와 단순화된 게이트 배치를 가진다. 임의 회로 샘플 추출을 0.8% 의 충실도로 수행하면 백만개 코어로 130초가 걸리며, 단일 코어인 양자 프로세서가 백만배 빠르다는 것에 대응한다.

우리는 이제 단순히 두 큐비트 게이트들을 재배치한, 계산적으로 가장 어려운 회로의 성능 측정을 진행한다. 그림4b 에서, 우리는 증가된 깊이를 갖는 전체 우월성 회로의 생략된 버전과 53 큐비트 부분(patch) 에서 측정된 FXEB 를 보인다. 53개의 큐비트를 가진 가장 큰 회로와 20번 순환으로, 우리는 10개 예제 회로에서 Ns = 30 x 106 표본을 수집하였으며, 생략된 회로들에서 FXEB = (2.24 ± 0.21) x 10-3 를 얻었다. 5∂ 신뢰도로, 우리는 양자 프로세서에서 실행중인 이 회로의 평균 충실도는 최소 0.1%보다 크다고 단언한다. 우리는 그림4b의 전체 데이터는 반드시 유사한 충실도를 가져야 한다고 예상하지만, 확인을 위한 모의 실험 시간(빨간 선)이 너무 오래 걸려서, 우리는 데이터를 보관했다(데이터 사용 가능 단원을 보라). 데이터는 현재까지 양자 우월 체제에 있다.

전통적인 계산 비용

우리는 두 가지 목적으로 전통 컴퓨터에서 시험한 양자 회로를 모의실험한다. (1) 간소화 가능한 회로(그림 4a)를 사용할 수 있는 FXEB 를 계산하여 우리의 양자 프로세서와 성능 측정 방법을 검증하고, (2) 우리의 가장 어려운 회로(그림 4b)에서 추출한 표본의 전통적인 계산과 FXEB를 추정한다. 43개 큐비트까지, 우리는 전체 양자 상태의 변화를 모의하는 슈뢰딩거 알고리즘[10]을 사용한다. 율리히 슈퍼컴퓨터[11](십만개 코어와 250 테라바이트로)가 가장 큰 경우를 실행한다. 상기 크기에서, 양자 상태를 저장하는 RAM 이 부족하다. 더 큰 양자 숫자들을 위해서, 우리는 개별 비트 문자열의 진폭을 계산하기 위해 구글 데이터 센터에서 실행하는 하이브리드 슈뢰딩거-파인만 알고리즘을 사용한다. 이 알고리즘은 회로를 큐비트의 두 부분으로 나누고 슈뢰딩거 방법을 이용하여 각 부분을 효율적으로 모의하며, 그들을 연결하기 전에 파인만 전체 경로(Feynman path-integral)과 유사(reminiscent)한 접근방법을 사용한다. 이 것이 더 메모리 효율적임에도, 회로가 커지면 부분들을 연결하는 게이트들의 수와 경로가 급수적으로 많아지기 때문에, 회로의 깊이가 늘어날수록 슈뢰딩거-파인만 알고리즘은 지수적으로 더 계산적 비용이 비싸진다.

우월성 회로의 전통적인 계산 비용(그림 4b에서 회색 숫자들)을 추정하기 위해, 우리는 Summit 의 슈퍼 컴퓨터와 구글 클러스터 양쪽 위에서 양자 회로 모의실험의 부분을 실행하였고, 전체 비용을 추론하였다. 이 추론에서, 우리는 FXEB로 검증 비용을 계량(scaling)하여 표본의 계산 비용을 설명한다. 예를 들어, 0.1% 충실도는 약 1,000의 비용을 감소시킨다. 세계에서 가장 강력한 Summit 의 슈퍼 컴퓨터에서, 우리는 파인만 전체 경로에서 영감을 받은 방법을 사용하며, 이는 낮은 깊이에서 가장 효율적이다. m = 20 에서, 텐서(tensor)[12]는 노드 메모리에 합리적으로 적합하지 않으므로, 우리는 실행시간을 m = 14까지만 측정할 수 있으며,  우리는 삼백만 비트 문자열과 1%의 충실도의 표본은 1년이 걸릴 것이라고 추정한다.

구글 클라우드 서버에서, 우리는 슈뢰딩거-파인만 알고리즘을 사용하여 m = 20 과 0.1%의 충실도로 같은 작업을 수행하는 것은 50 조(trillion) 개의 코어-시간과 1 페타와트(petawatt) 시의 에너지가 소요될 것으로 추정한다. 이 관점에서, 양자 프로세서 상의 회로를 300백만번 표본 실험하는 데는 600초가 소요되며, 표본 실험 시간은 하드웨어 통신 제어에 의해 제한된다. 사실, 순수한 양자 프로세서 시간은 오직 약 30초이다. 모든 회로에서 추출한 비트 문자열 표본은들은 더 진보한 검증 알고리즘을 테스트하고, 개발을 장려하기 위해 온라인에 저장되어 있다.("데이터 사용 가능" 항목을 보라)

한 가지 놀라울만한 알고리즘적 혁신의 연장은 전통 모의 실험들을 향상시킬 수 있다. 복잡성 이론에서 온 통찰력을 기반으로 하는 우리 가정은, 이 알고리즘적 작업의 비용이 회로 크기에 따라 지수적으로 증가한다는 것이다. 사실, 모의실험 방법들은 수년간 서서히 발전하였다. 우리는 여기에서 알려진 것보다 낮은 모의 실험 비용이 결국 밝혀질 것으로 기대하며, 또한 더 큰 양자 프로세서의 하드웨어적 발전에 의해 지속적으로 따라 잡힐 것을 기대한다.

디지털 오류 모델 검증하기

양자 오류 보정의 논리의 기초를 이루는 핵심 가정은 양자 상태 오류가 계수화(digitized)되고 국지적(localized)으로 고려될 수 있다는 것이다. 이런 디지털 모델 아래에서, 양자 상태와 관련된 모든 오류들은 회로에 흩뿌려진(interspersed) 국지적인 파울리 오류(비트 플립 또는 페이즈 플립)으로 특징될 수 있다. 연속적인 진폭은 양자 역학의 근본이기 때문에, 양자 시스템의 오류가 분리되거나 확률적으로 다뤄질 수 있는지에 대한 테스트가 필요하다. 사실, 우리의 실험적 관찰은 우리의 프로세서에 대한 이 모델의 타당성을 뒷받침한다. 우리의 시스템 충실도는 각 게이트가 개별적으로 특성화된 충실도가 함께 곱해지는 단순한 모델로 잘 예측되었다.

계수화된 오류 모델에 의해 성공적으로 설명되기 위해, 하나의 시스템은 연관된 오류가 낮아야 한다. 우리는 이를 우리의 실험에서 회로를 임의로 선택하여 오류를 연관시키지 않고, 제어를 최적화하여 시스템적 오류와 유출을 최소화하며, 게이트가 1/f flux 소음 같은 관련된 소음들보다 훨씬 빠르게 동작하도록 설계하여 이를 달성한다. 253 크기의 힐베르트 공간까지 예측한 상호 관계 없는 오류 모델을 입증하는 것은 우리가 얽힘과 같은 양자 자원이 전혀 취약하지 않게(not prohibitively fragile) 존재하는 시스템을 만들 수 있음을 보인다.

미래

이제 초전도체 큐비트들을 기반하는 양자 프로세서는 오늘날 가장 빠른 전통적인 슈퍼컴퓨터가 도달하는 것을 넘어서는, 253 ≈ 9 × 1015차원의 힐베르트 공간안에서의 계산을 수행할 수 있다. 우리가 알기로는, 이 실험은 단일 양자 프로세서에서 수행될 수 있는 계산의 첫 기록(mark)이다. 그러므로 양자 프로세서는 양자 유월성 체제에 도달하였다. 우리는 그들의 계산 능력이 2의 지수승의 비율로 계속 증가할 것을 기대한다 : 양자 회로를 모의실험하는 전통적인 비용은 계산량에 따라 지수적으로 증가하고, 하드웨어의 개선으로 계산량은 수년마다 두 배가 된다는 무어의 법칙을 양자 프로세서도 동등하게 따를 것이다. 두 제곱의 성장 속도를 지속하고, 최종적으로 쇼어 또는 그로버 같은 잘 알려진 양자 알고리즘을 수행하는 데 필요한 계산량을 제공하기 위해서는 오류 보정 공학이 관심의 집중이 될 필요가 있을 것이다.

번스타인과 바지라니[13]에 의해 공식화된 확장된 처치-튜링 명제는 모든 '합리적인' 계산 모델은 튜링 머신에 의해 모의될 수 있다고 단언한다. 우리의 실험은 하나의 계산 모델이 이 단언을 위반할 수 있음을 시사한다(suggest). 우리는 물리적으로 실현가능한 (충분히 낮은 오류율을 갖는)양자 프로세서를 사용하여 다항시간에 난수 양자 회로 표본화(sampling)를 수행하였지만, 전통적인 계산 기계에서 효과적인 방법이 존재할 것이라고는 아직 알려지지 않았다. 이러한 발전들의 결과로, 양자 컴퓨팅은 하나의 연구 주제에서 새로운 계산 능력을 여는(unlocks) 하나의 기술로 전이(transition)하고 있다. 우리는 단지 하나의 창의적인 알고리즘을 가치있는 가까운 기일 내의 응용들에서 떨어뜨린다(away).

데이터 사용 가능

이 연구에서 생성되고 분석된 데이터 집합들은 우리의 공개된 Dryad 저장소[14]에서 사용 가능하다.

(참고문헌, 사사, 저자 정보,  윤리선언, 추가 정보 생략)


보충 정보

이 보충 정보[15] 파일은 보충 그림 S1 ~ S44 와 보충 표1~10 을 포함하는 보충 정보1~11을 가지고 있다.

(저작권 등 이하 단원 생략)




[2] '충실도'라고 번역한 기고문 : "이온 포획장치를 이용한 양자컴퓨터", 김기환 등, 2019
http://webzine.kps.or.kr/contents/data/webzine/webzine/15574590701.pdf
[3] 영의 이중슬릿 실험을 생각해보면 보강과 간섭을 통해 빛의 세기가 중가하거나 감소하는 부분이 생성되므로, 레이저 빛은 흩뿌렸을 때도 레이저 빛들의 보강과 간섭을 통해 반점 무늬들의 세기는 다를 것이다.
[4] 초전도체 전하 큐비트의 한 종류라고 한다. https://en.wikipedia.org/wiki/Transmon
그림1. https://www.nature.com/articles/s41586-019-1666-5/figures/1
[5] 양자 암호화 양자비트 책 요약에서 다루었다. 두 개의 초전도체 도선들과 그 사이에 절연체로 된 작은 판 조각으로 구성된다. 절연체는 전류가 흐르지 않으나, 양자역학적으로 쿠퍼 쌍들이 터널을 통해 간격을 이어주어 전류가 흐르게 되고, 두 개의 양자 상태를 선택하여 각각 큐비트 |0> 과 |1> 상태로 사용할 수 있다.
[6] 실리콘 칩과 반도체 디바이스의 외부 선을 매우 미세한 배선으로 전기적 연결하는 공정이라고 한다. 출처는 아래 블로그.
https://m.blog.naver.com/PostView.nhn?blogId=beer50cc&logNo=110042984902&proxyReferer=https:%2F%2Fwww.google.com%2F
[7] 양자 오차 보정에서 사용되는 용어로 보이며, 오차가 발생한 큐비트의 비트플립과 사인플립(위상플립)이 모두 발생한 경우를 호칭하는 것으로 보인다. 출처는 아래 위키.
https://en.wikipedia.org/wiki/Quantum_error_correction
[8] 클리포드 게이트는 클리포드 그룹의 원소들이며, 파울리 연산의 치환에 영향을 주는 수학적 형변환의 집합이라고 한다. 출처는 아래 위키.
https://en.wikipedia.org/wiki/Clifford_gates
그림2. https://www.nature.com/articles/s41586-019-1666-5/figures/2
[9] 두 큐비트의 위상을 교환하는 게이트로 보인다. 출처는 아래 링크.
https://quantumcomputing.stackexchange.com/questions/2594/what-is-the-matrix-of-the-iswap-gate
그림3. https://www.nature.com/articles/s41586-019-1666-5/figures/3
그림4. https://www.nature.com/articles/s41586-019-1666-5/figures/4
[10] 슈뢰딩거 방정식(Schrödinger equation) 또는 슈뢰딩거 메소드(Schrödinger method)라고도 불리며, 양자역학적 관점에서 물질의 상태를 기술하는 방정식. 세부 내용은 아래 두 위키 참고.
[12] 차원의 계수를 나타내는 물리량으로 이해된다. 설명은 아래 두 블로그.
[13] 우메쉬 바지라니, UC버클리 EECS 교수 : https://en.wikipedia.org/wiki/Umesh_Vazirani
[14] Dryad 저장소 링크 : https://doi.org/10.5061/dryad.k6t1rj8

2020년 4월 6일 월요일

"양자비트와 양자암호" 요약 - 마무리하는 글

정말 좋은 책입니다. 제 인생에 상당한 영향을 준 책 중 하나가 될 것이라 생각합니다. 저자와 역자가 모두 물리학 전공이시지만, 컴퓨터를 전공하고, 그중 컴퓨터 보안을 전공하는 모든 사람들에게 추천하고 싶습니다.

책에 오타가 다소 있습니다. 예를 들어 8장이 두 개이고, RSA 알고리즘 수식에서도 오타가 있어서 블로그에 요약할 때는 수정해서 올렸습니다. 처음 봤을 때는 조금 거슬린다고 생각했는 데, 블로그에 요약을 써보면서 오타가 생길 수 밖에 없다는 걸 알게 되었습니다. 제 글을 여러번 읽으면서 오타를 수정했습니다만, 제가 발견하지 못한 오타가 또 있을 수도 있습니다. 댓글로 알려주시면 검토해서 수정하겠습니다.

책이 비전문가를 위한 읽기 쉬운 입문서다보니 알고리즘 설명에 깊이가 조금 아쉬울 때가 있었습니다. 특히 도이치 알고리즘 부분이 저에게는 그랬습니다. 그래서 다음 책은 ' 양자 컴퓨터 입문(Parag Lala 지음, 이태휘 옮김, 2020년 1월 출간)'을 요약할 예정입니다. 빠르게 한번 읽은 소감으로는 다루는 범위가 '양자비트와 양자암호(Oliver Morsch 지음, 김말진ㆍ김형헌 옮김, 2010년 4월 출간)' 책보다 넓지는 않고, 다소 읽기 어렵지만, 내용의 깊이가 더 있는 것 같습니다. 또 최신이기도 하고요.

다음 책을 요약하기 전에, 포스팅 중간에 언급되었던 Google 의 양자컴퓨터 '시커모어(Sycamore)' 논문을 다뤄보려고 합니다. 아마 이해는 거의 포기하고, 직역하는 수준이 될 것 같습니다.

2020년 4월 5일 일요일

"양자비트와 양자암호" 요약 - 12장. 꿈인가 실제인가?

2003년 MIT 기술회보(MIT Technology Review)는 "세계를 바꿀 수 있는 10가지 기술"에서 양자암호를 소개했고, 2007년 컴퓨터 세계(Personal Computer World)란 잡지는 "미래의 10가지 기술" 중의 하나로 양자컴퓨터를 지목하였다. 양자정보는 미래의 기술 응용에서 큰 기대를 모으고 있으나, 아직 걸음마 단계이며, 실험적인 단계에 머물러있다. 이 장에서는 현재와 다가올 미래에 대해 분석한다.

12.1. 과거

양자정보의 역사에서 양자암호로 발전될 아이디어는 스티브 위즈너(Steve Wiesner)[1]가 시작했다. 이어 10년동안 급속하게 퍼져 양자역학을 알리는 역할을 하였다. 1970년 '짝 암호화(conjugate coding)'를 고안할 당시 위즈너는 브랜데이즈 대학의 학부생이었다.

위즈너가 위조 지폐의 유동을 막는 데 유용하다고 생각한 짝 암호를 간단히 알아보자. 각 지폐에 광자로 구성된 양자 일련번호(quantum serial number)를 인쇄하고 이를 작은 상자에 넣어 잠궈놓는다. 수평이나 수직 편광된 광자들이 들어 있는 이 상자는 일려번호가 각각 1과 0이 된다. 그 이외의 상자들은 ±45도로 편광된 광자들이 포함된다. 위조범은 복사를 위해 일련번호를 알아내려 할 것이고 각 상자의 기본 기저를 갖게 되지만 받은 기저의 반은 올바르지 않다. 그러므로 위조된 지폐는 자릿수의 약 4분의 1이 올바르지 않게 된다. 이는 10년 후 발전된 BB84 프로토콜과 비슷하다.

위즈너의 논문은 과학 저널지에서 거절되었으나, 다행히 위즈너의 동료인 찰스 베네트(Charles Benett)는 위즈너의 아이디어를 지지하였고, 나중에 베네트도 양자암호에 대한 연구를 시작하게 된다.

12.1.1. 파인만의 입력
1981년 MIT의 에디콧 하우스에서는 "물리학 그리고 계산"을 주제로 회의가 열렸고, 노벨상 수상자인 리처드 파인만이 기조연설을 하였다. 그 연설은 후에 "시물레이션 물리학"이란 제목으로 연구 저널에 실렸으며, 내용은 컴퓨터로 양자역학적 세계를 시뮬레이션할 수 있는 가에 대한 것이었다. 파인만은 "보편적 양자 시뮬레이터"를 가정한다면 가능하다고 하였으나, 불행히도 1988년 병으로 세상을 떠나 더 발전될 수 없었다.

1984년 찰스 베니트와 질 브라사드가 양자키 배분에 대한 프로토콜을 논문으로 발표하였으며, BB84 프로토콜로 유명하게 알려진다. 5년 후 그들의 예상치 못한 실험 성공은 세계의 많은 연구 그룹들이 양자 암호 실험에 박차를 가하는 계기가 되었다.

데이비드 도이치는 1984년 왕립학회 회보에 파인만의 아이디어를 기반으로 보편적 양자 컴퓨터에 대한 논문을 게재하고, 양자적인 특정을 나타내는 비트를 큐비트라고 하였다. 큐비트는 '0'과 '1'의 양자 상태의 중첩으로 존재할 수 있다. 예를 들어 도이치는 중첩 상태의 큐비트가 CNOT 게이트로 입력될 때, 게이트의 출력은 제어와 출력 큐비트의 결과로 정확히 분리될 수 없음을 보였다. 그것은 서로 얽혀 있기 때문이다.

도이치는 양자역학 법칙을 기초로한 양자 컴퓨터는 고전적인 컴퓨터가 할 수 없는 일들을 수행할 수 있다는 것을 보였다. 예를 들어 그는 균형 함수와 상수 함수를 단 한 번에 구분하는 알고리즘을 고안하였다. 이는 처음으로 양자병렬성을 인식하기 시작했다는 것을 의미한다. 양자병렬성이란 양자 컴퓨터가 여러 개의 입력 값을 동시에 수행할 수 있는 것을 말하며, 양자컴퓨터를 사용한 양자 중첩 상태의 최종 결과는 하나의 계산만 처리한 것보다 더 많은 정보를 가져다준다.

양자컴퓨터 프로그래밍에서 실제적인 돌파구가 열린 것은 피터 쇼어가 소인수분해의 알고리즘에 대한 논문을 출간한 1994년 무렵이다. 소인수에 대한 고전적 알고리즘은 수의 길이가 증가할 때마다 지수함수적으로 처리속도가 감속되는 반면 쇼어의 알고리즘은 수백 개의 자리수를 처리하는 시간이 수천 년에서 두세 시간으로 줄일 수 있는 대단한 능률을 보일 수 있다는 것이다. 그 후 얼마 되지 않아 로브 그로버는 비구조화된 목록에서 제 시간 안에 원하는 항목을 찾는 검색 알고리즘을 선보였다. 그로버의 알고리즘은 목록의 항목수에 비례하여 증가하지 않고, 제곱근에 비례하게 된다.

양자컴퓨터의 잠재적인 영향력이 명확해지자 이런 막강한 프로그램을 수행할 수 있는 장치를 만들기 위한 연구가 앞다투어 진행되기 시작하였다. 특히 병렬적 실험이 이루어진 이후로 이온트랩에서부터 양자점에 이르기까지 다양한 실험이 이루어지고 있다.

12.2. 현재[2]

디빈센쪼는 현재의 양자컴퓨터는 역사적으로 1950년대의 전자컴퓨터 상황과 비슷하다고 답하고 있다. 1947년 트랜지스터가 처음 발명되고, 점점 고밀도화되어 18개월마다 컴퓨터의 속도가 2배가 된다는 무어의 법칙이 시작되었다. 1950년 당시의 컴퓨터는 무게가 수톤에 달했다. 양자계산의 현 주소도 이와 같은 상황이라 할 수 있으며, 아직 이삼십년이나 더 기다려야 할지도 모른다.

어떤 관점에서는 1950년대보다 지금 상황이 더 나쁘다고 할 수 있다. 1950년대에는 트랜지스터가 이미 개발되어 있었으나, 현재 양자 컴퓨터는 트랜지스터와 같은 적합한 장치가 아직 없으며, 어느 과학자도 양자컴퓨터를 발전시킬 만한 확실한 기술이 발견되었다고 말하지 못한다. 양자점이나 초전도 겁합점과 같은 기술이 향상된 면도 있지만, 다른 대안이 없다고 말하기는 아직 이르다. 미처 발견되지 않는 양자 논리게이트나 다른 적합한 양자 회로 시스템이 정말로 존재할 수도 있다.

1950년대에도 유체 펌프를 이용한 공기압 컴퓨터 제작에 투자했듯이 현재에도 잘못된 기술에 투자할 가능성도 배제할 수 없다. 따라서 1940년대의 고전컴퓨터 개발 시대와 유사하다고 보는 쪽이 더 정확할지 모른다. 적합한 신기술이 발견되는 약간의 행운이 함께 한다면 양자컴퓨터의 개발을 이루어낼 수 있다. 현재 새로운 기술은 이삼 개월마다 제안되고 시험되고 있다.

최근에는 다이아몬드 내 질소 빈자리 결함을 기초로 한 연구가 계획되고 있다. 다이아몬도는 탄소분자의 큐빅 격자구조로 이루어져 있으며, 질소와 브롬과 같은 몇 개의 다른 분자들을 이 구조에 합성시켜서 특수한 색깔을 띠는 불순물이 첨가된 다이아몬드를 만든다. 이와 유사한 방법으로 몇 개의 탄소원자들을 격자구조로부터 이탈하게 만들 수 있는 데 소위 빈자리를 만드는 것이다. 가끔 빈자리는 불순물의 옆자리에 발견될 수 있으며, 만일 질소 불순물이 빈자리 옆에 바로 위치한다면 탄소원자 사이의 화학결합에 포함되지 않는 전자들은 과잉으로 남는다. 이 전자들은 '스핀 위'와 '스핀 아래'를 갖는 화합물을 만들어 큐비트 제작에 적합하다. 이러한 '다이아몬드 큐비트'의 제어는 마이크로파를 사용하여 과잉으로 남는 전자들을 |0> (스핀 위) 와 |1> (스핀 아래) 상태 사이에서 전환되게 한다. 레이저 빛을 다이아몬드에 쪼이면 전자들의 상태에 따라 많이 혹은 적게 빛을 흡수하며 이를 통해 큐비트의 값을 읽게 된다. 다이아몬드 큐비트의 결맞지 않는 시간은 50㎲ 정도인데 일반적인 초전도 큐비트의 결맞음 시간보다 훨씬 더 길다[3]. 또한 질소 빈자리 결함과 이웃하는 질소 분자의 빈자리가 없는 결함도 '가상광자'에 의해 서로 결합되므로 두 개의 큐비트 게이트를 실현하는 데 중요하다.

12.3. 미국고등기술연구처(ARDA)의 기술개발계획안(roadmap)

양자계산과 양자암호는 비록 아직 기본적인 연구에 머물고 있지만, '파격적인 기술'로서 인정되는 점에서 물리학의 다른 연구와 비교해서 차이가 있다. 비밀을 지키거나 도청하는 데에 강력한 기술인 양자정보 분야는 한번 기술이 성공되면 전혀 다른 세상을 만들 수 있다. 정부나 첩보기관이 매우 관심있게 그 진보를 주시하고 있으며, 미국의 정보공동체 재정기관(미국무부와 CIA를 포함한 16개 미정부기관)인 고등기술연구처(ARDA, 현재는 기술혁신국, DTO로 불린다)의 중장기 발전방안에도 반영되고 있다.

이 발전 방안의 초기 안은 2002년에 마련되었고, 2004년에 갱신되었으며, 2007년 다시 갱신 예정이었다. 이 문서들은 현재 이 분야의 최첨단 기술을 망라하고 미래에 달성해야 할 현실적인 목표를 정의한다. 현재 이 ARDA 발전 방안의 시간 지평선은 2012년이다. 다시 말해 2012년까지 양자 알고리즘을 시험할 수 있는 정도의 양자 컴퓨터가 가동되어야 하며, 그 정도의 능력을 가진 양자컴퓨터는 적어도 50큐비트 정도는 되어야 오차보정도 가능할 것으로 예측된다.

12.4. 양자 시뮬레이터

오늘날 컴퓨터의 위력은 바로 유연한 적응성이라 해도 과언이 아니다. 하나의 장치로 문서편집, 게임, 영화 감상까지 할 수 있다. 만일 매번 다른 것을 하려 할 때마다 기계의 배선을 바꿔야 한다면 컴퓨터의 매력은 덜할 것이다. 융통성 많은 컴퓨터에 이미 익숙해져서 양자컴퓨터에서도 같은 일이 행해지기를 바랄지도 모르지만, 그런 일이 가까운 미래에는 일어나지 않을 것이 확실하다.

첫째로 수 많은 양자컴퓨터의 알고리즘은 한계를 드러낼 것이며, 가까운 시일 내 새로운 알고리즘을 발견할 수 있을지 예측할 수 없다. 그러나 이미 알려진 알고리즘은 많은 수학적 문제와 소인수와 데이터베이스 검색의 방법을 전환시킬 수 있다. 둘째는 한 종류의 문제만 다룰 수 있는 '단순한' 컴퓨터가 유용할 수도 있다는 점이다. 예를 들어 일기예보를 위해서만 만들어진 컴퓨터로 체스나 소설을 쓰지 못해도 대단히 유용한 컴퓨터이다. 현재 보편적인 양자컴퓨터의 실행을 위해 연구되는 기술들은 양자계의 거동만을 집중하여 처리하게 될 '양자 시뮬레이터(quantum simulator)'의 구축에도 활용될 수 있다. 이는 리처드 파인만이 제안한 것으로 통상의 컴퓨터에서 계산할 수 없는 양자계의 거동을 정확히 예측할 수 있는 컴퓨터이다.

특별히 많은 입자를 포함하는 양자계는 고전적인 컴퓨터로는 시뮬레이션이 어렵지만, 양자컴퓨터는 어떤 알고리즘의 속도를 지수함수적으로 향상시킬 수 있다. 고전컴퓨터는 양자계의 크기가 커질수록 처리 속도가 지수함수적으로 감소되기 때문이다. 예를 들어 양자컴퓨터는 두세 개 정도의 큐비트를 가지고도 동시에 "0"과 "1"의 수백 개의 가능한 조합으로 중첩 상태에 놓일 수 있으나[4], 고전컴퓨터는 계산과정 동안 이런 모든 과정을 다 추적해내야만 한다. 이 과정은 많은 메모리 용량을 요구하고 처리 속도를 심각하게 증가시킨다.

양자 시뮬레이터를 구축하는 한가지 가능성은 9장에서 다룬 광학격자를 사용하는 것이다.  현재 많은 연구그룹들이 고체 상태의 계의 양자적인 거동에 대한 시뮬레이션을 발전시키고 있으며, 일부 과학자들은 고온 초전도체의 신비의 베일을 벗길 수 있을 것으로 기대하고 있다.

12.5. 상업적 가치가 있는 계

2007년 2월 13일 캐나다의 D-Wave 사의 "오리온(Orion)"이라는 양자 컴퓨터를 발표했다. 사람들은 양자컴퓨터가 수도쿠(sudokus) 퍼즐을 풀고 파티의 좌석을 배치하는 업무를 수행하는 것을 보았으나, 이 후 그 컴퓨터는 박물관에 없고 인터넷을 통해 원격조정된다고 하였다. 회사의 대변인은 그 양자컴퓨터의 16개 큐비트가 작은 초전도체의 루프로 만들어졌으며, 두 방향의 전류로부터 |0> 과 |1> 의 중첩상태를 만들 수 있다고 밝혔다. 또 2008년까지 512큐비트로 증가할 것으로 기대된다고 하였는 데, 이는 당시 다른 실험실의 목표의 50배에 해당했다.

대부분의 전문가들은 오리온이 최초의 상용 양자컴퓨터가 되지 않을 것이라고 믿는다. 무엇보다 D-Wave 사가 자세한 기술적 데이터를 공개하지 않았으며, 두세 개의 큐비트를 가지고 씨름하는 동안 16개의 큐비트 기계를 만들었다는 기술의 세부 과정이 밝혀지지 않았다. 물론 D-Wave 사가 가장 어려운 기술로 알려진 결읾음(decoherence)을 극복하는 방법을 발견했다면 기술보호의 명목으로 외부 공개를 꺼렸을 수도 있을 것이다.

D-Wave 사가 2007년 초에 그들이 양자컴퓨터를 증명하기 사용했던 문제는 지금 다른 평범한 컴퓨터로도 짧은 시간 안에 풀 수 있다. 이 말은 오리온이 양자컴퓨터일 수도 있지만, 세계 도처의 수 백명의 과학자들이 실패한 분야에서 홀로 성공을 거두었다는 것을 아직 그대로 믿기 어렵다는 의미이기도 하다.

양자계산의 상용화가 아직 갈 길이 멀어 보이는 반면 양자암호는 이미 실제화되고 있다. 스위스의 Idequantique 사, 프랑스의 SmartQuantum사, 미국의 MagiQ 사의 세 회사는 이미 상업적인 시스템을 제공하고 있고, IBM, Toshiba, HP 사 등도 그들이 개발한 시스템의 상용화를 수행하고 있다.

12.6. 미래

"컴퓨터와 암호에 일어나고 있는 양자물리학의 혁명"이라는 이 책의 부재가 현재형 시제를 사용한 이유는 명확해졌다. 지금까지의 내용은 빙산의 일각이며, 미래의 아주 희미한 암시 정도이다. 지금부터 이삼 년 안에 이 책에서 설명한 많은 실험들이 고대 역사와 같이 될 수도 있으며, 실제로 그렇게 되기를 바란다. 책을 탈고 하며 저자는 "광학격자의 원자들로 구성된 SWAP 양자게이트의 실현"에 대한 기사를 보았는 데, SWAP 게이트는 CNOT 게이트와 비슷하므로 양자컴퓨터를 구축하는 기본틀로서 사용될 수 있다. 또, "서로 단일한 광자의 교환을 통해 소통되는 초전도체의 큐비트"에 관한 기사도 보았다. 이 두 개의 기사들은 양자컴퓨터를 구축하는 데 중요한 단계에 들어섰음을 시사하지만, 그 둘은 매우 다른 '하드웨어'를 사용하고 있다. 큰 돌파구에 해당하는 새로운 발견이 양자 컴퓨터의 미래를 결정하기 까지는 다각적으로 시도되는 실험적인 상황이 한동안 유지될 것으로 보인다.

실험과 발견이 하나의 견해로서 끝날 수도 있지만, 모든 것이 완전히 뒤바뀔 수도 있다. 오스카 와일드(Oscar Wilde)가 "추측은 어렵다. 미래에 대해서는 더욱더 어렵다"라고 하였듯이, 양자정보에 대한 흥분된 시대가 가진 미래의 전망은 밝아 보인다. 이제 여러분이 이 속도를 즐기기 바란다.

[1] 스티븐 위즈너(Stephen Wiesner) 가 맞아 보인다.  아래 위키 참고.
https://en.wikipedia.org/wiki/Stephen_Wiesner
[2] 현재라고 하지만 책이 출간된 날짜는 2010년 4월이다.
[3] 문맥상 "다이아몬드 큐비트의 결맞지 않는 시간" 보다는 "결맞음 유지 시간" 이  맞아 보인다.
[4] 각 큐비트의 위상을 수직-수평 편광 뿐만 아니라, 미세한 각도까지 편광, 측정이 가능해야 말이 될 것 같다.