Quantum algorithm and Hidden Subgroup Problem

지난주 금요일 이훈희 교수님과 정자아 교수님 앞에서 세미나를 했습니다. 주제는 Survey of Hard problems in Cryptography & Quantum algorithms 였습니다. 완전히 성공적이였던 것 같지는 않지만요..

하여간 그래서 Quantum algorithm쪽에서 다뤘던 얘기를 포스팅하려 합니다.

주제는 Survey of Quantum Algorithm and the Hidden Subgroup Problem입니다.

Quantum algorithm and Hidden Subgroup Problem 더보기

Most interesting computational mistake in 2016

할 일이 이것저것 생기니 포스팅을 잘 하지 않네요.
원래 쓰려고 했던 것들도 쓰려고 하면 손에 잘 안잡히고 글이 짧아지고 그러네요..
이 글도 원래는 Babai의 graph isomorphism에 대해서도 쓰려고 했지만, 이 부분은 제가 잘 모르기도 하고 여러군데 많이 글이 올라와서 아예 빼버렸습니다.

 

Shor 와 Eldar의 논문 [1]은 암호학계(와 아마도 Computer Sciecne에도)에 꽤나 큰 반향을 일으켰습니다.

이 논문은 BDD의 특수한 경우(GapBDD)를 quantum polynomial time에 푼다고 주장하고 있습니다. 물론 실제로 보면 그 특수한 경우의 factor들이 (보통 수백~수천으로 잡히는) 문제의 차원 n에 대해 \frac{1}{n^17}이나 \frac{1}{n^13}이 되는  등 현실적인 수준은 아닙니다만, 지금까지의 일반적인 알고리즘은 모두 최소한 subexponential time이 필요했고, polynomial time이 있다면 이 논문보다 훨~씬 특수한 경우에만 풀었을 겁니다. 아마 이 문제의 언어로 바꾸면 factor들이 exponential이 되지 않을까 싶습니다.(이부분은 제가 정확히 잘 모르겠습니다)

앞선 연구에 따르면 bounded distance decoding(BDD)는 up to polynomial factor로 Gap-shortest vector problem(GapSVP)와 같은 난이도를 갖고 [2], 이는 어렵다고 믿어지는 문제일 뿐더러 GapSVP는 SVP의 특수한 경우이고, SVP는 randomize NP-hard라고 알려져 있기 때문입니다 [3].

또한 저 \frac{1}{n^a} factor들을 \frac{1}{\sqrt{n}}수준으로 줄일 수 있다면 Learning with error(LWE)라는 암호학적 문제가 깨진다고 합니다 [1]. 그런데 이는 현재에도 엄청나게 많은 암호스킴들의 기반문제가 되는 문제라서, 심지어는 quantumly 안전하다고 모두가 믿고있는 문제여서 이게 참이라고 밝혀지면 정말 암호학계가 난리가 나는 겁니다.

이 논문이 처음 arxiv에 업로드 되었을 때 한창 학교에서 PQcrypto Asia forum in Seoul이 진행중이였는데, 많이들 이 논문의 얘기를 했습니다.

 

하지만 아쉽게도 업로드된지 얼마 되지도 않고 이 논문은 결국 철회됩니다. Appendix에 있는 Fact 7의 증명이 계산이 Regev에 의해 (꽤 크게)틀렸다는게 밝혀진거죠. 그 명제와 증명은 다음과 같습니다. 여기서 n차원 벡터 x에 대해 {\rm sinc}_s (x)\prod\limits_{i=1}^{n} \frac{\sin (x_i/s)}{x_i/s}로 정의됩니다.

errorines

ㅋㅋ.. 저는 읽기 싫어서 안읽었습니다. quantum algorithm에도 관심이 있어서 좀 읽어볼까 했는데 두분이 다른 논문 [4]에서 쓴 개념인 SysNF를 쓰길래 그냥 일단 접어뒀습니다.

Quantum algorithm들은 참 재미있지만, 저런 계산이 조금 많이 필요한가봅니다. 하긴 확률 근사같은게 들어가야하니 당연하려나요. 빨리 Shor의 Prime factorization 후편들을 올려야하는데.. 빨리빨리 정리하고 올리겠습니다.

 

References

[1]https://arxiv.org/abs/1611.06999
[2]Stephens-Davidowitz, Noah. “Dimension-preserving reductions between lattice problems.” h ttp://www. noahsd. com/latticeproblems. pdf (2015).
[3]Ajtai, Miklós. “The shortest vector problem in L 2 is NP-hard for randomized reductions.” Proceedings of the thirtieth annual ACM symposium on Theory of computing. ACM, 1998.
[4]Eldar, Lior, and Peter W. Shor. “The Systematic Normal Form of Lattices.” arXiv preprint arXiv:1604.07800 (2016).

The probability that two random integers are relatively prime.

영어공부를 하다 심심해서 오랜만에 기억나는 다음 정리를 다시 한번 증명해봤습니다.

(Theorem) The probability that two random positive integer are relatively prime is 1/\zeta(2)=6/\pi^2.

아래의 증명은 (아마도) Niven책[1]에서 처음 본 것 같습니다. 조금 다르더라도 이런 방식의 정의와 증명을 처음 본 건 Niven이 맞으니까 뭐 저기서 인용했다고 칩시다.

The probability that two random integers are relatively prime. 더보기

TEPS

Nowadays I’m studying English to achieve high score in TEPS, authorized English test in Korea. I really want to write about quantum computations, Shor’s algorithms, and other fascinating topics, but I cannot because I memorized words and grammar, solve and read too many problems in English everyday…

 

영어로 글을 쓰긴 참 힘들군요. 아무래도 한글이 답인 것 같습니다..
내일 당장 텝스 시험인데, 일단 700점이나 넘었으면 좋겠네요. 800점을 넘기는게 최종 목표긴 합니다만..

Quantum computation and Shor’s factorization algorithm (0)

Shor의 Factorization algorithm은 굉장히 유명한 논문입니다 [1]. classical 컴퓨터로는 어렵다고 믿어지는 소인수분해 문제를 양자컴퓨터로 다항식시간에, 그것도 굉장히 낮은 시간복잡도로 해결해버린 놀라운 알고리즘이거든요. 이 알고리즘에 따르면 양자컴퓨터가 현실화되면 RSA나 기타등등 소인수분해가 어렵다고 가정하고 시작하는 많은 암호논문이 종이쪼가리가 되어버립니다!! 이중에서는 실제로 쓰는 시스템도 많은데 말이죠..

최근에 미국 국가안보국(NSA, National Security Agency)에서는 대 양자컴퓨터 암호(post-quantum cryptography)를 만들어야 한다고 경고했고, NIST(National Institute of Standards and Technology)에서는 post-quantum cryptography의 표준을 공모했습니다 [2].

현실에서는 문제가 좀  있습니다. 물리적으로 큰 메모리를 갖는 양자컴퓨터를 만들기가 힘들거든요. 절대 0도에 가까워져야 하고.. 물리는 잘 모르지만 하여튼 힘들다고 합니다.
자세하게는 classical computer의 bit에 해당하는 quantum computer의 대상을 qubit라고 부르는데, 이 qubit를 100개 갖는 컴퓨터를 만드는 것도 힘듭니다. 구글이 2017년 말까지 50 qubit의 quantum computer를 만들겠다고 발표했는데 [3], classical computer의 것과 비교하면 애들 장난같죠. 훨씬 큰 qubit를 갖는 D-wave라는 물건이 있긴 한데, 이건 정확하게는 quantum computer는 아니고 quantum annealing이라는 global minimum을 찾는 알고리즘에 특화된 컴퓨터라고 합니다 [4].
이에 더해 소인수분해는 아예 4qubit정도만 사용하는 선에서만 성공했다고 하고, 심지어 shor의 알고리즘이 아니라 qubit를 적게 쓰는 다른 알고리즘을 통해서 했다는 말도 들었습니다.
즉 양자컴퓨터에서는 시간복잡도뿐만 아니라 공간복잡도도 엄청나게 큰 문제라는 거죠.

 

소인수분해에 관한 Shor의 결과는 다음과 같습니다.

[Shor] There is a quantum algorithm to factorize $n$, which uses \mathcal O(\log n) space and \widetilde{\mathcal O}(\log ^3 n) time.

Shor의 논문이 엄청 어려운 편은 아닌데, 개념이 생소하다보니 읽다보면 이게 대체 맞는 소리인가 헷갈리곤 합니다. 다음 글부터는 그 디테일들을 확인해 봅시다! 언제 올라올지는 모르겠지만요..

 

[1] Shor, Peter W. “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer.” SIAM review 41.2 (1999): 303-332.

[2] NSA says it “must act now”, MIT technology report, Feb. 2016.
https://www.technologyreview.com/s/600715/nsa-says-it-must-act-now-against-the-quantum-computing-threat/

[3] Google’s quantum dream may be just around the corner, MIT technology report, Aug. 2016.
https://www.technologyreview.com/s/602283/googles-quantum-dream-may-be-just-around-the-corner/

[4] D-wave system, wikipedia.
https://en.wikipedia.org/wiki/D-Wave_Systems

 

A toy problem

얼마전에 (크리스마스날!) 학원 수업 대타를 하루 했습니다. 이제 다시는 학원수업을 하지 않을줄 알았는데.. 오랜만에 올림피아드 문제좀 풀어볼까 하고 잠시 시간을 내어 수업을 했습니다. 그런데 그 전후로 너무 바빠서 생각보다 힘들었습니다..

그날 수업을 위해 준비한 문제중 다음과 같은 문제가 있습니다.

There are n positive integer a_1,\cdots , a_n, need not to be different, in the blackboard. In each “step”, we can erase two numbers a,b  and write greatest common divisor and least common multiple of a,b in the blackboard. The “meaningful step” is a step which change the set of integers in the blackboard.

  1. Prove that the possible number of meaningful steps is finite.
  2. Regardless of the way we do steps, if we cannot do any meaningful steps, the possible set of integers in the blackboard is  unique.

원래 문제는 1번만 있었는데, 너무 쉬워서 내지 말까 고민했었습니다. 근데 왠지 더이상 할 수 없는 상태가 유일하지 않을까 싶어서 이리저리 고민해보니 적당한 난이도로 해결이 되고, 재미있는 toy problem인 것 같아서 출제했습니다. 풀이는 비밀로 ㅎㅎ.