양자 컴퓨터 과연 지금 나와있을까?

사실 양자 컴퓨터의 존재에 대해 많은 기사가 쏟아져 나오는데, 실질적인 양자 컴퓨터의 등장 여부를 알 수 있는 가장 좋은 방법은 예전에 진행했던(지금은 매년 시행이 중단되었지만) RSA 소수 분해 숙제가 풀렸는지 확인하는 것이다. 오래전에 중단되어 상금은 없어졌지만, 그 문제는 흔히 회자되는 양자 컴퓨터의 성능 경쟁에서 역사적으로 가장 기사 쓰기 좋은 challenge라고 볼 수 있다. 분해해야할 큰 숫자는 공개되어 있지만, 실제 분해되어 곱해지는 소수값은 초기 그것을 만들었을때 파기해 버려 실제 정답은 아무도 모르는 숫자이기 때문이다. 개인적으로는 상당히 기대되는 기사 발표다.

 

https://en.wikipedia.org/wiki/RSA_Factoring_Challenge

RSA Factoring Challenge - Wikipedia

 

양자 컴퓨터가 할 수 있는 연산은 현재 피터 쇼어의 소인수분해 알고리즘이 대표적이기 때문에 이를 통하는게 가장 좋은 것이다. 별도로 IBM은 자사의 양자 컴퓨터를 사용해 연산할 수 있는 클라우드 API를 제공하고 있지만(15 qubit) 아직까지 이를 통해 역시 위 RSA문제를 풀었다고 알려진 사례는 없으므로 유의미하게 제공하고 있는지는 의문이다. 물론 D-Wave에서 다루어지고 있다는 optimization문제에 최적화된 양자 컴퓨터 같은 것들에게는 좀 유효하지 않을 수는 있다.(그녀석들은 쇼어 알고리즘을 수행하는 형태의 양자컴퓨터가 아닌 것으로 알려져 있다)

 

https://developer.ibm.com/dwblog/2017/quantum-computing-api-sdk-david-lubensky/

Quantum computing gets an API and SDK - The developerWorks Blog

혹시 실제 이 수가 어떤 것인지 궁금해하시는 분이 있을것 같아 간단히 남겨둔다.

 

과연 아래 수를 수시간안에 소인수 분해할 수 있는 컴퓨터는 언제 등장할 수 있을까? (지금 일반 컴퓨터로는 아마 엄두도 나지 않는 계산일것이다)

 

RSA challenge :

 

RSA-1024 = 13506641086599522334960321627880596993888147560566702752448514385152651060485953383394028715057190944179820728216447155137368041970396419174304649658927425623934102086438320211037295872576235850964311056407350150818751067694629205563685529475213500852879416377328533906109750544334999811150056977236890927563

 

RSA-2048 = 25195908475657893494027183240048398571429282126204032027777137836043662020707595556264018525880784406918290641249515082189298559149176184502808489120072844992687392807287776735971418347270261896375014971824691165077613379859095700097330459748808428401797429100642458691817195118746121515172654632282216869987549182422433637259085141865462043576798423387184774447920739934236584823824281198163815010674810451660377306056201619676256133844143603833904414952634432190114657544454178424020924616515723350778707749817125772467962926386356373289912154831438167899885040445364023527381951378636564391212010397122822120720357