양자 근사 최적화를 통한 비구조적 검색의 깊이 스케일링

변분 양자 알고리즘은 현재 양자 컴퓨테이션의 사실상의 모델이 되었습니다. 이러한 알고리즘의 두드러진 예인 양자 근사 최적화 알고리즘(QAOA)은 본래 조합 최적화 작업을 위해 설계되었지만, 다양한 다른 문제에서도 성공적인 결과를 보여주었습니다. 그러나 이러한 문제의 대부분에 대해서는 최적 회로 깊이가 여전히 알려져 있지 않습니다. 이러한 문제 중 하나는 특정 비트 문자열을 찾는 것으로 구성된 비구조적 검색입니다. 또는 동등하게, 목표 상태와 높은 겹침을 가진 상태를 준비하는 것입니다. 이러한 문제에 대한 최적 QAOA 깊이를 한정짓기 위해, 우리는 연속 시간 양자 워크(CTQW)에서 알려진 해결책을 기반으로 합니다. 우리는 CTQW를 트로터화하여 QAOA 시퀀스를 복원하고, 목표 상태와 거의 완벽한 겹침을 가진 상태를 준비하기 위해 필요한 질의 복잡도(회로 깊이)를 한정짓기 위해 트로터 공식 이론의 최근 발전을 활용합니다. 얻어진 복잡도는 그로버 알고리즘 복잡도 O (N¹2)을 초과하지만, O (N^1{2+c})보다 작게 유지되어 c>0인 모든 경우에 대해 양자적 이점을 보여줍니다. 우리는 최대 68 큐비트의 수치 시뮬레이션을 통해 우리의 분석 예측을 검증하며, 이 결과가 트로터화된 CTQW에서 발생하는 QAOA 레이어의 수를 최대 다항식 배율로 과대평가한다는 것을 보여줍니다.