Tight bound for the total time in digital-analog quantum computation

기술 요약: 디지털-아날로그 양자 컴퓨팅의 총 시간에 대한 타이트한 상한(Tight Bound)

문제 정의
디지털-아날로그 양자 컴퓨팅(DAQC)은 자연스러운 얽힘 해밀토니안($H_S$) 하에서의 자유 진화와 단일 큐비트 게이트의 적용을 결합한 보편적인 패러다임이다. DAQC는 임의의 유니터리 연산을 시뮬레이션하는 견고한 프레임워크를 제공하지만, 핵심적인 자원 지표로서 특정 프로토콜을 실행하는 데 필요한 총 시간이 남아 있는 과제이다. 기존 연구들은 이 총 시간에 대해, 구체적으로 큐비트 수($n$)에 대해 이차적으로 스케일링되는 하위 최적(suboptimal) 상한을 설정했다. Baßler-Heinrich-Kliesch의 추측은 ZZ-Ising 해밀토니안에 대해 $n$에 비례하는 선형 스케일링을 제안했다. 그러나 이러한 상한의 정확한 타이트함과 일반적인 2-바디(two-body) 해밀토니안에 대한 거동은 미해결 상태로 남아 있었다. 본 논문에서 다루는 핵심 문제는 DAQC 프레임워크 내에서 임의의 타겟 해밀토니안($H_P$)을 시뮬레이션하기 위해 필요한 총 아날로그 시간($\|t_{opt}\|_1$)의 타이트한 상한을 결정하는 것이다.

방법론
저자들은 DAQC 프로토콜의 컴파일을 선형 대수 문제로 접근한다. 타겟($h_P$) 및 소스($h_S$) 해밀토니안의 결합(coupling)들을 벡터화함으로써, 최적의 아날로그 블록 시간($t$)의 시퀀스를 찾는 문제는 $M t = b$라는 선형 시스템을 푸는 문제로 환원된다. 여기서 $b = T (h_P \oslash h_S)$이며, $M$은 단일 큐비트 게이트(Pauli 또는 Clifford)에 의해 생성된 결합의 유효 부호를 나타내는 행렬이다.

타이트한 상한을 도출하기 위해, 저자들은 볼록 다면체(convex polytope)에 기반한 기하학적 관점을 채택한다:

1. 기하학적 해석: 행렬 $M$의 열들은 $\mathbb{R}^d$ 공간의 볼록 다면체의 꼭짓점(vertices)으로 취급된다 (여기서 $d$는 결합의 수). $t$를 구하는 것은 타겟 벡터 $b$를 이 꼭짓점들의 양의 선형 결합으로 표현하는 것에 해당한다.
2. 다면체 분석: 저자들은 이 다면체의 특성을 분석하며, 꼭짓점의 수는 $n$에 따라 지수적으로 증가하는 반면 차원은 오직 이차적으로만 증가한다는 점에 주목한다. 저자들은 $n$이 증가함에 따라 다면체가 고차원 구(ball)에 점점 더 가까워진다고 주장한다.
3. 재귀적 구조: $M(n+1)$이 $M(n)$과 부호 변화 행렬으로부터 구성되는 $M$의 재귀적 구조를 활용하여, 저자들은 최악의 경우의 총 시간이 원점으로부터 다면체 표면까지의 최소 거리와 관련하여 $n$에 따라 증가하는 방식으로 스케일링되지 않음을 입증한다.
4. 증명 전략: 증명은 두 단계로 구성된다. 먼저 ZZ 해밀토니안에 대한 상한을 확립한 후, 이를 임의의 2-바디 해밀토니안으로 일반화한다. 저자들은 최악의 시나리오가 추가적인 계수가 0으로 설정된 가장 작은 비자명한 시스템 크기(2 또는 3 큐비트)에 대응함을 식별한다.

주요 기여 및 결과

• 타이트한 상한 (Tight Upper Bound): 본 논문은 임의의 2-바디 해밀토니안을 시뮬레이션하는 모든 보편적 DAQC 프로토콜에 대해, 총 아날로그 시간이 다음과 같이 타이트하게 상한이 됨을 증명한다:
  $$\|t_{opt}\|_1 \leq T \sqrt{3} \|h_P \oslash h_S\|_2$$
  여기서 $T$는 타겟 진화 시간이고, $\| \cdot \|_2$는 결합 벡터의 유클리드 노름(Euclidean norm)을 나타낸다.
• 기존 추측의 반박: 저자들은 ZZ 해밀토니안에 대해 $n$에 따라 선형적으로 스케일링된다고 제안했던(홀수/짝수 $n$에 대해) Baßler-Heinrich-Kliesch 추측에 대한 반례를 제시하며, 상한이 $n$에 명시적으로 의존하는 대신 결합의 2-노름에 의존함을 보여준다.
• 스케일링 거동: 결과는 상한이 큐비트 수에 명시적으로 의존하지는 않지만, 최악의 시나리오(all-to-all 해밀토니안)에서 결합 벡터의 2-노름은 $n$에 따라 선형적으로 스케일링됨을 나타낸다. 이는 선형 스케일링에 대한 직관을 확인시켜 주는 동시에 더욱 정밀한 수학적 정식화를 제공한다.
• 수치적 검증: 최대 $n=10$ 큐비트에 대해 ZZ 및 임의의 2-바디 해밀토니안에 대한 광범위한 수치 계산이 수행되었다. 무작위 문제 분포와 특정 엣지 케이스(예: 축이나 면에 정렬된 문제)를 포함한 시뮬레이션은 도출된 상한이 타이트하며, 균등하게 무작위적인 문제들은 상한에 비해 아선형(sublinear) 거동을 보임을 확인시켜 준다.

의의
본 논문은 DAQC의 자원 추정에 관한 열린 문제를 해결했다고 주장한다. 타이트하고 명시적인 상한을 제공함으로써, 이 연구는 다음을 가능하게 한다:

1. 정밀한 자원 추정: 연구자들은 이제 DAQC 프레임워크 내에서 구현된 양자 시뮬레이션 및 알고리즘에 필요한 시간 자원을 정확하게 추정할 수 있다.
2. 엄격한 비교: 이 상한은 DAQC의 효율성을 완전 디지털 양자 컴퓨팅(DQC)과 같은 다른 패러다임과 엄격하게 비교할 수 있게 한다.
3. 오차 분석: 정밀한 시간 상한은 회로 컴파일에서의 오차 추정을 용이하게 하여, 최첨단 기술을 통한 트로터화(Trotterization) 오차의 식별 및 감소를 도울 수 있다.
4. 패러다임 발전: 결과는 상한이 시스템 크기(결합 노름을 통해)에 대한 선형 의존성을 가짐을 확인하며, DAQC가 확장 가능한 계산 패러다임으로서 유효함을 뒷받침한다.

저자들은 이러한 상한이 임의의 회전각 또는 고정된 단일 큐비트 회전각을 사용하는 경우와 관계없이 총 시간을 최적화하는 프로토콜에 적용된다고 강조하며, 파울리 게이트로 구성된 프로토콜가 이러한 변형들 중 최악의 시나리오를 나타낸다고 언급한다.