計算のクエリモデル

計算を数学的な観点でモデル化する際、私たちは通常、次の図が示すようなプロセスを想定しています。情報が入力として提供され、計算が行われ、出力が生成されます。

今日私たちが使うコンピューターは、常に入力を受け取り出力を生成しており、この図に示されていない形で私たちや他のコンピューターと相互作用しているのも事実です。しかし、この図の目的はコンピューターの継続的な動作を表現することではありません。 むしろ、計算の単純な抽象化を作り、個別の計算タスクに焦点を当てることを目的としています。 例えば、入力は数値、ベクトル、行列、グラフ、分子の記述、あるいはより複雑なものをエンコードし、出力は私たちが念頭に置いている計算タスクの解をエンコードします。

重要な点は、入力は通常バイナリ文字列の形式で計算に提供され、その一部も隠されないということです。

モデルの説明

計算のクエリモデルでは、上記のより標準的なモデルのように入力の全体が計算に提供されるわけではありません。 むしろ、入力は関数の形で利用可能になり、計算はクエリを行うことでその入力にアクセスします。 また、クエリモデルにおける計算は、入力のビット（またはビットのセグメント）への ランダムアクセス を持つものとして見ることもできます。

クエリモデルの文脈では、入力がオラクルまたはブラックボックスによって提供されると言うことがよくあります。 どちらの用語も、入力の完全な説明が計算から隠されており、それにアクセスする唯一の方法が質問をすることであることを示唆しています。 まるでデルフォイのオラクルに入力について相談しているようなものです。彼女は知っていることすべてを教えてくれるわけではなく、特定の質問にだけ答えます。 ブラックボックスという用語は、特に入力が関数で表されると考えるとき意味をなします。 関数の内部を覗いてその仕組みを理解することはできず、自分が選んだ引数で評価するだけです。

このレッスンでは、異なる記号を含む文字列ではなく、バイナリ文字列のみを扱います。そのため、以降では便宜上バイナリアルファベットを $\Sigma = \{0,1\}$ と書くことにします。 様々な計算問題について考えますが、すぐにいくつかの簡単な例を説明します。それらすべてにおいて、入力は次の形式の関数で表されます。

$$f:\Sigma^n \rightarrow \Sigma^m$$

ここで $n$ と $m$ は2つの正の整数です。 当然、$f$ の代わりに別の名前を選ぶこともできますが、このレッスン全体を通じて $f$ を使用します。

計算がクエリを行うとは、ある文字列 $x \in \Sigma^n$ が選択され、次に文字列 $f(x)\in\Sigma^m$ がオラクルによって計算に利用可能にされることを意味します。 量子アルゴリズムにおけるこれの正確な動作については後ほど説明します。クエリを重ね合わせで行うことができる、ユニタリ量子演算でこれが可能であることを確認する必要があります。しかし今は、高いレベルで直感的に考えることができます。

最後に、クエリアルゴリズムの効率を測る方法は単純です。それらが必要とするクエリの数を数えます。 これは計算の実行に必要な時間と関連していますが、クエリ以外の演算の時間を無視しており、またすべてのクエリをコスト1として扱っているため、全く同じではありません。 クエリ以外の演算も考慮に入れることは可能ですし（そのようにすることもあります）、クエリの数だけに注目することで物事をシンプルに保てます。

クエリ問題の例

ここにいくつかのクエリ問題の簡単な例を示します。

• OR。 入力関数は $f:\Sigma^n \rightarrow \Sigma$ の形式をとります（この問題では $m=1$）。タスクは、$f(x) = 1$ となる文字列 $x\in\Sigma^n$ が存在する場合に $1$ を出力し、そのような文字列が存在しない場合に $0$ を出力することです。関数 $f$ がランダムアクセスを持つ $2^n$ ビットのシーケンスを表すと考えると、この問題はこれらのビットのORを計算することです。

• パリティ。 入力関数は再び $f:\Sigma^n \rightarrow \Sigma$ の形式をとります。タスクは、$f(x) = 1$ となる文字列 $x\in\Sigma^n$ の数が偶数か奇数かを判定することです。 より正確には、集合 $\{x\in\Sigma^n : f(x) = 1\}$ の要素数が偶数の場合は $0$、奇数の場合は $1$ を出力する必要があります。関数 $f$ がランダムアクセスを持つ $2^n$ ビットのシーケンスを表すと考えると、この問題はこれらのビットのパリティ（または排他的OR）を計算することです。

• 最小値。 入力関数は、正の整数 $n$ と $m$ の任意の選択に対して $f:\Sigma^n \rightarrow \Sigma^m$ の形式をとります。必要な出力は、$\Sigma^m$ の辞書的順序（つまり、辞書順）で最初に来る文字列 $y \in \{f(x) : x\in\Sigma^n\}$ です。 関数 $f$ がランダムアクセスを持つ $2^n$ 個の整数（長さ $m$ の2進法の文字列としてエンコードされたもの）のシーケンスを表すと考えると、この問題はこれらの整数の最小値を計算することです。

入力に事前条件（プロミス）がある場合のクエリ問題も考えます。 これは、入力に何らかの保証が与えられており、その保証が満たされない場合に何が起こるかについては責任を負わないということを意味します。 このタイプの問題を説明する別の方法は、いくつかの入力関数（プロミスが満たされないもの）が「どうでもよい」入力として見なされると言うことです。 アルゴリズムが「どうでもよい」入力を与えられた場合、いかなる要件も課されません。

プロミスのある問題の一例を示します。

• 一意探索。 入力関数は $f:\Sigma^n \rightarrow \Sigma$ の形式をとり、$f(z) = 1$ となる文字列 $z\in\Sigma^n$ がちょうど1つ存在し、$x\neq z$ のすべての文字列 $x$ に対して $f(x) = 0$ であることが保証されます。タスクはこの一意な文字列 $z$ を見つけることです。

今述べた4つの例はすべて、自然な問題です。つまり、説明が容易であり、それらが生じるかもしれない様々な状況や文脈を想像できます。

対照的に、クエリ問題の中には全くこのような「自然」な問題でないものもあります。 実際、クエリモデルの研究においては、実際に誰かがそれを実際に解こうとするとは想像しにくい、非常に複雑で人工的な問題が考案されることがあります。 しかし、それはその問題が興味深くないということを意味しません。 一見わざとらしく不自然に思えるものが、予期しないヒントを提供したり、新しいアイデアを触発したりすることがあります。 サイモンのアルゴリズムに触発された、因数分解のためのショアの量子アルゴリズムはその好例です。 また、クエリモデルの研究において極端なケースを探ることも重要な部分であり、これにより量子計算の潜在的な優位性と限界の両方に光を当てることができます。

クエリゲート

回路で計算を記述する場合、クエリはクエリゲートと呼ばれる特殊なゲートによって行われます。

古典的なブール回路におけるクエリゲートを定義する最も単純な方法は、次の図が示すように、入力関数 $f$ を直接計算できるようにすることです。

クエリ問題のためのブール回路が作成される場合、入力関数 $f$ はこれらのゲートを通じてアクセスされ、回路が行うクエリの数は回路に現れるクエリゲートの数に過ぎません。 ブール回路自体の入力ワイヤは固定値に初期化されており、これはアルゴリズムの一部（問題への入力とは対照的に）と見なされるべきです。

例えば、$f:\Sigma\rightarrow\Sigma$ の形式の関数に対して、上記で説明したパリティ問題を解く古典的なクエリゲートを使ったブール回路は次のとおりです。

このアルゴリズムは2つのクエリゲートがあるため、2つのクエリを行います。 その仕組みは、関数 $f$ が2つの可能な入力 $0$ と $1$ に対してクエリされ、その結果がXORを計算するブール回路に入力されます。 （この特定の回路は、量子情報の基礎コースの量子回路レッスンでブール回路の例として登場しました。）

量子回路では、関数 $f$ の選択によってはこれらのゲートが非ユニタリになることがあるため、このクエリゲートの定義は機能しません。 そこで代わりに、次の図が示すように標準基底状態に対して動作するユニタリクエリゲートを定義します。

ここで、$x\in\Sigma^n$ と $y\in\Sigma^m$ は任意の文字列であることを前提としています。 表記 $y\oplus f(x)$ は2つの文字列のビット単位の排他的ORを指し、この場合長さ $m$ です。 例えば、$001 \oplus 101 = 100$ です。

直感的に言えば、ゲート $U_f$（任意の選択された関数 $f$ に対して）が行うことは、上部の入力文字列 $x$ をエコーし、関数値 $f(x)$ を下部の入力文字列 $y$ にXORすることです。これは関数 $f$ のあらゆる選択に対してユニタリ演算です。 実際、これは決定論的演算であり、それ自身の逆演算です。 これは、行列として、$U_f$ は常に置換行列であることを意味します。つまり、各行と各列に1つの $1$ があり、他のすべての要素が $0$ である行列です。 置換行列をベクトルに適用すると、単純にベクトルの要素をシャッフルします（したがって置換行列という用語）。そのため、そのベクトルのユークリッドノルムは変わらず、置換行列が常にユニタリであることが明らかになります。

クエリアルゴリズムがクエリの数を数えるだけで分析される場合、古典的および量子的の両バージョンで述べたクエリゲートを物理的に構築することの難しさを完全に無視していることを強調すべきです。 直感的に言えば、クエリゲートの構築は入力の準備の一部であり、解を見つけることの一部ではありません。

それは不合理に思えるかもしれませんが、私たちが実用的なコンピューティングを記述したり、必要なリソースを完全に説明しようとしているのではないことを念頭に置く必要があります。 むしろ、量子計算の潜在的な優位性に光を当てるのに役立つ理論的モデルを定義しています。 この点については、次のレッスンで入力がバイナリ文字列として回路に明示的に与えられるより標準的な計算モデルに注目する際に、さらに詳しく述べます。