Quantum effects on machine learning

Abstract

This thesis focuses on the synergy of integrating two computation science fields, quantum computation and machine learning, answering following two questions: (a) can a machine learn quantum algorithm in order to solve the lack of quantum algorithm which is the core of quantum computation, and (b) how can quantum phenomena lead lowering learning-complexity which is the major issue in machine learning? To answer the first question, we suggest a strategy where we employ machine learning to design quantum algorithm. We demonstrate that a ma- chine learns algorithm for Deutsch-Jozsa problem which is one of oracle- based problem. The found algorithm is obviously quantum, needing just a single query same as Deutsch-Jozsa algorithm; this performance is impossible in classical world. This thesis also concerns advantages in the learning by using quantum, which is the second question. We prepare two kinds of machines, classical and quantum machines. These two machines are equivalent except quantum superposition that is utilised only in the quantum one. We first compare learning-time which is a temporal resource often investigated in computational complexity. The learning-time is significantly little in the quantum machine compared to the classical one. We also evaluate Fisher information to define the required number of training samples for machines to learn. In this comparison, we show that the quantum machine needs less samples than classical one for much more concept. These advantages in the quantum machine originates quantum superposition.|본 논문은 양자전산과 기계학습의 결합으로 얻을 수 있는 효과를 다룬다. 양자정보처리를 이용한 양자계산이 고전계산으로는 구현하기 힘든 계산 능력을 보일 수 있음이 확인되면서 이에 대한 연구가 활발히 이루어 졌다. 그러나 인간의 사고방식은 고전적인 논리를 바탕으로 하고 있다. 이러한 사실은 양자 알고리즘 계발이 난해함을 의미 하며, 실제로 고전알고리즘에 비교하여 매우 적은수의 양자알고리즘이 존재한다. 이러한 양자알고리즘의 부족이 현재 양자 계산 분야가 직면하고 있는 문제이다. 한편, 기계학습은 기계에게 학습능력을 부여하는데 목적이 있다. 이러한 기계의 학습 능력은 프로그램 개발자의 노력을 덜어줄 수 있다. 하지만, 학습하고자 하는 문제의 크기가 커질 경우 계산에 필요한 자원이 크게 증가하게 된다. 양자전산과 기계학습의 결합을 통해 우리는 시너지를 기대할 수 있다. 기계학습의 학습능력을 통해 양자알고리즘 개발의 난해함이 해결될 가능성이 있으며, 반대로 양자전산의 계산능력이 기계학습의 계산복잡도 문제를 해결할 수 있을 것으로 예상된다. 본 논문에서는 이러한 기대를 바탕으로 다음 질문에 대해 고려해 볼 것이다. (가) 기계학습을 통해 양자알고리즘을 개발에 도움을 받을 수 있을까? (나) 양자효과가 기계학습에 어떠한 영향을 줄 수 있을까? 질문 (가)를 확인하기 위해 양자알고리즘 개발 전략을 제안한다. 관리자는 학습기계에게 문제에 대한 예시를 주고, 학습기계는 주어진 예시를 기반으 로 양자시스템의 파라미터를 수정하여 적절한 양자시스템을 구성한다. 이러한 양자시스템은 주어진 문제를 해결하기 위한 양자알고리즘으로 간주된다. 본 논문에서는 이러한 전략으로 도이치-조사 문제를 학습하는데 성공하였고, 학 습기계가 찾은 알고리즘은 고전알고리즘으로는 불가능한 계산능력을 보여줌을 확인하였다. 질문 (나)에 대한 분석을 위해 고전학습모델과 양자학습모델을 제시했다. 양자학습모델은 양자중첩을 사용하며, 고전학습모델은 고전확률론을 사용한다는 데에 차이점이 있으며, 이러한 차이점을 제외하면 두 모델은 동등하다. 먼저 두 모델의 계산 복잡도를 분석하였다. 계산복잡도의 분석을 위해 유한한 오류를 허용하는 영역을 고려했고, 양자 중첩에 의해 이 영역이 변화할 수 있음을 증명하였다. 이러한 영역의 변화는 양자변환의 위상에 영향을 받는다. 적절한 위상을 선택할 경우 이 영역을 극대화 할 수 있고 이로 인해 학습 속도가 증 가함을 확인하였다. 한편으로, 두 학습모델의 표본 복잡도를 분석하였다. 표본복잡도는 피셔정보량에 의해 결정되며, 양자학습모델에서 평균적으로 피셔정 보량이 크다는 것을 확인하였다. 즉, 양자학습모델이 더 낮은 표본 복잡도를 보인다. 본 논문에서 간단한 모델을 통해 양자학습 모델이 계산 복잡도와 표 본 복잡도 측면에서 고전학습모델에 비해 이득이 있음을 보였다. 또한, 이러한 이득은 양자중첩에 기인한 현상임을 확인하였다. 본 연구는 양자기계학습에서 양자현상이 학습에 어떠한 영향을 주는지 근 본적인 차원의 이해를 목적으로 한다. 보다 발전된 이해를 위해 보다 다양한 학습모델에서 다양한 양자현상에 대한 분석이 필요하다. 이러한 분석을 통 한 양자현상이 기계학습에 대한 기여를 이해하는 것은 양자기계학습 분야를 발전시키는데 핵심과제이다. 본 연구는 양자기계학습의 발전을 위한 연구의 시발점이 될 것이다.; this performance is impossible in classical world. This thesis also concerns advantages in the learning by using quantum, which is the second question. We prepare two kinds of machines, classical and quantum machines. These two machines are equivalent except quantum superposition that is utilised only in the quantum one. We first compare learning-time which is a temporal resource often investigated in computational complexity. The learning-time is significantly little in the quantum machine compared to the classical one. We also evaluate Fisher information to define the required number of training samples for machines to learn. In this comparison, we show that the quantum machine needs less samples than classical one for much more concept. These advantages in the quantum machine originates quantum superposition.