On the Complexity of Finding Decoherence Free Subspaces

기술 요약: 결맞음 자유 부공간(Decoherence Free Subspaces) 탐색의 복잡성에 관하여

문제 정의
본 논문은 시간 독립적인 림블라디안 마스터 방정식(Lindblad master equation)에 의해 지배되는 주어진 열린 양자 시스템이 결맞음 자유 부공간(Decoherence Free Subspace, DFS)을 갖는지 여부를 결정하는 계산 복잡도를 조사한다. DFS는 순수 양자 상태들의 부분 공간으로 정의되며, 해당 상태들뿐만 아니라 그들 사이의 양자 결맞음(coherence)까지도 보존하며 시스템의 역학 하에서 안정적으로 유지된다. 저자는 이 탐구를 결정 문제(decision problems)로 공식화하며, 특히 $k$-국소 림블라디안 디시페이터(k-Local Lindbladian dissipator)가 1차원 DFS(순수 정상 상태)를 갖는지 묻는 k-Local Lindbladian Pure Steady-State 문제에 초점을 맞춘다. 또한, 저자는 림블라디안 역학 하에서의 순도 붕괴율(purity decay rates)을 계산하는 난이도와 관련된 k-Local Lindbladian 문제를 도입한다.

방법론
저자는 이러한 문제들을 분석하기 위해 양자 복잡도 이론, 특히 양자 머린 아서(Quantum Merlin Arthur, QMA) 클래스의 기법을 사용한다. 저자의 방법론은 다음과 같은 몇 가지 핵심적인 기술적 구성 요소로 이루어진다:

1. 축약(Reductions) 및 문제 정의:

   • k-Local Lindbladian Pure Steady-State 문제와 k-Local Lindbladian 문제를 정의한다.
   • 열린 시스템의 정상 상태와 닫힌 시스템의 바닥 상태 사이의 간극을 메우기 위해, Separable k-Local Hamiltonian 문제의 변형인 Symmetric Separable k-Local Hamiltonian*을 도입한다.
   • 이들 문제 사이의 축약을 확립하여, k-Local Lindbladian 문제가 Symmetric* Separable k-Local Hamiltonian 문제로 축약됨을 보여줌으로써, 전자가 QMA 클래스 내에 있음을 입증한다.

2. 난이도 구축 (키타에프의 시계(Kitaev's clock)의 일반화):

   • QMA-Hardness를 증명하기 위해, 키타에프의 시계 해밀토니안 구성을 열린 양자 시스템 환경으로 일반화한다.
   • 양자 회로(구체적으로 Quantum Circuit-SAT 문제)의 실행을 구축된 림블라디안의 정상 상태 부공간으로 인코딩한다.
   • 기존의 구성들이 혼합 히스토리 상태(mixed history states)만을 생성했던 것과 달리, 저자의 새로운 매핑은 혼합 상태와 순수 상태 히스토리 상태를 모두 포함하는 정상 부공간을 유도한다. 이는 두 상태 사이의 보간(interpolation)을 가능하게 하며, 순수 상태 붕괴를 분석하는 데 결정적이다.
   • 키타에프 구성의 해밀토니안 항들로부터 유도된 점프 연산자(jump operators)를 사용하여 "전파 디시페이터(Propagation Dissipator)"를 구축한다. 이 디시페이터는 회로 게이트의 올바른 전파를 검사한다.
   • 보조 큐비트의 초기화와 회로의 출력을 확인하기 위한 추가적인 디시페이터들을 설계한다. 출력 디시페이터는 회로가 거절(reject-case)할 경우 정상 상태 부공간을 혼합시키고, 수락(accept-case)할 경우 이를 보존하도록 설계되었다.

3. 기술적 도구:

   • 연산자-벡터 대응(Operator-Vector Correspondence): 특정 붕괴율을 갖는 순수 상태를 찾는 문제를 이중화된 힐베르트 공간($H \otimes H$)에서의 특정 "에너지"를 갖는 곱 상태(product state)를 찾는 문제로 매핑하기 위해, 연산자 공간 $B(H)$와 이중 힐베르트 공간 $H \otimes H$ 사이의 동형 사상을 활용한다.
   • 순수 상태 붕괴 투영 보조정리(Pure State Decay Projection Lemma): 림블라디안 역학 하에서 순수 상태의 붕괴율을 제한하기 위해 Kempe 등의 투영 보조정리를 적응시킨 일반화된 버전이다. 이 도구를 통해 저자는 누출(leakage)에 의한 오차를 제한하면서 분석을 특정 부공간(예: 히스토리 상태 부공간)으로 투영할 수 있다.
   • 단항 인코딩(Unary Encoding): 상수 국소성($k \ge 5$)을 달로하기 위해, 회로의 시계 레지스터를 이진(binary)이 아닌 단항(unary) 방식으로 인코딩한다. 이를 위해 유효한 시계 상태를 안정화하면서도 힐베르트-슈미트 내적에 대해 에르미트성을 보장하는 새로운 Hermitian k-Local Lindbladian 디시페이터를 사용한다.

주요 기여

1. 복잡도 분류:

   • k-Local Lindbladian Pure Steady-State 문제는 상수 $k \ge 5$에 대해 QMA1-Hard임이 밝혀졌다.
   • k-Local Lindbladian 문제는 상수 $k \ge 5$에 대해 QMA-Complete임이 밝혀졌다.
   • Symmetric Separable k-Local Hamiltonian* 문제는 상수 $k \ge 5$에 대해 QMA-Complete임이 밝혀졌다.

2. 새로운 매핑 및 구성:

   • 혼합 상태와 순수 상태 히스토리 상태를 모두 허용하는 림블라디안 디시페이터로의 새로운 양자 회로 매핑.
   • 유효한 시계 상태를 안정화하는 동시에 힐베르트-슈미트 내적에 대해 에르미트성을 보장하는 새로운 Hermitian 림블라디안 디시페이터.
   • 열린 양자 시스템에 적응된 "순수 상태 붕괴 투영 보조정리".

결과
본 논문은 일반적인 마르코프 열린 양자 시스템이 결맞음 자유 부공간을 갖는지 여부를 결정하는 것이, $\text{BQP} \neq \text{QMA}$라는 가정하에 양자 컴퓨터로도 계산 불가능함을 입증한다. 구체적으로:

• $k \ge 5$일 때, 순수 정상 상태(따라서 1차원 DFS)의 존재를 결정하는 것은 QMA1-Hard하다.
• 순도 붕괴율을 결정하는 것(k-Local Lindbladian 문제)은 QMA-Complete하다.
• 이 난이도는 림블라디안이 에르미트 점프 연산자에 의해 생성되는 경우에도 유효하다.

의의
저자는 이러한 결과가 결맞음 자유 부공간을 찾는 것이 양자 계산에 있어 매우 어렵다는 것을 시사한다고 주장한다. 이는 닫힌 시스템의 바닥 상태 구조에서는 특정 효율적인 알고리즘이나 근사법이 존재할 수 있는 반면, 열린 시스템의 정상 상태 구조는 근본적인 계산적 장벽을 제시한다는 점을 강조한다. 또한, 느리게 붕괴하는 순수 상태를 찾는 완화된 문제(순도 붕괴율을 1차까지 계산하는 것)조차도 여전히 계산적으로 불가능함을 보여준다.

본 연구는 해밀토니안 복잡도 이론을 열린 양자 시스템으로 확장하여, 로컬 해밀토니안의 바닥 상태 구조와 림블라디안의 정상 상태 구조 사이의 엄격한 연결을 확립한다. 저자는 $k \ge 5$에 대한 난이도는 입증하였으나, 더 낮은 국소성(예: $k=2$)에 대한 복잡도는 2-Local Hamiltonian 문제의 상태와 마찬가지로 여전히 미해결 과제로 남아 있다고 언급한다. 결론적으로, 이러한 난해성 결과는 물리적으로 유의미한 시스템에서 결맞음 자유 부공간의 존재 여부나 부재를 보장하는, 더 효율적으로 식별 가능한 조건들에 대한 탐색을 촉구한다.