This work discusses the ability of constructing a quantum machine learning system that can be learned from noisy classical training samples. The learner constructs a hypothesis that is assumed to be the closest to answer from the training samples given in input-output form. This learning system can be formulated in the probably approximately correct (PAC) framework. In PAC learning, import measures of the performance are the sample and time complexity that corresponds to the minimum number of samples required to reach the goal and the run time of the system, respectively.
A noisy parity learning (LPN) problem is a well-known example of the PAC problem, which is the problem of learning parity from a uniformly randomly extracted input-output pairs. However, the parity learning problem is more difficult than the general PAC problem because the binary sequence that determines the parity must be exactly correct. Both classical and quantum LPN algorithms can easily solve LPN problems when there is no noise, but only quantum LPN algorithms solve the LPN problem efficiently when there is noise. Quantum LPN algorithms shows strong quantum advantage, such as robustness against errors and exponentially improved time complexity and sample complexity. Quantum LPN algorithms have the quantum advantage in presence of quantum parity oracle that produces all possible input-output pairs in an equal superposition state. However, the assumption of quantum parity oracle is very unrealistic. In this paper, we propose a quantum LPN algorithm learned from a limited number of noisy classical training samples and also retains the quantum advantage.
The proposed algorithm uses reinforcement learning system with quantum environment and classical agent. The algorithm introduces a guess quantum parity oracle, that produces all possible input and guessed output pairs. The performance of the algorithm is predicted using the loose mathematical verification and simulation results on classical computer.
The proposed quantum LPN algorithm is numerically verified that the sample complexity and time complexity are significantly reduced compared to the classical LPN algorithms. In addition, we confirmed that the proposed algorithm shows the comparable or enhanced performance than the classical LPN algorithms through simulations. In addition, the proposed algorithm is more robust against error than the classical LPN algorithms.
본 논문은 오류가 있는 고전적인 훈련 샘플들로부터 학습 가능한 양자 기계 학습 알고리듬 체계 구성 능력에 대하여 논한다. 학습자는 입력-출력 형태로 주어진 훈련 표본들로부터 가장 정답에 가깝다고 추측되는 가설을 학습한다. 이러한 학습 체계는 확률적으로 거의 정확한 답 찾기(PAC) 학습 체계와 같다. PAC 체계의 문제는 문제 해결의 위해 필요한 최소 표본의 수인 표본 복잡도와 문제 해결에 걸리는 시간인 시간 복잡도가 성능의 중요한 지표가 된다.
오류가 있는 패리티 학습(LPN) 문제는 상기한 문제의 유명한 예로써, 완전 무작위로 추출된 입력-출력 쌍으로부터 패리티를 학습하는 문제이다. 다만 패리티 학습 문제는 패리티를 결정하는 이진 수열을 정확하게 맞춰야하기에 일반적인 PAC 문제에 비해 어렵다. 오류가 없을 경우 고전 알고리즘과 양자 알고리즘 모두 LPN 문제를 쉽게 해결하지만, 오류가 있을 때는 양자 알고리즘만이 LPN 문제를 효율적으로 해결한다. 양자 알고리즘은 가능한 모든 입력 값에 대한 패리티 값을 출력하는 양자 패리티 오라클을 통해 오류에 대해 강인하고 시간 복잡도와 샘플 복잡도 역시 기하급수적으로 개선된 강력한 양자 우월성을 보여주지만, 양자 패리티 오라클이라는 가정 자체가 매우 비현실적이다. 때문에 본 논문에서는 한정된 수의 오류가 있는 고전적인 훈련 표본을 통해 학습할 수 있으며, 양자 우월성 또한 가지고 있는 양자 알고리즘을 제안한다.
제안하는 알고리즘은 양자 환경 상태와 고전적인 에이전트를 가지는 강화 학습 체계를 사용하였다. 알고리즘은 가능한 모든 입력 데이터에 대해 입력과 그에 대한 추측 패리티 쌍이 균등하게 중첩되어 있는 양자 상태를 출력하는 추측 양자 패리티 오라클을 사용한다. 느슨한 수준의 수학적 검증과 고전 컴퓨터를 통한 시뮬레이션 결과를 이용해 알고리즘의 성능을 예측하였다.
제안하는 양자 알고리즘은 고전적인 알고리즘에 비해 샘플 복잡도와 시간 복잡도가 두드러지게 감소함을 계수적으로 검증하였다. 또한, 제안하는 알고리즘이 고전 알고리즘과 같게 또는 그보다 좋은 성능을 보임을 시뮬레이션을 통해 확인하였다. 더불어 제안하는 알고리즘은 고전적인 알고리즘보다 오류게 대해 더욱 강인함을 확인하였다.
