Single Query를 통한 Constant/Balanced 함수 판별 및 계산 복잡도 최적화

Context

함수 f(x)의 성질을 판별하기 위해 고전적 컴퓨팅에서는 최소 2회의 Query가 필수적인 구조적 한계 존재. 입력값에 따른 출력값의 일관성을 확인하는 과정에서 발생하는 시간 복잡도 최적화 필요성 대두.

Technical Solution

• Hadamard Gate를 통한 입력 상태의 Superposition 구축으로 모든 가능한 입력값을 동시에 처리하는 병렬성 확보
• Target Qubit을 |−⟩ 상태로 준비하여 Oracle 연산 결과를 Phase로 전이시키는 Phase Kickback 메커니즘 적용
• U_f Oracle 설계를 통해 |x⟩|y⟩ 상태를 |x⟩|y ⊕ f(x)⟩로 변환함으로써 함수 결과값을 위상 정보로 인코딩
• 최종 Hadamard Gate를 통해 위상 차이를 측정 가능한 0 또는 1의 상태로 변환하는 간섭 기반의 판별 로직 구현
• Constant 함수인 경우 위상 상쇄를 통한 0 출력, Balanced 함수인 경우 위상 보존을 통한 1 출력을 유도하는 구조 설계