MBUndo: 양자 회로를 위한 정확하고 자동적이며 효율적인 측정 기반 언컴퓨테이션 (Measurement-Based Uncomputation)

임시 값으로 사용되는 앙실라(ancilla) 큐비트를 사용하는 양자 프로그램은 프로그램이 올바른 출력을 생성하도록 보장하기 위해 각 앙실라를 명시적으로 언컴퓨트(uncompute, 역계산)해야 합니다. 기존의 언컴퓨테이션 방식은 유니터리 양자 게이트(unitary quantum gates)를 사용하지만, 선도적인 양자 알고리즘들은 이제 비용이 많이 드는 유니터리 T 게이트를 더 저렴한 측정 및 위상 보정으로 대체하는 측정 기반 언컴퓨테이션(measurement-based uncomputation, MBU)을 활용합니다. 현재의 양자 프로그래밍 프레임워크는 Toffoli와 같은 특정 게이트를 언컴퓨트하기 위해 측정을 사용할 수 있습니다. 하지만, 표준 접근 방식을 통해 앙실라가 계산되고 언컴퓨트되는 임의의 회로를 받아 이를 MBU를 사용하도록 변환하는 자동적인 방법은 존재하지 않습니다. 연구자들은 대신 개별 회로 설계에 MBU를 수동으로 적용하는데, 이는 알고리즘 개발과 컴파일러 최적화를 제한합니다. 이러한 변환이 없었던 이유는 두 가지 근본적인 미지수 때문입니다: MBU가 적용되는 위치와 임의의 계산에 대해 MBU를 실현하는 게이트가 무엇인지입니다. 이를 해결하기 위해, 우리는 먼저 각 앙실라 큐비트에 대해 측정이 타당한(sound) 회로 위치를 식별하는 정적 분석(static analysis)을 제시합니다. 이는 MBU가 회로의 끝에서만 적용된다는 기본적인 가정을 포괄합니다. 다음으로, 우리는 유니터리 언컴퓨테이션 게이트를 측정 후 효율적인 위상 보정으로 타당하게 변환하는 회로 변환을 제시하는데, 이는 이전에 단일 게이트에 국한되거나 일반 회로에 적용할 수 없었던 기존 문헌의 리라이트 규칙(rewrite rules)을 일반화합니다. 우리는 회로를 측정 기반 언컴퓨테이션으로 자동으로 변환하는 통합 컴파일러 패스인 extsf{MBUndo}를 제시합니다. 이 도구는 기존의 언컴퓨테이션 합성기(uncomputation synthesizers)가 필요로 하는 큐비트 중 어떤 것이 앙실라인지에 대한 사용자 주석 외에는 아무것도 필요하지 않으며, 그들의 출력 회로를 향상시킬 수 있습니다. 우리는 extsf{MBUndo}를 22개의 벤치마크에서 평가하여 언컴퓨테이션 합성기에 비해 ${>}36.5$%의 T 게이트 감소율을 보여주었습니다.