Methods for Reducing Ancilla-Overhead in Block Encodings

양자 컴퓨터는 고전적 기계가 수천 년이 걸릴 문제를 해결할 가능성을 약속하지만, 매우 취약하기로 악명이 높습니다. 복잡한 계산을 수행하기 위해 이 기계들은 블록 인코딩(block encoding)이라 불리는 기술에 의존하는데, 이는 화학 반응 시뮬레이션이나 미분 방정식 풀이와 같은 실제 응용 분야에서 필수적인, 완벽하게 가역적이지 않은 수학적 연산을 표현할 수 있게 해줍니다. 블록 인코딩을 앤실라(ancillae)라고 알려진 추가적인 보조 비트를 사용하여 더 큰 가역적 양자 프로세스 안에 복잡하고 비가역적인 계산을 숨기는 방법이라고 생각하십시오. 이 보조 비트들은 임시 작업 공간 역할을 하여, 양자 컴퓨터가 양자 역학의 근본 법칙을 깨뜨리지 않고 데이터를 조작할 수 있게 해줍니다. 그러나 알고리즘이 더 복잡해짐에 따라 점점 더 많은 보조 비트를 필요로 하게 됩니다. 현재 양자 하드웨어는 보유할 수 있는 큐비트의 수가 제한되어 있으므로, 이러한 추가 공간에 대한 수요는 심각한 병목 현상을 일으키며, 종종 연구자들이 계산을 실행할 것인지 아니면 메모리가 완전히 바닥날 것인지를 선택해야 하는 상황을 강요합니다.

캘리포니아 대학교 버클리 캠퍼스와 헝가리 알프레드 레니 수학 연구소의 연구팀은 블록 인딩에 필요한 보조 비트의 수를 획기적으로 줄이는 두 가지 새로운 방법을 개발했습니다. 그들의 연구는 두 가지 다른 관점에서 접근하여, 첫 번째 경우에는 공간과 시간 사이의 절충안을, 두 번째 경우에는 공간과 정확도 사이의 절충안을 제공합니다. 첫 번째 방법은 계산이 끝난 후 작업 공간을 "정리"하는 방법을 도입합니다. 많은 양자 알고리즘에서 블록 인코딩이 한 번 사용되면, 보조 비트들은 재사용할 수 없는 지저도 있고 얽힌 상태로 남게 됩니다. 연구진은 거의 모든 보조 비트를 깨끗한 제로 상태로 일관되게 재설정하여, 알고리즘의 후속 부분에서 다시 사용할 수 있도록 자유롭게 만드는 프로토콜을 고안했습니다. 이 과정은 즉각적으로 이루어지지 않으며, 추가적인 계산 단계를 필요로 합니다. 즉, 귀중한 자원인 추가 공간을 얻기 위해 추가적인 시간을 사용하는 것입니다. 그 결과, 계산이 완벽하게 정밀하지 않더라도 실용적으로 충분히 가깝다면, 원래 얼마나 많은 비트가 필요했는지와 상관없이 단 하나의 보조 비트만을 사용하여 동일한 복잡한 연산을 수행할 수 있는 시스템이 만들어집니다.

연구의 두 번째 부분은 물리 계의 진화를 시뮬레이션하는 데 흔히 요구되는 작업인, 여러 블록 인코딩을 함께 곱하는 특정한 과제를 다룹니다. 전통적으로 다수의 블록 인코딩을 곱하려면 연산 횟수에 따라 로그 함수적으로 증가하는 수의 보조 비트가 필요했는데, 이는 하드웨어의 능력을 빠르게 초과하는 요구치입니다. 연구진은 정확하고 완벽한 곱셈을 위해서는 이 로그 함수적 요구가 우회할 수 없는 엄격한 한계임을 증명했습니다. 그러나 만약 아주 미세하고 통제된 수준의 오차를 수용할 용의가 있다면, 이 한계를 깰 수 있다는 것을 보여주었습니다. 그들은 연산들이 서로 사슬처럼 연결되어 있을 때도 일정하고 작은 수의 보조 비트만으로 이러한 곱셈을 수행하는 새로운 가젯(gadget)을 도입했습니다. 이 압축 과정에서 발생하는 오차는 극도로 작으며, 보조 비트의 수가 약간만 증가해도 급격히 감소합니다. 이 접근 방식은 개별 단계가 이미 '아무것도 하지 않는 상태'에 매우 가깝게 설정된 시뮬레이션, 즉 변화를 추적하기 위해 작은 시간 간격을 사용하는 물리 시뮬레이션의 일반적인 시나리오에서 특히 효과적입니다.

이러한 압축된 계산들이 여전히 유용함을 보장하기 위해, 연구진은 또한 '무차별 진폭 증폭(oblivious amplitude amplification)'이라 불리는 기술을 사용하는 방법을 시연했습니다. 이 방법은 계산이 성공할 확률을 높여주는 필터처럼 작동하여, 압축된 근사 방식을 사용할 때조차 실패가 잦을 수 있는 과정을 거의 매번 성공하는 과정으로 바꾸어 놓습니다. 이러한 발견은 정밀도와 자원 사용량 사이의 절충안을 신중하게 관리함으로써 양자 알고리즘을 훨씬 더 효율적으로 만들 수 있음을 시사합니다. 이것은 단순히 이론적인 연습이 아닙니다. 이 방법들은 에너지가 계를 통해 어떻게 이동하는지를 설명하는 해밀토니안 역학(Hamiltonian dynamics)을 시뮬레이션하고, 유체 역학부터 화학 반응에 이르기까지 모든 것을 모델링하는 데 필수적인 양자 미분 방정식을 푸는 데 직접적으로 적용될 수 있습니다. 앤실라의 오버헤드를 줄임으로써, 이러한 기술들은 현재 및 가까운 미래의 양자 컴퓨터가 가용 메모리의 부족으로 인해 이전에는 도달할 수 없었던 문제들을 다룰 수 있게 해줄 것입니다.