𝒌近傍探索のための量子アルゴリズム
A Quantum Algorithm for 𝑘-Nearest Neighbor Search

１．研究の目的
本研究では、データ数が𝑁のデータベース𝐷と検索質問データ（クエリ）𝑥が与えられたとき、クエリに最も近い𝑘個のデータを𝑂(√𝑘𝑁)の計算量で求めることができる量子アルゴリズム（量子コンピュータで動作するアルゴリズム）を提案する[1, 2]。この問題は𝑘近傍探索と呼ばれ、時間を掛ければ必ず解けるタイプの問

岩村 雅一 ( Masakazu Iwamura, Ph. D.)

題である。とはいえ、データ数𝑁の増加や次元数の増

大阪府立大学 大学院工学研究科 知能情報工学分野
准教授

加に伴い、大きな計算量が必要になるため、より小さな計算量で解くことができるアルゴリズムの開発が求(Associate Professor, Dept. of Computer Science and Intelligent
Systems, Osaka Prefecture University)

められる。量子コンピュータは、従来のコンピュータ

電子情報通信学会, 情報処理学会, IEEE, ACM
受賞：MIRU 学生優秀賞( 2018 年). MVA Best Paper Award (2017 年).
IAPR/ICDAR Young Investigator Award (2011 年). IAPR Nakano Award(Best Paper Award) ( 2010 年). ICFHR Best Paper Award ( 2010 年).
IAPR/ICDAR Best Paper Award ( 2007 年). 電子情報通信学会 論文賞(2006 年) 他
著書：Reading-Life Log as a New Paradigm of Utilizing Character andDocument Media, Springer (2017 年 )Camera-Based Document
Analysis and Recognition - 5th International Workshop, CBDAR 2013,
Revised Selected Papers, Springer (2014 年) (編集者) Camera-BasedDocument Analysis and Recognition - 4th International Workshop,CBDAR 2011, Revised Selected Papers, Springer (2012 年) (編集者) 他
研究専門分野：物体認識、物体検出、視覚障碍者支援（古典的コンピュータと呼ばれる）よりも高速に実行できることが期待されており、𝑘近傍探索においても同様の期待が持てる。
𝑘近傍探索の既存の量子アルゴリズム[3]がある。このアルゴリズムの計算量は提案手法と同じ𝑂(√𝑘𝑁)であるが、実現方法が大きく異なる。詳細は後述するが、既存手法は同じ方法を繰り返すことによってクエリの𝑘近傍を見つけるが、提案手法は 3 つの段階に分けてクエリの𝑘近傍を見つける。特に、第 2 段階の終わり
では、𝑘近傍よりも少し多い𝑘′近傍が𝑂(√𝑁 log 𝑘)の計算量で求まっている。そのため、この段階で出力すれば、近似𝑘近傍探索手法が実現できる可能性がある。

あらまし
𝑘近傍探索とは、検索質問データが与えられたとき、そ２．量子計算機と量子アルゴリズム

れに最も近い𝑘個のデータをデータベースから探し出

量子計算機は、量子イジングマシンモデルと量子ゲす問題である。この問題は、時間を掛けさえすれば必ートモデルの 2 種類に大別できる。前者は量子トンネず解ける。しかし、データベースの大規模化や高次元リング効果を利用して局所解を回避しながら特定の最化に伴い、計算時間が大きくなってしまう。この問題適化関数を最適化するものであり、量子アニーリングを高速に解くために、探索過程に近似を導入し、探索方式がよく知られている。後者は、量子ビットの状態誤りを許容するのが近似𝑘近傍探索である。本研究でを別の状態に遷移できる量子ゲートを組み合わせるこは、従来用いられている計算機（古典的コンピュータ）とにより問題を解くことを目指すものである。使用すではなく、量子コンピュータで動作する𝑘近傍探索手る量子ゲートが増えると、ノイズの蓄積や、重ね合わ法の量子アルゴリズムを提案する。提案手法は、デーせやもつれ状態が解消されやすくなり、精度が下がる

タ数が𝑁のとき、𝑂(√𝑘𝑁)の計算量で解を求めることがという技術的課題があるが、前者と比較すると、よりできる。同じオーダーの計算量を持つ既存の量子アル広い範囲の応用が期待できる。代表例として IBM Q がゴリズムもあるが、提案手法は近似計算に適用できる知られている。本研究では後者を使用する。

可能性を持つ。

量子コンピュータが従来用いられている古典的コン
ピュータと大きく異なるのは、複数の状態を同時に保持して計算できることである。古典的コンピュータで1TELECOM FRONTIER No.107 2020 SPRING𝒌近傍探索のための量子アルゴリズム
A Quantum Algorithm for 𝑘-Nearest Neighbor Search

は、データをその最小単位であるビットの組み合わせで表現する。1 ビットは 0 または 1 の状態を保持でき・Finding Minimum (FM) [4]る。それに対して、量子コンピュータで用いる「量子これは与えられたデータの中から最小値を持つものビット」は 0 と 1 が確率的に混じった状態を表現できを発見するアルゴリズムである。図１に概念図を示す。

るため、複数の状態を重ね合わせて、それらに対してこの手法では、閾値𝑡を設定して、その閾値よりも小さ一度の処理で計算できる。そのため、このような処理い値を持つデータにマークをする関数（オラクル）𝑓(𝑥)を上手く使えれば、高速な処理が期待できる。ただし、を用いる。すなわち、データの値が閾値𝑡よりも小さい

量子コンピュータ特有の状態の重ね合わせが可能なのときに𝑓(𝑥) = 1となり、それ以外は𝑓(𝑥) = 0となる。こは、状態の観測前だけであることに注意が必要である。のとき、𝑓(𝑥) = 1となったデータから 1 つ選んで新し

すなわち、量子ビットの状態を観測する前は、0 と 1い閾値にすれば、前の閾値よりも値が小さくなる。そが確率的に重なった状態であるが、観測した瞬間に、こで、閾値𝑡の初期値をランダムに設定してから、この確率 1 で特定の状態に決まってしまう。この制約から、処理を繰り返すことで最小値を発見できる。このアル多くの量子アルゴリズムの出力は 1 つである。もし複ゴリズムはオラクルを𝑂(√𝑁)回呼び出すため、計算量数の出力が必要であれば、何度も量子ビットの状態をは𝑂(√𝑁)である。なお、𝑓(𝑥)の適用を何度も繰り返す観測する必要があるため、その分計算量が増加してし処理は、Amplitude Amplification (AA) [5]と呼ばれるまい、量子コンピュータを使う利点が失われる。本研

よく用いられる量子アルゴリズムである。これはよく究で実現する𝑘近傍探索は𝑘個の出力が必要なため、そ知られた Grover の探索アルゴリズム[6]の一般化であれをいかに実現するかが 1 つの工夫ポイントである。

る。

量子ゲートモデルの量子アルゴリズムでは、その実

この Finding Minimum アルゴリズムはデータの最行に要する量子ゲートの数を基準に計算量を求める方小値を発見するものであり、クエリに近いデータを探法と、オラクルと呼ばれる関数が何回呼ばれるかを基すものでは無い。しかし、データとしてクエリとデー準に計算量を算出する方法がある。ここでオラクルは、タとの距離を与えることで、最近傍探索手法として用中見や実装は未知であっても、望んだ答えを出してくいることができる。

れる関数のことを表す。本稿では、基本的にオラクルの呼び出し回数を基準に計算量を算出する。
２．関連アルゴリズム
２．１ 既存の𝒌近傍探索の量子アルゴリズム
既存の𝑘近傍探索の量子アルゴリズムである
Finding 𝑘-Minimum アルゴリズム [3]を紹介する。
その準備として、Finding Minimum アルゴリズム

図２：Finding 𝑘-Minimum アルゴリズムの既存手法[3][4]を紹介する。と提案手法
・Finding 𝑘-Minimum (F𝑘M) [3]Finding Minimum アルゴリズムの出力を𝑘個に拡張したものであり、既存の𝑘近傍探索の量子アルゴリ

図１：Finding Minimum アルゴリズムの概要[4]2TELECOM FRONTIER No.107 2020 SPRING𝒌近傍探索のための量子アルゴリズム
A Quantum Algorithm for 𝑘-Nearest Neighbor Search

ズム1である。このアルゴリズムの処理の概要を図２の左側に示す。この図は、後で説明する提案手法と同じ・Search All Marked 𝑘-indices (SAMkI) [9–13]

入力に対して処理がどう違うかを表した図であり、既これは AA アルゴリズムにおいて𝑓(𝑥) = 1となった

存手法は図の中央にあるデータが入力されて、処理が要素を全て取り出すアルゴリズムである。いま、𝑁個左側に進む。このアルゴリズムを一言で言えば、前述のデータのうち𝑘個について𝑓(𝑥) = 1であるとする。その FM アルゴリズムにおいて閾値を𝑘個同時に用いるして、𝑘個のデータ全てを取り出したいとする。このとものである。すなわち、𝑘個の閾値（図中では、その集き、𝑘個のデータのどれか 1 つを取り出す処理に要す合を𝑇と表す）から１つを選び、それに対して FM アる計算量は𝑂(√𝑁/𝑘)である。この処理の後、𝑁 − 1個のルゴリズムを実行する。この処理を繰り返し、前述のデータが残り、そのうち𝑘 − 1個が𝑓(𝑥) = 1である。簡

オラクル𝑓(𝑥)を𝑂(√𝑘𝑁)回適用することにより、𝑘個の単のため、𝑁個のデータが残り、そのうち𝑘 − 1個が閾値は𝑘個の最小値にたどり着くことが期待できる。

𝑓(𝑥) = 1であるとしよう。このとき、𝑘 − 1個のどれかなお、このアルゴリズムを効率よく実行するためには、1 つを取り出す処理に要する計算量は𝑂(√𝑁/(𝑘 − 1))

毎回閾値集合𝑇の最大の閾値を選んで、より小さい閾である。これを繰り返すと、計算の過程は省略するが、値に更新するのが良い。しかし、これを実現しようと𝑁𝑁𝑁√ +√+ ⋯ + √ = 𝑂(√𝑘𝑁)𝑘𝑘−1
1

すれば、大きな計算量を要する閾値のソートが必要になるため、更新する閾値はランダムで選ぶと考えられる。また、閾値同士が同じ値にならないような工夫もが得られる。したがって、SAMkI アルゴリズムの計算必要である。

量は𝑂(√𝑘𝑁)である。

前述のように、量子アルゴリズムは 1 度の観測で 1つの値しか出力できないため、通常多数の値を出力で３．提案手法きない。実は、このアルゴリズムは𝑘個の「閾値」を出提案する𝑘近傍探索手法の処理の概要を図２の右側力するものであるというのがミソである。つまり、閾に示す。この図は処理が右側に進む。提案手法は、既値は別途外部メモリにでも保持しておけば、量子状態存の𝑘近傍探索手法が単一の処理（FM アルゴリズムのの観測は 1 回であっても、所望の解が得られるというオラクル𝑓(𝑥)の呼び出しとそれに付随する処理）を繰考え方である。

り返すのとは異なり、大きく３つの処理を順に実行することで𝑘近傍探索を実現する。

２．２ 本研究で利用するアルゴリズム

提案方法は、FM アルゴリズムを一度実行すると、本研究で利用する量子アルゴリズムを紹介する。

その副産物として、「閾値の軌跡」が得られるというアイディアに基づく。ここで FM アルゴリズムを用いて・Quantum Counting (QC) [7,8]

データの最小値を求める過程を見てみよう。最初の閾

これは AA アルゴリズムにおいて𝑓(𝑥) = 1であるデ値はランダムに決まるため、何番目に小さいデータがータの個数𝑐を数える量子アルゴリズムである。

閾値になっているのかがわからない。しかし、2 回目

Amplitude Estimation (AE) [5]と呼ばれる、データのに実行すれば、少なくとも最初の閾値よりも小さい値𝑐𝑓(𝑥) = 1である確率 を求めるアルゴリズムがある。こになっていることが保証できる。FM アルゴリズムはれを利用して得られた確率に𝑁を乗じることにより、𝑐これを何度も繰り返すことで最小値を求める。このよが得られる。AE の計算量が𝑂(√𝑁)であるため、QC のうに、求まる閾値がどんどん小さくなり、降順に並ん計算量も𝑂(√𝑁)である。

でいることがわかる。そして、閾値より値が小さいデ1が、特殊な場合として k 近傍探索にも適用可能である。

𝑁

このアルゴリズムは、個々のデータが属性を持つという、より複雑な状況のために提案された手法である
3TELECOM FRONTIER No.107 2020 SPRING𝒌近傍探索のための量子アルゴリズム
A Quantum Algorithm for 𝑘-Nearest Neighbor Search

ータ数が単調に減少する。このことを利用すれば、閾

𝑂 (√(𝑘 − 1)𝑁) = 𝑂(√𝑘𝑁)であり、𝑂(√𝑘𝑁)の計算量で値より値が小さいデータ数が大凡𝑘個のところをうまく取れないか？というのが提案手法のアイディアであ実現できることが分かる。

る。この考え方に沿って、𝑘よりも少し多い𝑘’個のデー

したがって、提案手法を構成する FM アルゴリズム、タ（𝑘 ≥ 𝑘）を得ることを考える。FM アルゴリズムをQC アルゴリズムを用いる二分探索、SAMkI アルゴリ

実行すれば、𝑖番目の閾値より値が小さいデータが𝑘個ズムの計算量を合計すれば、′以上であり、𝑖 + 1番目の閾値より値が小さいデータが𝑂(√𝑁) + 𝑂(√𝑁 log 𝑘) + 𝑂(√𝑘𝑁) = 𝑂(√𝑘𝑁)となり、提案手法の計算量は𝑂(√𝑘𝑁)となる。

𝑘個より少ないという状況が必ず存在する。ここで𝑖番目の閾値より値が小さいデータの個数を𝑘’とおく。一端𝑘’個のデータが求まれば、𝑘’個のデータに対して部４．まとめ分ソートを実行することで、値が小さい𝑘個のデータ本研究では、𝑂(√𝑘𝑁)の計算量で実現できる𝑘近傍が得られる。これが提案手法の概要である。

探索の量子アルゴリズムを提案した。提案手法は既存

では、どのようにちょうど良い閾値（前述の𝑖番目の手法と異なり、3 つの処理に分けて𝑘近傍探索を実現閾値）を見つければ良いか。FM アルゴリズムを実行する。そのため、途中で処理を止めれば、少ない計算すれば、F𝑘M のように、閾値の系列を記録しておくこ量で近似𝑘近傍探索が実現できる可能性がある。このとができる。しかし、ある閾値より小さい値がいくつ検討が今後の課題である。

あるかは、自明では無い。これを実現するのが、前述

なお、本稿の図は共同研究者である宮本康平氏がの QC アルゴリズムである。ただ、QC アルゴリズム[1] の発表に用いたポスター

は一度の実行に𝑂(√𝑁)の計算量を要するため、できる（http://www.m.cs.osakafu-だけ実行回数を減らしたい。そこで二分探索を用いる。

u.ac.jp/publication_data/1681/AQIS2019_poster.pdf

すなわち、二分探索で良い閾値を探しつつ、それが良）から抜粋して修正したものである。

い閾値かどうかは QC アルゴリズムで確認する。閾値の数は、オラクル𝑓(𝑥)の実行回数と等しいため、𝑂(√𝑁)参考文献個である。閾値は整列済みで、降順に並んでいる。し[1] Kohei Miyamoto, Masakazu Iwamura and Koichi

たがって、通常であれば、データ数O(√𝑁)のデータにKise, "A Quantum Algorithm for Finding k-

対する二分探索の計算量は𝑂(log √𝑁) = 𝑂(log 𝑁)であMinima", Proc. 19th Asian Quantum Information

る。しかし、我々が欲しい𝑘個のデータを求めるには、Science Conference (AQIS2019), 2019.

値が小さい方から最悪でも𝑘個の閾値を探索すれば事[2] Kohei Miyamoto, Masakazu Iwamura and Koichi足りる。 したが って、二 分探索に 要する 計算量 はKise, "A Quantum Algorithm for Finding k-𝑂(log 𝑁)ではなく、𝑂(log 𝑘)である。QC アルゴリズム

Minima",の計算量𝑂(√𝑁)と掛け合わせることで、閾値を求める[quant-ph], 2019.

arXiv

preprint

arXiv:1907.03315[3] Christoph Dürr, Mark Heiligman, Peter Høyer,のに𝑂(√𝑁 log 𝑘)の計算量が必要とわかる。

and Mehdi Mhalla. Quantum query complexity of

最後に、𝑘’個のデータが得られた後の処理を考える。
最初に FM アルゴリズムを実行しているので、値が一some番小さいデータは既に判明している。そのため、残る

Computing, 35(6):1310–1328, 2006.

graphproblems.

SIAM

Journalon𝑘’ − 1個のデータの中から、値が小さい𝑘 − 1個のデー[4] Christoph Dürr and Peter Hyer. A quantum

タを見つける必要がある。これには SAMkI アルゴリ

algorithm for finding the minimum. arXiv

ズムを用いる。簡単のために、𝑘’ − 1ではなく、それよpreprint quant-ph/9607014, 1996.

り大きい𝑁個のデータから𝑘 − 1個のデータを見つけ[5] Gilles Brassard, Peter Høyer, Michele Mosca, andる場合を考えると、この処理に要する計算量はAlain Tapp. Quantum amplitude amplification
4TELECOM FRONTIER No.107 2020 SPRING𝒌近傍探索のための量子アルゴリズム
A Quantum Algorithm for 𝑘-Nearest Neighbor Searchand estimation. In Jr. Samuel J. Lomonaco,
editor, Quantum Computation and Quantum
Information, volume 305, pages 53–74. American
Mathematical Society, 2002.
[6] Lov K. Grover. A fast quantum mechanicalalgorithm for database search. In Proceedings ofthe twenty-eighth annual ACM symposium on
Theory of computing, pages 212–219, 1996.
[7] Gilles Brassard, Peter Høyer, and Alain Tapp. Quantumcounting. In International Colloquium on Automata,Languages, and Programming, pages 820–831. Springer,
1998.
[8] Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain
Tapp. Quantum amplitude amplification and estimation.
InJr.

SamuelJ.

Lomonaco,editor,Quantum

Computation and Quantum Information, volume 305,pages 53–74. American Mathematical Society, 2002.
[9] Esma Aïmeur, Gilles Brassard, and Sébastien Gambs.
Quantum speed-up for unsupervised learning. Machine
Learning, 90(2):261–287, 2013.
[10] Andris Ambainis. Quantum search algorithms. ACM
SIGACT News, 35(2):22–35, 2004.
[11] Andris Ambainis. A new quantum lower bound method,with an application to strong direct product theorem forquantum search. arXiv preprint quantph/0508200, 2005.
[12] Hartmut Klauck, Robert Spalek, and Ronald De Wolf.
Quantum and classical strong direct product theorems
and optimal time-space tradeoffs. SIAM Journal on
Computing, 36(5):1472–1493, 2007.
[13] Sebastian Dörn and Thomas Thierauf. A note on thesearch for k elements via quantum walk. Information
Processing Letters, 110(22):975–978, 2010.
この研究は、平成２７年度ＳＣＡＴ研究助成の対象として採用され、平成２８～３０年度に実施されたものです。

5TELECOM FRONTIER No.107 2020 SPRING