Introduction to Quantum Computer and Grover's Algorithm

No video

Introduction to Quantum Computer and Grover's Algorithm

Рет қаралды 15,286

Күн бұрын

I will cover the basic understanding of quantum computing, and how it related to linear algebra. Using the basic understanding, I present the fundamentals of Grover algorithm.
00:00 - Introduction
00:34 - Quantum vs Classical
02:54 - Quantum Circuit: Qubit
05:21 - Quantum Circuit: X Gate
06:00 - Quantum Circuit: H Gate
07:13 - Quantum Circuit: Z Gate
08:35 - More Than Two Qubit
10:05 - Quantum Circuit: CX Gate
11:41 - Quantum Circuit: CZ Gate
12:20 - Quantum Circuit: CCX Gate
12:20 - Quantum Circuit: NOT Gate
14:30 - Quantum Circuit: AND Gate
15:10 - Quantum Circuit: OR Gate
16:11 - Quantum Circuit: Addition
18:17 - Cost of Quantum Circuit
20:42 - Grover Algorithm
22:13 - Grover Algorithm: Superposition
23:35 - Probability Amplitude Interpretation
24:30 - Vector Interpretation
25:46 - Grover Algorithm: Oracle
28:42 - Grover Algorithm: Diffuser
30:49 - Grover Algorithm Example: Two Qubit
36:41 - IBM Quantum Computing
37:15 - Grover Algorithm: Iterations
38:46 - Grover Algorithm: Limitations
40:05 - Ending

Пікірлер: 89

@nalayakshindra 3 жыл бұрын

Your teaching style is so simple and interesting .... it keeps our focus on the subject....please do more on the basics like this on the subject. Thank u.

@saesunkim 3 жыл бұрын

I will try my best

@logankim2782 3 жыл бұрын

와 진짜 너무 최고의 강의입니다. 저 늦은 나이에 미국에 유학와서 대학원 수업듣는데 그루버 알고리즘 숙제를 받았네요..멘붕에 허우적대다 설마하면서 유투브 검색해보다 Saesun 님의 명강의를 발견하게 되었습니다. 저보다 훨씬 어려보이시고 전공능력이나 영어(Presentation 하시는 것 봤음^^) 모두 월등하시네요 정말 같은 한국인으로서 자랑스럽습니다 항상 건승하시길 응원하겠습니다^^

@saesunkim 3 жыл бұрын

너무 감사합니다! 그리고 도움이 되었다니 너무나 기쁩니다. 학회나 다른장소에서 마주칠 날을 기대할게요!

@shlee0915 Жыл бұрын

수학적 지식이 부족하여 다 이해한 건 아니지만, 정말 많은 도움이 되는 것 같습니다. 쉽게 설명해 주셔서 감사합니다.

@saesunkim Жыл бұрын

도움이 되었다니 너무 감사합니다.

@yoojaewoong Жыл бұрын

가장 잘 설명된 양자컴퓨터의 개념들이네요 잘보고 공부합니다. 영사유감사합니다~~

@saesunkim Жыл бұрын

댓글 감사합니다!

@user-xo1di7ze1k 5 ай бұрын

정말 감동인 강의예요 조회수가 진짜 일억은 나와야하는데 아쉽네요ㅋㅋ 컴공전공자인데 늙어서도 계속 새로운 공부하려니 벅차요

@saesunkim 4 ай бұрын

대단하세요! 배움에는 끝이 없는 것 같아요~

@changyongkang7651 3 жыл бұрын

어려운 내용을 쉽게 설명해 주셔 감사합니다^^

@saesunkim 3 жыл бұрын

감사합니다.

@c1choi404 2 жыл бұрын

와.. 너무 이해가 안 돼서 여기저기 찾아보다가 이 영상 봤는데 바로 이해됐어요.. 감사합니다! 😀

@saesunkim 2 жыл бұрын

제가 도움을 줄수 있어서 너무 기쁩니다! 댓글 감사합니다.

@user-he3vy9ne8o 3 ай бұрын

좋은 강의 감사합니다. 혹시 게이트의 비용계산 공식이 어떻게 유도되었는지는 어떻게 알수 있나요?

@user-hu1kg4ml9d Жыл бұрын

영상 보고 그루버 알고리즘 바로 이해했습니다. 감사합니다!

@saesunkim Жыл бұрын

감사합니다!

@ha_rheem 3 жыл бұрын

좋은 강의 감사합니다 !! 도움 많이 되었습니다. 정말 명료하게 잘 설명해주시네요 저도 언젠간 홍보대사가 되면 좋겠네요

@saesunkim 3 жыл бұрын

네 같이 홍보대사하는날을 기대할게요!

@user-tn8du6rq1q Жыл бұрын

너무 감사해요 ㅠㅠ

@saesunkim 2 жыл бұрын

13:16 CCX 행렬이 8*8 이 되어야 합니다. qiskit.org/documentation/stubs/qiskit.circuit.library.CCXGate.html 21:57 하단 수식에서 확률진폭의 분모가 |N>이 아니라 |N+1>이어야 합니다 K JW과 김세진님 감사합니다.

@user-cg4rj2cc7q 3 жыл бұрын

좋은 강의 정말 감사합니다. 알고리즘 관련해서 작게나마 공부하고 있었는데, 설명해주신 부분들이 이해하는데 있어서 정말 큰 도움이 되었어요! 정말 감사합니다!

@saesunkim 3 жыл бұрын

댓글감사합니다. 같은 필드에 있기에 나중에 같이 만나볼수 있기를 기대할게요! :D

@karysshin 3 жыл бұрын

훌륭한 강의 감사합니다!

@saesunkim 3 жыл бұрын

감사합니다~

@faint0121 Жыл бұрын

6분 30초쯤에 H |1> 에서 뒤는 왜 마이너스를 하는건가요?

@saesunkim Жыл бұрын

늦게 답해드려서 죄송합니다. 마이너스는 0과 1큐비트 사이의 페이즈 차이를 의미합니다. 그래서 페이즈 차이때문에 나중에 간섭을 할때 증폭할지 감소 할지가 결정됩니다.

@jspark971 2 жыл бұрын

안녕하세요. 혹시 이 자료와 유튜브 채널을 Quantum Computing KR 페이스북 페이지에 공유해도 괜찮을까요? 공부하는데 너무 유익해서 다른 사람들에게도 보여주고 싶어서 댓글 남깁니다!

@saesunkim 2 жыл бұрын

당연하죠, 감사합니다.

@billyoon_hs 2 жыл бұрын

강의 잘 봤습니다. 교수님!! 강의를 봤는데도 왜 기존 비트 방식보다 큐비트 방식으로 한 양자컴퓨터의 계산속도가 빠른지 잘 이해가 안되네요. 다른 동영상을 봐도 잘 이해안되긴 하네요. 어떻게 이해하면 쉬울까요?

@saesunkim 2 жыл бұрын

여기서 왜 양자 시뮬레이션과 양자컴퓨터가 효율적인지 설명했습니다. 한번 보시고 이해가 안가시면 다시 답글 남겨주세요. kzbin.info/www/bejne/oJbchId8gdCSjsU

@sooyoon1646 Жыл бұрын

좋은 강의자료 감사드립니다. 그루버 알고리즘에 대해 질문이 있습니다. 실제로 이 알고리즘으로 자전거 열쇠를 여는 경우와 같이 암호를 찾아내는 경우에 적용하려면 실제 정답인 암호를 모르고 있으니 모든 중첩상태를 모르고 있는 실제 암호와 비교해서 일치하는 경우의 상태만 부호가 바뀌도록 해야하는데 이것을 어떻게 가능하게 하는지요?

@saesunkim Жыл бұрын

늦게 답해드려서 죄송합니다. 좋은 포인트입니다. 쉬운 예로 설명을 한다면. 예를들어서 0에서 20까지 숫자가 있다고 생각해 봅시다. 여기서 우리는 20이라는 숫자를 찾고 싶습니다. 그러면 오라클로 20에 반응하게 만들어 준다면, 가장 큰 숫자를 찾아주는 빠른 알고리듬을 만들어 줄수 있습니다. 그렇기 때문에 제가 드린 자전거 비밀번호 예가 사실 좋은 예가 아니었던것 같습니다. 간단하게 제한된 데이타 내에서 가장 큰수 찾는 알고리듬으로 쓸수도 있다고 생각하면 쉽지 않을까 싶네요!

@user-jw9uz9vt5m 2 жыл бұрын

오라클을 설계할때 이미 답을 알고있어야 설계할수 있는것 같은데 그럼 이게 어떻게 암호를 찾는 알고리즘으로 쓰일수가 있는거죠?

@saesunkim 2 жыл бұрын

정말 좋은 질문입니다. 이런 (문제?) 때문에 대부분 확률진폭 알고리듬으로 사용하는 경우가 많습니다. 제가 만든 어플리케이션 알고리즘으로, 그루버 알고리듬을 통해서 작은 픽셀의 변화를 찾는 알고리듬입니다. github.com/bagmk/Quantum_storm-chasers

@ksjksjgg 2 жыл бұрын

양자컴퓨터 개념을 잘 이해할수 있었습니다. 감사합니다

@saesunkim 2 жыл бұрын

도움이 되었다니 너무 기쁩니다!

@stevenk1591 2 жыл бұрын

교수님 질문이 있는데요. 양자컴퓨터로 분자 시뮬레이션을 하려면 저런 논리회로를 만들어서 시뮬레이션 프로그램을 완성해야 하는 건가요? 아니면 기존 프로그램을 양자 컴퓨터에 접목시킬 수 있는 건가요?

@saesunkim 2 жыл бұрын

늦게 답장해서 죄송합니다. 이미 알아내셨을지도 모르겠지만, 새로운 양자 코드를 만들어 주어야 합니다. 기존에 있는 코드로 시뮬레이션을 하지 않습니다. 예를들어서 분자의 상태를 알아내고 싶다면, Egen value를 풀어주는 VQE 알고리듬 (pennylane.ai/qml/demos/tutorial_vqe.html)을 접목시켜서 분자를 시뮬레이션 할수 있습니다. 기존의 코드를 도와주는 양자 코딩방법으로는 아마도 머신러닝쪽이지 않을까 싶습니다.

@stevenk1591 2 жыл бұрын

@@saesunkim 교수님, 답장 감사합니다. 큰 도움이 되었습니다^^

@kjw809 2 жыл бұрын

좋은 강의 정말 감사드립니다...ㅠㅠ 양자컴퓨터 기초 배우려는데 이 강의만큼 도움된게 없어요....ㅠㅠ 혹시 제가 착각한 것일 수도 있는데 (잘 몰라 질문드립니다;;) 13:16 에서 CCX 행렬이 8*8이 되어야 하는 것 아닌가요..? Qubit 3개를 텐서곱 한 것만 해도 8*1 행렬이 나오면은.. 행렬 곱이 가능하려면 8*8이 되어야 하는거 아닌지... 잘 모르겠습니다

@saesunkim 2 жыл бұрын

네 맞네요! 제가 빼먹었습니다. 감사합니다. qiskit.org/documentation/stubs/qiskit.circuit.library.CCXGate.html

@user-uq1jb2xb1q Жыл бұрын

선생님! 질문이 있습니다! 오라클을 만드려면 정답을 사전에 미리 알고 있어야 하잖아요? 그러면 자전거 비밀번호를 풀기 위해서 자전거 비밀번호를 알아야 된다는 말이죠?

@saesunkim Жыл бұрын

@user-uq1jb2xb1q Жыл бұрын

와 찾기 알고리듬에서 엄청 좋겠네요!! 감사합니다!

@yoojaewoong Жыл бұрын

30:56 11에 반응 하는 오라클 이라면 이미 답을 알고 있다는 것인데 이 문제를 왜 푸는지 이해가 잘 안되네요... 양자 컴퓨터의 성능을 확인하기 위한 것이라면 이해가 되는데 이런 작업들을 통해 작동 방식이 확률이 99.9999%라고 할때 인류가 풓지 못한 답을 연산한 후 결과를 정답일 확률이 99.999%라고 이야기하는 방식으로 사용하기 위한 것 인지요? 귱금하네요...

@saesunkim Жыл бұрын

@yoojaewoong Жыл бұрын

@@saesunkim 상세한 답변 감사합니다~~ 저는 메타모델 이나 RSM관련 엔지니어링 적용을 검토하는데 가장 큰 걸림돌이 증명된 것이냐 하는 부분이었던 것이 비슷한 상황인것 같아 문의 올렸던 글입니다. 더 좋은영상 올려주시면 열심히 공부하겠습니다.

@user-tn8du6rq1q Жыл бұрын

너무 감사합니다 현재 고2학생입니다. 혹시 사진이나 내용같은 것을 발표하는데 인용해도 됩니까??

@saesunkim Жыл бұрын

너무 늦게 답해서 죄송합니다. 네 가능합니다.

@user-wq1cn2rk8z 2 жыл бұрын

엇 잘 몰라서 그러는데요! 21:57 하단 수식에서 확률진폭의 분모가 |N>이 아니라 |N+1>이어야 하지 않나요? 그래야 전체 확률이 1 될 것 같은데...

@saesunkim 2 жыл бұрын

맞네요! 동영상을 고칠수는 없는데 감사합니다.

@user-wq1cn2rk8z 2 жыл бұрын

@@saesunkim 헉 아닙니다. 영상 정말 정말 유익해요... 책으로만 볼 땐 이해가 안 됐는데 영상 보니까 너무 큰 도움됐습니다!!! 이런 영상 만들어 주셔서 감사합니다ㅠㅠ!!!!!!!

@user-xw1ox6we6b Жыл бұрын

왜 이제서야 이 영상을 봤는지ㅠㅠ.. 좋은 강의 감사합니다! 궁금한 점이 하나 있는데요..! 35:20에서 |00>의 위상을 전환해주는 오라클 앞의 부호 -는 구현 단계에서 어떻게 무시할 수 있는지 궁금합니다..! 즉, |00>의 위상을 전환해주는 오라클은 앞서 설명해주신 것과 같이 I-2|00>

@saesunkim Жыл бұрын

늦게 대답해서 죄송합니다. 개인적인 추측으로는 Global Phase이기 때문에 무시할수 있는 것이 아닐까 싶습니다.

@kimhyu5226 Жыл бұрын

궁금한점이 있습니다. 양자컴퓨터의 '입력'이 가장 궁금한데요, 기존 컴퓨터는 사람이 이해하는 1을 컴퓨터에 입력하면 트랜지스터에 전압이 인가 돼서 전자가 넣어지거나 제거되는 방식으로 1 또는 0이 들어가고 logic문을 이용해 사칙연산을 계산합니다(i.e. 1+2=?는 01과 10이 담긴 데이터를 XOR, AND로직게이트를 이용해 101이라는 값을 도출). 그런데 양자컴퓨터에서는 근본적 계산 방식인 '파장을 줘서(input) 양자가 이동하는 경로를 수학적으로 예측한다(output)'에서 가령 1+2 =?의 정답을 찾는다고 가정할 때 1이라는 입력은 어떻게 파장으로 줘야하고 +수식은 어떻게 상수와 다른 방식으로 줘야하고 그 정답은 어떻게 계산이 되는것인지가 계속 이해가 안됩니다.

@saesunkim Жыл бұрын

위에 답변 했습니다.

@user-hr1sn2hs4w 2 жыл бұрын

좋은 강의 감사합니다. 최근 교수님 밑에서 학부연구생으로 학습하고 있는데, 중요한 부분들을 골라 쉽게 설명해주시니 배웠던 내용을 짧은 시간내에 다시금 되돌아보는데 큰 도움이 되었습니다!

@saesunkim 2 жыл бұрын

도움이 되어서 너무 기쁩니다. 새해 복 많이 받으세요

@user-ib8ul4rt1n 2 жыл бұрын

일반인인데 잘모르겠습니다. 제가 보기에는 양자역학에서 아이디어를 딴 알고리즘을 구현한 컴퓨터라고 보면 될까요? 실제로 물질이 곧 파동이라는 양자역학 기술은 아닌거네요? 마치 당낭권이나 취권같은?

@saesunkim 2 жыл бұрын

잘이해하신것 같습니다. 그 알고리즘이 기존에 우리가 생각하던 알고리즘과는 새로운 방식으로 길을 제시했고, 그 알고리즘을 구현하려면 새로운 기술체계를 만들어야 하는것 이고요. 실제로 물질은 파동+양자얽힘이라는 것을 기반으로 만든 기술입니다

@mystous 3 жыл бұрын

진법을 몰라서 질문 드린건 아니고 대부분 켓과 브라에 이진법이나 프사이를 사용하는데 십진법이 쓰여서 다른 notation이 있는지 궁금해서 질문 드렸습니다. 답변감사드립니다. 이전 질문은 너무 민망해서 삭제하였습니다.

@saesunkim 3 жыл бұрын

충분히 궁금할수 있는 있는 부분인데, 제가 따로 이야기하지 않은거 같아요! 좋은 피드백 감사합니다.

@mystous 3 жыл бұрын

@@saesunkim 아닙니다. 사실 QC에 대해서 대부분의 설명이 너무 마케팅적인 내용이 많았는데 선대수로 설명을 해주시니 이해가 너무 빠르게 잘 되었습니다. 혹시 자료를 PDF 형태로라도 받아 볼 수 있을까요?

@saesunkim 3 жыл бұрын

@@mystous 곧 파일 만들어볼게요, 이메일 남겨주세요~

@mystous 3 жыл бұрын

감사합니다. mystous@지메일 입니다.

@user-ig6zk2ul4m 11 ай бұрын

양자컴퓨터를 이용해서 메이플스토리를 하는게 가능할까요? 기존의 Logic 논리 회로로서 기능할 수 있는지 궁금합니다 (효율 측면의 떠나서요)

@saesunkim 11 ай бұрын

일반 컴퓨터의 모든 작업은 양자컴퓨터로 가능합니다. 그렇기에 원한다면 메이플 스토리를 위한 양자컴퓨터도 만들수는 있겠지요. 하지만 특정한 알고리듬에 의해서 메이플스토리의 효율성이 좋아지는 것이 아니라면, 오히려 더 느려질수 있지 않을까요?

@aerockh 3 жыл бұрын

훌륭하십니다. 제가 열심히 찾고 있는 것은 실제로 해당 게이트들을 어떻게 만드는가 인데요. 혹시 시간나시면 강의 부탁드리겠습니다.

@saesunkim 3 жыл бұрын

실제로라는 의미는 실험적으로 어떻게 만들어 지는가 인가요? 많은 연구들이 진행되고 있지만, 빛 큐빗으로 하는 예를 든다면, 원자나 물질을 이용해서 Nonlinear interaction을 통하여 두개의 빛이 들어올때 위상을 바꾼다던지 하여서 조정을 하고 있고 이온같은 경우에는 빛의 펄스나 전기장으로, 트렌스몬 큐빗은 마이크로웨이브로 게이트를 만드는 것으로 알고 있습니다. 나중에 시간나면 한번 다뤄보겠습니다!

@aerockh 3 жыл бұрын

@@saesunkim 네 일단 하나의 이온을 트랩한 상태에서 어떤 interaction으로 superposition 상태를 만들며 추가로 2개의 경우 entanglement를 위해서 어떤 interaction(operation)을 하는가 문제입니다. 결국 전자회로는 OR, NAND 등의 기초 회로가 스위치와 다이오드를 이용하는 기본적인 operation,manipulation,tool이 있다면 이온 입자의 경우 H,Z,X 등의 연산자가 어떻게 전자기파를 이용해 구현되며 광자의 경우 편광판, 그레이팅 등의 도구로 어떻게 중첩, 얽힘을 구현할 수 있는지 실질적인 방법이 궁금합니다. 나름 취미삼아 공부하는 측면에서 꾸준히 보고 있는데요. 쉽지 않네요. 더 말씀드리자면 성능과 비용을 무시한다면 저도 4비트 CPU를 만들 수 있는데요. 2개 큐빗짜리 양자컴퓨터는 어떻게 만들어야할지 모르겠어요. 뭐든 자원이 있다고 하면요.

@saesunkim 3 жыл бұрын

@@aerockh 제가 이온쪽을 공부하지 않아, 제가 설명하기보단 레퍼렌스를 남겨드릴게요., journals.aps.org/prl/abstract/10.1103/PhysRevLett.74.4091, 만약 엑세스가 없다면, en.wikipedia.org/wiki/Cirac%E2%80%93Zoller_controlled-NOT_gate 에도 나와있습니다. 그리고 크리스 먼로교수님의 얽힘구현하는 강의를 첨부할게요. kzbin.info/www/bejne/b5Kyfaqgir9_o5I .

@aerockh 3 жыл бұрын

@@saesunkim 오 감사합니다. 제 검색 실력이 부족한 것이었군요!!!

@saesunkim 3 жыл бұрын

@@aerockh 이해가시지 않으면 말씀주세요!

@kimhyu5226 Жыл бұрын

질문을 요약하면 파장을 발생시켰을 때 양자의 위치를 측정하는것으로 어떻게 그것이 '1'인지 'ㄱ'인지 1+2의 결과인지 이해할 수 있는 것일까요? 다이아몬드/극저온 초전도방식 등 어떤방식이든 상관없어요. 아무거나 한가지 방법만 이해하면 다른 방법도 대략 이해할 수 있을것같습니다!

@saesunkim Жыл бұрын

직접적인 예를 들어서 일반적으로 1 혹은 0을 기존 컴퓨터에서 받아드릴때에는 빛이 있다 없다로 알수 있습니다. 양자컴퓨터에서는 예를들어 이중슬릿 실험으로 본다면, 하나의 광자는 슬릿 A에 있거나 슬릿 B에 있거나 둘중 하나에 있습니다. 반대로 IBM의 양자 컴퓨터나 다이아몬드 같은 경우에는 원자나 (혹은 전체적인 시스템)의 상태를 Ground state |g>에서 Excited state |e>로 전자기파를 이용해서 이동시킬수 있습니다. 예를들어 1초동안 빛을 쏘면 원자가 |g>에서 |e>로 바뀌게 됩니다. 이러한 상태는 일반적인 컴퓨터가 신호를 처리하는 0 이나 1로 사용할수 있겠죠. 그런데 만약 빛을 0.5초만 쏜다면, 원자는 |g>과 |e>가 동시에 존재하는 상태가 됩니다. 이것은 양자적인 상태로 Qubit으로 사용할수 있겠지요. 위치를 측정하는 것은 이제 이러한 중첩되있는 상태가 어떤 분포로 되어있는지 보면 되는 것입니다 (100번을 측정해서 몇번 |g>이 나왔는지 확인하면 되는 것이죠)

@kimhyu5226 Жыл бұрын

@@saesunkim 답변해주셔서 감사합니다! 그라운드상태도 아니고 여기상태도 아닌 qubit인 상태를 확인한다까지는 이해했습니다. 하지만 사실 이해가 아직 덜된부분이 좀 있습니다. 빛을 쏜다는것에서 파라미터는 시간을 말씀하셨는데 제가 헷갈리는것은 슬릿실험을 통해 알 수 있는건 광원 하나로 하나의 벽에 맞고 그려지는 파장 하나잖아요? 그러니까.. 빛(파장)입력으로 파장출력이 나왔다. 라고 생각이 계속 들다보니까 '광케이블 선 끝에 빛 주면 다른 끝에 빛이 들어오더라'랑 뭐가 다른지 조차 헷갈립니다. 제가 살아온 아날로그의 세계를 보고 느낀것은 입력이 하나면 출력도 하나여가지고.. 죄송해요 ㅎㅎ.. 어렵네요 양자역학 동영상강의부터 듣고와야겠어요!!ㅋㅋㅋ 듣고나서 양자컴퓨터가 빛 몇개 입력한다고 해서 어떻게 기존 슈퍼컴퓨터가 몇년동안 풀만한 연산들을 몇초만에 해낼 수 있을까. 한번 더 질문하겠습니다 ㅎ

@user-hc1he5hs5e 3 жыл бұрын

좋은 강의 잘 들었습니다! 그로버 알고리즘 부분에서 의문이 들었던 부분이, 오라클 게이트와 디퓨저 게이트 설계를 할 때 게이트가 정답 신호에 대한 정보를 이미 담고 있는 것으로 보이는데, 저 알고리즘이 암호를 풀기 위한 알고리즘인데 암호를 알고 있어야 암호를 풀수 있다는 것으로 이해가 됩니다.. 혹시 제가 이해한 것이 맞나요?

@saesunkim 3 жыл бұрын

네 오라클 같은 경우에는 그 결과를 알고 있어야 하는 게이트 입니다. 하지만 디퓨져는 답에대한 정보가 필요 없습니다.

@user-pn2io9hk8q 2 жыл бұрын

제가 질문하고 싶은 내용이네요. 제가 알고 싶은것은 중첩에서 어떻게 내가 원하는 답을 찾아내야는것인데 그런 예제 없나요