計算コストの測定

次に、計算コストを測定するための数学的な枠組みを説明します。本コースの目的に絞った内容となっています。 アルゴリズムの解析と計算複雑性はそれぞれ独立した分野であり、これらの概念についてさらに多くのことを述べています。

出発点として、前のレッスンで登場した以下の図を考えてみましょう。これは計算の非常に高レベルな抽象的表現です。

計算そのものは、Pythonで書かれたコンピュータプログラム、チューリングマシン、ブール回路、量子回路など、さまざまな方法でモデル化・記述できます。 本コースでは（ブール回路と量子回路の両方を含む）回路に焦点を当てます。

エンコードと入力長

まず、計算問題の入力と出力について考えます。ここでは入力と出力が二進文字列であると仮定します。 他の記号を使うこともできますが、この説明では二進文字列の入出力に限定してシンプルに保ちます。 二進文字列を通じて、解きたい問題に関係する様々な興味深いオブジェクト（数値、ベクトル、行列、グラフ、あるいはそれらのリストなど）をエンコードすることができます。

たとえば、非負整数をエンコードするには二進表記を使うことができます。 以下の表は、最初の9つの非負整数の二進エンコードと、各エンコードの長さ（つまりビットの総数）を示しています。

数値	二進エンコード	長さ
0	0	1
1	1	1
2	10	2
3	11	2
4	100	3
5	101	3
6	110	3
7	111	3
8	1000	4

必要に応じて符号ビットを付加することで、正の整数だけでなく負の整数も扱えるようにこのエンコードを簡単に拡張できます。 また、非負整数の二進表現に先頭のゼロを許すことが便利な場合もあります。先頭ゼロはエンコードされた値を変えませんが、固定サイズの文字列やワードを埋めるために利用できます。

非負整数を表すために二進表記を使うのは一般的かつ効率的ですが、好みに応じて以下の表のような別の方法で二進文字列を使って非負整数を表すこともできます。 これらの代替手段の詳細はここでは重要ではありません。ポイントは、使用するエンコード方式に選択の余地があるということを明確にすることだけです。

数値	単項エンコード	辞書式エンコード
0	$\varepsilon$	$\varepsilon$
1	0	0
2	00	1
3	000	00
4	0000	01
5	00000	10
6	000000	11
7	0000000	000
8	00000000	001

（この表において、記号 $\varepsilon$ は空文字列を表します。空文字列は記号を含まず、長さはゼロです。当然ながら、わかりにくさを避けるために、何も書かないのではなく $\varepsilon$ のような特別な記号を使って空文字列を表します。）

ベクトルや行列、あるいは分子の記述のようなより複雑なオブジェクトなど、他の種類の入力も二進文字列としてエンコードできます。 非負整数の場合と同様に、さまざまなエンコード方式を選択したり考案したりできます。 与えられた問題への入力をエンコードするためにどのような方式を採用しても、入力文字列の長さは解かれる問題インスタンスの規模を表すものとして解釈されます。

たとえば、非負整数 $N$ を二進表記で表すために必要なビット数は、$\operatorname{lg}(N)$ と表記されることがあり、以下の式で与えられます。

$$\operatorname{lg}(N) = \begin{cases} 1 & N = 0\\ 1 + \lfloor \log_2 (N) \rfloor & N \geq 1 \end{cases}$$

整数因数分解問題の入力を二進表記でエンコードすると仮定すると、数値 $N$ の入力長は $\operatorname{lg}(N)$ になります。 特に注目すべき点は、入力 $N$ の長さ（または規模）は $N$ そのものではないということです。$N$ が大きい場合でも、二進表記で $N$ を表すためにこれほど多くのビットは必要ありません。

厳密に形式的な観点からは、計算問題やタスクを考える際には必ず、入力として与えられたり出力として生成されたりするオブジェクトをエンコードするための具体的な方式が選択されていると理解する必要があります。 これにより、興味深い問題を解く計算を、二進文字列入力から二進文字列出力への変換として抽象的に捉えることができます。

オブジェクトを二進文字列としてエンコードする方法の詳細は、ある程度はこれらの計算において重要です。 しかし通常、計算コストを分析する際にはこれらの詳細についてあまり気にしません。これは、二次的に重要な詳細への深入りを避けるためです。 基本的な考え方は、「合理的な」エンコード方式間で変換する計算コストは、実際の問題を解くコストに比べてわずかであると期待されるというものです。 そうでない場合には、詳細を（必要に応じて）明確にすることができます。

たとえば、非常に単純な計算で、非負整数の二進表現とその辞書式エンコード間の変換（詳細は説明していませんが、上の表から推測できます）ができます。このため、整数因数分解の計算コストは、入力 $N$ にどちらのエンコードを使うかを切り替えても大きく変わりません。 一方、単項表記で非負整数をエンコードすると、必要な記号の総数が指数関数的に膨れ上がります。そのため、これは「合理的な」エンコード方式とは見なされません。

基本演算

次に、上の図で青い長方形として表された計算そのものを考えましょう。 計算コストを測定する方法として、各計算が必要とする基本演算の数を数えます。 直感的には、基本演算とは少数の固定されたビットまたは量子ビットを扱い、ANDの演算のように素早く簡単に実行できる演算のことです。 一方、factorint 関数を実行することは基本演算とは合理的に見なせません。

形式的には、基本演算として何を採用するかは使用する計算モデルによって異なります。 ここでは回路モデル、特に量子回路とブール回路に焦点を当てます。

万能ゲートセット

回路ベースの計算モデルでは、通常、各ゲートが基本演算とみなされます。 これにより、回路に使用するゲートを正確に何にするかという問題が生じます。 まず量子回路に焦点を当てると、このシリーズでこれまで $X,$ $Y,$ $Z,$ $H,$ $S,$ $T$ ゲート、スワップゲート、制御付きゲートの各種（制御NOT、Toffoli、Fredkin ゲートを含む）、および標準基底測定を表すゲートを見てきました。 CHSHゲームの文脈では、いくつかの追加の回転ゲートも登場しました。

クエリモデルの文脈でクエリゲートも議論しましたが、任意の数の量子ビットに作用する任意のユニタリ演算 $U$ もゲートとして見なせることも示しました。しかし、この議論ではこれらの両方の選択肢を除外します。 クエリモデルでは作業しません（ただし、基本演算を使ったクエリゲートの実装については、レッスンの後半で説明します）。また、潜在的に数百万の量子ビットに作用する任意のユニタリゲートを基本演算とみなすことは、意味のある現実的な計算コストの概念にはつながりません。

少数の量子ビットに作用する量子ゲートに限定した場合、どれを基本演算とするかを決める一つのアプローチは厳密な基準を定めることですが、それは標準的なアプローチでも本コースで採用するアプローチでもありません。 むしろ、単純に選択します。

以下は量子回路のデフォルトゲートセットとして採用する標準的な選択肢です：

• 以下のリストからの1量子ビットユニタリゲート：$X,$ $Y,$ $Z,$ $H,$ $S,$ $S^{\dagger},$ $T,$ および $T^{\dagger}$
• 制御NOTゲート
• 1量子ビット標準基底測定

一般的な代替案として、Toffoli、Hadamard、$S$ ゲートを基本演算として（標準基底測定に加えて）扱うことがあります。 すべての1量子ビットゲートを基本演算と見なす場合もありますが、ゲートの実行精度を適切に考慮しないと非現実的に強力なモデルになってしまいます。

デフォルトコレクションのユニタリゲートは万能ゲートセットを形成します。 これは、これらのゲートだけで構成される回路を使って、任意の数の量子ビットに対する任意のユニタリ演算を任意の精度で近似できることを意味します。 明確にしておくと、万能性の定義はそのような近似のコスト、つまり必要なゲートの数については何も要求しません。 実際、数学的測度の概念に基づく比較的単純な議論から、ほとんどのユニタリ演算は非常に高いコストを持たなければならないことが明らかになります。 量子ゲートセットの万能性を証明することは単純ではなく、このコースでは扱いません。

ブール回路では、AND、OR、NOT、FANOUTゲートを基本演算として採用します。 実際にはANDゲートとORゲートの両方は必要ありません。すべての入出力線にNOTゲートを配置することでド・モルガンの法則を使ってどちらか一方から他方に変換できます。しかし、両方を許可することは典型的であり便利です。 AND、OR、NOT、FANOUTゲートは決定論的計算に対して万能なセットを形成します。つまり、固定数の入力ビットから固定数の出力ビットへの任意の関数をこれらのゲートで実装できます。

測定の遅延原理

標準基底測定ゲートは量子回路の途中に現れることがありますが、最後まで遅延させると便利な場合があります。 これにより、量子計算を、（計算そのものを表す）ユニタリ部分と、その後の量子ビットを測定して結果を出力する単純な読み出しフェーズとして捉えることができます。 これは常に可能であり、ただし各標準基底測定に対して追加の量子ビットを1つ加える必要があります。 以下の図では、右の回路が左のゲートに対してこれをどのように行うかを示しています。

具体的には、左の回路の古典ビットが右では量子ビット（$\vert 0\rangle$ 状態に初期化）に置き換えられ、標準基底測定が制御NOTゲートに置き換えられ、その後に下の量子ビットの標準基底測定が続きます。 ポイントは、右側の回路の標準基底測定を回路の最後まで押しやれることです。 左の回路の古典ビットが後で制御ビットとして使われる場合、右の回路の下の量子ビットを代わりに制御として使えば、全体的な効果は同じになります。 （左の回路の古典ビットが測定後に別の測定によって上書きされないと仮定しています。もし上書きされる場合は、以前の測定で使われたビットを上書きする代わりに新しい古典ビットを使えばよいだけです。）

回路サイズと深度

回路サイズ

回路内のゲートの総数は、その回路のサイズと呼ばれます。 したがって、回路内のゲートが基本演算を表すと仮定すれば、回路のサイズは必要な基本演算の数、つまり計算コストを表します。 与えられた回路 $C$ のサイズを $\operatorname{size}(C)$ と書きます。

たとえば、2つのビットのXORを計算する以下のブール回路を考えましょう。

この回路のサイズは7です。合計7つのゲートがあるからです。 （FANOUTゲートはゲートとして数えないことが多いですが、このレッスンではゲートとして数えます。）

時間、コスト、回路深度

時間は計算において極めて重要なリソース、または制限的な制約です。 RSA1024の因数分解のタスクなど、上記の例はこの観点を強調しています。 factorint 関数がRSA1024を因数分解できないわけではありません。単に、それが終わるのを待つ時間が十分にないだけです。

計算コストという概念は、計算を実行するために必要な基本演算の数として、計算の実装に必要な時間の抽象的な代替指標として意図されています。 各基本演算は実行するのに一定量の時間を必要とし、より多くの基本演算が必要な計算は少なくとも一般的により長くかかります。 シンプルさを保つために、計算コストとアルゴリズムの実行時間の間のこの関連付けを続けます。

しかし、回路のサイズは実行にかかる時間と必ずしも直接対応するわけではないことに注意してください。 たとえば、2つのビットのXORを計算するブール回路では、2つのFANOUTゲートを同時に実行でき、2つのNOTゲートも同様、2つのANDゲートも同様です。 この並列化の可能性を考慮した、回路の効率を測る別の方法が深度です。 これは回路内で必要なゲートの層の最小数であり、各層内のゲートは異なる線上で動作します。 同等に、回路の深度は入力線から出力線への任意のパス上で出会うゲートの最大数です。 たとえば上記の回路では、深度は4です。

回路深度は並列計算の実行時間を形式化する一つの方法です。 これは高度なトピックであり、特定の計算に必要な深度を最小化するための非常に洗練された回路構成が知られています。 また、回路深度に関する非常に興味深い未解決の問題も存在します。 （たとえば、GCDの計算に必要な回路深度については多くが不明のままです。） このシリーズでは回路深度についてこれ以上多くは述べませんが、随時いくつかの興味深い事実を紹介します。並列化が計算上の優位性の潜在的な源であることは明確に認識されるべきです。

ゲートへの異なるコストの割り当て

回路サイズと計算コストに関する最後の注意として、すべてのゲートを同等に扱うのではなく、ゲートに異なるコストを割り当てることが可能です。

たとえば、すでに述べたように、FANOUTゲートはブール回路では無料とみなされることが多く、つまりFANOUTゲートのコストをゼロとすることができます。 別の例として、クエリモデルで作業しており、回路がブラックボックス形式の入力関数に対して行うクエリ数を数える場合、クエリゲートに単位コストを割り当て、Hadamardゲートなど他のゲートにはゼロコストを割り当てていることになります。 最後の例として、考慮するハードウェアに応じて実装の難しさによってゲートに異なるコストを割り当てることがあります。

これらのオプションはすべて異なる文脈で合理的ですが、このレッスンではシンプルに保ち、計算コストの表現として回路サイズを使います。

入力長の関数としてのコスト

私たちが主に関心を持つのは、入力が大きくなるにつれて計算コストがどのようにスケールするかです。 これにより、アルゴリズムのコストを入力長の関数として表すことになります。

回路のファミリー

与えられた計算問題への入力は長さが異なり、任意に大きくなりえます。 一方、すべての回路は固定数のゲートと線を持ちます。 このため、アルゴリズムを回路の観点から考える場合、アルゴリズムを表現するために無限に大きな回路のファミリーが一般的に必要になります。 回路のファミリーとは、サイズが大きくなりより大きな入力に対応できる回路の列のことです。

たとえば、factorint が使用するような古典的な整数因数分解アルゴリズムがあると想像してください。 すべての古典的アルゴリズムと同様、このアルゴリズムはブール回路を使って実装できますが、そのためには入力長ごとに別々の回路が必要です。 異なる入力長の回路を見ると、入力長が大きくなるにつれてそのサイズが自然に大きくなるのがわかります。これは、4ビット整数の因数分解が1024ビット整数の因数分解よりはるかに簡単で、基本演算の数もはるかに少ないという事実を反映しています。

これにより、アルゴリズムの計算コストを関数 $t$ で表すことになります。$t(n)$ は $n$ ビット入力に対してアルゴリズムを実装する回路のゲート数として定義されます。 より形式的には、ブール回路モデルのアルゴリズムは回路の列 $\{C_1, C_2, C_3,\ldots\}$ で記述されます。ここで $C_n$ は $n$ ビット入力（またはより一般的には、何らかの形で $n$ によってパラメータ化された規模の入力）に対して対象の問題を解き、このアルゴリズムのコストを表す関数 $t$ は次のように定義されます。

$$t(n) = \operatorname{size}(C_n).$$

量子回路でも状況は同様で、より長い入力文字列に対応するためにより大きな回路が必要になります。

例：整数の加算

さらに説明するために、整数の加算問題を考えてみましょう。これは整数の因数分解やGCDの計算よりもはるかに単純です。

整数の加算

入力：整数 $N$ と $M$
出力：$N+M$

この問題を解くためのブール回路をどのように設計すればよいでしょうか？

シンプルにするために、$N$ と $M$ がともに二進表記の $n$ ビット文字列で表された非負整数の場合に限定しましょう。 これらのエンコードでは任意の数の先頭ゼロを許します。したがって

$$0\leq N,M\leq 2^n - 1.$$

出力は結果を表す $(n+1)$ ビットの二進文字列になります。これは結果を表すのに必要な最大ビット数です。

二進表現の標準的な加算アルゴリズムから始めます。これは世界中の小学校で教えられる加算方法の2進数版です。 このアルゴリズムは次のようにブール回路で実装できます。

最下位ビットから始め、それらのXORを計算して和の最下位ビットを求めます。 次に、$N$ と $M$ の2つの最下位ビットのANDであるキャリービットを計算します。 これら2つの演算をまとめて半加算器と呼ぶことがあります。

これまで何度か見たXOR回路にANDゲートと2つのFANOUTゲートを組み合わせて、10ゲートで半加算器を作ることができます。 もし何らかの理由でXORゲートを基本演算のセットに含めることにした場合、半加算器を作るには1つのANDゲート、1つのXORゲート、2つのFANOUTゲートが必要です。

より上位のビットに進むと、同様の手順を使いますが、今度は前の位からのキャリービットを計算に含めます。 2つの半加算器をカスケードし、それらが生成するキャリービットのORをとることで、全加算器として知られるものを作ることができます。

これには合計21ゲートが必要です：2つのANDゲート、2つのXORゲート（それぞれ7ゲートで実装）、1つのORゲート、4つのFANOUTゲートです。

最後に、全加算器をカスケードすることで、非負整数の加算のためのブール回路が得られます。たとえば、以下の回路は2つの4ビット整数の和を計算します。

一般に、これには

$$21 (n-1) + 10 = 21 n - 11$$

個のゲートが必要です。 XORゲートを基本演算のセットに含めることにした場合、$2n-1$ 個のANDゲート、$2n-1$ 個のXORゲート、$n-1$ 個のORゲート、$4n-2$ 個のFANOUTゲートが必要となり、合計で $9n-5$ 個のゲートになります。 さらにFANOUTゲートを数えない場合は $5n-3$ 個のゲートになります。

漸近的記法

一方では、上記の整数加算の例のように、様々な計算に必要なゲート数を正確に知ることは重要です。 これらの詳細は実際に回路を構築するために必要です。

他方、加算よりはるかに複雑なタスクを含む関心のあるすべての計算でこのレベルの詳細な分析を行うと、すぐに詳細に埋もれてしまいます。 管理しやすくするため、また二次的に重要な詳細を意図的に省略するために、アルゴリズムを分析する際には通常ビッグO記法を使います。 この記法を通じて、関数のオーダー（増加の程度）を表現できます。

形式的には、2つの関数 $g(n)$ と $h(n)$ がある場合、正の実数 $c > 0$ と正の整数 $n_0$ が存在して

$$g(n) \leq c\cdot h(n)$$

がすべての $n \geq n_0$ に対して成り立つとき、$g(n) = O(h(n))$ と書きます。 通常、$h(n)$ はできるだけ単純な式を選びます。これにより、関数の漸近的な挙動を簡単な言葉で表現できます。 たとえば、$17 n^3 - 257 n^2 + 65537 = O(n^3)$ です。

この記法は複数の引数を持つ関数にも比較的単純な方法で拡張できます。 たとえば、正の整数 $n$ と $m$ 上で定義された2つの関数 $g(n,m)$ と $h(n,m)$ がある場合、正の実数 $c > 0$ と正の整数 $k_0$ が存在して

$$g(n,m) \leq c\cdot h(n,m)$$

が $n+m \geq k_0$ のときに成り立つなら、$g(n,m) = O(h(n,m))$ と書きます。

この記法を非負整数の加算の例に結びつけると、ブール回路のファミリー $\{C_1, C_2,\ldots,\}$（ここで $C_n$ は2つの $n$ ビット非負整数を足し合わせる）が存在して $\operatorname{size}(C_n) = O(n)$ となると結論付けられます。 これは加算のコストが入力サイズとともにどのようにスケールするかの最も本質的な特徴を明らかにします：線形にスケールします。

また、XORゲートのコストを単位コストとするか $7$ とするかという具体的な詳細に依存しないことも注目してください。 一般に、ビッグO記法を使うことで、そのような低レベルの詳細に左右されない計算コストの記述が可能になります。

さらなる例

計算数論からのいくつかの問題の例を挙げます。まず乗算から始めます。

整数の乗算

入力：整数 $N$ と $M$
出力：$NM$

この問題のブール回路の作成は加算の回路よりも難しいですが、標準的な乗算アルゴリズムを考えることで、この問題に対してサイズ $O(n^2)$ の回路を思いつくことができます（$N$ と $M$ がともに $n$ ビットの二進表現であると仮定）。 より一般的には、$N$ が $n$ ビットで $M$ が $m$ ビットの場合、$N$ と $M$ の乗算のためにサイズ $O(nm)$ のブール回路があります。

実際には、よりよいスケーリングを持つ他の乗算方法もあります。 たとえば、Schönhage-Strassenの乗算アルゴリズムを使うと、2つの $n$ ビット整数の乗算に対してコスト $O(n \operatorname{lg}(n) \operatorname{lg}(\operatorname{lg}(n)))$ のブール回路を作ることができます。 ただし、この方法の複雑さにより大きなオーバーヘッドが生じるため、数万ビットを持つ数値に対してのみ実用的です。

別の基本的な問題は除算で、整数の除数と被除数が与えられたときに商と余りの両方を計算することを意味します。

整数の除算

入力：整数 $N$ と $M\neq0$
出力：$0\leq r < |M|$ かつ $N = q M + r$ を満たす整数 $q$ と $r$

整数除算のコストは乗算と同様です：$N$ が $n$ ビットで $M$ が $m$ ビットの場合、この問題を解くためにサイズ $O(nm)$ のブール回路があります。 そして乗算と同様に、漸近的により優れた方法が知られています。

次に、GCDを計算する既知のアルゴリズムを加算と乗算のものと比較できます。 $n$ ビット数 $N$ と $m$ ビット数 $M$ のGCDを計算するユークリッドのアルゴリズムには、サイズ $O(nm)$ のブール回路が必要であり、これは乗算と除算の標準アルゴリズムと同様です。 また、乗算と除算と同様に、漸近的に高速なGCDアルゴリズムがあります。2つの $n$ ビット数のGCDを計算するのに $O(n(\operatorname{lg}(n))^2 \operatorname{lg}(\operatorname{lg}(n)))$ 個の基本演算しか必要としないものも含まれます。

数論で出てくるやや費用のかかる計算としてモジュラー冪乗があります。

整数のモジュラー冪乗

入力：$K\geq 0$ かつ $M\geq 1$ を満たす整数 $N,$ $K,$ および $M$
出力：$N^K \hspace{1mm} (\text{mod }M)$

$N^K\hspace{1mm} (\text{mod }M)$ とは、$N^K$ を $M$ で割った余り、つまり $0\leq r < M$ かつある整数 $q$ に対して $N^K = q M + r$ を満たす唯一の整数 $r$ を意味します。

$N$ が $n$ ビット、$M$ が $m$ ビット、$K$ が $k$ ビットの場合、この問題はサイズ $O(k m^2 + nm)$ のブール回路で解くことができます。 これはまったく明らかではありません。 解決策は $N^K$ を最初に計算してから余りをとることではありません。そうすると $N^K$ を格納するだけで指数関数的なビット数が必要になります。 むしろ、$K$ の二進表現を使って計算全体を $M$ でのモジュラー演算として実行する冪乗アルゴリズム（二進法または繰り返し二乗法とも呼ばれる）を使うことができます。 $N,$ $M,$ $K$ がすべて $n$ ビット数だと仮定すると、$O(n^3)$ アルゴリズム（3次時間アルゴリズム）が得られます。 そして再び、より複雑だが漸近的により高速なアルゴリズムが知られています。

整数因数分解のコスト

先ほど説明したアルゴリズムとは対照的に、整数因数分解の既知のアルゴリズムははるかに高コストです。これはレッスン前半の議論からも予想できます。

因数分解の単純なアプローチの一つは試し割り法です。入力数 $N$ の素因数を見つけるために $2,\ldots,\sqrt{N}$ のリストを探索するアルゴリズムです。 これは $N$ が $n$ ビット数の場合、最悪のケースで $O(2^{n/2})$ 回の反復が必要です。 各反復には試し割りが必要で、（整数除算の標準アルゴリズムを使うと）各反復に $O(n^2)$ 個の基本演算がかかります。 最終的にサイズ $O(n^2 2^{n/2})$ の回路が得られ、これは入力サイズ $n$ に対して指数関数的です。

整数因数分解にはよりよいスケーリングを持つアルゴリズムがあります。 たとえば、先ほど述べた数体篩は乱数を使うアルゴリズムですが、高確率で $n$ ビット整数を因数分解するために

$$2^{O(n^{1/3} (\operatorname{lg}(n))^{2/3})}$$

個の基本演算が必要であると一般に信じられています（厳密には証明されていません）。 この式の指数における $n$ の冪が $1/3$ であることは非常に重要ですが、指数に現れるという事実はスケーリングを悪化させる問題であり、RSA1024が依然としてその適用範囲外にある理由の一つを説明しています。

多項式コスト対指数関数コスト

整数の加算、乗算、除算、および最大公約数の計算に対する古典的アルゴリズムにより、数千ビットの入力に対してもこれらの問題を瞬時に解くことができます。 加算は線形コストを持ち、他の3つの問題は2次コスト（または漸近的に高速なアルゴリズムを使った場合は2次以下のコスト）を持ちます。 モジュラー冪乗はより高コストですが、3次コスト（または漸近的に高速なアルゴリズムを使った場合は3次以下のコスト）で比較的効率的に実行できます。

これらはすべて多項式コストを持つアルゴリズムの例であり、ある固定定数 $c > 0$ に対してコスト $O(n^c)$ を持ちます。 大まかな第1近似として、多項式コストを持つアルゴリズムは抽象的に効率的なアルゴリズムを表すものとして見なされます。

対照的に、整数因数分解の既知の古典アルゴリズムは指数関数的コストを持ちます。 数体篩のコストは指数における $n$ の冪が $1/3$ であるため準指数関数的と表現されることがありますが、複雑性理論ではこの用語を

$$O\bigl(2^{n^{\varepsilon}}\bigr)$$

がすべての $\varepsilon > 0$ に対して成り立つアルゴリズムに対して使うことが一般的です。 いわゆるNP完全問題は、多項式コストアルゴリズムを持たない（そして広く持たないと推測されている）問題のクラスです。 指数時間仮説の回路ベースの定式化はさらに強いことを主張しており、NP完全問題のいずれも準指数関数的コストアルゴリズムを持てないというものです。

多項式コストアルゴリズムを効率的アルゴリズムと関連付けることは、大まかな抽象化として理解する必要があります。 もちろん、アルゴリズムのコストが入力サイズ $n$ に対して $n^{1000}$ や $n^{1000000}$ でスケールするなら、そのアルゴリズムを効率的と表現するのは誇張です。 しかし、コストが $n^{1000000}$ でスケールするアルゴリズムでさえ、何らかの形での「ブルートフォース」や「全探索」に基づくアルゴリズムで一般的に期待される指数関数的コストを避けるために何か巧妙なことをしているはずです。 たとえば、数体篩の洗練された改良版でさえ、コストのこの指数関数的スケーリングを避けることはできていません。 一方、多項式コストアルゴリズムは、指数関数的スケーリングを避けるために問題の構造を何らかの形で活用しています。

実際には、問題に対する多項式コストアルゴリズムの特定は、実際の効率化への第一歩に過ぎません。 アルゴリズムの改良を通じて、指数が大きい多項式コストアルゴリズムが劇的に改善され、コストがより「合理的な」多項式スケーリングに下がることがあります。 可能であることが分かれば物事が楽になることがあります。そのため、問題に対する多項式コストアルゴリズムの特定は、新しいさらに効率的なアルゴリズムを生む刺激になることもあります。

量子コンピューティングが古典コンピューティングに対して持つ優位性を考える際、私たちは一般的にまず指数関数的優位性、あるいは少なくとも超多項式的優位性に注目します。多項式コストの古典アルゴリズムが知られていない問題に対して、多項式コストの量子アルゴリズムを見つけることが理想です。 このオーダーの理論的優位性は実際の実用的な優位性につながる可能性が最も高いですが、そのような優位性を特定することは非常に困難な課題です。 現在知られている例はわずかしかありませんが、探索は続いています。

量子の古典に対する多項式的（ただし超多項式的ではない）な計算コスト上の優位性も興味深く、見過ごすべきではありません。しかし、量子と古典のコンピューティング技術の現在のギャップを考えると、現時点ではあまり説得力がないように見えます。 しかしいつか、それらは重要になるかもしれません。 たとえば、後のレッスンで扱われるGroverのアルゴリズムは、いわゆる非構造化探索において量子の古典に対する2次的な優位性を提供し、幅広い応用の可能性を持っています。

回路計算の隠れたコスト

このコースではこれ以上は取り上げませんが、言及する価値のある問題が最後に一つあります。 回路で作業する際に「隠れた」計算コストがあり、それは回路の仕様そのものに関係します。 入力が長くなるにつれてより大きな回路が必要になりますが、それらを実装するためには何らかの方法でこれらの回路の記述を入手する必要があります。

ここで議論したすべての例、または後続のレッスンで議論する例において、回路が導出される元となる基礎的なアルゴリズムがあります。 通常、ファミリー内の回路はより大きな入力に外挿しやすい基本的なパターンに従います。たとえば、加算のためのブール回路を作るために全加算器をカスケードしたり、簡単に記述できるパターンでHadamardゲートや他のゲートの層を実行したりします。

しかし、回路のパターン自体に法外な計算コストが伴う場合はどうなるでしょうか？ たとえば、回路ファミリーの各メンバー $C_n$ の記述は、原理的には $n$ の非常に計算が困難な関数によって決まる可能性があります。

答えは、これは確かに問題であり、多項式コストを持つことに加えて、回路ファミリーが真に効率的なアルゴリズムを表すためには、回路ファミリーに追加の制限を課す必要があるということです。 回路の一様性という性質は、様々な厳密な定式化において、ファミリー内の各回路の記述を計算的に容易に取得できることを規定することで、これを実現します。 ここで議論するすべての回路ファミリーはこの性質を持っています。しかしながら、これは回路計算モデルを形式的な観点から研究する際に一般的に意識すべき重要な問題です。