도달 가능한 부분 공간에서의 정확한 대각 완성: 배치 문제에의 적용

사용되지 않는 인코딩 상태는 양자 회로를 단순화할 기회를 제공합니다. 도달 가능한 부분 공간으로 제한되는 알고리즘의 경우, 지정되지 않은 대각 연산자 항목은 이상적인 계산을 변경하지 않고 최적화될 수 있습니다. 우리는 순열 보존 레지스터 스왑을 사용하여 배치 문제에 적용된 양자 근사 최적화 알고리즘(QAOA)에 대한 정확한 대각 완성(exact diagonal completion)을 조사합니다. 우리는 Walsh 계수의 가중-$ ext{l}_1$ 최적화와 균형 잡힌 직사각형에서 $O( ext{m})$ 항이 필요한 희소 재귀를 통해 정확한 맨해튼 거리 연산자를 구성하며, 이는 $O( ext{m}^4)$의 밀집 제약 저장 공간을 피합니다. 160개 기하학 구조에 걸쳐, 가중-$ ext{l}_1$ 완성은 그레이 코드 합성 하에서 사용되지 않는 이진 코드를 가진 96가지 경우 모두에서 네 가지 대체 확장 방식 대비 제어-NOT(CX) 카운트를 줄였습니다. 독립적으로 지정된 60개 사례 그룹에서는, 가상 좌표 확장 방식 대비 여섯, 아홉, 열두 사이트에서 각각 28.0%, 53.9%, 21.6%의 중앙값 감소율을 보였습니다. 일반적인 대각 합성 조건 하에서는, 감소율이 10.9%, 1.3%, 0.7%로 줄어들어 컴파일러 의존성을 입증했습니다. 추가적인 보조 비트(ancillas)는 믹서 직렬화를 줄이지만, 토큰 회로는 여전히 원-핫 기준선보다 깊게 남아 있습니다. 이상적인 배치 시뮬레이션은 기준선에 따라 솔루션 품질이 달라지며, 클래식 검색 방식이 더 나은 성능을 보였습니다. OpenROAD 통합은 클럭 트리 합성 및 제로 오버플로우를 사용한 전역 라우팅을 통해 6개의 RTL 설계에서 각각 72회의 QAOA와 216회의 클래식 배치를 수행했습니다. 완성 기법은 위상 구성을 개선했지만, 엔드투엔드(end-to-end) 이점은 확립되지 않았습니다.