Single-shot online sequence classification with unbounded quantum memory advantage

한 여행자가 거대하고 변화무쌍한 풍경을 항해하고 있다고 상상해 보십시오. 매 걸음마다 그는 소리, 시각, 혹은 신호와 같은 새로운 정보를 받으며, 그 사건의 순서가 무엇을 의미하는지 실시간으로 결정해야 합니다. 이 길이 위험을 향하고 있는 것일까요? 시장이 안정되고 있는 것일까요? 올바르게 답하기 위해서 여행자는 단순히 현재의 순간에만 반응해서는 안 됩니다. 그는 이전의 신호들이 어떻게 결합하여 여정의 진정한 본질을 드러내는지 기억하며 과거를 붙잡고 있어야 합니다. 컴퓨팅의 세계에서 이 여행자는 알고리즘이며, 그가 과거의 세부 사항을 저장하기 위해 사용하는 '기억'은 매우 귀중하고 제한된 자원입니다. 수십 년 동안 과학자들은 양자 역학의 기묘한 법칙이 여행자로 하여금 고전적인 기계보다 훨씬 적은 공간을 사용하면서도 그만큼 많은 것을 기억할 수 있는, 더 가벼운 배낭을 짊어지게 할 수 있을지 궁금해해 왔습니다.

이 질문은 난양 공과대학교(Nanyang Technological University) 연구진과 그 협력자들이 수행한 새로운 연구의 핵심에 자리 잡고 있습니다. 그들은 에이전트가 데이터의 전체 모습을 한 번에 보지 못한 채, 도착하는 대로 들어오는 데이터 스트림을 하나씩 분류해야 하는 특정한 형태의 퍼즐을 구축했습니다. 연구진은 단순하지만 심오한 질문을 던졌습니다. 환경의 복잡성이 증가함에 따라, 클래식 컴퓨터가 퍼즐을 풀기 위해 필요한 메모리의 양이 무한히 늘어나는가, 아니면 양자 컴퓨터가 메모리 사용량을 작고 일정하게 유지할 수 있는가? 그들이 찾아낸 답은 명확하고 놀라웠습니다. 특정 복잡한 작업의 경우, 클래식 에이전트는 정확도를 유지하기 위해 메모리를 무한히 확장해야 하지만, 양자 에이전트는 동일한 작업을 고정되고 유한한 양의 메모리만을 사용하여 완벽하게 해결할 수 있다는 것을 그들은 증명했습니다.

이 돌파구를 이해하려면 먼저 도전의 본질을 파악해야 합니다. 연구진은 여러 구획이 있는 회전하는 바퀴를 이용한 일련의 게임을 설계했는데, 각 구획에는 잠재적으로 유색 구슬이 들어 있을 수 있습니다. 바퀴는 알려진 위치에서 시작되지만, 매 회전할 때마다 일정량만큼 회전합니다. 바퀴를 지켜보는 에이전트는 바퀴 자체를 보지 못하며, 오직 바퀴가 얼마나 회전했는지를 나타내는 숫자만을 봅니다. 목표는 바퀴가 멈췄을 때 고정된 표식 아래에 놓인 구슬의 색을 예측하는 것입니다. 여기서 핵심은 에이전트가 바퀴의 현재 상태를 전혀 보지 못한 채, 목격한 회전의 순서에만 기반하여 이 예측을 수행해야 한다는 점입니다. 만약 바퀴의 가능한 위치가 많다면, 클래식 에이전트는 실수를 하지 않기 위해 모든 개별 위치에 대해 별도의 정신적 기록을 유지해야 합니다. 가능한 위치의 수가 증가함에 따라, 완벽한 추적을 위해 필요한 메모리는 점점 더 커지며 결국 무한해집니다.

연구진은 이것이 단순한 이론적 제한이 아니라 확고한 장벽임을 입증했습니다. 그들은 만약 클래식 에이전트가 가능한 위치의 수보다 적은 메모리를 사용하려고 시도한다면, 그 성능이 붕괴된다는 것을 보여주었습니다. 적절한 조건 하에서, 그러한 에이전트는 무작위로 추측하는 것보다 나을 것이 없게 되며, 서로 다른 결과들을 구별하는 능력을 상실하게 됩니다. 이는 마치 에이전트가 자신이 걸어온 길을 잊어버려 어둠 속에서 비틀거리는 것과 같습니다. 이는 날카로운 경계를 만듭니다. 완벽해지기 위해서 클래식 기계는 자신이 관찰하는 세계의 복잡성에 직접적으로 비례하는 메모리 부하를 짊어져야 합니다.

반면, 연구진이 구축한 양자 에이전트들은 다르게 행동합니다. 바퀴의 회전 이력을 양자 시스템의 섬세한 상태 속에 인코딩함으로써, 이 에이전트들은 모든 가능한 위치에 대해 별도의 기록을 저장할 필요 없이 동일한 복잡한 환경을 추적할 수 있습니다. 연구진은 에이전트가 바퀴의 총 위치 수가 아니라, 서로 다른 바퀴 위치가 서로 다른 색상의 결과를 초래하는 특정 사례인 '충돌 회전(colliding rotations)'의 수에 의존하여 완벽한 기록을 유지할 수 있게 하는 특정한 양자 전략을 구축했습니다. 클래식 메모리 요구량이 위치의 총수와 함께 증가하는 반면, 양자 메모리 요구량은 이 충돌 횟수에 의해 제한됩니다. 많은 경우, 이 횟수는 바퀴의 총 위치 수가 엄청나게 커지더라도 작고 일정하게 유지됩니다. 그러나 이러한 이점이 보편적인 것은 아닙니다. 만약 위치의 수에 비해 서로 다른 구슬의 색상이 너무 많으면 양자 이점은 사라집니다. 연구진은 자신들의 양자 전략이 가장 효율적인 방법임을 수학적으로 증명했습니다. 즉, 클래식이나 양자 방식 중 그 어떤 방법도 이보다 더 적은 메모리로 그 일을 수행할 수 없습니다.

이 발견의 의의는 회전하는 바퀴라는 특정 게임을 넘어 확장됩니다. 이는 온라인 의사결정 맥락에서 클래식 컴퓨팅과 양자 컴퓨팅의 메모리 비용 사이에 존재하는 명확하고 무한한 격차를 확립합니다. 금융 시장 모니터링부터 센서 데이터의 이상 탐지에 이르기까지, 많은 현실 세계의 시나리오에서 정보는 연속적인 스트림으로 들어오며 시스템은 이를 즉석에서 분류해야 합니다. 이 연구는 이러한 유형의 문제에 대해 양자 역학이 근본적인 이점을 제공한다는 것을 보여줍니다. 즉, 고정된 최소한의 메모리로 복잡하고 진화하는 정보를 처리할 수 있는 능력입니다. 이것은 속도나 처리 능력의 문제가 아니라, 정보를 저장하고 검색하는 방식의 효율성에 관한 문제입니다. 연구진은 양자 세계가 클래식 세계에서는 불가능한 일종의 메모리 압축을 허용하며, 이를 통해 에이전트가 클래식 에이전트는 결코 달성할 수 없는 가벼움으로 복잡한 환경을 항해할 수 있게 함을 보여주었습니다.

또한 이 연구는 이러한 이점의 한계를 명확히 합니다. 연구진은 양자 컴퓨터가 모든 작업에 더 낫다고 주장하거나, 이 이점이 모든 상황에서 나타난다고 제안한 것이 아닙니다. 대신, 그들은 차이가 절대적이고 증명 가능한 특정 범주의 문제들을 식별했습니다. 그들은 자신들의 양자 구조가 해당 작업을 해결할 수 있는 가장 작은 메모리 시스템임을 증으로써, 무엇이 성취 가능한지에 대한 정밀한 벤치마크를 제공했습니다. 이를 통해 과학자들에게 지능과 의사결정에 필요한 근본적인 자원을 이해할 수 있는 새로운 도구를 제공하였으며, 양자 영역이 클래식 물리학이 복제할 수 없는 독특한 효율성의 경로를 제공한다는 것을 밝혀냈습니다.

궁극적으로, 이 연구는 메모리와 복잡성의 관계를 바라보는 우리의 관점을 변화시킵니다. 이는 과거를 기억하는 비용이 세계의 크기에 의해 결정되는 고정된 가격이 아니라, 관찰자의 본질에 따라 달라지는 변수임을 시사합니다. 클래식 관찰자에게 복잡한 세계는 복잡한 정신을 요구합니다. 하지만 양자 관찰자에게 동일한 복잡한 세계는 작고 일정한 정신으로 이해될 수 있습니다. 이러한 구분은 정보 연구의 새로운 장을 열며, 양자 역학의 법칙이 무한한 메모리의 부담 없이 과거의 무게를 짊어질 수 있는 방법을 제공한다는 것을 보여줍니다.