SabreSwap

class qiskit.transpiler.passes.SabreSwap(*args, **kwargs)

베이스: TransformationPass

스왑 삽입을 통해 입력 회로를 백엔드 토폴로지에 매핑합니다.

SABRE 큐비트 매핑 논문 [2] (알고리즘 1)의 SWAP 기반 휴리스틱 검색을 LightSABRE 논문 [1에서] 수정하여 구현했습니다. 이 휴리스틱은 삽입되는 손실 스왑의 수와 회로의 깊이를 최소화하는 것을 목표로 합니다.

이 알고리즘은 가상 큐비트를 물리적 큐비트에 초기 레이아웃하는 것부터 시작하여 모든 게이트가 소진될 때까지 회로 DAG를 반복하고, 그 과정에서 SWAP을 삽입합니다. 2큐비트 게이트만 매핑 문제에 중요하므로 2큐비트 게이트만 고려합니다(3큐비트 이상의 게이트는 이미 분해된 것으로 가정).

각 반복에서 먼저 front_layer 에 직접 적용할 수 있는 게이트가 있는지 확인합니다. 그렇다면 이를 적용하고 front_layer 에서 제거하고 가능한 경우 해당 레이어를 새 게이트로 채웁니다. 그렇지 않으면 스왑을 검색하고, 스왑을 삽입하고, 매핑을 업데이트하려고 시도합니다.

스왑 검색은 front_layer 에 관련된 큐비트 인근의 물리적 큐비트만 고려한다는 의미에서 제한적으로 이루어집니다. 이렇게 하면 몇 가지 휴리스틱 비용 함수에 따라 점수가 매겨진 swap_candidate_list 이 생성됩니다. 최상의 스왑이 구현되고 current_layout 업데이트됩니다.

이 트랜스파일러 단계는 서로 다른 시드 값을 사용하여 알고리즘을 여러 번 실행한다는 점에서 SABRE 알고리즘을 확장합니다. 무작위로 선정된 실험 중, SWAP 삽입 횟수가 가장 적은 실험에서 도출된 최상의 결과가 선택될 것입니다.

참조 자료:

[1] 헨리 조우, 매튜 트레이니쉬, 케빈 하트만, 알렉산더 이브리, 제이크 리쉬먼. “LightSABRE: 가볍고 향상된 SABRE 알고리즘" arXiv:2409.08368 [2] 리, 구슈, 유페이 딩, 위안 시에. "NISQ 시대의 양자 디바이스를 위한 큐비트 매핑 문제 해결." ASPLOS 2019. arXiv:1809.02573

SabreSwap 이니셜라이저.

매개변수

• coupling_map (Union[CouplingMap, Target]) – CouplingMap 대상 백엔드의
• heuristic (str) – 최적의 스왑 전략을 결정할 때 사용할 휴리스틱 유형('기본' 또는 '룩헤드' 또는 '붕괴').
• seed (int) – 후보 스왑 중 타이브레이크에 사용되는 무작위 시드입니다.
• fake_run (bool) – 참이면 라우팅을 수행하는 시늉만 할 뿐, 즉 스왑이 실제로 추가되지 않습니다.
• trials (int) – 세이버를 실행할 시드 트라이얼 횟수입니다. 이들은 병렬로 실행됩니다( PassManager 이 이미 병렬로 실행되고 있지 않은 경우). 지정하지 않으면 기본값은 로컬 시스템의 물리적 CPU 수로 설정됩니다. 재현 가능한 결과를 얻으려면 고정된 시도 횟수에 대해 결과가 결정적이므로 이를 명시적으로 설정하는 것이 좋습니다.

레이즈

TranspilerError – 지정된 휴리스틱이 유효하지 않은 경우.

추가 정보:

물리적 큐비트에서 가능한 스왑의 검색 공간은 각 스왑으로 인해 발생할 수 있는 레이아웃에 점수를 할당하여 탐색합니다. 레이아웃의 우수성은 적용해야 하는 나머지 가상 게이트를 얼마나 실행 가능하게 만드는지에 따라 평가됩니다. 몇 가지 휴리스틱 비용 함수가 지원됩니다

• '기본':

전면_레이어에서 상호작용하는 가상 큐비트의 해당 물리적 큐비트에 대한 거리의 합계입니다.

$$H_{basic} = \sum_{gate \in F} D[\pi(gate.q_1)][\pi(gate.q2)]$$

• '룩어헤드':

이는 두 가지 비용의 합계입니다. 첫 번째 비용은 기본 비용과 동일합니다. 두 번째는 기본 비용이지만, 이제는 확장된 집합에 대해서도 평가됩니다(즉, $|E|$ 는 layer F에 있는 게이트 앞의 후속 게이트 수입니다). 이는 EXTENDED_SET_WEIGHT (W)라는 가중치를 적용하여, 뒤쪽 게이트들이 앞쪽 레이어보다 중요도가 낮음을 나타냅니다.

$$H_{decay}=\frac{1}{\left|{F}\right|}\sum_{gate \in F} D[\pi(gate.q_1)][\pi(gate.q2)] + W*\frac{1}{\left|{E}\right|} \sum_{gate \in E} D[\pi(gate.q_1)][\pi(gate.q2)]$$

• '쇠퇴':

이는 '룩어헤드'와 동일하지만 전체 비용에 감가상각 계수가 곱해집니다. 트라이얼 레이아웃을 생성한 스왑이 최근에 사용된 경우 비용이 증가합니다(즉, 깊이 증가에 불이익을 줍니다).

$$H_{decay} = max(decay(SWAP.q_1), decay(SWAP.q_2)) { \frac{1}{\left|{F}\right|} \sum_{gate \in F} D[\pi(gate.q_1)][\pi(gate.q2)]\\ + W *\frac{1}{\left|{E}\right|} \sum_{gate \in E} D[\pi(gate.q_1)][\pi(gate.q2)] }$$

속성

coupling_map

dist_matrix

is_analysis_pass

is_transformation_pass

메소드

execute

name

run

update_status