Random-Oracle Unitary Synthesis is Impossible

양자 세계에서, 물리 법칙의 근본적인 법칙들은 거의 무한히 다양한 변환을 가능하게 합니다. 정보의 한 조각을 가져와서 그것이 아무리 복잡하거나 기이하더라도 어떤 형태든 원하는 모양으로 비틀 수 있는 기계를 상상해 보십시오. 유니터리(unitaries)라고 알려진 이러한 변환들은 양자 컴퓨팅의 구성 요소입니다. 그러나 자연이 어떤 변환을 허용한다고 해서, 반드시 컴퓨터가 그것을 구축할 수 있다는 의미는 아닙니다. 구축하기 쉬운 유니터리와 현재의 기술로는 사실상 불가능한 유니터리 사이에는 거대한 격차가 존재합니다. 수십 년 동안 과학자들은 이 격차가 실재하는 것인지, 아니면 단지 우리의 이해가 부족해서 생긴 틈인지를 궁금해해 왔습니다. 구체적으로, 그들은 모든 어려운 양자 변환이 단순히 특정한 어려운 고전적 함수를 계산하는 방법을 아는 것만으로 구축될 수 있는지 물었습니다. 만약 답이 '그렇다'라면, 이는 양자 컴퓨팅에서 가장 어려운 문제들이 고전 컴퓨팅의 가장 어려운 문제들과 똑같이 어렵다는 것을 의미하며, 두 세계를 긴밀하게 연결할 것입니다. 만약 답이 '아니오'라면, 이는 양자 역학이 고전적 논리로는 풀 수 없는 비밀을 간직하고 있음을 시사하며, 잠재적으로 완전히 새로운 복잡성 이론을 요구할 수도 있습니다.

한 연구팀은 게임의 규칙을 약간 바꾸어 이 질문을 조사했습니다. 컴퓨터가 특정하고 복잡한 함수를 사용하여 특정 변환을 구축할 수 있는지 묻는 대신, 그들은 컴퓨터가 무작위적이고 구조가 없는 함수만을 사용하여 완전히 무작위적이고 예측 불가능한 변환을 구축할 수 있는지를 물었습니다. 이러한 변화를 통해 그들은 입력 데이터에 활용할 수 있는 숨겨진 패턴이 없을 때 무엇이 가능한지의 한계를 테스트할 수 있었습니다. 그들의 결과는 결정적입니다: 무작위 함수만을 사용하여 진정으로 무작위적인 양자 변환을 효율적으로 합성하는 것은 불가능합니다. 그들은 아무리 영리한 알고리즘이라 할지라도, 만약 그것이 무작위로 선택된 함수에 의존한다면, 천문학적인 횟수의 질문을 던지지 않는 한 원하는 양자 상태를 만들어내는 데 실패할 것임을 증명했습니다. 이 결과는 정보의 구조가 제공되는 정보의 구조에 전적으로 의존한다는 것을 보여줌으로써 오랫동안 지속된 논쟁을 종결지었습니다. 구조가 없다면, 그 과업은 도달할 수 없는 영역으로 남습니다.

연구진은 또한 양자 암호학에서 사용되는 유사 무작위 유니터리(pseudorandom unitaries)라는 관련 개념도 탐구했습니다. 이것들은 비록 단순하고 효율적인 과정에 의해 만들어졌지만, 이를 만드는 데 사용된 비밀 키를 모르는 사람에게는 무작위처럼 보이는 양자 변환들입니다. 이러한 '가짜' 무작위 변환을 만드는 데 사용되는 기존의 최선책들은 제한적이었습니다. 그것들은 상대적으로 적은 수의 질문을 던지는 관찰자만을 속일 수 있었습니다. 연구진은 이 한계가 일시적인 기술적 장애물인지, 아니면 근본적인 자연 법칙인지를 알고 싶었습니다. 그들은 관찰자가 시스템 전체 크기에 비례하는 훨씬 더 많은 수의 질문을 던지더라도 보안이 유지되는 방식으로 이러한 변형을 성공적으로 생성하는 새로운 방법을 구축했습니다. 이는 시스템 크기의 제곱근에 비례하는 질문만을 처리할 수 있었던 이전의 방법들에 비해 상당한 개선입니다.

그러나 그들의 작업은 엄격한 천장 또한 드러냈습니다. 그들이 이 가짜 무작비 변환의 보안성을 훨씬 더 멀리 밀어붙일 수는 있었지만, 이론적인 최대치까지 밀어붙이는 것은 불가능하다는 것을 증명했습니다. 그들은 만약 어떤 방법이 수행되는 단계 수 측면에서 효율적이어야 한다면, 매우 많은 수의 질문을 던지는 관찰자에 대해 보안을 유지할 수 없음을 입증했습니다. 이는 정밀한 경계를 만들어냅니다: 적당한 수의 질문에 대해 효율적이고 안전한 방법을 가질 수도 있고, 혹은 방대한 수의 질문에 대해 안전한 방법을 가질 수도 있지만, 두 가지를 동시에 가질 수는 없습니다. 이 발견은 양자 암호학의 현재 한계가 단지 더 나은 알고리즘을 기다리는 문제만이 아니라, 근본적인 제약임을 시사합니다.

또한 이 연구는 적절한 고전적 지침이 주어진다면 우리가 언제쯤 모든 양자 변환을 합성할 수 있는 보편적인 기계를 구축할 수 있을지에 대한 광범위한 질문을 다루었습니다. 무작위 입력이 무작위 출력을 생성하지 못한다는 것을 보여줌으로써, 연구진은 입력의 구조가 필수적이라는 강력한 증거를 제시했습니다. 강력한 컴퓨터와 무작위 함수를 갖는 것만으로는 충분하지 않습니다. 함수 자체가 원하는 결과를 향해 컴퓨터를 안내하도록 정교하게 설계되어야 합니다. 이는 특정 양자 상태를 만드는 것의 어려움이 단순히 계산 능력의 문제가 아니라, 그것을 설명하는 데 필요한 정보의 본질적인 특성임을 의미합니다. 이 연구는 단순한 무작위 오라클(oracle)이 모든 양자 가능성을 여는 보편적인 열쇠 역할을 할 수 있다는 생각에 효과적으로 종지부를 찍었습니다.

결국, 이 논문은 효율성과 무작위성이 서로 긴장 관계에 있는 양자 경관을 그려냅니다. 연구진은 우리가 매우 설득력 있는 무작위성의 모조품을 만들 수는 있지만, 그 과정을 빠르게 유지하고자 한다면 그 모조품이 얼마나 훌륭해질 수 있는지에는 엄격한 한계가 있음을 보여주었습니다. 또한 단순한 무작위 함수를 사용하여 모든 양자 변환을 구축할 수 있다는 희망은 근거 없는 것임을 보여주었습니다. 이 결과들은 단순히 새로운 알고리즘이나 새로운 제한을 제시하는 것이 아니라, 양자 영역에서 무엇이 가능한지의 경계를 재정의합니다. 그들은 양자의 복잡성이 영리한 속임수로 우회할 수 있는 환상이 아니라, 특정한 구조화된 정보를 필요로 하는 실제적인 특징임을 말해줍니다. 양자 기술의 미래를 건설하는 이들에게, 이는 앞으로 나아가는 길이 단지 더 큰 힘뿐만 아니라 더 정밀한 설계가 필요함을 의미합니다. 우주는 우리가 답을 얻기 전에 우리가 정확히 무엇을 요구하고 있는지를 먼저 알기를 요구하는 듯합니다.