Training Variational Quantum Algorithms Is NP-Hard

Introduction

• 불모의 고원 현상은 초기 변수의 랜덤 설정, non-local한 관측값, 양자 게이트 구현의 노이즈로 인한 랜덤성으로 인해 발생할 수 있다.
• 다음과 같이 4가지 다른 관점으로 문제를 접근한다.
  1) 오라클을 사용해서 VQA 문제를 풀고, NP-Hard를 주장
  2) 오라클을 제거하고 클래식하게 효율적으로 풀 수 있는 시스템을 다룸
  3) 패러미터의 개수에 따라 다항 스케일로 증가하는 Hilbert space dim.을 갖는 양자 시스템을 고려.
  4) 3)에서 푼 문제가 QAOA 타입으로 제한했을 때, Hardness가 나타나는지 확인.

Complexity Theory

• VQA 최적화는 QCMA 클래스. QCMA는 양자 컴퓨터 상에서 클래식한 증명을 통해 검증이 가능한 문제 클래스.
• QMA는 양자 컴퓨터 상에서 양자 상태를 통해 검증이 가능한 문제 클래스. QCMA의 부분집합.
• MA, QMA, QCMA의 3자 상관관계는 아직 불분명함.
• 그러나, local Hamiltonian의 ground state energy를 찾는 것은 명백히 QMA-Hard. 즉, QCMA != QMA라면 VQA는 QCMA에 있는 문제만 해결이 가능하고 나머지 QMA에 존재하는 문제들은 해결이 불가능할 것.
• 이 논문의 요지는, VQA 안사츠가 적절한 eigenstates를 표현할 수 있다고 하더라도, 고전적인 최적화 과정이 여전히 NP-Problem을 푸는 것만큼 어려울 것임을 주장.

Problems

A Continuous MaxCut optimization

• 방향성 없이 0, 1로만 정의된 Adjacency matrix가 있다. 여기서 $\sum_{i \in S, j \in [d] \backslash S} A_{i, j}$ 를 최대화 하는 노드 집합 $S$를 찾아라.
• 당연하게도 NP-hard 이며, 추가로 APX-hard로 알려져 있다.