2025-11-10T03:01:44.701257

Query Complexity of Classical and Quantum Channel Discrimination

Nuradha, Wilde

Quantum channel discrimination has been studied from an information-theoretic perspective, wherein one is interested in the optimal decay rate of error probabilities as a function of the number of unknown channel accesses. In this paper, we study the query complexity of quantum channel discrimination, wherein the goal is to determine the minimum number of channel uses needed to reach a desired error probability. To this end, we show that the query complexity of binary channel discrimination depends logarithmically on the inverse error probability and inversely on the negative logarithm of the (geometric and Holevo) channel fidelity. As a special case of these findings, we precisely characterize the query complexity of discriminating two classical channels and two classical-quantum channels. Furthermore, by obtaining an optimal characterization of the sample complexity of quantum hypothesis testing, including prior probabilities, we provide a more precise characterization of query complexity when the error probability does not exceed a fixed threshold. We also provide lower and upper bounds on the query complexity of binary asymmetric channel discrimination and multiple quantum channel discrimination. For the former, the query complexity depends on the geometric RÃ©nyi and Petz RÃ©nyi channel divergences, while for the latter, it depends on the negative logarithm of the (geometric and Uhlmann) channel fidelity. For multiple channel discrimination, the upper bound scales as the logarithm of the number of channels.

academic

고전 및 양자 채널 판별의 질의 복잡도

기본 정보

논문 ID: 2504.12989
제목: Query Complexity of Classical and Quantum Channel Discrimination
저자: Theshani Nuradha (Cornell University & University of Illinois Urbana-Champaign), Mark M. Wilde (Cornell University)
분류: quant-ph cs.IT cs.LG math.IT math.ST stat.TH
발표 시간: 2025년 10월 13일 (arXiv v3)
논문 링크: https://arxiv.org/abs/2504.12989

초록

본 논문은 질의 복잡도의 관점에서 양자 채널 판별 문제를 연구하며, 원하는 오류 확률을 달성하기 위해 필요한 최소 채널 사용 횟수를 결정하는 것을 목표로 한다. 연구 결과에 따르면 이진 채널 판별의 질의 복잡도는 오류 확률의 역수와 로그 관계를 가지며, 기하학적 및 Holevo 채널 충실도의 음의 로그와 반비례 관계를 가진다. 특수한 경우로서, 본 논문은 두 개의 고전 채널과 두 개의 고전-양자 채널의 질의 복잡도를 정확히 특성화한다. 양자 가설 검정 표본 복잡도의 최적 특성화를 획득함으로써, 오류 확률이 고정된 임계값을 초과하지 않을 때 더욱 정확한 질의 복잡도 특성을 제공한다. 또한 이진 비대칭 채널 판별 및 다중 채널 판별 질의 복잡도의 상한과 하한을 제시한다.

연구 배경 및 동기

문제 정의

양자 채널 판별은 양자 가설 검정의 일반화로, 미지의 채널의 정체성을 결정하는 것과 관련된다. 기존 연구는 주로 점근적 상황에서 오류 확률의 최적 감소율에 초점을 맞추었으나, 본 논문은 비점근적 상황에서의 질의 복잡도 문제에 초점을 맞춘다.

연구의 중요성

이론적 의의: 양자 채널 판별의 비점근적 분석 공백을 메우고, 표본 복잡도 관점에서 새로운 이론적 프레임워크를 제공
실용적 가치: 양자 학습 이론, 양자 계산 및 양자 알고리즘에서 중요한 응용 가능성
방법론적 기여: 이론 컴퓨터 과학의 질의 복잡도 개념을 양자 정보 이론에 도입

기존 방법의 한계

기존 연구는 주로 점근적 상황(n → ∞)에 집중
고정된 0이 아닌 오류 확률에서 최소 질의 횟수의 정확한 특성화 부재
다양한 유형의 채널에 대한 질의 복잡도의 통일된 이론적 프레임워크 부족

핵심 기여

세 가지 양자 채널 판별의 질의 복잡도 정의: 대칭 이진, 비대칭 이진 및 다중 채널 판별
양자 가설 검정의 표본 복잡도 경계 개선: 임계값 제약 조건 하에서의 최적 특성화 제공(정리 3)
대칭 이진 채널 판별의 타이트한 경계 획득: 오류 확률 및 채널 충실도에 관한 정확한 특성화(정리 8)
특수한 경우의 완전한 해결: 고전 채널 및 고전-양자 채널의 질의 복잡도 타이트한 특성화(추론 10, 12, 14, 15)
일반적인 경우로의 확장: 비대칭 채널 판별 및 다중 채널 판별의 상한과 하한(정리 16, 19)

방법 상세 설명

작업 정의

대칭 이진 채널 판별

두 개의 양자 채널 $\mathcal{N}$ 과 $\mathcal{M}$ 이 사전 확률 $p$ 와 $q = 1-p$ 로 선택된다. 질의 복잡도는 다음과 같이 정의된다: $n^*(p,\mathcal{N},q,\mathcal{M},\varepsilon) := \inf\{n \in \mathbb{N} : p_e(p,\mathcal{N},q,\mathcal{M},n) \leq \varepsilon\}$

여기서 $p_e$ 는 최적 오류 확률이다.

비대칭 이진 채널 판별

제1종 오류 확률을 $\varepsilon$ 이하로 제약하고 제2종 오류 확률을 최소화한다: $n^*(\mathcal{N},\mathcal{M},\varepsilon,\delta) := \inf\{n \in \mathbb{N} : \beta_\varepsilon(\mathcal{N}^{(n)}\|\mathcal{M}^{(n)}) \leq \delta\}$

다중 채널 판별

$M$ 개의 채널 중에서 미지의 채널을 식별한다: $n^*(\mathcal{S},\varepsilon) := \inf\{n \in \mathbb{N} : p_e(\mathcal{S},n) \leq \varepsilon\}$

핵심 기술 방법

1. 채널 충실도 및 산발도

논문은 다양한 양자 정보 측도를 사용한다:

기하학적 충실도: $\hat{F}(\rho,\sigma) = \inf_{\epsilon>0}(\text{Tr}[\rho^{(\epsilon)}\#\sigma^{(\epsilon)}])^2$
Holevo 충실도: $F_H(\rho,\sigma) = (\text{Tr}[\sqrt{\rho}\sqrt{\sigma}])^2$
기하학적 Rényi 산발도: $\hat{D}_\alpha(\rho\|\sigma)$
Petz-Rényi 산발도: $D_\alpha(\rho\|\sigma)$

2. 연쇄 법칙 및 데이터 처리 부등식

기하학적 Rényi 산발도의 연쇄 법칙을 활용한다: $\hat{F}(\mathcal{N}(\rho),\mathcal{M}(\sigma)) \geq \hat{F}(\mathcal{N},\mathcal{M})\hat{F}(\rho,\sigma)$

3. 적응형 전략 분석

다음을 포함한 가장 일반적인 적응형 전략을 고려한다:

임의의 초기 상태 준비
각 채널 사용 후의 적응형 연산
최종 양자 측정

기술적 혁신점

통일된 프레임워크: 다양한 유형의 채널 판별 문제를 통일된 질의 복잡도 프레임워크에 포함
타이트한 경계: 개선된 양자 Chernoff 경계 및 기하학적 방법을 통해 타이트한 상한과 하한 획득
최적 전략: 특정 경우(예: 고전-양자 채널)에 대해 곱 전략이 점근적으로 최적임을 증명
세밀한 분석: 사전 확률의 영향을 고려하여 모든 매개변수에 의존하는 정확한 특성화 제공

주요 이론적 결과

정리 8: 대칭 이진 채널 판별

$\max\left\{\frac{\ln\left(\frac{pq}{\varepsilon(1-\varepsilon)}\right)}{-\ln\hat{F}(\mathcal{N},\mathcal{M})}, \frac{1-\frac{\varepsilon(1-\varepsilon)}{pq}}{[d_{\hat{F}}(\mathcal{N},\mathcal{M})]^2}\right\} \leq n^*(p,\mathcal{N},q,\mathcal{M},\varepsilon)$

$n^*(p,\mathcal{N},q,\mathcal{M},\varepsilon) \leq \left\lceil\inf_{s\in[0,1]}\frac{\ln\left(\frac{p^s q^{1-s}}{\varepsilon}\right)}{C_s(\mathcal{N}\|\mathcal{M})}\right\rceil$

추론 10: 고전 채널의 타이트한 특성화

고전 채널의 경우, 질의 복잡도는 다음을 만족한다: $n^*(p,\mathcal{N},q,\mathcal{M},\varepsilon) = \Theta\left(\frac{\ln(1/\varepsilon)}{-\ln F(\mathcal{N},\mathcal{M})}\right)$

정리 13: 개선된 특성화

$p \in (0,1/2]$ 과 $\varepsilon \in (0,p/64)$ 조건 하에서: $\left\lceil\frac{1}{2}\frac{\lambda^*\ln(p/\varepsilon)}{-\ln\hat{Q}_{\lambda^*}(\mathcal{N}\|\mathcal{M})}\right\rceil \leq n^*(p,\mathcal{N},q,\mathcal{M},\varepsilon) \leq \left\lceil\frac{2\lambda^*\ln(p/\varepsilon)}{-\ln Q_{\lambda^*}(\mathcal{N}\|\mathcal{M})}\right\rceil$

여기서 $\lambda^* = \frac{\ln(q/\varepsilon)}{\ln(q/\varepsilon) + \ln(p/\varepsilon)}$ 이다.

실험 검증 및 응용

특수한 경우의 완전한 해결

고전 채널(추론 14)

고전 입출력 채널의 경우, 상한과 하한은 상수 인수 4만큼만 차이나며, 비점근적 최적성을 달성한다.

고전-양자 채널(추론 15)

곱 전략(최적 입력을 선택하고 텐서 거듭제곱 전략을 적용)이 오류 확률이 충분히 작을 때 최적임을 증명하며, 적응형 전략이 필요하지 않다.

다중 채널 판별(정리 19)

상한은 채널 수 $M$ 의 로그로 스케일된다: $n^*(\mathcal{S},\varepsilon) \leq \left\lceil\max_{m\neq\bar{m}}\frac{2\ln\left(\frac{M(M-1)\sqrt{p_m}\sqrt{p_{\bar{m}}}}{2\varepsilon}\right)}{-\ln F(\mathcal{N}_m,\mathcal{N}_{\bar{m}})}\right\rceil$