Subscribe
Share
Share
Embed
"양자컴퓨터는 모든 답을 한 번에 시도해서 빠르다"는 흔한 설명이 왜 틀렸는지, 진짜 힘인 진폭과 간섭이 무엇인지 풀어 봅니다. 소인수분해처럼 크게 빨라지는 문제와 검색·최적화처럼 조금만 빨라지거나 거의 그대로인 문제를 나누고, Google Willow로 하드웨어 현황도 짧게 짚습니다.
"양자컴퓨터는 모든 답을 한 번에 시도해서 빠르다"는 흔한 설명이 왜 틀렸는지, 진짜 힘인 진폭과 간섭이 무엇인지 풀어 봅니다. 소인수분해처럼 크게 빨라지는 문제와 검색·최적화처럼 조금만 빨라지거나 거의 그대로인 문제를 나누고, Google Willow로 하드웨어 현황도 짧게 짚습니다.
참고 자료
이 에피소드의 음성은 TTS로 합성되었습니다.
kalee 가 공부하고자 하는 내용들을 두서없이 업로드하는 팟캐스트
진행자: 안녕하세요. 오늘은 양자컴퓨터 얘기를 해 볼게요. 그런데 뉴스에서 자주 듣는 설명을 하나 의심해 보는 회차예요.
진행자: 양자컴퓨터는 모든 답을 동시에 시도하니까 엄청 빠르다. 이런 설명 많이 들어 보셨죠?
전문가: 네, 아마 가장 흔한 설명일 거예요. 병렬 우주에서 모든 답을 한꺼번에 시도한다는 식으로요.
전문가: 그런데 양자 계산 이론을 연구하는 Scott Aaronson은 이 설명을 이 분야 대중 설명의 근본적인 실수라고 불러요.
진행자: 오늘 질문은 두 가지예요. 그 설명은 왜 틀렸나. 그리고 양자컴퓨터가 정말 빨라지는 문제와 그렇지 않은 문제는 뭐가 다른가.
전문가: 오늘 얘기는 Aaronson이 Quanta Magazine에 쓴 칼럼과 그의 블로그, IBM의 양자 알고리즘 교재, 그리고 Google의 Willow 발표를 바탕으로 할게요.
진행자: 먼저 용어부터요. 큐비트, 중첩. 이건 어떻게 이해하면 돼요?
전문가: 큐비트는 양자 정보의 기본 단위예요. 보통 비트는 0 아니면 1인데, 큐비트는 0과 1이 겹쳐 있는 상태가 될 수 있어요. 이걸 중첩이라고 해요.
진행자: 겹쳐 있다는 게 결국 둘 다라는 거고, 그래서 동시에 계산한다는 거 아니에요?
전문가: 바로 거기서 오해가 시작돼요. Aaronson은 중첩을 복소수 계수를 붙인 선형 결합으로 이해하라고 말해요.
전문가: 쉽게 말하면, 가능한 결과마다 진폭이라는 숫자가 하나씩 붙어 있어요. 그리고 어떤 결과가 나올 확률은 그 진폭 크기의 제곱이에요.
진행자: 진폭이 확률이랑 비슷한 거네요.
전문가: 비슷한데 결정적으로 다른 점이 있어요. 확률은 늘 0 이상이지만, 진폭은 음수나 복소수도 될 수 있어요. 그래서 서로 더하면 지워질 수 있어요.
전문가: 진폭끼리 지워지거나 커지는 현상을 간섭이라고 해요. 오늘 얘기의 핵심 단어예요.
진행자: 그럼 모든 답을 겹쳐 놓는 것 자체는 가능해요?
전문가: 가능해요. 모든 답이 같은 진폭으로 겹친 상태를 만들 수 있어요. 문제는 그다음이에요. 측정하면 그중 무작위로 답 하나만 나와요.
진행자: 아, 결과를 보려면 측정해야 하는데, 측정하면 하나만 나오는군요.
전문가: 네. 모든 답을 겹쳐 놓고 그냥 측정하면, 그건 답을 무작위로 하나 찍는 것과 다르지 않아요. 그러니까 모든 답을 시도한다는 그림만으로는 아무것도 얻지 못해요.
진행자: 그럼 양자컴퓨터는 대체 뭘로 빨라지는 거예요?
전문가: 간섭이에요. 양자 알고리즘은 오답들의 진폭은 서로 지워지고, 정답의 진폭은 서로 강해지도록 계산 순서를 설계해요.
전문가: 비유하자면 소음 제거 헤드폰 같아요. 반대 모양의 파동을 더해서 소음을 지우잖아요. 오답들이 서로 지워지게 만들고, 마지막에 측정하면 정답이 나올 확률이 높아지는 거죠.
진행자: 그러니까 모든 답을 다 해 보는 게 아니라, 오답이 사라지게 판을 짜는 거네요.
전문가: 맞아요. Aaronson은 2014년 블로그에서도 같은 얘기를 해요. 양자컴퓨터는 모든 해를 병렬로 시도해서 어려운 문제를 순식간에 풀지 않는다고요.
진행자: 그런데 그런 판을 짜는 게 아무 문제에서나 되는 건 아니겠죠?
전문가: 네, 그게 두 번째 질문으로 이어져요. 오답을 지우는 설계가 가능하려면 문제에 특별한 수학적 구조가 있어야 해요.
진행자: 그럼 빨라지는 쪽부터 볼까요. 대표 예가 뭐예요?
전문가: 가장 유명한 건 쇼어 알고리즘이에요. 정수를 소인수분해하는 양자 알고리즘인데, 지금 널리 쓰는 암호를 위협하는 것으로 알려져 있어요.
전문가: 중요한 건 이게 아무 문제에나 통하는 요령이 아니라는 점이에요. 알려진 양자 속도 향상은 문제에 숨은 특별한 수학적 구조를 이용할 때 나와요.
진행자: 다른 유망한 분야도 있어요?
전문가: 화학 시뮬레이션이 자주 꼽혀요. 다만 Aaronson은 이것도 아직 손에 닿지 않은 일이라고 봐요.
진행자: 그런데 빠르다는 게 몇 배 빠르다는 얘기예요?
전문가: 그것도 흔한 오해예요. 속도 향상은 몇 배냐가 아니라, 입력이 커질 때 걸리는 시간이 얼마나 빨리 늘어나느냐의 문제예요.
전문가: 그래서 작은 입력에서는 양자 쪽이 오히려 느릴 수 있고, 입력이 커져야 이겨요.
진행자: 개발자한테 익숙한 시간 복잡도 얘기네요.
전문가: 네, 그 감각이에요. 함정도 하나 있어요. 더 빠른 고전 알고리즘이 없다는 걸 증명하기가 아주 어려워요. 양자 속도 향상으로 여겨졌다가 고전 알고리즘이 따라잡은 사례도 있고요.
진행자: 반대로 양자컴퓨터로도 크게 안 빨라질 문제는요?
전문가: Aaronson은 외판원 문제를 예로 들어요. 이런 문제를 모든 답을 시도하는 식으로 빨리 푸는 건 거의 모든 전문가가 불가능하다고 본대요. 많은 중요한 문제는 속도 향상이 작거나 없을 거라고 하고요.
전문가: 외판원 문제 같은 어려운 문제들을 묶어서 NP-완전 문제라고 불러요. 이걸 다항 시간에 푸는 양자 알고리즘은 알려져 있지 않아요.
진행자: 그래도 조금은 빨라지는 경우가 있지 않아요?
전문가: 있어요. IBM 교재에 따르면 그로버 알고리즘은 구조가 없는 검색에서 필요한 연산 수를 고전 방식의 제곱근 정도로 줄여요. 그리고 이 문제 설정에서는 그보다 더 줄일 수는 없다는 게 증명돼 있어요.
전문가: 같은 교재는 이 정도 이점은 당분간 실용적인 차이로 이어지기 어렵다고 봐요. 고전 컴퓨터 하드웨어가 훨씬 앞서 있으니까요.
진행자: 결국 모든 답을 동시에 시도한다는 그림이 맞았다면, 이런 한계도 없었겠네요.
전문가: 맞아요. 그래서 그 그림이 문제예요. 양자컴퓨터가 모든 걸 바꿀 거라는 기대를 만들거든요. Aaronson도 양자컴퓨터가 모든 걸 혁신하지는 않을 거라고 써요.
진행자: 마지막으로 하드웨어 얘기도 잠깐 해 볼까요. 지금 어디까지 왔어요?
전문가: 큐비트는 주변 환경 때문에 양자 상태를 쉽게 잃어요. 이걸 결어긋남이라고 하고, 알려진 해법이 양자 오류 정정이에요. Aaronson이 칼럼을 쓴 2021년에는 오류 정정이 안 된 50~60개 큐비트 수준이었어요.
전문가: 2024년 12월 Google은 105큐비트 칩 Willow를 발표했어요. 오류 정정에 쓰는 큐비트 격자를 키울 때마다 오류율이 절반으로 줄었다고 보고했고요.
전문가: 같은 발표에서 어떤 벤치마크를 5분 안에 끝냈다고도 했는데, Google 스스로 그 벤치마크는 아직 상용 응용이 없다고 밝혀요. 회사 발표라는 점도 감안해서 들어 주세요.
진행자: 정리해 볼게요. 첫째, 양자컴퓨터는 모든 답을 동시에 시도하지 않아요. 그렇게 하면 측정할 때 답 하나가 무작위로 나올 뿐이에요.
진행자: 둘째, 진짜 힘은 간섭이에요. 오답의 진폭은 지우고 정답의 진폭은 키우는 판을 짜는 거죠.
진행자: 셋째, 그 판은 문제에 구조가 있을 때만 짤 수 있어요. 소인수분해처럼 크게 빨라지는 문제도 있지만, 많은 문제는 조금 빨라지거나 거의 그대로예요.
전문가: 한마디만 덧붙이면, 양자컴퓨터 뉴스를 볼 때 어떤 문제를, 입력이 커질 때 얼마나 빨리 푸는지를 물어보시면 과장을 꽤 걸러낼 수 있어요.
진행자: 오늘 참고한 자료는 설명란에 정리해 두었어요. 들어 주셔서 감사합니다.