양자 컴퓨터 과연 지금 나와있을까?
사실 양자 컴퓨터의 존재에 대해 많은 기사가 쏟아져 나오는데, 실질적인 양자 컴퓨터의 등장 여부를 알 수 있는 가장 좋은 방법은 예전에 진행했던(지금은 매년 시행이 중단되었지만) RSA 소수 분해 숙제가 풀렸는지 확인하는 것이다. 오래전에 중단되어 상금은 없어졌지만, 그 문제는 흔히 회자되는 양자 컴퓨터의 성능 경쟁에서 역사적으로 가장 기사 쓰기 좋은 challenge라고 볼 수 있다. 분해해야할 큰 숫자는 공개되어 있지만, 실제 분해되어 곱해지는 소수값은 초기 그것을 만들었을때 파기해 버려 실제 정답은 아무도 모르는 숫자이기 때문이다. 개인적으로는 상당히 기대되는 기사 발표다.
https://en.wikipedia.org/wiki/RSA_Factoring_Challenge
RSA Factoring Challenge - Wikipedia
The RSA Factoring Challenge was a challenge put forward by RSA Laboratories on March 18, 1991 to encourage research into computational number theory and the practical difficulty of factoring large integers and cracking RSA keys used in cryptography. They p
en.wikipedia.org
양자 컴퓨터가 할 수 있는 연산은 현재 피터 쇼어의 소인수분해 알고리즘이 대표적이기 때문에 이를 통하는게 가장 좋은 것이다. 별도로 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
Explore quantum computing with our new API and SDK available for IBM's Quantum Experience. Use python scripts to access the power of quantum computing!
developer.ibm.com
혹시 실제 이 수가 어떤 것인지 궁금해하시는 분이 있을것 같아 간단히 남겨둔다.
과연 아래 수를 수시간안에 소인수 분해할 수 있는 컴퓨터는 언제 등장할 수 있을까? (지금 일반 컴퓨터로는 아마 엄두도 나지 않는 계산일것이다)
RSA challenge :
RSA-1024 = 13506641086599522334960321627880596993888147560566702752448514385152651060485953383394028715057190944179820728216447155137368041970396419174304649658927425623934102086438320211037295872576235850964311056407350150818751067694629205563685529475213500852879416377328533906109750544334999811150056977236890927563
RSA-2048 = 25195908475657893494027183240048398571429282126204032027777137836043662020707595556264018525880784406918290641249515082189298559149176184502808489120072844992687392807287776735971418347270261896375014971824691165077613379859095700097330459748808428401797429100642458691817195118746121515172654632282216869987549182422433637259085141865462043576798423387184774447920739934236584823824281198163815010674810451660377306056201619676256133844143603833904414952634432190114657544454178424020924616515723350778707749817125772467962926386356373289912154831438167899885040445364023527381951378636564391212010397122822120720357