Видео

그렇게 생각하셔도 거의 문제가 없지만... 정확히는 그보다는 조금 복잡합니다. 다만 소수 p와 q를 알면 암호를 풀 수 있기 때문에 사실상 private key만큼 중요하다고 봐도 문제 없습니다! RSA 암호 위키를 한 번 읽어보시면 좋을 것 같습니다: ko.wikipedia.org/wiki/RSA_%EC%95%94%ED%98%B8

일반적으로 학부 4학년~석사 과정 내용이며, 관련 전공 학부 3~4학년 학생들을 대상으로 준비하였습니다.

감사합니다. 큰 도움이 되었습니다

영상에서 말했듯이 쇼어 알고리즘은 기본적으로 주기를 찾는 알고리즘입니다. 따라서 주기를 찾는 문제에 광범위하게 적용이 가능하고, 특히 discrete logarithm 문제는 abelian hidden subgroup problem으로 변형할 수 있기 때문에 같은 방법으로 풀 수 있습니다. en.wikipedia.org/wiki/Shor%27s_algorithm 역사적으로 원래 이 알고리즘은 discrete logarithm 문제를 푸는 알고리즘으로 먼저 발표했었는데, discrete logarithm 문제의 역시 elliptic curve group과 관련이 있어서 암호학 분야에서 중요한 발견이었다고 해요. 그런데 당시 이 내용이 미국 동부에서 미국 서부로 전달되면서 discrete logarithm 문제가 아니라 prime factorization 문제가 풀렸다고 잘못 알려졌고, 이걸 들은 쇼어 교수님이 '근데 그것도 풀 수 있겠는데?' 라고 생각하면서 소인수분해 알고리즘이 되었다는 썰이 있네요. 영상에서 언급했었나..? 아무튼 사실 이 알고리즘은 discrete logarithm 문제를 푸는 알고리즘이었다는 사실!

소중한 답변 감사드립니다!!!:)

해당 영상 및 깃허브를 통해 공개된 소스코드 등은 출처만 정확하게 남기시면 자유롭게 활용가능합니다.

가장 간단한 오라클은 input과 output이 있는 오라클입니다. 오라클 O에 |x>ⓧ|0> 을 input으로 넣으면 |x>ⓧ|f(x)> 를 output으로 돌려주는 형태죠. 일반적으로 input x가 원하는 정답이면 f(x)=1, 아니면 f(x)=0 으로 설정합니다. 그런데 양자컴퓨터에서는 이 오라클에서 output f(x)를 얻는 대신, phase kickback이라는 방법을 이용해 input |x> 에 -|x> 로 (-) 부호를 돌려주도록 할 수 있습니다. 많은 양자 알고리즘에서 output f(x) 를 직접 확인하는 것보다 이렇게 (-) phase가 생기도록 하는 것이 더 효과적이고, 따라서 오라클 자체를 그냥 정답 |w> 에 (-) 부호를 붙여주는 오라클로 설정하곤 합니다. 영상에서는 이 (-) 부호를 돌려주는 오라클을 가정했습니다. Phase kickback은 최근에 이 영상에서 설명한 적이 있습니다: ruclips.net/video/f7FOnNzBIwQ/видео.html

이론상 가능하긴한데 정밀한 결과를 위해서는 델타 t 를 굉장히 작게 해야할 수도 있습니다. 다른 메소드도 있을거 같긴한데 최적화를 위해 입자간의 거리를 매번 측정해서 거리가 짧을 수록 델타 t를 짧게 한다가..

확인했습니다 오늘 안에 깃허브에 올려보도록 하겠습니다. 올리고 다시 답글드릴게요!

@@boseong14 넵 감사합니다! 그리고 오늘 해커톤 강의도 듣고 질문 하시는것도 보았습니다..!ㅎㅎ

관심 감사합니다ㅠㅠ 방금 깃허브에 올리고 설명에 링크 올렸습니다!

좋은 질문 정말 감사합니다! 처음 접했을 때 이 부분을 가장 헷갈려 하시는 것 같아요. 댓글 내용 일부를 설명하는 이미지입니다. 보면서 읽으시면 좋을 것 같습니다. drive.google.com/file/d/16L6gYkbVLAEMWq9a-rJaSzgxRiYQL1Kk/view?usp=sharing 23번 슬라이드는 4개의 큐빗에 각각 Hadamard 게이트를 가하여 중첩상태를 만드는 부분입니다. 일단 bit, 2진법으로 수를 표현할 때에 0 = 0000(2), 5 = 0101(2), 15 = 1111(2) 등 4개의 0과 1으로 0~15의 16개 숫자를 표현할 수 있다는 점을 기억해주세요. 이제 4개의 qubit이 각각 (1/√2) * (|0>+|1>) 의 중첩(superposition) 상태에 놓이게 되면 전체 상태는 (1/√2)^4 * (|0>+|1>) ⓧ (|0>+|1>) ⓧ (|0>+|1>) ⓧ (|0>+|1>) = 1/4 * (|0000> + |0001> + ... + |1111>) 으로 16개의 상태가 정확히 동등하게 존재하는 상태가 됩니다. 해당 상태를 만드는 것은 얽힘(entanglement)을 만든다고 말하지 않습니다. 얽힘 상태에 있다는 것은 "어떤 하나의 큐빗을 관측하는 것이 -> 다른 큐빗을 관측하는 결과에 영향을 줄 때"를 가리킵니다. 하지만 우리가 원하는 상태인 0000~1111 까지 16개의 상태가 똑같이 존재하는 상태에서는, 예를 들어 첫 번째 큐빗이 '1'이었다고 해서 다른 큐빗이 무조건 0이 나와야 한다거나 하는 제약조건이 없죠. 다음으로 자물쇠 함수 f가 받는 입력은 qubit 4개, 16차원의 벡터를 입력으로 받는 것이 맞습니다. 사실 고전 컴퓨터에서 생각하는 함수 f와는 조금 다른 것이 맞습니다. 다만 구현되는 원리 자체는 일관적입니다. 예를 들어서 답 |w> = |15> = |1111> 인 경우를 생각해볼까요? |1111>에만 (-) 부호를 붙여주는 방법은 한마디로 "CCCZ 게이트"를 아무렇게나 가해주면 됩니다. 먼저 Z 게이트는 |0>은 그대로, |1>에는 (-) 부호를 붙여주는 게이트입니다. 이 게이트에 control이 3개가 붙는다는 것은 나머지 3개의 큐빗이 전부 1일 때만 Z 게이트를 가한다는 뜻입니다. Control이 붙어있는 3개의 큐빗이 전부 1이고, Z 게이트를 가하는 큐빗이 1일 때만 (-) 부호를 붙여주니까, 결국 모든 큐빗이 1일 때만 (-) 부호를 붙여준다는 거죠. 일반적으로 우리가 고려하는 자물쇠 함수 f는 꽤 복잡한 함수입니다. 하지만 많은 경우 문제의 정답을 구하는 것보다, 정답에만 어떤 일이 일어나도록 하는 것이 더 쉽습니다. 예를 들어 소인수 분해 문제를 생각해보면, 어떤 숫자 x의 소인수를 정확히 찾는 것은 어렵지만, 입력 a에 대해 x/a가 정확히 나누어 떨어지는지 확인하는 것은 쉽습니다. (modulo 연산이라고 하죠) 즉, 숫자 x가 있을 때, x의 소인수를 구하지 않고, x%a = 0 인지만 확인하는 함수를 구현하자는 것입니다. 그러면 그로버 알고리즘에서 f는 x%a = 0 이면 a에 (-) 부호를 붙이고, 그렇지 않으면 그대로 두는 함수가 되는 것이죠. 마지막으로 짚어볼 부분은 "이것이 왜 고전적인 방법으로는 구현이 불가능한가?"에 대한 답입니다. 이미 감을 잡으셨겠지만, 고전적인 방식으로는 '입력을 특정하지 않고 함수를 가하는 것'이 불가능합니다. 말씀하신 내용에서 보면, 16차원의 벡터를 한꺼번에 연산하는 것이 불가능하다는 뜻입니다. 말씀하신대로 이 자물쇠 함수 f는 고전 컴퓨팅에서는 하나의 입력에 하나의 출력만을 주는 함수이고, 양자 컴퓨터에서는 벡터를 입력받아 벡터를 출력하는 함수가 맞습니다. 하지만 이를 구현하는 방법에서는 차이가 없습니다. 고전 컴퓨터에서 x%a를 구현한 방법과 똑같이 양자 컴퓨터에서도 x%a를 구현할 것이니까요. 음... Qiskit textbook이 업데이트가 되면서 그랬는지 한국어 페이지가 안 뜨네요... Qiskit 문서들의 번역을 위해서 한국어 번역팀이 계속해서 노력해주시고 있습니다. 업데이트될 한국어 페이지도 기대해주시고, 질문이 있으시면 계속해서 댓글이나 메일, 또는 Qiskit Slack korean 채널을 통해서 질문해주세요! SCC가 학생 운영진으로 참여한 Qiskit Hackathon Korea 2022 가 곧 열릴 예정이기도 하니, 한국의 많은 학생들, 선배님들 그리고 교수님들과 함께 공부할 수 있는 기회로 많이 참여해주시면 감사하겠습니다. 감사합니다.

26:49

설명란에 소스 코드 링크를 추가하였습니다 관심 가져주셔서 감사합니다!