Quantumly controlled measurement, Hermitian conjugation and normalization in matrix-manipulation algorithms

기술 요약: 행렬 조작 알고리즘에서의 양자 제어 측정, 에르미트 공액 및 정규화

문제 정의
본 논문은 기존의 행렬 조작 양자 알고리즘(특히 Ref. [33–35]에서 제안된, 행렬 요소를 순수 중첩 상태의 확률 진폭으로 인코딩하는 방식)이 가진 세 가지 결정적인 한계를 다룬다:

1. 사후 선택(Post-Selection)의 비효율성: 기존 알고리즘은 "가비지(garbage)" 상태를 필터링하고 원하는 결과를 선택하기 위해 단일 큐비트 보조 시스템(ancilla)을 측정하는 방식에 의존한다. 이 과정은 행렬 차원에 따라 다항식 또는 지수적으로 감소하는 낮은 성공 확률로 인해 문제가 된다. 결과적으로, 알고리즘은 원하는 결과를 얻기 위해 여러 번의 실행을 필요로 하며, 이는 효율성을 심각하게 저하시킨다.
2. 에르미트 공액(Hermitian Conjugation) 처리 불가능: 이러한 알고리즘들은 일반적으로 복소 행렬을 다룰 수 있지만, 에르미트 공액과 같은 특정 연산은 표준 인코딩 프레임워크 내에서 구현될 수 없어 대수적 조작의 다양성을 제한한다.
3. 엄격한 정규화 제약: 행렬 요소를 순수 양자 상태로 인코딩하는 것은 엄격한 정규화 조건($\sum |a_{jk}|^2 = 1$)을 부과한다. 이는 행렬 요소의 절댓값을 제한하며, 모든 응용 분야에 최적화된 스케일링을 어렵게 만든다.

방법론
저자들은 행렬 조작 프레임워크에 대한 세 가지 별도의 확장 방안을 제안한다:

1. 양자 제어 측정 (Quantumly Controlled Measurement, QCM):

   • 단일 보조 큐비트($B_1$)에 대한 표준 투영 측정 대신, 저자들은 두 큐비트 보조 시스템($B_1$ 및 $B_2$)을 도입한다.
   • 첫 번째 큐비트($B_1$)의 상태는 두 번째 큐비트($B_2$)에 적용되는 측정 연산자의 제어 역할을 한다.
   • 구체적으로, 시스템이 "유용한" 항이 $|1\rangle_{B_1}$과 얽혀 있고 "가비지" 항이 $|0\rangle_{B_1}$과 얽혀 있는 중첩 상태에 있을 때, C-NOT 게이트가 $B_1$과 $B_2$를 얽히게 한다. 그 후 제어 측정 연산자 $W^{(3)}_{B_1B_2} = |1\rangle_{B_1}\langle 1| \otimes M_{B_2} + |0\rangle_{B_1}\langle 0| \otimes I_{B_2}$가 적용된다.
   • 이 메커니즘은 유용한 성분이 존재할 경우($\alpha \neq 0$), 표준 사후 선택과 관련된 확률적 실패 없이 측정이 결정론적으로 트리거되어 시스템을 원하는 상태로 붕괴시킴을 보장한다.

2. 실수부와 허수부의 분리 인코딩:

   • 에르미트 공액을 가능하게 하기 위해, 저자들은 추가적인 1-큐비트 하위 시스템($M$)을 사용하여 실수부와 허수부를 두 개의 직교하는 부분 공간에 인코딩할 것을 제안한다.
   • 상태 $|0\rangle_M$은 실수부를 나타내고, $|1\rangle_{M}$은 허수부를 나타낸다.
   • 에르미트 공액은 행/열 레지스터에 대한 SWAP 연산과 $M$ 레지스터에 대한 $\sigma_z$ 연산을 결합하여 구현되며, 이를 통해 전치(transposition)와 복소 공액을 효과적으로 수행한다.

3. 완화된 정규화 제약:

   • 저자들은 인코딩 방식에 추가적인 보조 큐비트($K$)를 도입한다.
   • 초기 상태는 $|0\rangle_K$와 연관된 진폭 $b$를 가진 추가 항을 포함하도록 수정되며, 행렬 요소들은 $|1\rangle_K$와 연관된다.
   • 이는 정규화 조건을 등식($\sum |a_{jk}|^2 = 1$)에서 부등식($\sum |a_{jk}|^2 \leq 1$)으로 변경하여, 행렬 요소의 크기에 대해 더 큰 유연성을 제공한다.

주요 기여 및 결과

• 행렬 곱셈 구현: 저자들은 QCM과 두 가지 인코딩 확장을 행렬 곱셈 알고리즘에 통합한다. 이들은 알고리즘이 표준 곱셈뿐만 아니라 에르미트 공액이 포함된 연산(예: $A^\dagger B$, $A B^\dagger$)을 수행할 수 있음을 입증한다.
• 회로 구성: 다음을 위한 상세한 양자 회로가 제시된다:
  • QCM 서브루틴.
  • 에르미트 공액 연산자.
  • 세 가지 확장이 모두 포함된 수정된 행렬 곱셈 알고리즘.
• 복잡도 분석:
  • 공간 복잡도: 이러한 수정 사항은 단지 상수 개의 추가 큐비트(인코딩 확장을 위한 4개의 추가 큐비트와 곱셈 맥락에서의 QCM 보조 큐비트 1개)만을 요구한다. 공간 복잡도는 $N=2^n$ (행렬 차원)에 대해 $O(n)$을 유지한다.
  • 깊이(Depth): 회로 깊이는 $O(n)$을 유지한다. 저자들은 낮은 성공 확률을 극복하기 위한 반복 실행 필요성 때문에 이전 알고리즘들의 실제 총 실행 시간이 실질적으로 $O(2^n n)$이었던 반면, QCM 기반 알고리즘은 단 한 번의 실행으로 결과를 얻음으로써 회로 자체의 $O(n)$ 깊이 특성을 유지한다고 언급한다.
• 정규화 회수: 저자들은 QCM이 (이전의 측정 성공 확률로부터 도출되었던) 정규화 상수 $G$에 관한 확률적 정보를 제거한다는 점을 인정한다. 이들은 보조 상태 $|0\rangle_K$의 확률을 측정하기 위해 알고리즘을 여러 번 실행함으로써 $G$를 확률적으로 측정하는 방법을 제안하지만, 이는 단일 샷 결과 생성과는 별개의 실행 과정을 필요로 한다.

의의 및 주장
본 논문은 양자 제어 측정(QCM)의 도입이 측정 기반 양자 행렬 알고리즘에 내재된 "사후 선택 문제"를 근본적으로 해결한다고 주장한다. 가비지 상태를 확률적으로 필터링하는 대신 결정론적인 양자 제어 프로세스로 대체함으로써, 알고리즘은 반복 실행에 따른 지수적 오버헤드를 제거한다.

저자들은 QCM이 단순히 그로버(Grover) 알고리즘과 같은 진폭 증폭 기술이 아니라, 양자 제어와 고전적 측정을 결합한 구별된 연산자이며, 잠재적으로 새로운 유형의 "양자-고전 제어"를 제공한다고 강조한다.

또한, 에르미트 공액 및 완화된 정규화 제약에 관한 확장 사항은 더 넓은 범위의 복소 행렬 및 데이터 인코딩 시나리오에 대한 행렬 조작 알고리즘의 적용 가능성을 넓힌다. 저자들은 QCM의 실제 물리적 구현이 아직 표준 양자/고전 연산자의 관점에서 완전히 상세화되지는 않았으나, 그 이론적 정식화가 양자 중첩 상태의 실재성에 대한 정당성을 제공하며 더 효율적인 양자 선형 대수로 가는 경로를 제시한다고 밝힌다.

결론적으로, 본 논문의 이러한 수정 사항들은 행렬 곱셈뿐만 아니라 Ref. [34, 35]에서 논의된 행렬 덧셈, 행렬식 계산, 역행렬, 선형 시스템 솔버 및 기타 측정 기반 양자 알고리즘에도 적용될 수 있다.