양자 프로그램에서 여러 단언(Assertion)을 검사하는 시간-공간 복잡도

요약

양자 프로그램 테스트 및 디버깅을 위한 런타임 단언(Runtime assertions)의 시간-공간 복잡도를 분석합니다. 여러 개의 단언 검사는 추가 공간 사용이나 반복 실행이 필요하며, 이는 현재 양자 하드웨어 제약과 관련됩니다.

핵심 포인트

• 양자 프로그램 디버깅에 런타임 단언은 유망한 메커니즘입니다.
• 여러 단언 검사는 추가 공간(보조 큐비트) 또는 반복 실행이 필요합니다.
• 단순 전략은 $n$개의 보조 큐비트를 사용하고, 대안적 방법은 $n$회 반복 실행을 합니다.
• 두 방식 모두 시간-공간 복잡도는 $O(n)$으로 유지됩니다.