수 분할 문제는 NP-hard로 분류되어 최적의 솔루션을 찾기는 어렵지만 검증하기는 쉽다.
미국 스탠포드 대학(Stanford University) 연구원들은 NP-hard 문제에 대한 양자 접근 방식을 개발했습니다. 글로버(Grover) 알고리즘으로 알려진 잘 확립된 양자 알고리즘을 숫자 분할 문제에 적용함으로써 동등한 기존 알고리즘에 비해 2차 지수적 향상을 얻다. 팀은 또한 차가운 원자를 사용하는 것과 같은 단기 양자 장치에서 이 알고리즘을 구현하는 방법을 제안한다.
Grover의 알고리즘은 데이터베이스에서 특정 항목을 찾도록 설계되었으며 특정 항목이 검색 대상인지 여부를 판단하기 위해 소위 오라클에 의존한다. 데이터베이스의 각 항목이 별개의 양자 상태로 인코딩되면 다음 단계는 이러한 상태의 동일한 가중치 중첩을 구성하는 것이다. 그 후 오라클은 중첩에 적용되어 대상 항목을 인코딩하는 양자 상태에 위상차를 부여한다. 이것은 목표를 표시하고 그 후에 측정 확률을 높일 수 있다. 그런 다음 측정 확률이 충분히 높아질 때까지 프로세스를 반복적으로 적용한다.
스탠포드 연구진은 정수 목록의 가능한 분할을 양자 상태로 인코딩하여 그로버 알고리즘을 숫자 분할 문제에 적용했다. 그들은 또한 최적의 파티션을 식별할 수 있는 오라클을 공식화하는데, 이는 NP-hard 문제의 솔루션을 쉽게 확인할 수 있기 때문에 가능하다. 그런 다음 Grover의 알고리즘은 최적의 파티션을 검색한다.
알고리즘을 구현하기 위해 물리학자들은 중앙 양자 스핀(예 : Rydberg 원자) 또는 중앙 보손(boson)이 시스템의 다른 모든 스핀과 결합되는 하드웨어 아키텍처를 제안한다. 다른 커플링이 없는 이 배열을 별 그래프라고 한다. 중앙 엔티티는 오라클 역할을 하며 다른 스핀에 대한 결합 강도는 목록의 정수를 나타낸다.
이 연구의 공동 저자 Ognjen Marković는“우리의 제안은 완전한 양자 오류 수정이 이루어지기 전에 장치에서 Grover의 알고리즘을 효율적으로 구현할 수있는 가능성을 열어줌으로써 이러한 단기 장치에서 실제 문제를 해결할 가능성을 개선한다” 고 말했다.
연구팀은 이 작업이 양자-고전적 하이브리드 알고리즘 분야의 연구를 자극할 수 있다고 믿는다. 예를 들어, 팀이 제안한 Grover 알고리즘 구현은 더 큰 고전 알고리즘에서 양자 서브 루틴으로 사용될 수 있다.
이 연구는 PRX Quantum에 발표됐다.
