Exploiting all ancilla outcomes in linear combinations of unitaries: low-rank recovery and quantum trapdoor functions

양자 컴퓨팅의 세계에서 과학자들은 우리가 일상적으로 사용하는 노트북이나 휴대폰과는 근본적으로 다른 방식으로 정보를 처리하는 기계를 다룹니다. 이러한 양자 장치들은 여러 가능성이 동시에 존재할 수 있는 미세한 물질 상태에 의존하며, 이 특성은 특정 문제들을 놀라운 속도로 해결할 수 있게 해줍니다. 그러나 유용한 양자 컴퓨터를 구축하는 데 있어 주요한 장애물은 이들이 매우 취약하다는 점입니다. 양자 컴퓨터가 계산을 수행할 때, 종종 '사후 선택(post-selection)'이라고 불리는 과정을 거치는데, 이는 기계가 복잡한 연산을 수행한 후 특정 결과를 확인하는 과정입니다. 만약 결과가 정확히 기대했던 것이라면 그 계산은 유지되지만, 그 외의 다른 결과라면 전체 시도는 실패로 간주되어 폐기되며 기계는 처음부터 다시 시작해야 합니다. 이러한 노력의 낭비는 상당한 병목 현상을 일으킵니다. 왜냐하면 버려지는 시도들은 대개 아무런 생각 없이 버려지며, 시스템 내의 단순한 노이즈로 취급되기 때문입니다.

이스탄불 메데니예트 대학교의 아마르 다스킨(Ammar Daskin)이라는 연구자는 이 버려진 정보에 대한 새로운 관점을 제안했습니다. 최근 연구에서 그는 '유니터리 선형 결합(linear combination of unitaries)'이라 불리는 특정 유형의 양자 계산에서 버려지는 정보들을 더 이상 무시하지 않을 때 어떤 일이 발생하는지 탐구했습니다. 다스킨은 이러한 결과들을 쓸모없는 오류로 보는 대신, 그 안에 숨겨진 조직적인 구조가 존재함을 보여주었습니다. 단 한 번의 회로 실행으로부터 얻은 모든 가능한 결과들을 수집하면, 평소 무시되었던 것들을 포함하여 데이터가 하나의 패턴을 형성하게 됩니다. 이 발견은 한때 폐기물로 여겨졌던 것이 가치 있는 자원으로 전환될 수 있음을 시사하며, 이를 통해 과학자들이 단지 데이터의 일부만을 가지고도 문제의 전체 답을 복구하거나, 이 숨겨진 구조를 해독하는 난이도에 기반한 새로운 형태의 보안 통신 방법을 만들어낼 수 있을 것입니다.

다스킨 연구의 핵심은 서로 다른 연산들을 하나의 더 복잡한 연산으로 결합하는 표준적인 양자 기법을 활용하는 것입니다. 전형적인 설정에서 양자 컴퓨터는 계산의 계수를 관리하기 위해 '안실라 큐비트(ancilla qubits)'라고 불리는 일련의 추가 헬퍼 비트를 사용합니다. 기계는 이 헬퍼 비트들을 특정 상태로 준비하고, 계산을 수행한 뒤, 헬러 비트들을 확인합니다. 만약 헬퍼 비트들이 시작 위치로 돌아온다면 주 계산은 성공한 것으로 간주됩니다. 표준 방식에서는 헬퍼 비트가 도달하는 다른 모든 위치를 실책으로 취급하며, 그에 해당하는 결과는 버려집니다. 다스킨은 이 '실수'들을 조사하기 위해 회로 설계를 단순화하기로 했습니다. 그는 헬퍼 비트를 준비하는 데 사용되는 복잡한 장치들을 대신하여, 가능성의 균등한 혼합을 만드는 일련의 게이트와 계산의 가중치를 조절하는 단일 회전 게이트를 사용하는 기본적인 양자 게이트들의 단순한 배열을 사용했습니다.

이 단순화된 회로가 실행되면, 헬퍼 비트의 측정 결과에 따라 다양한 결과물이 생성됩니다. 다스킨은 모든 가능한 측정 결과로부터 얻은 결과들을 모아 쌓으면 하나의 커다란 데이터 격자(grid)를 형성한다는 것을 발견했습니다. 이 격자는 놀라운 성질을 가지고 있는데, 바로 전체를 재현하기 위해 곱해질 수 있는 두 개의 더 작은 조각들로 분해될 수 있다는 점입니다. 한 조각은 회로의 설계에 의해 결정되는 알려진 패턴이며, 다른 한 조라는 실제 수행하려는 개별 연산들의 결과들을 담고 있습니다. 이 회로는 제한된 수의 독립적인 조합만을 생성하기 때문에, 전체 커다란 격자는 수학적으로 '저계수(low-rank)'를 가집니다. 즉, 겉으로 보이는 것보다 훨씬 단순하다는 의미입니다. 이러한 구조는 계산의 전체 답이 데이터 속에 숨겨져 있으며, 심지어 데이터의 아주 작은 부분에만 접근할 수 있더라도 이를 찾아낼 수 있음을 시사합니다.

이 아이디어를 테스트하기 위해, 연구자는 컴퓨터로 회로를 시뮬레이션하여 부분적인 정보로부터 전체 출력을 복구할 수 있는지 확인했습니다. 시뮬레이션 결과, 회로의 설계를 알고 있다면 고전적인 수학적 기법을 사용하여 데이터 격자의 누락된 부분을 채울 수 있음이 나타났습니다. 결과의 일부만을 관찰함으로써, 알고리즘은 표준 방식이 유지했을 특정 결과뿐만 아니라 전체 행렬의 결과를 재구성할 수 있었습니다. 이 복구 작업은 데이터가 깨끗할 때 가장 잘 작동하지만, 연구는 실제 양자 하드웨어에서 발생하는 오류를 모사하여 데이터에 노이즈가 섞였을 때 이 방법이 어떻게 견디는지도 조사했습니다. 결과는 이 방법이 견고하긴 하지만, 측정이 불완전할 때 신뢰할 만하게 작동하려면 상당한 양의 데이터가 필요하다는 것을 보여주었습니다. 연구는 실제 환경에서 복소수 값 전체가 아닌 신호의 강도만을 측정하는 경우, 완전한 정보를 복구하기 위해 추가적인 단계가 필요하겠지만, 근본적인 구조는 재구성을 위한 강력한 도구로 남는다는 점을 시사합니다.

데이터 복구라는 실용적인 응용을 넘어, 이 발견은 새로운 종류의 암호학적 아이디어로 향하는 문을 엽니다. 연구자는 회로 내에서 결과를 혼합하는 데 사용되는 특정 패턴을 비밀 키처럼 비밀로 유지할 수 있다고 제안했습니다. 만약 관찰자가 최종 데이터 격자를 보더라도, 그 안에 숨겨진 혼합 패턴을 알지 못한다면 원래의 입력을 알아내기 위해 어려운 수학적 퍼즐에 직면하게 될 것입니다. 이는 열쇠가 메커니즘 내부에 숨겨진 자물쇠와 유사합니다. 그러나 이 연구는 이것이 보안 시스템의 하나의 후보일 뿐이라는 점을 주의 깊게 명시합니다. 보안은 파동의 세부 사항을 그 강도로부터 알아내는 '위상 복원(phase retrieval)'이라 불리는 특정 유형의 문제를 푸는 어려움에 달려 있습니다. 이 문제는 어려운 것으로 알려져 있지만, 연구자는 이것이 깨뜨리는 것이 불가능하다는 것을 증명하지는 않았으며, 시스템의 보안은 아무도 그것을 해결하는 지름길을 찾을 수 없다는 가정에 의존합니다.

또한 이 논문은 이 구조가 사용자 선호도를 예측하거나 웹 페이지 간의 링크를 분석하는 데 사용되는 추천 시스템이나 랭킹 알고리즘 등에서 어떻게 사용될 수 있는지를 탐구합니다. 발견된 수학적 관계는 대량의 데이터를 더 단순한 구성 요소로 분해하는 고전 컴퓨팅의 기법들과 닮아 있습니다. 연구자는 양자 회로를 이러한 패턴을 생성하는 수단으로 취급함으로써, 양자 컴퓨터가 이러한 작업들을 수행하는 새로운 방법을 제공할 수 있다고 제안합니다. 연구는 양자 회로의 출력을 바라보는 방식을 바꿈으로써, 한때 폐기물로 여겨졌던 것을 구조화된 자원으로 바꿀 수 있다고 결론짓습니다. 이 접근 방식은 현재 계산의 효율성을 개선할 뿐만 아니라, 양자 정보를 저장, 복구 및 보호하는 방식에 대한 새로운 가능성을 제시합니다. 이 작업은 시뮬레이션에 의해 뒷받침되는 이론적 제안이지만, 이 '쓰레기' 결과물들이 실제로 더 강력하고 안전한 양자 기술을 구축하는 데 활용될 수 있는지에 대한 명확한 경로를 제시하고 있습니다.