Leaving Quantum Bias on the Table: Pushforwards as a Path to Quantum Advantage in Constrained Optimization

현대 컴퓨팅의 세계에는 표준적인 기계로는 풀기에는 너무 복잡하지만, 가장 강력한 새로운 도구들로 다루기에는 너무 경직된 문제들을 해결하려는 지속적인 투쟁이 존재합니다. 이들은 배송 경로 계획부터 항공편 일정 관리까지 모든 곳에 나타나는 제약 최적화 문제(constrained optimization problems)로 알려져 있습니다. 목표는 많은 움직이는 부품들의 단 하나의 최적의 배치를 찾는 것이지만, 반드시 따라야 하는 엄격한 규칙들이 존재합니다. 시간을 절약하더라도 규칙을 어기는 솔루션은 무용지물이기 때문입니다. 최근 과학자들은 양자 컴퓨터를 활용하고 있는데, 양자 컴퓨터는 양자 역학의 기묘한 법칙을 사용하여 동시에 많은 가능성을 탐색합니다. 그러나 이 기계들은 현재 노이즈가 많고 불완전합니다. 이들은 유망해 보이는 답을 내놓기도 하지만 종종 엄격한 규칙을 충족하지 못하며, 이로 인해 연구자들은 사용할 수 없는 데이터의 홍수에 직면하게 됩니다. 과제는 그 안에 숨겨진 가치 있는 패턴을 버리지 않으면서 이러한 결함이 있는 출력값을 어떻게 이해하느냐는 것이었습니다.

연구팀은 이 간극을 메울 수 있는 새로운 방법을 개발하여, 양자 컴퓨터의 가공되지 않은 무질서한 출력을 신뢰할 수 있는 유효한 솔루션의 흐름으로 전환했습니다. 양자 컴퓨터가 직접 완벽한 답을 내놓도록 강요하는 대신, 그들은 기계의 출력을 두 번째 단계인 고전적(classical) 단계의 시작점으로 취급합니다. 양자 컴퓨터를 과녁을 향해 화살을 쏘는 숙련되었지만 약간 서투른 궁수로 상상해 보십시오. 종종 화살은 정중앙을 벗어나 근처에 떨어지는데, 이는 목표를 놓쳤을지라도 여전히 그 방향을 명확히 보여줍니다. 연구진의 방법은 근처에 떨어진 모든 화살을 가져와 부드럽게 중심부로 밀어 넣는 것입니다. 이 "밀어넣기(nudge)"는 화살의 경로에 있는 오류를 수리하여 빗나간 것을 완벽한 적중으로 변환하는 고정된 수학적 규칙입니다. 이 수리 규칙을 모든 발사된 화살에 적용함으로써, 연구팀은 양자 컴퓨터가 최적의 솔루션 근처로 화살을 집중시키는 자연스러운 경향이 이전보다 훨씬 적은 시도만으로도 최적의 답을 찾을 수 있을 만큼 강력하다는 것을 발견했습니다.

이 발견의 핵심은 "푸시포워드(pushforward)"라고 불리는 개념에 있는데, 이는 모든 결과가 하나의 규칙에 의해 변환될 때 확률 분포가 어떻게 이동하는지를 설명합니다. 이 연구의 맥락에서 연구진은 양자 컴퓨터가 (그중 다수가 유효하지 않은) 가능한 답들의 구름을 생성할 때, 고전적인 수리 과정이 좋은 솔루션에 가까운 모든 유효하지 않은 것들을 휩쓸어 그 좋은 솔루션으로 매핑할 수 있음을 보여주었습니다. 이는 효과적으로 타겟 영역을 확장합니다. 양자 컴퓨터가 특정한 완벽한 구성을 맞출 필요 없이, 쉽게 수정 가능한 많은 결함 있는 구성 중 하나만 맞춰도 되기 때문입니다. 이러한 변화는 게임의 판도를 완전히 바꿉니다. 즉, 양자 컴퓨터가 성공하기 위해 정밀하거나 계산이 깊을 필요가 없다는 것을 의미합니다. 왜냐하면 고전적인 수리 단계가 흩어진 근접 실패 시도들을 모아 하나의 유효한 결과로 통합하는 힘든 작업을 수행하기 때문입니다.

이 아이디어를 테스트하기 위해 연구팀은 여행하는 외판원 문제(traveling salesman problem), 즉 여행자가 각 도시를 정확히 한 번씩 방문하고 가장 짧은 거리를 이동하며 집으로 돌아와야 하는 고전적인 퍼즐에 집중했습니다. 그들은 양자 알고리즘을 사용하여 이 시나리오를 시뮬레이션했는데, 이 알고리즘은 각 도시를 한 번씩 방문한다는 문제의 기본 구조는 준수하지만 최종 배치에서는 오류를 허용하도록 설계되었습니다. 연구진이 이 수리 방법을 결과에 적용했을 때, 양자 컴퓨터가 최적의 경로로 수정될 수 있는 특정 그룹의 결함 있는 답들에 확률 질량을 집중시키고 있다는 것을 발견했습니다. 10개 도시가 포함된 문제에 대한 시뮬레이션에서, 수리된 양자 방법은 약 1,000번의 시도 만에 최적의 솔루션을 찾아냈습니다. 반면, 이 수리 단계가 없는 원래의 방법은 동일한 결과를 얻기 위해 100만 번의 시도가 필요했습니다. 이 엄청난 시도 횟수의 감소는 양자 컴퓨터가 기술적으로는 틀린 출력이라 할지라도 최적의 솔루션에 대한 유용한 정보를 실제로 보유하고 있었음을 입 demonstrates 합니다.

연구진은 또한 이 방법이 실제 하드웨어의 노이즈와 오류에 어떻게 대응하는지 확인하기 위해 IBM이 제작한 127-큐비트 양자 프로세서를 사용하여 실험했습니다. 그들은 이 물리적 장치에서 동일한 여행하는 외판원 문제를 실행했는데, 이 장치는 완벽한 시뮬레이션보다 훨씬 더 노이즈가 심합니다. 실제 기계의 불완전함에도 불구하고, 수리 과정은 종종 혼란스러운 출력들을 유효한 경로로 성공적으로 변환했습니다. 더 작은 테스트 케이스의 경우, 수리된 결과는 알려진 최적의 솔루션과 일치했습니다. 더 크고 어려운 케 케이스의 경우, 수리된 솔루션은 표준 소프트웨어 라이브러리에서 제공하는 참조 답변보다 더 나은 결과를 보여주었습니다. 이는 이 방법이 이론이나 시뮬레이션뿐만 아니라, 현재 사용 가능한 불완전한 하드웨어에서도 작동함을 확인시켜 주었습니다. 핵심적인 발견은 양자 컴퓨터가 단순히 무작위 노이즈를 생성하는 것이 아니라, 가장 유용하고 수정 가능한 오류들이 서로 밀집되어 있는 편향된 분포를 생성하고 있었으며, 수리 과정이 이 편향을 수확하여 고품질의 솔루션을 찾아낼 수 있었다는 점입니다.

이 연구는 가까운 미래에 우리가 양자 컴퓨터를 사용하는 방식에 대한 새로운 설계 원칙을 제시합니다. 양자 컴퓨터가 어려운 문제를 직접 해결할 수 있을 만큼 완벽해지기를 기다리는 대신, 양자 부분이 솔루션 공간을 탐색하는 무거운 작업을 수행하고 고전적인 부분이 필터 및 수리 메커니즘 역할을 하는 하이브리드 시스템을 구축할 수 있습니다. 양자 컴퓨터의 역할은 정확한 답을 짚어내는 것이 아니라, 답이 포함되어 있을 가능성이 가장 높은 문제 영역을 식별하는 것입니다. 그러면 고전적인 수리 규칙이 그 유망한 영역을 가져와 최선의 솔루션을 추출합니다. 이 접근 방식은 '유용한 영역에 확률을 집중시키는 능력'인 양자 이점과 '엄격한 규칙을 강제하고 오류를 수정하는 능력'인 고전적 이점을 분리합니다. 이러한 강점들을 결합함으로써, 연구진은 우리가 이미 보유한 불완전한 양자 하드웨어를 사용하여 복잡한 문제를 해결하는 데 있어 상당한 개선을 달성할 수 있음을 보여주었습니다.

또한 이 연구는 노이즈가 이 과정에 어떤 영향을 미치는지 강조했습니다. 양자 컴퓨터가 너무 노이즈가 심하면, 정보가 유효한 솔루션 공간 밖으로 새어나가 수리가 불가능한 영역으로 데이터를 보내게 됩니다. 연구진은 이러한 누출이 증가함에 따라 수리 방법의 이점이 줄어들어 결국 과정이 무작위 탐색으로 변한다는 것을 발견했습니다. 그러나 현재 기계들에 존재하는 수준의 노이즈에 대해서는 이 방법이 매우 효과적이었습니다. 연구팀은 수리 과정이 얼마나 도움이 될 수 있는지 예측하는 수학적 경계치를 도출하였으며, 이를 통해 수리 과정이 솔루션을 찾는 데 필요한 양자 회로의 깊이를 줄일 수 있음을 보여주었습니다. 이는 매우 중요한 세부 사항인데, 왜냐นั้น 더 깊은 회로는 오류에 더 취약하기 때문입니다. 더 얕은 회로를 사용할 수 있게 함으로써, 수리 방법은 노이즈에 의해 결과가 파괴되지 않으면서도 기존 하드웨어에서 더 복합적인 문제를 실행할 수 있게 해줍니다.

궁극적으로, 이 논문은 제약 최적화에서 양자 샘플러의 가치가 단순히 그것이 만들어내는 완벽한 답에 있는 것이 아니라, 그 실수들의 구조에 있다는 점을 확립합니다. 양자 컴퓨터는 "틀린" 답들이 무작위로 흩어져 있는 것이 아니라, 올바른 답을 가리키는 특정 방식으로 군집을 이루는 지형을 만들어냅니다. 결정론적인 수리 규칙을 통해 이러한 구조를 인식하고 활용함으로써, 우리는 양자 기계나 고전 컴퓨터가 단독으로는 달성할 수 없는 성능을 끌어낼 수 있습니다. 시뮬레이션과 실제 하드웨어 실험 모두에서 얻은 결과는 이 접근 방식이 현재의 노이즈가 있는 중간 규모 양자 장치(NISQ) 시대에 양자 우위를 확보하기 위한 실행 가능한 경로라는 강력한 증거를 제공합니다. 이 방법은 실행 불가능한 출력을 처리하는 문제를 실패 모드에서 하나의 기능(feature)으로 전환하여, 연구자들이 양자 컴퓨터가 가장 잘하는 일, 즉 길을 찾되 때로는 길을 벗어나지 않도록 약간의 도움을 받는 일을 수행할 수 있도록 해줍니다.