Quantum framework for Reinforcement Learning: Integrating Markov decision process, quantum arithmetic, and trajectory search

1. 문제 제기 (Problem)

강화학습 (RL) 은 로봇, 자율주행 등 복잡한 의사결정 문제를 해결하는 데 핵심적인 역할을 하지만, 고전적인 (Classical) RL 은 다음과 같은 한계를 겪고 있습니다.

• 차원의 저주: 상태 (State) 와 행동 (Action) 공간이 커질수록 계산 비용이 기하급수적으로 증가합니다.
• 계산 자원 및 시간: 확률적 환경에서의 학습은 방대한 계산 자원과 시간이 소요됩니다.
• 하이브리드 방식의 한계: 기존 양자 - 고전 하이브리드 방식은 양자와 고전 시스템 간의 통신 오버헤드가 발생하며, 양자 컴퓨팅의 잠재력을 완전히 활용하지 못합니다. 또한, 환경은 고전적으로 모델링되어 상호작용의 병렬성이 제한적입니다.

이러한 병목 현상을 해결하기 위해, 모든 계산이 양자 도메인 내에서 수행되는 완전한 양자 강화학습 (Full Quantum RL) 프레임워크의 필요성이 대두되었습니다.

2. 방법론 (Methodology)

이 논문은 고전적인 마르코프 의사결정 과정 (MDP) 을 완전히 양자화하여 에이전트와 환경의 상호작용, 보상 계산, 경로 탐색을 양자 원리만으로 구현합니다.

가. 양자 MDP 구현 (Quantum Implementation of MDP)

• 상태 및 행동 초기화: 고전적인 상태 ($S$) 와 행동 ($A$) 을 양자 비트 (Qubit) 로 인코딩합니다. 하디마드 (Hadamard) 게이트를 적용하여 모든 상태와 행동의 균일 중첩 (Uniform Superposition) 상태를 생성함으로써, 에이전트가 동시에 수많은 상태 - 행동 쌍을 탐색할 수 있게 합니다.
• 양자 상태 전이 (State Transitions): 고전적인 전이 확률 $P(s'|s, a)$를 양자 진폭 (Amplitude) 으로 인코딩합니다. 제어된 $R_y(\theta)$ 게이트를 사용하여 특정 상태 - 행동 쌍에 따라 다음 상태 레지스터에 회전 각도 $\theta$를 적용하여 전이 확률을 구현합니다.
• 양자 보상 함수 (Reward Function): CNOT 게이트를 활용하여 다음 상태에 따라 보상 레지스터를 조건부로 토글 (Flip) 하는 방식으로 보상을 인코딩합니다.

나. 다단계 에이전트 - 환경 상호작용

• 시간 단계 확장: $T$개의 시간 단계에 걸쳐 상호작용을 확장합니다. 각 단계에서 다음 상태 ($s'_{t}$) 는 CNOT 게이트를 통해 다음 시간 단계의 현재 상태 ($s_{t+1}$) 레지스터로 전달됩니다. 이를 통해 양자 중첩 상태에서 모든 가능한 경로 (Trajectory) 가 동시에 생성됩니다.
• 양자 회수 계산 (Return Calculation): 고전적인 할인된 보상의 합 ($\sum \gamma^t r_t$) 을 양자 산술 (Quantum Arithmetic) 회로를 통해 수행합니다. CNOT 및 Toffoli 게이트를 사용하여 각 시간 단계의 보상 레지스터를 순차적으로 더하고, 그 결과를 '회수 (Return)' 레지스터에 저장합니다.

다. 양자 경로 탐색 (Quantum Trajectory Search)

• 그로버 알고리즘 (Grover's Algorithm) 적용: 생성된 모든 양자 경로 중에서 누적 보상이 최대인 최적 경로를 찾기 위해 그로버 탐색 알고리즘을 사용합니다.
• 오라클 (Oracle) 설계: 경로가 최대 보상을 달성하는지 여부를 판별하는 오라클을 설계하여 해당 경로의 위상 (Phase) 을 반전시킵니다.
• 진폭 증폭 (Amplitude Amplification): 오라클과 증폭 연산을 반복하여 최적 경로의 측정 확률을 극대화합니다. 이는 고전적인 탐색보다 $O(\sqrt{N})$의 속도로 최적 경로를 찾습니다.

3. 주요 기여 (Key Contributions)

1. 완전 양자 RL 프레임워크: 에이전트, 환경, 상호작용, 보상 계산, 경로 탐색까지 모든 과정을 고전적인 보조 계산 없이 양자 도메인 내에서만 수행하는 최초의 통합 프레임워크를 제시했습니다.
2. 양자 MDP 모델링: 고전 MDP 의 상태 전이와 보상 구조를 양자 중첩과 양자 게이트 연산으로 정밀하게 재현하여, 고전적 확률 분포를 양자 진폭으로 매핑했습니다.
3. 양자 산술 기반 회수 계산: 고전적인 RL 의 핵심 요소인 '회수 (Return)' 계산을 양자 회로 (Quantum Arithmetic) 를 통해 구현하여, 모든 경로의 보상을 동시에 평가할 수 있게 했습니다.
4. 최적 경로 탐색 가속화: 그로버 알고리즘을 다단계 MDP 경로 탐색에 적용하여, 고정된 초기 상태뿐만 아니라 다양한 초기 조건에서도 최적 정책을 효율적으로 발견하는 방법을 입증했습니다.

4. 실험 결과 (Results)

• 시뮬레이션 환경: IBM Qiskit Aer 시뮬레이터 (Statevector) 를 사용하여 4 개의 상태 ($s_0 \sim s_3$) 와 2 개의 행동 ($a_0, a_1$) 으로 구성된 확률적 MDP 를 3 시간 단계 ($T=3$) 로 시뮬레이션했습니다.
• 정확성 검증:
  • 단일 상호작용 시뮬레이션에서 양자 회로의 상태 전이 확률과 보상 분포가 고전 MDP 와 정확히 일치함을 열지도 (Heat-map) 와 샘플 분포를 통해 확인했습니다.
  • 고전 Q-learning 알고리즘으로 학습한 최적 정책 (최대 보상 8) 과 양자 그로버 탐색이 찾은 최적 경로가 완전히 일치함을 확인했습니다.
• 성능 향상:
  • 샘플 효율성: 양자 중첩을 통해 한 번의 실행으로 모든 가능한 상호작용 시퀀스를 평가하므로, 고전적인 방법보다 환경 탐색에 필요한 상호작용 횟수가 현저히 줄어듭니다.
  • 탐색 속도: 그로버 알고리즘을 통해 최적 경로를 찾는 데 고전적인 반복 평가 없이 단일 오라클 호출로 근사적으로 최적 해를 찾을 수 있음을 보였습니다.
  • 다양한 시나리오: 고정된 초기 상태뿐만 아니라, 초기 상태가 불확실한 경우에도 그로버 탐색이 최대 보상을 주는 경로들을 성공적으로 식별했습니다.

5. 의의 및 중요성 (Significance)

• 이론적 기여: 강화학습의 모든 단계를 양자 원리로 재해석하고 구현함으로써, 양자 컴퓨팅이 기계학습 분야에서 가질 수 있는 잠재력을 실증적으로 보여줍니다.
• 실용적 응용 가능성:
  • 자율주행: 여러 주행 경로를 동시에 평가하고 최적의 충돌 회피 경로를 빠르게 탐색.
  • 헬스케어: 다양한 치료 계획을 병렬로 평가하여 최적의 치료법을 신속히 선정.
  • 금융: 실시간으로 다양한 투자 전략을 탐색하여 고수익 경로를 식별.
• 미래 연구 방향: 더 복잡한 MDP 로의 확장, 큐비트 재사용을 통한 리소스 최적화, 그리고 사전 지식 없이 최적 보상을 찾는 알고리즘 개발 등 양자 강화학습 (QRL) 의 실용화를 위한 기초를 마련했습니다.

결론적으로, 이 연구는 고전적인 계산의 한계를 극복하고, 양자 중첩과 양자 검색 알고리즘을 활용하여 강화학습의 효율성과 속도를 혁신적으로 향상시킬 수 있는 완전한 양자 프레임워크를 제시했다는 점에서 의의가 큽니다.