Claude가 양자회로를 다시 설계해 게이트와 큐비트 비용을 줄인 방법

배경과 문제

양자 컴퓨터는 큐비트에 정보를 저장하며, 중첩과 같은 양자 현상을 이용해 화학, 재료과학, 정수론의 특정 문제를 고전 컴퓨터보다 빠르게 풀 수 있다. 그러나 현재까지 만들어진 양자 컴퓨터는 큐비트 수가 수백에서 수천 개에 불과하고, 열·진동·우주선 같은 환경 잡음에 매우 민감하다. 작은 교란 하나가 큐비트 상태를 흔들면 오류가 쌓여 결국 잘못된 답을 내놓는다. 따라서 큐비트와 계산 시간이 모두 부족한 상황에서, 연구자들은 더 적은 큐비트와 더 짧은 시간에 계산을 끝내도록 양자 알고리즘을 다시 설계해 왔다.

양자 회로 설계에는 일반 프로그래밍에는 없는 두 가지 제약이 있다. 첫째, 양자 회로는 입력이 중첩 상태일 수 있으므로 중간 값을 검사해 일반적인 if-then 분기를 선택할 수 없다. 대신 모든 분기의 연산을 고정된 게이트 순서에 포함해야 하며, 특정 입력에만 적용되는 분기도 회로 비용에 포함된다. 둘째, 양자 회로는 정보를 버릴 수 없다. 중간 계산 결과를 지우려면 그 계산을 역으로 실행하는 '언컴퓨팅'이 필요하며, 이는 추가 게이트를 요구한다. 이 두 제약 때문에 양자 회로는 고전 회로보다 실행 시간과 큐비트 측면에서 훨씬 비싸진다.

기존 접근의 한계

기존의 자동 회로 최적화 도구는 주로 미리 정의된 동치 변환 규칙만 적용하기 때문에, 고정된 설계의 변형만 탐색할 수 있다. 일반적인 양자 회로의 정확성을 직접 검증하려면 지수적으로 비싼 고전 시뮬레이션이나 완전한 대규모 양자 프로세서가 필요하기 때문이다. 따라서 기존 도구는 알고리즘 구조 자체를 바꾸는 근본적인 재설계를 찾기 어렵다.

또한 고전 알고리즘을 양자 회로로 단순 이식하면 가역성 제약 때문에 효율성이 크게 떨어진다. 예를 들어, 고전 컴퓨터에서 효율적인 divsteps 알고리즘은 각 반복에서 선택한 연산 기록(분기 정보)을 버릴 수 있지만, 양자 회로에서는 역방향 실행을 위해 그 기록을 보존해야 한다. 단순한 가역 구현은 분기 정보의 긴 이력을 저장해야 하므로 막대한 수의 추가 큐비트가 필요하다. 마찬가지로 리드-솔로몬 디코더의 기존 확장 유클리드 알고리즘 기반 회로는 입력에 따라 단계 수와 순서가 달라지는 제어 흐름을 하나의 고정된 게이트 순서로 펼쳐야 하므로, 불필요한 연산을 모든 라운드에서 실행해야 해서 비용이 커진다.

연구방법을 단계별로

연구진은 대규모 언어 모델(LLM)이 회로 설계를 제안하고, 독립적인 평가기가 각 후보를 검증하고 점수를 매기는 진화적 프레임워크를 도입했다. 각 탐색은 손으로 작성한 작업 명세와 빈 프로그램에서 시작한다. 명세는 필요한 회로 동작만 기술하고 구현 지침은 제공하지 않는다. LLM은 후보 회로를 Python 코드로 작성하고, 평가기는 그 코드를 실행해 정확성과 자원 비용을 확인한 뒤 피드백을 돌려준다. LLM은 이 피드백을 바탕으로 다음 후보를 개선한다.

탐색은 단일 후보의 반복적 개선이 지역 최적해에 갇히는 것을 막기 위해, 먼저 서로 다른 알고리즘 계열을 여러 개 제안하는 아이디에이션 단계를 거친다. 각 계열은 병렬로 독립적으로 최적화되며, 좋은 후보는 주기적으로 계열 사이에 공유되어 한 접근에서 얻은 개선을 다른 접근에도 활용한다. 평가기는 각 후보 회로를 계산 기저 상태에서 시뮬레이션하여 정확성을 검사하고, 토폴리 게이트 수(T)와 최대 큐비트 수(Q)를 측정한 뒤 그 곱인 TQ 비용으로 점수를 매긴다. TQ 비용은 시간과 공간 자원을 묶은 평가 점수이며 실제 장비의 경과 시간을 측정한 값은 아니다.

탐색 과정에서 발견된 회로들은 세 가지 공통 설계 원리를 반복적으로 보여준다. 첫째, 조건부 산술을 조건부 라우팅으로 대체한다. 예를 들어 제어 비트에 따라 두 개의 곱셈-덧셈 연산 중 하나를 선택하는 대신, 값비싼 산술 블록 하나를 공유하고 제어된 스왑으로 적절한 값을 그 블록으로 라우팅한다. 둘째, 중간 계산의 전체 이력을 저장하지 않고 현재 상태에서 분기 결정을 복원한다. 셋째, 응용이 허용하는 작은 실패 확률을 이용해 드문 입력만을 위한 회로 자원을 제거한다.

결과와 숫자의 의미

8개 컴파일 과제 중 7개에서 발견된 회로는 각 비교 기준보다 토폴리 게이트 수와 큐비트 수를 동시에 줄였다. 다만 Hermitian DQI의 기준은 기존 최적 회로가 아니라 단순한 가역 구현이었다. 예를 들어 리드-솔로몬 DQI 디코더는 기존 (5.1×10^6, 1,938)에서 (4.4×10^5, 1,837)로 개선되어 TQ 비용이 12배 감소했다. HHL 회전각 회로는 (1.6×10^4, 300)에서 (1,348, 115)로 개선되어 TQ 비용이 32배 감소했다. 쿨롱 퍼텐셜 회로는 9.9배, 고정소수점 가우시안 회로는 39배, Fe2S2 alias–Select 회로는 4.1배, 비아벨 격자 게이지 시뮬레이션 회로는 7.7배의 TQ 비용 감소를 보였다.

8번째 과제인 소수체 모듈러 역원에서는 단일 기준선이 없어 TQ 비용 개선 배수를 보고하지 않았다. 대신 이 과제에서는 divsteps를 가역적으로 구현하는 새로운 아키텍처를 발견하여 토폴리-큐비트 절충선을 확장했다. 완전한 벤치마크 회로는 4.0×10^6 토폴리와 935 큐비트를 사용한다. 이 회로는 분기 정보를 저장하는 대신 현재 상태에서 복원하는 디코딩 방식을 사용하며, 저장과 디코딩 사이의 임계값을 조절해 다양한 토폴리-큐비트 조합을 제공한다. 예를 들어 한 구성은 이전 최소 설계보다 큐비트를 12% 더 쓰지만 게이트 수를 17배 줄인다.

리드-솔로몬 디코더의 개선은 세 가지 수준의 재설계에서 비롯되었다. 첫째, 확장 유클리드 알고리즘을 산술적으로 더 저렴한 벌레캠프-매시(BM) 알고리즘으로 교체했다. 둘째, BM의 중간 값들을 저장하는 대신 현재 상태에서 재구성하여 이력 스택을 거의 없앴다. 셋째, 4.03억 개의 표본 디코딩을 시뮬레이션하여 예외 값이 실제로 얼마나 자주 발생하는지 측정하고, 최악의 경우를 위한 큰 저장 공간 대신 작은 고정 공간만 할당했다. 그 결과 약 1만 회 중 1회 실패를 허용하는 대신, 예외 값을 저장하는 공간을 665 큐비트에서 19 큐비트로 줄였다. 이는 디코더 전체의 큐비트 수가 아니다.

구체적인 예시

모듈러 역원은 숫자가 일정한 크기에서 되돌아오는 산술의 나눗셈에 해당한다. divsteps는 정수 쌍을 단순화하는 여러 단계로 이를 구한다. 어려움은 각 단계에서 어느 연산을 했는지 나중에 되짚을 수 있어야 한다는 점이다. 모든 기록을 보관하면 큐비트를 많이 쓰고, 기록 없이 복원하려면 추가 계산이 든다. 따라서 더 작거나 더 빠른 단일 해답보다 두 비용 사이의 새로운 선택지를 찾는 것이 이 과제의 성과다.

Claude는 분기 정보를 아예 저장하지 않을 수 있다는 아이디어를 떠올렸다. 각 반복 후의 숫자 쌍을 주의 깊게 검사하면 분기 정보를 직접 추론(디코딩)할 수 있다는 것이다. 즉, 숫자 자체가 기록을 저장하는 셈이다. 초기의 단순한 후보 규칙은 작은 테스트 케이스에서는 작동했지만 256비트 숫자의 전체 문제 크기에서는 실패했다. Claude는 추측과 테스트 대신 divsteps가 왜 그렇게 동작하는지 수학적으로 이해하려 했고, 반복 과정에 대한 여러 결과와 새로운 대수적 항등식을 증명했다. 이 항등식들로부터 숫자 쌍에서 분기 정보를 정확히 복원하는 디코딩 규칙의 정확한 공식을 도출했고, 대규모 수치 시뮬레이션과 Lean 형식 검증으로 확인했다.

리드-솔로몬 디코더의 경우, BM 알고리즘은 각 라운드에서 임시 값들을 계산하지만 이 정보를 단순히 삭제할 수 없다. 나중에 언컴퓨팅하려면 그 정보를 복구할 수 있어야 한다. Claude는 divsteps에서와 같은 접근법을 사용해 대부분의 정보를 회로의 현재 상태에서 재구성하여 저장하지 않았다. 그러나 일부 예외 값은 재구성할 수 없어 저장해야 했다. 최악의 경우 35개 라운드에서 예외 값이 발생할 수 있어 665 큐비트가 필요하지만, 4.03억 개의 표본 디코딩 시뮬레이션 결과 거의 모든 실행에서 저장할 값이 최대 하나뿐이었다. 그래서 회로는 저장 공간을 하나의 값(19 큐비트)만 할당하고, 약 1만 회 중 1회는 더 많은 공간이 필요해 실패하도록 허용했다. 이 실패율은 작업이 허용하는 오류율 내에 있다.

한계와 오해하기 쉬운 점

이 연구의 개선은 양자 하드웨어에서 실측한 실행 시간 개선이 아니라, 고전적으로 검사 가능한 특정 회로의 설계·게이트·큐비트 자원 비교다. TQ 비용(토폴리 수 × 최대 큐비트 수)은 비용 대리 지표이며, 하드웨어 라우팅, 오류 정정, 회로 깊이 등의 전체 현실 비용을 포함하지 않는다. 또한 8개 과제 중 7개에서 게이트와 큐비트를 동시에 줄였고, 8번째 모듈러 역원에서는 자원 절충선을 개선했다고 명시되어 있다. 8개 모두 두 지표를 동시에 개선했다고 일반화해서는 안 된다.

점 덧셈 사례의 53시간 탐색은 초기 지시와 가끔 탐색을 넓히라는 사람의 개입이 있던 단일 탐색 사례다. 이는 내부 Claude Mythos 5 모델의 결과이며, 공개 모델에서 같은 성능을 재현했다고 쓰지 않았다. 또한 12% 더 많은 큐비트 대신 17배 적은 게이트라는 절충을 보존한다. 리드-솔로몬 디코더의 약 12배 개선은 해당 연산의 게이트 및 TQ 비용 비교이며, 전체 DQI나 모든 양자 알고리즘이 12배 빨라진 실측 결과가 아니다.

희귀 입력 실패를 허용한 설계와 모든 입력에 대한 정확성 증명은 구분해야 한다. divsteps 수학 규칙의 Lean 검증은 전체 하드웨어나 모든 회로의 완전한 형식 검증을 뜻하지 않는다. FeMoco의 약 15만 배 개선은 2017~2025년 여러 연구진의 기존 역사이며 이번 Claude의 개선이 아니다. 이번 연구의 Fe2S2와 FeMoco를 혼동해서는 안 된다. 실용 양자컴퓨터가 즉시 완성됐거나 현재 암호를 실제 해독했다는 결과가 아니다.

실제로 어떻게 활용할까

이 프레임워크는 설계를 코드로 표현하고, 충분히 저렴하게 정확성과 비용을 평가할 수 있는 다른 문제로 확장할 가능성을 제시한다. 모든 문제에서 효과가 검증된 것은 아니다. 연구진은 오류 정정 코드, 빠른 디코더, 하드웨어 제어 등 양자 컴퓨터의 다른 구성 요소들도 이러한 특성을 공유한다고 지적한다. 현재는 복잡성을 관리하기 위해 각 구성 요소를 개별적으로 설계하지만, AI가 알고리즘부터 하드웨어까지 모든 계층을 공동으로 최적화할 수 있다면 특정 문제에 맞춘 전체 오류 정정 양자 컴퓨터를 설계할 수 있을 것이다.

이러한 공동 설계는 하드웨어 제작자에게 특정 응용 분야에 어떤 능력이 가장 중요한지 알려줄 수 있다. 예를 들어 촉매 설계나 신소재 이해 같은 문제를 첫 번째 내결함성 기계의 도달 범위 안에 넣을 수 있다. 다만 이 연구의 결과는 회로 설계 단계에 국한되며, 실제 양자 하드웨어에서의 성능은 오류 정정, 큐비트 연결성, 게이트 충실도 등 추가 요소에 크게 의존한다는 점을 유의해야 한다.