감독 및 비감독 학습을 위한 최근접 이웃 방법에 대한 양자 알고리즘

우리는 최근접 이웃 학습 및 k-평균 클러스터링을 수행하기 위한 양자 알고리즘을 제시합니다. 우리의 알고리즘의 핵심은 유클리드 거리를 직접 계산하거나 내적을 통해 계산하는 빠르고 일관된 양자 방법이며, 이는 측정을 필요로 하지 않는 앰플리튜드 추정 방법과 결합됩니다. 우리는 이러한 거리 계산 및 특정 테스트 예제에 대한 최근접 벡터를 찾기 위해 필요한 입력 데이터에 대한 쿼리 수의 상한을 증명합니다. 최악의 경우, 우리의 양자 알고리즘은 몬테카를로 알고리즘에 비해 쿼리 복잡도의 다항식 감소로 이어집니다. 또한 우리는 여러 실제 이진 분류 작업에서 우리의 양자 최근접 이웃 알고리즘의 성능을 연구하고 분류 정확도가 고전적인 방법과 경쟁적이라는 것을 발견했습니다.