量子計算の受理確率は古典計算でも多項式回の問い合わせで近似できる

量子計算機は、古典計算機よりどれほど速く問題を解けるのか。この問いに答えるには、両者が解く問題、入力の条件、正解と認める基準、計算費用の測り方をそろえる必要がある。例えば、ある量子アルゴリズムが入力への問い合わせを 10 回行い、同じ問題を解く古典アルゴリズムが 1000 回の問い合わせを必要とするなら、問い合わせ回数には 100 倍の差がある。しかし、問い合わせ以外の演算や入力を準備する処理まで含めた実行時間にも 100 倍の差があるとは限らない。問い合わせ回数と実行時間は、それぞれ異なる計算資源を測っている。

正解条件によっても比較は変わる。すべての入力について正しい答えを返すことと、入力の大部分について一定の誤差以内で答えることでは、必要な情報量が異なる。例えば、100 万通りの入力のうち 999,000 通りで正しく答える方法は、入力を一様に選んだ場合には 99.9% の正解率を持つ。一方、残りの 1000 通りに含まれる入力を確実に処理する必要があるなら、その正解率だけでは要求を満たさない。平均的な入力に関する保証と、最も処理が難しい入力に関する保証は、別々に評価する必要がある。

数学的な計算量の上界は、指定した条件の下で、ある計算方法に必要な資源がどこまで増え得るかを制限する。例えば、古典的な問い合わせ回数が量子的な問い合わせ回数の多項式で抑えられると証明されれば、両者の問い合わせ回数に指数関数的な差が生じる可能性は、その定理が対象とする問題と成功条件の下で制限される。ただし、入力分布を変えたり、誤差を許さない条件へ変更したりすれば、定理の仮定との対応を改めて調べる必要がある。計算の高速化に対する制約は、計算方式の名称だけで決まるものではなく、問題を定義する条件と結び付いている。

量子計算については、低次数の有界多項式が持つ変数の影響力に注目すると、この関係を数学的に調べられる。量子アルゴリズムが入力を受け取ったときの受理確率は、問い合わせ回数によって次数が制限された多項式で表現できる。その多項式に十分な分散があれば、値を変化させる影響が一定以上の入力変数が存在する。この性質を利用すると、量子アルゴリズムの受理確率を古典的な方法で近似するための問い合わせ回数に上界を導ける。分散の下限、入力の分布、近似の許容誤差、例外として認める入力の割合が、この保証の成立範囲を定める。

1. 高速化を比較するには計算量の単位をそろえる

長さ \(N\) の二値入力を考える。一つのビットは 0 または 1 のどちらかを取るため、入力全体の候補数は \(2^N\) 通りになる。例えば、\(N=10\) なら 1024 通り、\(N=100\) なら約 \(1.27\times10^{30}\) 通りである。しかし、この候補数は、与えられた一つの入力に対して答えを求めるための計算回数を直接表しているわけではない。どのような規則で出力が決まるかによって、必要な処理は大きく変わる。

例えば、\(N\) 個のビットの排他的論理和を求める問題がある。排他的論理和は、二つのビットが異なる場合に 1、同じ場合に 0 を返す演算である。入力の先頭から順にこの演算を適用すれば、すべての入力を一度ずつ読み取るだけで最終結果を求められる。入力が \(2^N\) 通り存在していても、その候補を一つずつ試す処理は必要なく、ビット単位の演算回数は \(N\) に比例する。既稿「ソフトウェアの複雑性はどこへ移るのか」では、入力候補数、規則の記述量、一つの入力に対する計算量を区別した[1]。量子計算の性能差を比較するときにも、候補数と実際の計算資源を分ける必要がある。

この排他的論理和を、入力への問い合わせ回数だけで評価してみる。入力ビットをまだ読んでいない段階では、どの位置に 0 または 1 があるか分からない。仮に一つでも読み取っていないビットがあれば、そのビットだけが異なる二つの入力を区別できない。しかし、その二つの入力では排他的論理和の結果が必ず反転する。したがって、古典的な決定的アルゴリズムがすべての入力に対して正解するためには、\(N\) 個のビットをすべて問い合わせる必要がある。この問題では、入力候補数が指数関数的に増えても、古典的な問い合わせ回数は \(N\) 回であり、ビット単位の演算回数も \(O(N)\) である。

問い合わせ回数を計算資源として数えるモデルでは、入力の指定された位置から情報を得る操作を一回の問い合わせとして扱う。古典計算機は、これまでに読み取った値に応じて次の問い合わせ位置を決められる。量子計算機では、入力位置を重ね合わせた状態に対して量子的な問い合わせを行い、その後の干渉を利用して答えを得られる。重ね合わせに対する問い合わせは、複数の入力ビットの値を一度に古典的な情報として読み出す操作とは異なる。問い合わせの定義を統一した上で、それぞれの方式が必要とする回数を比較する。

同じ問題を同じ成功条件で解くとき、古典計算機の問い合わせ回数を \(R\)、量子計算機の問い合わせ回数を \(Q\) とする。\(Q>0\) の場合、問い合わせ回数に関する高速化倍率を次のように定義できる。

\[
S_{\mathrm{query}}=\frac{R}{Q}
\]

\(S_{\mathrm{query}}\) は問い合わせ回数の比であり、値が大きいほど、古典的な方法に対して量子的な方法の問い合わせ回数が少ないことを表す。例えば、\(R=1000\)、\(Q=10\) なら \(S_{\mathrm{query}}=100\) であり、量子的な問い合わせ回数は古典的な場合の 100 分の 1 である。一方、古典的な問い合わせ一回と量子的な問い合わせ一回には、実行する回路や必要な処理の違いがある。問い合わせ以外の演算、メモリへのアクセス、入力を用意する処理を含めた実行時間については、それぞれの費用を加えて評価する必要がある。

さらに、問い合わせ回数が少ないという結果にも、どの入力で正解することを要求するかという条件が付く。古典的な決定木は、読み取ったビットの値によって次の問い合わせ先を分岐させる計算方法である。すべての入力で正解する決定木では、最も多くの問い合わせを必要とする入力経路の長さが評価対象になる。一方、入力を一定の確率分布から選び、一定割合の誤答を許す場合には、その分布で現れやすい入力を優先する決定木も利用できる。

例えば、1000 個の入力のうち 999 個では関数の値が 0 で、残りの 1 個だけが 1 だとする。入力を 1000 個の候補から一様に選ぶ場合、常に 0 を返す方法は問い合わせを一度も行わずに 99.9% の正解率を達成する。しかし、その一つの例外入力についても正しく答える必要がある場合、同じ方法では条件を満たさない。要求する正解率が 99% なのか 100% なのかによって、必要な問い合わせ回数は変わり得る。分布上の平均的な正しさと、全入力に対する正しさは異なる制約だからである。

計算の高速化を比較する際の主要な条件は、次のように整理できる。

比較対象	評価する量	条件を変えた場合の影響
入力候補数	長さ \(N\) の二値入力には \(2^N\) 通りの候補が存在する。	候補数が増加しても、一つの入力の評価に必要な問い合わせ回数や演算回数が同じ割合で増加するとは限らない。
問い合わせ回数	入力にアクセスする回数を数え、古典計算と量子計算の差を比較する。	問い合わせ以外の演算費用を含めると、実行時間の比は問い合わせ回数の比と異なる場合がある。
正解条件	全入力での正解、一定の成功確率、許容誤差以内の近似などを区別する。	誤差や例外入力を許すと、より少ない問い合わせで条件を満たせる場合がある。
入力分布	どの入力がどの確率で与えられるかを定める。	特定の入力へ確率が集中すると、一様分布で得られた正解率や計算量の保証が変化し得る。
実行時間	問い合わせ、内部演算、データの読み書きなどを実行する費用を評価する。	問い合わせ回数が同じでも、各処理に必要な時間が異なれば、全体の実行時間には差が生じる。

この表のうち、問い合わせ回数、正解条件、入力分布は、量子計算の理論的な高速化を比較する際に直接結び付く。問い合わせ回数を減らすには、入力のどの情報を取得すれば出力を決められるかが関係する。正解条件を緩めれば、すべての入力情報を取得する必要がなくなる場合がある。入力分布が変われば、どの入力を正しく扱うことが全体の正解率に大きく寄与するかも変わる。これらの条件を固定して初めて、古典計算と量子計算の問い合わせ回数にどのような差があるかを数学的に比較できる。

量子アルゴリズムの受理確率を近似する問題では、さらに対象となる関数を明確にする必要がある。量子アルゴリズムが入力 \(x\) を受け取って 1 を出力する確率を \(p_Q(x)\) とすると、古典的な近似アルゴリズムは、この確率に近い数値を返すことを目標にできる。これは、量子アルゴリズムの内部状態を再現することとも、量子アルゴリズムが生成する個々の出力を必ず一致させることとも異なる。例えば、ある入力で \(p_Q(x)=0.7\) であれば、0.7 に近い数値を返すことと、確率 70% で 1 を出力することは別の処理である。

入力分布を \(\mu\)、近似する関数を \(p\)、古典的な近似値を \(\hat p\) とする。許容誤差を \(\varepsilon\)、その誤差を超えてもよい入力の割合を \(\delta\) とすれば、近似の成功条件は次のように表せる。

\[
\Pr_{X\sim\mu}\left[|\hat p(X)-p(X)|>\varepsilon\right]\le\delta
\]

この式の \(X\sim\mu\) は、入力 \(X\) が確率分布 \(\mu\) に従って選ばれることを表す。絶対値の中は古典的な近似値と対象関数の値との差であり、\(\varepsilon\) は許容する差の大きさである。左辺は、その差が許容誤差を超える入力が現れる確率を表す。例えば \(\varepsilon=0.1\)、\(\delta=0.01\) なら、少なくとも 99% の確率で、近似値と対象関数の値との差を 0.1 以下に抑える条件になる。この保証は、指定した分布における入力の割合について成立する。

古典的な問い合わせ回数と量子的な問い合わせ回数を比較する場合、両者が同じ関数を求め、同じ誤差条件を満たすことが前提となる。量子アルゴリズムの受理確率を古典的に近似する場合には、近似対象が確率値であること、入力がどの分布から選ばれること、どの程度の誤差と例外率を認めることを先に定義する。これらの条件が定まれば、問い合わせ回数の上界が表している計算上の保証と、その保証が適用される入力の範囲を区別できる。

2. 量子アルゴリズムの受理確率を多項式で表す

量子アルゴリズムの問い合わせ回数を数学的に調べるには、アルゴリズムが入力に対してどのような値を返すかを関数として表す必要がある。入力を \(x=(x_1,\ldots,x_N)\) とし、各ビット \(x_i\) は 0 または 1 を取るものとする。量子アルゴリズム \(A\) を実行し、最後の測定で 1 が得られる確率を \(p_A(x)\) と定義する。これは一回の実行結果ではなく、入力 \(x\) を固定して同じ測定を繰り返した場合に、1 が観測される確率である。

\[
p_A(x)=\Pr[A(x)=1],\qquad 0\le p_A(x)\le 1
\]

例えば、ある入力について \(p_A(x)=0.7\) なら、その入力に対する受理確率は 70% である。測定結果は 0 または 1 だが、受理確率そのものは 0 から 1 までの実数値を取る。量子アルゴリズムの受理確率を古典計算機で近似するという問題では、個々の測定結果を一致させる代わりに、この実数値に近い値を求めることが目標になる。どの入力について、どれだけ近い値を得られるかを指定すれば、古典的な近似の成功条件を定義できる。

ブール入力上の実数値関数には、多項式による表現を利用できる。例えば、二つのビットがともに 1 の場合だけ 1 を返す関数は、\(p(x_1,x_2)=x_1x_2\) と書ける。この式には二つの変数の積が含まれているため、次数は 2 である。一方、\(p(x_1,x_2)=(x_1+x_2)/2\) は、それぞれの変数が単独で現れるため次数 1 である。ここでいう次数は、単項式の中で掛け合わされる変数の数の最大値を表す。

各ビットが 0 または 1 に限られる場合、\(x_i^2=x_i\) が成立する。そのため、同じ変数を繰り返し掛けた項は一つの変数にまとめられる。この性質を使うと、ブール入力上の任意の実数値関数を、各変数が一つの項に高々一回しか現れない多項式で一意に表現できる。Ryan O’Donnell によるブール関数の解析の体系は、このような関数の次数、分散、変数の影響力を調べる数学的な基礎を与えている[2]。

量子アルゴリズムと多項式の間には、問い合わせ回数によって次数が制限される関係がある。量子的な問い合わせを一回行う操作では、入力ビットに依存する量子状態の振幅について、多項式の次数が高々 1 だけ増える。入力に依存しない量子ゲートは、振幅の線形結合を作るため、次数の上界を増やさない。したがって、入力への問い合わせを \(T\) 回行った後の各振幅は、次数が高々 \(T\) の多項式として表せる。

測定で特定の結果が得られる確率は、対応する振幅の絶対値の二乗から求められる。振幅を二乗する際に多項式の次数は最大で 2 倍になるため、受理確率を表す多項式の次数は高々 \(2T\) となる。Beals らの多項式法は、この関係を量子問い合わせ計算量の解析に利用した[3]。

\[
\deg(p_A)\le 2T
\]

この式の \(T\) は量子的な問い合わせ回数、\(\deg(p_A)\) は受理確率を表す多項式の次数である。例えば、量子的な問い合わせ回数が 10 回なら、受理確率の多項式の次数は高々 20 になる。入力ビットの数 \(N\) が 1000 個であっても、10 回の問い合わせから得られる受理確率は、次数 20 以下の多項式として表現できる。ただし、次数の上界は多項式に含まれる項の数を直接制限するものではない。次数 20 以下でも、多数の変数の組み合わせを表す項が存在し得る。

この関係は、量子状態全体を古典計算機で効率よく計算できることを意味するものではない。次数の制約が与えられる対象は、指定された測定結果の受理確率である。また、次数が小さいという性質だけで、その関数を少数の入力ビットから正確に決定できるとは限らない。入力への問い合わせ回数を制限するには、関数の値がどの程度変動し、どの変数がその変動に寄与しているかを調べる必要がある。

関数全体の変動を測る量として、分散を定義する。入力 \(X\) を \(N\) 個のビットからなる集合 \(\{0,1\}^N\) から一様ランダムに選ぶとする。これは、\(2^N\) 通りの入力がそれぞれ同じ確率で選ばれるという条件である。このとき、関数 \(p\) の分散を次のように定義する。

\[
V(p)=\mathbb E_X\left[\left(p(X)-\mathbb E_X[p(X)]\right)^2\right]
\]

\(\mathbb E_X[p(X)]\) は全入力にわたる関数値の平均であり、分散は各入力の関数値と平均値との差を二乗して平均したものである。\(V(p)=0\) なら、すべての入力で関数値が等しい。分散が正であれば、入力によって関数値が変わることが分かる。ただし、分散は変化の総量を表すため、その変化がどの入力変数によって生じたかまでは指定しない。

受理確率のように関数値が 0 から 1 までに収まる場合、分散には上限がある。平均値を \(m=\mathbb E_X[p(X)]\) とすると、\(0\le p(X)\le 1\) から \(p(X)^2\le p(X)\) が成立するため、次の不等式が得られる。

\[
V(p)=\mathbb E_X[p(X)^2]-m^2
\le m-m^2
\le \frac14
\]

つまり、受理確率の分散は 0 以上 \(1/4\) 以下である。平均値が \(1/2\) で、関数値が 0 と 1 に分かれる場合には、分散が \(1/4\) になる。値域の制約があることで、関数全体の変動量にも上界が生じる。この性質は、低次数多項式に関する影響力の評価で用いられる。

次に、関数値の変動を各入力変数に対応付ける。入力 \(X\) のうち、\(i\) 番目のビットだけを反転したものを \(X^{(i)}\) と書く。変数 \(i\) の影響力 \(I_i(p)\) を、元の入力と反転後の入力における関数値の差の二乗平均として定義する。

\[
I_i(p)=\mathbb E_X\left[\left(p(X)-p(X^{(i)})\right)^2\right]
\]

この定義では、変数 \(i\) を反転しても関数値が変わらない入力では、二乗差は 0 になる。反転によって関数値が変わる入力が多い場合や、変化の幅が大きい場合には、影響力も大きくなる。分散は関数全体の変動を測るのに対し、影響力は一つの入力変数を反転させた場合の変動を測る。関数値が 0 または 1 だけを取るときには、二乗差も 0 または 1 になるため、影響力はそのビットを反転すると出力が変わる確率に一致する。

具体例として、二つの入力ビットがともに 1 の場合だけ 1 を返す関数 \(p(x_1,x_2)=x_1x_2\) を考える。四つの入力 \((0,0)\)、\((0,1)\)、\((1,0)\)、\((1,1)\) のうち、関数値が 1 になるのは最後の一つだけである。したがって、入力を一様に選んだときの平均値は \(1/4\) となり、分散は次のように計算できる。

\[
\mathbb E_X[p(X)]=\frac14,\qquad
V(p)=\frac14-\left(\frac14\right)^2=\frac{3}{16}
\]

変数 \(x_1\) を反転した場合、関数値が変わるのは \(x_2=1\) のときだけである。この条件が成立する確率は \(1/2\) なので、\(I_1(p)=1/2\) となる。同様に、\(x_2\) を反転した場合も \(I_2(p)=1/2\) である。関数全体の分散が \(3/16\) である一方、個々の変数の影響力は \(1/2\) となる。このように、分散と影響力は同じ値になるとは限らず、異なる側面から関数の変動を測っている。

分散と影響力の間には、ブール立方体上の一様分布について、次の不等式が成立する。

\[
4V(p)\le\sum_{i=1}^{N}I_i(p)
\]

右辺はすべての入力変数の影響力の合計である。関数全体に変動があれば、どこかの変数を反転した際にも変動が生じるため、その合計には分散に応じた下界が与えられる。この不等式から、少なくとも一つの変数について次の関係が導かれる。

\[
\max_{1\le i\le N}I_i(p)\ge\frac{4V(p)}{N}
\]

この下界には入力変数の数 \(N\) が分母として現れる。分散を一定に保っても、入力数が増えれば、この評価から保証できる個々の変数の影響力は小さくなる。例えば、\(N=1000\) で分散が \(0.1\) の場合、この不等式から保証される最大影響力の下界は \(0.0004\) である。入力数がさらに増えれば、同じ分散でも保証される下界は小さくなる。

量子アルゴリズムの受理確率には、値域が \([0,1]\) に収まることに加え、問い合わせ回数に応じて多項式の次数が制限されるという性質がある。分散と各変数の影響力の一般的な関係に、この低次数という条件を加えることで、入力数 \(N\) に直接依存しない影響力の下界を考えられる。全体の変動が存在するとき、その変動を担う変数の影響力をどこまで保証できるかが、古典的な問い合わせ回数の上界を導くための数学的な基礎になる。

3. 値域、分散、次数の条件はそれぞれ必要である

関数全体に変動があるとき、その変動に一定以上の影響を与える入力変数が存在するだろうか。前節で示した不等式 \(4V(p)\le\sum_{i=1}^{N}I_i(p)\) からは、少なくとも一つの変数について \(I_i(p)\ge4V(p)/N\) が得られる。しかし、この下界には入力変数の数 \(N\) が含まれる。入力数が増えるほど、多数の変数に影響を分散させられるため、分散が正であるという条件だけでは、入力数に依存しない影響力の下界を保証できない。

この入力数への依存を取り除くために、関数の値域、分散、次数という三つの条件を考える。値域の有界性は関数値の振幅を制限し、分散の正の下限は関数全体に一定以上の変動が残ることを保証する。次数の上界は、一つの項に含まれる変数の数を制限する。ブール関数の多項式次数を扱った Nisan と Szegedy の研究や、決定木と変数の影響力の関係を扱った O’Donnell らの研究は、これらの量を結びつける先行成果である[4][5]。

三条件の必要性は、それぞれ一つだけを取り除いた関数の列によって検証できる。入力数 \(N\) を増やしながら、残りの二条件を一定に保ち、すべての変数の影響力が 0 に近づく例を構成する。これにより、個々の関数で影響力が正になるかという問題と、入力数によらず共通の正の下界を保証できるかという問題を区別できる。

3.1 分散の下限を外す場合

最初に、値域と次数を固定したまま、分散だけを小さくできる例を考える。入力 \(X=(X_1,\ldots,X_N)\) の各ビットを 0 または 1 とし、その平均値を返す関数 \(p_N\) を定義する。

\[
p_N(X)=\frac{1}{N}\sum_{i=1}^{N}X_i
\]

例えば、\(N=4\) で入力が \((1,0,1,0)\) なら、出力は \(1/2\) である。入力がすべて 0 なら出力は 0、すべて 1 なら出力は 1 になる。各ビットの和を \(N\) で割っているため、入力数をいくら増やしても値域は \([0,1]\) に収まる。また、各変数は一次式として現れるだけなので、多項式の次数は常に 1 である。

入力を一様ランダムに選ぶと、各ビット \(X_i\) は独立に 0 と 1 を等確率で取る。このとき、各ビットの平均値は \(1/2\)、分散は \(1/4\) である。独立な確率変数の和の分散は、それぞれの分散の和に等しいため、\(N\) 個のビットの和の分散は \(N/4\) になる。さらに、確率変数を \(N\) で割ると分散は \(N^2\) で割られるので、\(p_N\) の分散は次のようになる。

\[
V(p_N)=\frac{1}{N^2}\sum_{i=1}^{N}V(X_i)
=\frac{1}{N^2}\cdot\frac{N}{4}
=\frac{1}{4N}
\]

次に、一つのビットだけを反転する。例えば、\(X_i\) が 0 から 1 に変われば、和は 1 増加する。反対に 1 から 0 に変われば、和は 1 減少する。したがって、どの入力についても関数値の変化の絶対値は \(1/N\) であり、その二乗平均として定義した影響力は \(1/N^2\) になる。

\[
I_i(p_N)
=\mathbb E_X\left[\left(p_N(X)-p_N(X^{(i)})\right)^2\right]
=\frac{1}{N^2}
\]

これらを合わせると、次の関係が成立する。

\[
V(p_N)=\frac{1}{4N},
\qquad
\max_{1\le i\le N}I_i(p_N)=\frac{1}{N^2}
\]

例えば、\(N=100\) では分散が \(0.0025\)、各変数の影響力が \(0.0001\) になる。\(N=10000\) では、分散は \(0.000025\)、影響力は \(10^{-8}\) まで小さくなる。値域は \([0,1]\)、次数は 1 のままであるにもかかわらず、すべての変数の影響力が 0 に近づく。

この例では、入力数が増えるにつれて関数全体の変動そのものが小さくなっている。一つのビットの寄与は常に \(1/N\) であり、独立なビットを平均することで関数値が \(1/2\) の付近へ集中する。その結果、各変数の影響力だけでなく、分散も 0 に収束する。入力数によらず正の影響力を保証するには、関数全体の変動が消失する場合を除くために、分散へ正の下限を設ける必要がある。

3.2 値域の有界性を外す場合

分散を一定に保てば、個々の変数の影響力も一定以上になるだろうか。関数値の振幅を入力数に応じて拡大できる場合には、その保証も成立しない。各入力ビット \(X_i\) を、0 なら \(-1\)、1 なら \(1\) となる値 \(2X_i-1\) に変換し、その和を \(\sqrt N\) で割る関数を考える。

\[
g_N(X)=\frac{1}{\sqrt N}\sum_{i=1}^{N}(2X_i-1)
\]

各項 \(2X_i-1\) は \(-1\) または \(1\) を等確率で取るため、平均値は 0、分散は 1 である。項同士は独立なので、その和の分散は \(N\) になる。関数全体を \(\sqrt N\) で割ると、分散は \(N\) で割られる。したがって、入力数が変わっても分散は常に 1 に保たれる。

\[
V(g_N)=\frac{1}{N}\sum_{i=1}^{N}V(2X_i-1)
=\frac{N}{N}=1
\]

この関数も各変数が一次式として現れるため、次数は 1 である。一つのビットを反転すると、対応する項 \(2X_i-1\) は \(-1\) から \(1\)、または \(1\) から \(-1\) に変わる。和の変化の絶対値は 2 であり、関数値の変化の絶対値は \(2/\sqrt N\) になる。その二乗平均から、各変数の影響力は次のように求められる。

\[
I_i(g_N)=\left(\frac{2}{\sqrt N}\right)^2=\frac4N
\]

分散と影響力を並べると、

\[
V(g_N)=1,
\qquad
\max_{1\le i\le N}I_i(g_N)=\frac4N
\]

となる。例えば \(N=100\) なら各変数の影響力は \(0.04\)、\(N=10000\) なら \(0.0004\) である。分散を 1 に固定しても、入力数を増やすことで、どの変数の影響力も任意に小さくできる。

この関数で分散を保てる理由は、出力の値域が広がることにある。すべてのビットが 1 の場合は \(g_N(X)=\sqrt N\)、すべて 0 の場合は \(g_N(X)=-\sqrt N\) となる。入力数が増えるほど、取り得る関数値の範囲は広がり、固定された区間には収まらない。

\[
-\sqrt N\le g_N(X)\le\sqrt N
\]

一つの変数が引き起こす変化は \(2/\sqrt N\) と小さくなるが、独立な \(N\) 個の変数による変動を合計すると、全体の分散は 1 に保たれる。分散が一定という条件は、関数値の振幅を制限しない場合、多数の微小な変数の寄与によって満たせる。値域に入力数と独立した上限と下限を設けることは、この構造を制限するために必要となる。

3.3 次数の上界を外す場合

値域を \([0,1]\) に固定し、分散にも正の下限を設けた場合を考える。この二条件を満たしていても、多項式の次数が入力数とともに増えるなら、各変数の影響力を小さくできる。具体例は、奇数 \(N\) 個の入力ビットの過半数が 1 なら 1、そうでなければ 0 を返す多数決関数 \(m_N\) である。

\[
m_N(X)=
\begin{cases}
1 & \displaystyle\sum_{i=1}^{N}X_i>\frac N2\\
0 & \displaystyle\sum_{i=1}^{N}X_i<\frac N2 \end{cases} \]

\(N\) を奇数にしているため、1 の個数がちょうど半数になる場合は存在しない。入力を一様に選べば、0 と 1 をすべて反転した入力も同じ確率で現れる。この反転操作によって多数決の結果は必ず入れ替わるため、出力が 0 になる確率と 1 になる確率はそれぞれ \(1/2\) である。したがって、平均値は \(1/2\)、分散は \(1/4\) となる。

\[
\mathbb E_X[m_N(X)]=\frac12,
\qquad
V(m_N)=\frac14
\]

次に、ある一つのビットを反転したとき、多数決の結果が変わる条件を調べる。残りの \(N-1\) 個のビットについて、すでに 1 が過半数を占めていれば、注目するビットをどちらにしても多数決の結果は 1 のままである。逆に、0 が過半数を占めていれば、結果は 0 のままである。注目するビットが結果を左右するのは、残りのビットに含まれる 0 と 1 がちょうど同数の場合だけである。

\(N-1\) 個のビットのうち、ちょうど \((N-1)/2\) 個が 1 になる入力の数は、組合せ数 \(\binom{N-1}{(N-1)/2}\) で表せる。残りのビットの入力候補数は \(2^{N-1}\) 通りなので、注目するビットの反転によって結果が変わる確率は、これらの比になる。多数決関数の出力は 0 または 1 であり、結果が変わるときの二乗差は 1 だから、この確率がそのまま影響力になる。

\[
I_i(m_N)=
\frac{\binom{N-1}{(N-1)/2}}{2^{N-1}}
\]

例えば \(N=3\) なら、残りの 2 ビットが異なる場合だけ注目するビットが結果を決めるため、影響力は \(1/2\) である。\(N=5\) なら、残りの 4 ビットのうち 2 個が 1 になる組合せは 6 通りなので、影響力は \(6/16=0.375\) となる。入力数が増えるほど、残りのビットが完全に半数ずつへ分かれる確率は小さくなる。

この確率の減少速度は、階乗を近似するスターリングの公式から求められる。\(N\) が大きいとき、中央付近の二項係数について次の近似が成立する。

\[
\binom{N-1}{(N-1)/2}
\sim
2^{N-1}\sqrt{\frac{2}{\pi(N-1)}}
\]

これを影響力の式へ代入すると、

\[
I_i(m_N)\sim\sqrt{\frac{2}{\pi N}}
\]

となる。ここで \(\sim\) は、左右の式の比が \(N\to\infty\) で 1 に近づくことを表す。影響力はおよそ \(N^{-1/2}\) の割合で減少する。値域が常に \([0,1]\) に収まり、分散が常に \(1/4\) であっても、すべての変数の影響力が 0 に近づく。

多数決関数がこのような挙動を取れるのは、多項式の次数が入力数とともに増えるためである。例えば、3 ビットの多数決関数は次の多項式で表せる。

\[
m_3(x_1,x_2,x_3)
=x_1x_2+x_1x_3+x_2x_3-2x_1x_2x_3
\]

この式には 3 個の変数をすべて掛け合わせた項が存在するため、次数は 3 である。一般の奇数 \(N\) に対しても、多数決関数の一意な多重線形多項式表現には、すべての変数の積 \(x_1x_2\cdots x_N\) が現れる。その係数は、\(N\) 個の変数から選ぶ組合せ数の交代和によって求められる。

\[
\sum_{k=(N+1)/2}^{N}
(-1)^{N-k}\binom Nk
=
(-1)^{(N-1)/2}
\binom{N-1}{(N-1)/2}
\ne0
\]

この係数が 0 にならないため、次数 \(N\) の項は消えない。したがって、奇数 \(N\) に対して \(\deg(m_N)=N\) が成立する。多数決の結果は入力全体の過半数によって決まる一方、一つのビットが結果を左右するのは、残りのビットが同数に分かれる場合だけである。この判定規則が、多数の変数に依存しながら個々の変数の影響力を小さくする構造を作っている。

値域と分散を固定しても、次数が入力数とともに増える場合には、入力数に依存しない影響力の下界を保証できない。次数に一定の上界を設けることは、多数決関数のような高次の変数間相互作用を制限するために必要となる。

外す条件	保持する条件	最大影響力の挙動
分散の正の下限	次数 1、値域 [0,1] を保持する。	\(N^{-2}\) として 0 に近づく。
値域の有界性	次数 1、分散 1 を保持する。	\(4/N\) として 0 に近づく。
次数の上界	値域 [0,1]、分散 \(1/4\) を保持する。	\(N^{-1/2}\) のオーダーで 0 に近づく。

三つの反例は、同じ結論へ異なる経路で到達している。入力ビットの平均値を返す関数では、変数が増えるほど関数全体の分散が消失する。正規化した和の関数では、値域を拡大することで分散を一定に保ちながら、各変数の影響力を小さくする。多数決関数では、分散と値域を固定したまま、多項式の次数を増やすことで、個々の変数が結果を左右する確率を小さくする。

これらは、特定の関数の影響力が必ず大きくなるために三条件が必要だという主張ではない。対象となるすべての関数に共通して、入力数 \(N\) に依存しない正の下界を保証するには、三条件がそれぞれ担う制約が必要だという結果である。値域を固定し、分散に正の下限を与え、次数を一定以下に抑えることで、関数全体の変動が任意に多くの変数へ薄く分散する構造を制限できる。低次数の有界多項式に対する影響力の下界は、この三条件が同時に成立する場合に意味を持つ。

4. 変数の影響力から古典計算の問い合わせ上界を導く

値域が有界で、分散に正の下限があり、次数も制限された多項式では、入力変数の影響力をどこまで小さくできるのか。前節の三つの反例は、いずれかの条件を外すと、入力数 \(N\) の増加に伴ってすべての変数の影響力が 0 に近づき得ることを示した。三条件を同時に満たす場合には、関数全体の変動が存在する限り、一定以上の影響力を持つ変数の存在を保証できる。この性質を定量化することが、量子アルゴリズムの受理確率を古典計算機で近似するための出発点になる。

ブール立方体上の関数の解析では、入力変数の組み合わせごとに関数の変動を分解する。例えば、0 と 1 の入力を \(-1\) と \(1\) に変換したとき、各変数の積を基底とするフーリエ展開を利用できる。低次数の関数では、多数の変数を同時に掛け合わせた高次の項が存在しない。Dinur、Friedgut、Kindler、O’Donnell による研究は、有界関数のフーリエ係数の尾部を評価し、次数と変動の分布を調べる先行成果の一つである[6]。また、Filmus らは、絶対値による変化を用いた \(L_1\) 影響力の総和について、次数に基づく評価を与えている[7]。

影響力の総和に関する性質を具体的に確認する。入力を \(-1\) または \(1\) に変換し、変数の集合 \(S\) に対応する積を \(\chi_S(x)=\prod_{i\in S}x_i\) と書くと、関数 \(p\) は次の形で表せる。

\[
p(x)=\sum_{S\subseteq[N]}\widehat p(S)\chi_S(x)
\]

\(\widehat p(S)\) は、それぞれの変数の組み合わせに対応する係数である。次数が高々 \(d\) なら、変数の個数が \(d\) を超える集合 \(S\) に対応する係数は 0 になる。一様分布では異なる基底が直交するため、分散と変数の影響力を係数の二乗和として計算できる。

\[
V(p)=\sum_{S\ne\varnothing}\widehat p(S)^2
\]

\[
I_i(p)=4\sum_{S\ni i}\widehat p(S)^2
\]

影響力の式にある係数 4 は、\(-1\) と \(1\) の間で一つの入力変数を反転すると、その変数を含む積の符号が反転し、差の大きさが 2 倍になることから生じる。各変数の影響力を合計すると、集合 \(S\) に対応する係数の二乗は、その集合に含まれる変数の個数 \(|S|\) だけ数えられる。

\[
\sum_{i=1}^{N}I_i(p)
=4\sum_{S\subseteq[N]}|S|\widehat p(S)^2
\le4dV(p)
\]

この不等式は、次数が高々 \(d\) であれば、影響力の総和が分散の \(4d\) 倍以下になることを示している。受理確率のように \(0\le p(x)\le1\) が成立する場合には \(V(p)\le1/4\) なので、さらに次の上界が得られる。

\[
\sum_{i=1}^{N}I_i(p)\le d
\]

影響力の総和に上界があることと、個々の変数に正の下界があることは、異なる性質である。総和が一定以下でも、入力数が増えれば、その総量を多数の変数に分散させられる可能性が残る。一方、分散が正である場合には、関数値の変動が入力全体に存在している。低次数と有界な値域が、この変動を多数の変数へどこまで分散させられるかを制限する。

Scott Aaronson と Andris Ambainis は、2014 年の論文で、この関係を予想として定式化した。値域が \([0,1]\) に収まる次数 \(d\) の多項式について、分散が正の下限 \(\eta\) 以上であれば、少なくとも一つの変数の影響力が、\(\eta/d\) の固定された正のべき乗以上になるという予想である。ここで \(\eta>0\)、\(d\ge1\) とする。元の論文は、この予想が成立した場合、量子アルゴリズムの受理確率を古典的に近似する問い合わせ回数に多項式的な上界を与えられることも示していた[8]。

この予想が要求する下界は、入力数 \(N\) を直接含まない。前節の一般的な評価 \(4V(p)/N\) では、入力数の増加に伴って保証される影響力が小さくなる。これに対して、分散の下限と次数を固定した場合に正の下界が残れば、入力数がいくら増えても、一定以上の影響力を持つ変数が存在することになる。量子計算の問い合わせ回数を古典計算へ結び付けるには、この入力数への依存を取り除くことが必要だった。

予想の研究では、関数値が異なる入力の組について、どの変数がその違いを説明できるかを調べる方法も発展してきた。分数証明書では、入力位置ごとに非負の重みを割り当て、関数値の異なる入力を区別するために必要な重みの合計を評価する。Lovett と Zhang は有界関数に関する分数証明書の性質を研究し[9]、Agarwal と Ben-David の研究にも、変数への重み付けによって関数値の変化を制限する評価が現れる[10]。こうした方法では、関数全体の変動を、個々の変数の寄与と関係付けて調べる。

一方、対象となる多項式の種類を制限した場合には、一般の予想より先に部分的な結果が得られていた。Bansal、Sinha、de Wolf は、完全有界なブロック多重線形形式という構造を持つ関数について、影響力と量子アルゴリズムの古典的な近似を結び付けた[11]。この結果は特定の多項式族に適用される。Aaronson–Ambainis 予想が対象とするのは、値域と次数に条件を置いた一般の実多項式であり、その広い関数族で同様の影響力の下界が成立するかが残されていた。

2026 年 11 月に公表された David Turturean の論文は、この一般的な下界の証明を提示した。入力を \(\{0,1\}^N\) とし、値域が \([0,1]\)、次数が高々 \(d\) の多項式 \(p\) を考える。\(d\ge1\)、\(V(p)>0\) のとき、少なくとも一つの変数 \(i\) について、次の不等式が成立すると主張している[12]。

\[
\boxed{
I_i(p)\ge
\frac{8\sqrt{15}}{125\pi^4}
\frac{V(p)^{5/2}}{d^6}
\ge
\left(\frac{V(p)}{d}\right)^7
}
\]

最初の不等式の右辺は、分散 \(V(p)\) の \(5/2\) 乗に比例し、次数 \(d\) の 6 乗に反比例する。係数 \(8\sqrt{15}/(125\pi^4)\) は約 \(0.00255\) であり、正の定数である。したがって、分散と次数を固定すれば、入力数 \(N\) に依存しない正の下界が得られる。後半の不等式は、値域が \([0,1]\) の関数について \(V(p)\le1/4\) となることを利用し、定数を吸収して指数 7 の形に整理したものである。

ここで、下界の数値がどれほどになるかを計算する。例えば、次数の上界を \(d=20\)、分散を \(V(p)=0.1\) とすると、最初の不等式は次の値を与える。

\[
\frac{8\sqrt{15}}{125\pi^4}
\frac{0.1^{5/2}}{20^6}
\approx1.26\times10^{-13}
\]

この値は、少なくとも一つの変数の影響力が \(1.26\times10^{-13}\) 以上になるという保証である。影響力は関数値の変化を二乗して平均した量なので、関数値そのものが少なくともこの数だけ変化するという主張とは異なる。また、この下界は実際の最大影響力に対する下限であり、最大影響力がこの値に近いことも意味しない。数学的に正の下界が存在することと、有限の入力規模においてその下界が実用的な変数選択の基準になることは、別々に評価する必要がある。

今回の論文では、証明の主要な数学的命題を Lean で形式化している。公開された命題定義には、分散、入力ビットの反転、影響力の正規化、定理に現れる定数が記述されている[13]。これにより、形式化された命題については、証明がその命題を導いているかを証明支援系の検査対象にできる。一方、量子問い合わせ回数への帰結には、受理確率の多項式表現と、Aaronson–Ambainis の元の論文で与えられた決定木の議論を組み合わせる必要がある。

量子アルゴリズムが入力に \(T\) 回問い合わせる場合、その受理確率 \(p_A(x)\) は次数が高々 \(2T\) の多項式として表せる。古典計算機がこの受理確率を近似する際には、入力を一様分布から選び、許容誤差を \(\epsilon>0\)、許容する失敗率を \(0<\delta<1\) とする。目標は、入力の少なくとも \(1-\delta\) の割合で、真の受理確率との差が \(\epsilon\) 以下になる近似値を返すことである。

\[
\Pr_{X\sim U_N}
\left[
|\hat p_C(X)-p_A(X)|>\epsilon
\right]\le\delta
\]

この式の \(U_N\) は、\(N\) ビットのすべての入力を同じ確率で選ぶ一様分布を表す。\(\hat p_C(X)\) は古典的な近似アルゴリズムが返す数値、\(p_A(X)\) は対象となる量子アルゴリズムの受理確率である。例えば、\(\epsilon=0.1\)、\(\delta=0.01\) なら、一様に選んだ入力の少なくとも 99% について、受理確率との差を 0.1 以下に抑えることが要求される。

この条件を満たす決定木の構成では、まず、まだ問い合わせていない入力変数について受理確率の分散を考える。すでに読み取ったビットの値を固定すると、元の多項式は残りの変数についての多項式になる。変数の固定によって次数が増えることはなく、値域も引き続き \([0,1]\) に収まる。そのため、残りの分散が正であれば、影響力の下界を繰り返し適用できる。

残りの分散が大きい間は、一定以上の影響力を持つ変数を選んで問い合わせ、その値に応じて分岐する。選んだ変数が 0 の場合と 1 の場合に関数を制限すると、残りの変数に関する影響力の総和は、二つの分岐について平均したときに減少する。フーリエ展開で見ると、問い合わせた変数を含む項から、その変数に対応する次数の寄与が取り除かれるためである。変数 \(i\) を問い合わせたとき、影響力の総和の期待減少量は \(I_i(p)\) に等しくなる。

この減少量を評価するために、影響力の下界を利用する。残りの分散が \(\epsilon^2\delta/2\) を超える場合、残りの多項式の次数は高々 \(2T\) なので、少なくとも一つの変数の影響力には次の下界が与えられる。

\[
I_i(p)>
\left(
\frac{\epsilon^2\delta}{4T}
\right)^7
\]

右辺を \(\alpha\) と置くと、分散が十分に大きい分岐では、問い合わせを一回進めるごとに、影響力の総和が平均して少なくとも \(\alpha\) だけ減少する。最初の影響力の総和は、次数と分散の上界から \(2T\) 以下である。したがって、分散が指定した閾値以下になるまでの問い合わせ回数の期待値は、\(2T/\alpha\) 以下に抑えられる。

\[
\alpha=
\left(
\frac{\epsilon^2\delta}{4T}
\right)^7,
\qquad
\mathbb E[C]\le\frac{2T}{\alpha}
\]

この期待値だけでは、すべての入力について問い合わせ回数が同じ値以下になるとは限らない。問い合わせが多数回続く入力の割合を制限するために、非負の確率変数に対するマルコフの不等式を利用する。問い合わせ回数が期待値の \(2/\delta\) 倍を超える確率は高々 \(\delta/2\) となるため、問い合わせ回数に次の上限を設定できる。

\[
C_{\mathrm{cl}}
\le
\frac{4T}{\delta\alpha}
=
\frac{4T}{\delta}
\left(
\frac{4T}{\epsilon^2\delta}
\right)^7
\]

右辺を整理すると、量子問い合わせ回数 \(T\)、許容誤差 \(\epsilon\)、許容失敗率 \(\delta\) に関する明示的な上界が得られる。

\[
\boxed{
C_{\mathrm{cl}}\le
(4T)^8\epsilon^{-14}\delta^{-8}
}
\]

一方、分散が \(\epsilon^2\delta/2\) 以下まで小さくなった分岐では、残りの入力による受理確率の変動を小さく抑えられる。この場合、残りの入力についての条件付き平均値を近似値として返す。分散が \(v\) の確率変数について、平均値との差が \(\epsilon\) を超える確率は、チェビシェフの不等式から \(v/\epsilon^2\) 以下になる。分散が指定した閾値以下なら、近似誤差が \(\epsilon\) を超える条件付き確率は \(\delta/2\) 以下である。

\[
\Pr\left[
|p_A(X)-\mathbb E[p_A(X)\mid\text{既知の入力ビット}]|>\epsilon
\right]
\le
\frac{\epsilon^2\delta/2}{\epsilon^2}
=
\frac{\delta}{2}
\]

問い合わせ回数が上限に達する確率を高々 \(\delta/2\) に抑え、分散が十分に小さくなった分岐で近似に失敗する確率も高々 \(\delta/2\) に抑える。二つの失敗事象の確率を合計すれば、全体の失敗率は \(\delta\) 以下になる。このように、影響力の下界は変数を選ぶ根拠となり、影響力の総和は問い合わせ回数を制限し、分散は近似誤差を制限する。それぞれ異なる役割を持つ量を結び付けることで、古典的な問い合わせ回数の上界が導かれる。

この上界の意味は、\(\epsilon\) と \(\delta\) を正の定数に固定すれば、古典的な問い合わせ回数が量子アルゴリズムの問い合わせ回数 \(T\) の 8 次多項式で抑えられることである。例えば、\(T\) が入力数 \(N\) の多項式で増加するなら、この上界も \(N\) の多項式として表せる。一様分布の大部分の入力について量子アルゴリズムの受理確率を近似する問題では、古典的な問い合わせ回数に超多項式的な増大を強制できないという帰結になる。

ただし、ここで得られたのは、指定した近似条件を満たす古典的な決定木の存在と、その問い合わせ回数の上界である。影響力の大きい変数を見つけるための内部計算や、条件付き平均値を求める処理に必要な実行時間まで、この式から直接評価できるわけではない。また、保証の対象は一様分布から選ばれる大部分の入力についての受理確率の近似であり、すべての入力に対する完全一致とは成功条件が異なる。量子計算と古典計算の性能差に関する数学的な制約は、問い合わせ回数、入力分布、誤差条件を固定した範囲で成立している。

5. 多項式上界は実用的な計算時間を保証しない

前節で得られた古典的な問い合わせ回数の上界は、量子アルゴリズムの問い合わせ回数 \(T\)、許容誤差 \(\epsilon\)、許容失敗率 \(\delta\) を使って表される。この上界は、\(\epsilon\) と \(\delta\) を正の定数に固定した場合、\(T\) の 8 次多項式になる。入力規模を大きくしたときに必要な問い合わせ回数がどのように増えるかを制限するという意味で、数学的な成果である。しかし、多項式であることから、有限の入力規模で少ない問い合わせ回数を保証できるとは限らない。指数、係数、誤差条件によって、上界の数値は大きく変わる。

具体的に、量子アルゴリズムの問い合わせ回数を \(T=10\)、許容誤差を \(\epsilon=0.1\)、許容失敗率を \(\delta=0.1\) とする。これは、量子アルゴリズムが入力へ 10 回問い合わせ、古典的な近似値と受理確率との差が 0.1 を超える入力の割合を 10% 以下に抑える条件である。これらを上界へ代入すると、次の値が得られる。

\[
\begin{aligned}
C_{\mathrm{cl}}
&\le(4T)^8\epsilon^{-14}\delta^{-8}\\
&=(4\times10)^8(0.1)^{-14}(0.1)^{-8}\\
&=6.5536\times10^{34}
\end{aligned}
\]

この値は、条件を満たす古典的な近似アルゴリズムが存在することを保証するための問い合わせ回数の上界である。実際に \(6.5536\times10^{34}\) 回の問い合わせが必要だという意味ではない。例えば、100 回の問い合わせで十分なアルゴリズムが存在していても、上記の不等式は成立する。上界が成立することと、その上界が実際の最小問い合わせ回数に近いことは異なる。

上界が大きくなる直接の原因は、\(T\) の 8 乗に加えて、許容誤差の逆数が 14 乗、許容失敗率の逆数が 8 乗で現れることである。例えば、\(T\) と \(\delta\) を固定し、許容誤差を \(0.1\) から \(0.05\) に半減すると、上界は \(2^{14}=16384\) 倍になる。また、\(T\) と \(\epsilon\) を固定し、許容失敗率を \(0.1\) から \(0.01\) に減らすと、上界は \(10^8\) 倍になる。どちらも保証する近似精度を厳しくした結果であり、実際のアルゴリズムの問い合わせ回数が必ず同じ倍率で増えるという主張ではない。

問い合わせ回数の上界を評価する際には、入力全体の長さも考慮する必要がある。入力が \(N\) ビットであれば、古典計算機は最大 \(N\) 回の問い合わせですべてのビットを取得できる。入力全体が分かれば、それ以上の入力問い合わせを行わずに、与えられた量子アルゴリズムの受理確率を計算するための情報がそろう。この後の数値計算に必要な時間は、問い合わせ回数とは別に評価される。

したがって、入力問い合わせだけを費用として数えるモデルでは、先ほどの多項式上界と全ビットの読み取りによる上界を組み合わせられる。

\[
C_{\mathrm{cl}}
\le
\min\left\{
N,\,
(4T)^8\epsilon^{-14}\delta^{-8}
\right\}
\]

右辺の \(\min\) は、二つの値のうち小さい方を選ぶことを表す。例えば、\(N=1000\)、\(T=10\)、\(\epsilon=0.1\)、\(\delta=0.1\) なら、多項式から得られる上界は約 \(6.55\times10^{34}\) 回だが、全ビットを読む方法では 1000 回で入力を取得できる。この条件では、問い合わせ回数について実際に有用な上界は 1000 回となる。

ただし、全ビットを読み取ったことと、受理確率を短時間で算出できることは別の問題である。量子アルゴリズムの受理確率を古典的に求めるには、そのアルゴリズムが実行する量子操作に対応した計算が必要になる。入力の値をすべて知っていても、受理確率の計算に多数の演算を必要とする場合がある。問い合わせモデルでは、この内部計算に必要な演算回数を費用として数えないため、\(N\) 回という上界から実行時間を直接導くことはできない。

この違いを、古典計算機の処理時間を分解することで確認できる。一回の入力取得に要する時間を \(t_{\mathrm{read}}\)、実際の問い合わせ回数を \(C_{\mathrm{cl}}\)、次に問い合わせる変数を選ぶための処理時間の合計を \(t_{\mathrm{select}}\)、必要な情報を取得した後に結果を計算する時間を \(t_{\mathrm{eval}}\) とする。各入力の取得に同じ時間がかかると仮定すれば、総処理時間を概念的に次のように表せる。

\[
T_{\mathrm{cl}}
=
C_{\mathrm{cl}}t_{\mathrm{read}}
+t_{\mathrm{select}}
+t_{\mathrm{eval}}
\]

この式の第一項は、入力を取得するための時間である。第二項は、問い合わせる変数を決定する計算の合計時間を表す。第三項は、読み取った情報から最終的な近似値を算出する時間である。問い合わせ回数の定理は第一項に含まれる \(C_{\mathrm{cl}}\) へ上界を与える。一方、変数選択や結果の算出に必要な演算回数については、別の計算量解析が必要になる。

例えば、影響力の大きい変数を選択する方法を考える。前節の決定木の議論では、分散が大きい場合に、一定以上の影響力を持つ変数が存在することを利用した。存在が保証されていれば、その変数を選択した決定木を数学的に考えることができる。しかし、影響力を計算して対象変数を効率よく発見するためには、各変数に対応する関数値の変化を評価する方法が必要である。存在の証明から、変数を選ぶ計算時間の多項式的な上界まで自動的に得られるわけではない。

多項式を展開して計算する方法でも、同じ区別が現れる。\(N\) 変数の多重線形多項式で次数が高々 \(d\) の場合、一つの項に含まれる変数の組み合わせは、変数を 0 個選ぶ場合から \(d\) 個選ぶ場合まで存在する。したがって、取り得る単項式の最大数は、次の組合せ数の和で表せる。

\[
M(N,d)
=
\sum_{k=0}^{\min(d,N)}
\binom Nk
\]

ここで \(\binom Nk\) は、\(N\) 個の変数から \(k\) 個を選ぶ組合せ数である。例えば、\(d=1\) なら定数項と一次項だけなので、単項式は最大 \(N+1\) 個になる。\(d=2\) なら二つの変数の積まで含まれるため、最大 \(1+N+N(N-1)/2\) 個になる。次数を固定すれば単項式数は \(N\) の多項式で抑えられるが、次数も入力数に応じて増える場合には、展開の大きさが急増する。

特に \(d\) が \(\log N\) に比例して増える場合、単項式数は一般に \(N^{O(\log N)}\) という規模まで増え得る。これは固定次数の多項式よりも速く増える。例えば、受理確率の次数が高々 \(2T\) という性質を使っても、\(T\) 自体が入力数とともに増えるなら、すべての単項式を列挙する方法の処理量は大きくなり得る。ただし、単項式をすべて列挙することは一つの計算方法にすぎない。より効率的な表現や評価方法が存在する場合には、列挙を避けられるため、この単項式数を一般の近似アルゴリズムに対する実行時間の下界として解釈することはできない。

古典計算機と量子計算機の計算費用を比較する場合、数えている資源の違いは次のように整理できる。

評価対象	数学的に評価する量	問い合わせ回数の上界から分かること
入力への問い合わせ	入力から情報を取得する操作の回数を数える。	指定した近似条件の下で、古典的な問い合わせ回数を \((4T)^8\epsilon^{-14}\delta^{-8}\) 以下に抑えられる。
変数の選択	次に問い合わせる変数を決定するための演算回数を数える。	影響力のある変数の存在は保証されるが、その変数を発見するための計算時間には別の評価が必要になる。
近似値の算出	取得済みの入力から受理確率の近似値を計算する演算回数を数える。	問い合わせ回数の上界だけでは、条件付き平均値や受理確率を算出する処理時間は定まらない。
量子操作の実行	量子ゲート、問い合わせ操作、測定などの費用を数える。	問い合わせ回数の差から、量子回路全体の実行時間の比を直接求めることはできない。
物理的な計算資源	情報の保持、誤り訂正、装置の制御などに必要な資源を数える。	抽象的な問い合わせ回数には、物理的な装置で必要となる資源の費用が含まれていない。

量子計算機の実行時間についても、問い合わせ回数と内部処理を区別する必要がある。量子的な問い合わせを \(T\) 回行うアルゴリズムであっても、一回の問い合わせに必要な量子操作の数や、問い合わせの間に実行する量子ゲートの数は、アルゴリズムによって異なる。また、実際の量子計算機では、量子情報を保持するための制御や誤り訂正が処理費用に影響する。既稿「量子計算機はなぜ壊れやすい情報で計算できるのか」では、量子情報の保持と誤り訂正に関する物理的な制約を扱った[14]。こうした費用は、入力への問い合わせを一回と数える抽象的なモデルとは異なる基準で評価される。

この違いから、数学的な上界について二つの判断が導かれる。第一に、入力分布と近似条件を固定した場合、古典的な問い合わせ回数が量子アルゴリズムの問い合わせ回数の多項式で抑えられるという結果には、計算複雑性理論上の意味がある。量子アルゴリズムの受理確率を大部分の入力について近似する際、古典的な問い合わせ回数に超多項式的な増大を要求することは、その条件の下で制限される。第二に、その多項式の次数や係数、変数選択と結果算出の費用によって、有限規模での実行可能性は変わる。

問い合わせ回数の上界が \(6.5536\times10^{34}\) という値を取る例では、多項式的な保証が成立していても、数値としての上界は実用的な計算資源の目安にならない。一方、入力をすべて読む \(N\) 回という上界は、問い合わせ費用だけを比較する場合には小さい値を与えることがある。しかし、その後の受理確率の計算に必要な時間は別に残る。量子計算の高速化に対する今回の数学的な制約は、古典的な近似に必要な入力問い合わせ回数について成立するものであり、実行時間や物理的な資源まで含めた性能差を評価するには、それぞれの費用に対応した追加の上界が必要となる。

6. 入力分布を変えると近似の保証も変わる

古典計算機による近似が、入力の 99% で正しいという結果は、どの入力がどの確率で選ばれるかによって意味が変わる。例えば、100 万通りの入力のうち 99 万通りで誤差が許容範囲に収まっていても、残りの 1 万通りに実際の処理対象が集中していれば、運用時の近似精度は低くなる。入力全体に対する失敗率と、特定の入力群に対する失敗率は、それぞれ異なる確率分布の下で評価されるからである。

量子アルゴリズムの受理確率を古典的に近似する場合も同様である。前節までに扱った問い合わせ回数の上界は、\(N\) ビットの入力全体から一様ランダムに選んだ場合の保証である。一様分布では、\(2^N\) 通りの入力がそれぞれ確率 \(2^{-N}\) で選ばれる。この分布を \(U_N\) と書き、古典的な近似値と受理確率との差が許容誤差 \(\epsilon\) を超える入力の集合を \(B\) とする。

\[
B=\left\{x\in\{0,1\}^N:
|\hat p_C(x)-p_A(x)|>\epsilon
\right\}
\]

\(\hat p_C(x)\) は古典計算機が返す近似値、\(p_A(x)\) は量子アルゴリズムの受理確率である。このとき、近似に失敗する入力の割合が \(\delta\) 以下であるという保証は、次のように表せる。

\[
U_N(B)=\frac{|B|}{2^N}\le\delta
\]

例えば、\(\delta=0.01\) なら、全入力の少なくとも 99% について許容誤差以内の近似が成立する。ただし、この式は失敗する入力の個数を制限するものであり、その入力がどこに集中しているかまでは指定しない。失敗する入力が全体に散在する場合もあれば、特定の条件を満たす入力群だけに集中する場合もある。

6.1 特定の入力集合では失敗率が増大し得る

入力全体のうち、ある条件を満たす部分集合 \(S\) に注目する。例えば、特定の形式を持つ入力や、一定の制約を満たす入力だけを対象とする場合である。全入力に対する \(S\) の割合を \(\rho\) とすると、次のように定義できる。

\[
\rho=\frac{|S|}{2^N},\qquad 0<\rho\le1 \]

\(\rho=1/8\) なら、全入力の 12.5% が \(S\) に属する。\(\rho=2^{-20}\) なら、約 100 万通りに 1 通りの割合で \(S\) に属する。入力を \(S\) の内部から一様に選ぶ場合、近似に失敗する確率は、失敗集合 \(B\) と \(S\) の共通部分が \(S\) 全体に占める割合になる。

\[
\Pr_{X\sim U_N}[X\in B\mid X\in S]
=
\frac{|B\cap S|}{|S|}
\]

失敗集合と \(S\) の共通部分は、失敗集合全体より大きくなることはない。したがって、\(|B\cap S|\le|B|\) を利用すると、次の不等式が得られる。

\[
\begin{aligned}
\Pr[X\in B\mid X\in S]
&=\frac{U_N(B\cap S)}{U_N(S)}\\
&\le\frac{U_N(B)}{\rho}\\
&\le\frac{\delta}{\rho}
\end{aligned}
\]

確率は最大でも 1 なので、最終的な上界は次のようになる。

\[
\boxed{
\Pr[X\in B\mid X\in S]
\le
\min\left(1,\frac{\delta}{\rho}\right)
}
\]

この式では、全入力における許容失敗率 \(\delta\) と、関心のある入力集合の割合 \(\rho\) が別の役割を持つ。\(\delta\) が小さくても、\(\rho\) がそれより小さければ、右辺は 1 になる。つまり、全入力に対する近似保証だけでは、\(S\) の内部でどれだけ正しく近似できるかを制限できない。

具体的に、\(\rho=2^{-20}\)、\(\delta=10^{-2}\) とする。全入力の約 100 万分の 1 に相当する集合 \(S\) に対して、近似の失敗を全入力の 1% まで許す条件である。この場合、\(\delta/\rho\approx10485.76\) なので、確率の上界は 1 になる。失敗集合 \(B\) が \(S\) 全体を含んでいても、全入力に対する失敗率は \(2^{-20}\) であり、元の \(\delta=10^{-2}\) という保証に違反しない。

この評価は単に上界が大きいというだけでなく、失敗集合の配置によって実際に起こり得る状況を表している。一般に \(\rho\le\delta\) なら、\(B=S\) とするだけで、全入力に対する失敗率が \(\delta\) 以下でありながら、\(S\) の内部では失敗率が 100% になる。失敗入力の総数だけを制限しても、その入力が特定の集合に集中することまでは防げない。

6.2 部分集合の精度を保証するための費用

それでは、\(S\) の内部で失敗する割合を \(\eta\) 以下に抑えるには、どの程度厳しい一様分布上の保証が必要になるのか。先ほどの不等式を利用する場合、全入力に対する失敗率を \(\rho\eta\) 以下に抑えれば、\(S\) 内部の失敗率を \(\eta\) 以下にできる。

\[
U_N(B)\le\rho\eta
\quad\Longrightarrow\quad
\Pr[X\in B\mid X\in S]\le\eta
\]

例えば、\(\rho=2^{-10}\) の集合について、内部の失敗率を \(\eta=0.05\) 以下にしたい場合を考える。単純な条件付き確率の評価を使うなら、一様分布における失敗率を \(\delta=0.05/1024\approx4.88\times10^{-5}\) 以下にすれば十分である。全入力の約 0.00488% 以下に失敗を抑えることで、全入力の約 0.0977% を占める集合の内部でも、失敗率を 5% 以下に抑えられる。

この条件を、前節で得られた古典的な問い合わせ回数の上界へ代入する。量子アルゴリズムの問い合わせ回数を \(T\)、許容誤差を \(\epsilon\) とすると、一様分布における失敗率 \(\delta\) を使った上界は次の形だった。

\[
C_{\mathrm{cl}}
\le
(4T)^8\epsilon^{-14}\delta^{-8}
\]

ここへ \(\delta=\rho\eta\) を代入すると、\(S\) の内部で失敗率 \(\eta\) 以下を保証するための十分な問い合わせ回数上界が得られる。

\[
\boxed{
C_{\mathrm{cl}}
\le
(4T)^8\epsilon^{-14}(\rho\eta)^{-8}
}
\]

右辺には \(\rho^{-8}\) が含まれている。これは、対象集合が全入力に占める割合を 10 分の 1 にすると、この方法で得られる上界が \(10^8\) 倍になることを意味する。ただし、対象集合上で最適な古典アルゴリズムの問い合わせ回数が同じ割合で増加するという意味ではない。一様分布上の保証を条件付き確率によって移すという特定の導出方法が、集合の密度に依存している。

対象集合の割合が入力数 \(N\) に対して指数関数的に小さくなる場合を考える。定数 \(\alpha>0\) に対して、\(\rho=2^{-\alpha N}\) と置くと、問い合わせ回数の上界は次のように変形できる。

\[
\begin{aligned}
C_{\mathrm{cl}}
&\le
(4T)^8\epsilon^{-14}
(2^{-\alpha N}\eta)^{-8}\\
&=
(4T)^8\epsilon^{-14}\eta^{-8}
2^{8\alpha N}
\end{aligned}
\]

この式には、入力数 \(N\) に対して指数関数的に増加する因子 \(2^{8\alpha N}\) が現れる。例えば、\(\alpha=1/10\) なら、この因子は \(2^{0.8N}\) となる。一様分布での保証をそのまま移す方法では、対象集合が指数関数的に希少になるにつれて、得られる上界が急速に増大する。

一方、この式は指数関数的な問い合わせ回数が必要だという下界を示していない。入力が \(N\) ビットなら、すべてのビットを読む方法によって問い合わせ回数は \(N\) 以下に抑えられる。ここで失われるのは、量子アルゴリズムの問い合わせ回数 \(T\) と許容誤差だけから得られる、対象集合の密度に依存しない多項式的な保証である。対象集合の性質を直接利用する別の近似方法が存在する可能性は、この評価では排除されない。

6.3 一般の入力分布では確率の集中度が関係する

入力が特定の部分集合から一様に選ばれる場合だけでなく、入力ごとに異なる確率が割り当てられる場合もある。例えば、入力ビットの 1 が 0 よりも現れやすい状況では、すべての入力を等確率に選ぶ一様分布とは異なる確率分布になる。このような分布を \(\mu\) と書く。

一様分布における入力 \(x\) の確率は \(U_N(x)=2^{-N}\) である。これに対し、別の分布 \(\mu\) における同じ入力の確率は \(\mu(x)\) となる。両者の比 \(\mu(x)/U_N(x)\) は、その入力が一様分布の場合と比べて何倍現れやすいかを表す。すべての入力について、この比の最大値を \(M\) と定義する。

\[
M=\max_{x\in\{0,1\}^N}
\frac{\mu(x)}{U_N(x)}
=
2^N\max_x\mu(x)
\]

\(M\) は 1 以上であり、一様分布と一致する場合に 1 になる。特定の入力に確率が集中すると、最大確率が増えるため、\(M\) も大きくなる。この値を使うと、同じ失敗集合 \(B\) に対して、分布を変えた場合の失敗確率を評価できる。

\[
\begin{aligned}
\Pr_{X\sim\mu}[X\in B]
&=\sum_{x\in B}\mu(x)\\
&=\sum_{x\in B}
\frac{\mu(x)}{U_N(x)}U_N(x)\\
&\le M\sum_{x\in B}U_N(x)\\
&\le M\delta
\end{aligned}
\]

したがって、別の分布における失敗確率には、次の上界が得られる。

\[
\boxed{
\Pr_{X\sim\mu}[X\in B]
\le\min(1,M\delta)
}
\]

この不等式は、入力分布を変更したときに、元の近似アルゴリズムの失敗率がどこまで増え得るかを表す。\(M=2\) なら失敗率の上界は元の 2 倍になり、\(M=100\) なら 100 倍になる。ただし、実際の失敗集合 \(B\) が確率の集中した入力と重なっていなければ、失敗率はこの上界より小さくなる。\(M\) はすべての入力の中で最大の確率比を利用しているため、個々の失敗集合に対する評価としては保守的な値になる。

例えば、各ビットが独立に 1 になる確率を \(p\)、0 になる確率を \(1-p\) とする分布を考える。この分布を \(\mu_p\) と書く。入力 \(x\) に含まれる 1 の個数を \(w(x)\) とすれば、その入力が現れる確率は次の式で表せる。

\[
\mu_p(x)=p^{w(x)}(1-p)^{N-w(x)}
\]

\(p=1/2\) の場合は、すべての入力が確率 \(2^{-N}\) で現れるため、一様分布になる。一方、\(p=0.7\) なら、各ビットは 0 よりも 1 になりやすい。すべてのビットが 1 である入力の確率は \(0.7^N\) となり、一様分布での確率 \(0.5^N\) より大きくなる。

一般に、この分布の最大確率比は次のように計算できる。

\[
M=
\left(2\max(p,1-p)\right)^N
\]

例えば \(p=0.7\) では、\(M=1.4^N\) となる。各ビットの偏りを一定に保っていても、入力数が増えると最大確率比は指数関数的に増大する。この値をそのまま失敗率の変換に使えば、\(M\delta\) も急速に大きくなり、有効な失敗率の上界を得るには \(\delta\) を非常に小さくする必要がある。

しかし、この計算で分かるのは、一様分布の下で構成した近似アルゴリズムについて、最大確率比だけを使って保証を移す方法の限界である。偏った分布そのものに適した近似アルゴリズムを構成した場合に、同じ問い合わせ回数が必要になるとは限らない。分布の偏りによって確率の集中度が変化することと、その分布で古典的な近似が難しくなることは、別々の数学的命題である。

6.4 分布の構造を利用すると別の保証が成立する

一様分布から近似保証を移す方法では、対象集合の密度 \(\rho\) や最大確率比 \(M\) が問い合わせ回数の上界を悪化させる。しかし、特定の確率分布について直接解析すれば、異なる結果が得られる。Girish、Mittal、Nehoran、Raz は、Aaronson–Ambainis 予想の分布を変更した場合を研究し、固定された偏りを持つ独立ベルヌーイ分布と、1 の個数を固定した入力集合上の一様分布について、元の一様分布上の予想と対応する予想が同値であることを示した[15]。

独立ベルヌーイ分布とは、先ほどの \(\mu_p\) のように、各ビットが他のビットから独立して 1 になる確率 \(p\) を持つ分布である。ここでの結果は、\(p\) を \(0<p<1\) の範囲にある定数として固定した場合に成立する。\(p\) が入力数 \(N\) に応じて 0 または 1 に近づく場合まで、同じ一様な計算量評価が自動的に得られるという意味ではない。

もう一つの対象は、1 の個数を固定した入力集合上の一様分布である。入力に含まれる 1 の個数を \(k\) とすると、この集合は次のように表せる。

\[
S_k=
\left\{
x\in\{0,1\}^N:
\sum_{i=1}^{N}x_i=k
\right\}
\]

この集合には \(\binom Nk\) 通りの入力が含まれる。集合上の一様分布では、それらの入力がすべて同じ確率で選ばれ、1 の個数が \(k\) 以外の入力は選ばれない。このような分布はスライス分布と呼ばれる。研究では、固定した \(0<p<1\) に対して \(k=\lfloor pN\rfloor\) とした分布を扱っている。

スライス分布の場合、全入力に対する集合の割合は次のようになる。

\[
\rho=
\frac{\binom N{\lfloor pN\rfloor}}{2^N}
\]

\(p\) が \(1/2\) から離れた定数であれば、この割合は入力数 \(N\) の増加とともに指数関数的に小さくなる。したがって、一様分布上で得られた一つの近似結果を、条件付き確率によってそのままスライス分布へ移す方法では、前述の \(\rho^{-8}\) という因子が大きくなる。一方、スライス分布の構造を直接利用する定理では、元の一様分布に関する予想と同値な性質を得られる。

二つの評価方法の違いは、次のように整理できる。

評価方法	利用する条件	得られる保証と制約
部分集合への条件付け	一様分布上の失敗集合 \(B\) と、対象集合の密度 \(\rho\) を利用する。	失敗率は \(\min(1,\delta/\rho)\) 以下になるが、対象集合が希少な場合には上界が 1 になり得る。
確率比による分布変換	一様分布と別の分布 \(\mu\) の最大確率比 \(M\) を利用する。	失敗率は \(\min(1,M\delta)\) 以下になるが、確率比が指数関数的に増える場合には保証が悪化する。
偏った積分布の直接解析	各ビットが独立で、1 になる確率 \(p\) が固定されている構造を利用する。	Aaronson–Ambainis 予想に対応する性質について、一様分布上の予想との同値性が示されている。
スライス分布の直接解析	入力に含まれる 1 の個数が固定されている構造を利用する。	固定された比率のスライス分布について、一様分布上の予想との同値性が示されている。

この表で、最初の二つはすでに得られた一つの近似結果について、別の入力分布での失敗率を評価する方法である。後半の二つは、分布の構造を利用し、その分布に対して対応する数学的性質を証明する方法である。前者では失敗集合の配置に関する情報が不足するため、密度や最大確率比に依存した上界が現れる。後者では、対象分布の独立性や入力ビット数の制約を直接利用するため、単純な確率の換算とは異なる保証を得られる。

この違いは、量子計算の高速化を評価する際に具体的な意味を持つ。一様分布で古典的な近似が可能であっても、その近似アルゴリズムが特定の入力群で同じ精度を保つとは限らない。しかし、ある入力群が一様分布では希少であることだけから、量子計算機に大きな優位性が存在すると結論することもできない。入力分布の構造に応じて、別の古典的な近似方法が成立する場合があるからである。

入力分布は、近似の成功率を計算するための付随的な条件ではなく、どの計算量上の保証が成立するかを決める数学的な条件である。一様分布からの確率の変換は、その保証を別の分布へ移すための十分条件を与える。一方、偏った積分布やスライス分布に関する研究は、変換による上界が悪化する場合でも、分布の構造から独立に保証を導けることを示している。量子計算と古典計算の性能差を評価するには、入力の偏りの大きさだけでなく、対象分布についてどの近似定理が成立するかを確認する必要がある。

7. 決定問題と探索問題では高速化の制約が異なる

計算に必要な資源は、入力の性質だけでなく、どのような出力を正解と認めるかによっても変わる。ある条件を満たす入力が存在するかを判定する問題では、答えは 0 または 1 である。一方、その条件を満たす具体的な入力を発見する問題では、解の位置や内容を出力する必要がある。量子アルゴリズムの受理確率を近似する問題では、さらに異なる実数値が計算対象になる。同じ入力に関する問題でも、出力の定義と成功条件が変われば、必要な問い合わせ回数を直接比較することはできない。

これらの違いを調べるために、未整列の候補から正解を探す問題を考える。候補の数を \(M\) とし、各候補 \(i\) が正解であれば \(f(i)=1\)、そうでなければ \(f(i)=0\) を返す関数を用意する。アルゴリズムは候補を指定して \(f(i)\) の値を問い合わせられるが、問い合わせる前には正解がどこにあるか分からない。候補間に、正解の位置を予測できる順序や規則が存在しない場合を想定する。

例えば、100 万件の候補の中に正解が一つだけ含まれている場合、古典計算機が候補を順に調べる方法では、正解が最後に現れると 100 万回の問い合わせが必要になる。候補を無作為な順序で調べても、正解位置に関する情報がなければ、必要な問い合わせ回数は候補数に比例する。既稿「暗号はいずれ破られる」では、探索空間の大きさと、量子探索によって必要な問い合わせ回数が変わる関係を扱っている[16]。

7.1 未整列探索では問い合わせ回数に平方根の差が生じる

正解がちょうど一つ存在すると仮定し、その位置を出力する探索問題を定義する。候補集合を \([M]=\{1,\ldots,M\}\) とすると、求める出力は次の条件を満たす番号 \(i\) である。

\[
i\in[M],\qquad f(i)=1,
\qquad
\sum_{j=1}^{M}f(j)=1
\]

最後の式は、正解が一つだけ存在するという約束を表す。この条件の下で、古典計算機が各候補について正解かどうかを問い合わせる場合を考える。決定的な方法では、正解が最後の未確認候補にある可能性を排除するまで問い合わせが必要になる。正解位置を事前に区別する情報がなければ、最悪の場合の問い合わせ回数は候補数 \(M\) に比例する。

確率的な古典アルゴリズムについても、一定以上の成功確率をすべての正解位置に対して保証するには、候補数に比例する問い合わせ回数が必要になる。例えば、正解位置を一様に選び、重複しない \(q\) 個の候補を調べると、調べた範囲に正解が含まれる確率は \(q/M\) である。未確認の候補から最後に一つを推測する方法を認めても、成功確率は高々 \((q+1)/M\) になる。成功確率を \(2/3\) 以上に保つには、\(q\) を \(M\) に比例させる必要がある。

一方、量子計算機では、候補位置の重ね合わせに対して問い合わせを行い、正解に対応する振幅を増幅する方法が利用できる。Grover の量子探索アルゴリズムは、候補数 \(M\) に対して平方根に比例する問い合わせ回数で正解を発見できる[17]。

\[
R_{\mathrm{search}}(M)=\Theta(M)
\]

\[
Q_{\mathrm{search}}(M)=\Theta(\sqrt M)
\]

ここで \(R_{\mathrm{search}}(M)\) は古典的な探索の問い合わせ計算量、\(Q_{\mathrm{search}}(M)\) は量子的な探索の問い合わせ計算量である。記号 \(\Theta\) は、定数倍の違いを除いて増加率が一致することを表す。上の評価は、正解が一つだけ存在する標準的な未整列探索について、一定以上の成功確率を要求した場合の最適な問い合わせ回数を示している。

例えば、候補数が \(M=10^6\) なら、古典的な探索は \(10^6\) に比例する回数の問い合わせを必要とするのに対し、量子探索では \(\sqrt{10^6}=1000\) に比例する回数で済む。候補数を 100 倍にすると、古典的な問い合わせ回数はおよそ 100 倍になるが、量子的な問い合わせ回数はおよそ 10 倍になる。両者の問い合わせ回数の比は、おおむね \(\sqrt M\) に比例して増加する。

\[
\frac{R_{\mathrm{search}}(M)}
{Q_{\mathrm{search}}(M)}
=\Theta(\sqrt M)
\]

この平方根の高速化は、候補のどれが正解かを発見するという成功条件に対する結果である。また、古典的な下界と量子的な上界を、同じブラックボックスへの問い合わせ回数として比較している。問い合わせ一回の実行時間や、量子状態を準備する処理まで含めた実行時間の比は、別の費用モデルで評価される。

7.2 正解の存在判定と正解位置の出力は異なる

同じ候補集合について、正解の位置を出力する代わりに、正解が存在するかどうかだけを答える問題を考える。各候補の判定結果を \(f(1),\ldots,f(M)\) とすれば、正解の存在を表す関数は次のように定義できる。

\[
\operatorname{OR}_M(f)
=
\begin{cases}
1 & \displaystyle\sum_{i=1}^{M}f(i)\ge1\\
0 & \displaystyle\sum_{i=1}^{M}f(i)=0
\end{cases}
\]

この関数は、少なくとも一つの正解があれば 1、正解が一つもなければ 0 を返す。出力は一つのビットであり、正解の位置そのものを示す必要はない。しかし、出力が一つのビットであることだけから、問い合わせ回数が少なくなるとは限らない。どの候補にも正解が存在しないことを確かめるには、すべての候補について情報が必要になる場合があるからである。

正解が 0 個または 1 個であるという約束を置き、そのどちらであるかを判定する問題では、古典的な確率的アルゴリズムに \(\Theta(M)\)、量子アルゴリズムに \(\Theta(\sqrt M)\) の問い合わせが必要になる。この場合、量子計算による平方根の高速化は、探索問題だけでなく決定問題にも存在する。

一方、正解が必ず一つ存在するという約束を決定問題にも適用すると、存在判定の答えは常に 1 になる。アルゴリズムは問い合わせを一回も行わずに正解できる。しかし、その正解の位置を出力する探索問題では、引き続き \(\Theta(M)\) 回の古典的問い合わせが必要になる。

同じ入力関数を利用していても、約束条件と出力形式の組み合わせによって、計算量が大きく変わる。探索問題と決定問題を区別する理由は、決定問題なら量子高速化が生じないということではない。アルゴリズムが解くべき関数と、正解として提出する情報を明示することで、定理を適用できる問題の範囲が確定するからである。

7.3 一様分布の大部分に対する近似は最悪入力の探索と両立する

未整列探索における平方根の高速化と、Aaronson–Ambainis 予想から導かれる古典的な近似の多項式上界は、どのように両立するのか。この違いは、入力分布と成功条件を明示することで説明できる。正解が存在するかどうかを表す \(\operatorname{OR}_M\) を、長さ \(M\) の二値入力 \(x=(x_1,\ldots,x_M)\) の関数として考える。

\[
\operatorname{OR}_M(x)=
\begin{cases}
1 & x_1+\cdots+x_M\ge1\\
0 & x_1+\cdots+x_M=0
\end{cases}
\]

この関数を、全 \(2^M\) 通りの入力から一様ランダムに選んだ場合に評価する。出力が 0 になるのは、すべてのビットが 0 の入力だけである。したがって、その入力が選ばれる確率は \(2^{-M}\) であり、それ以外の入力では必ず出力が 1 になる。

\[
\Pr_{X\sim U_M}[\operatorname{OR}_M(X)=0]
=2^{-M}
\]

\[
\Pr_{X\sim U_M}[\operatorname{OR}_M(X)=1]
=1-2^{-M}
\]

ここで、入力を一度も調べずに常に 1 を返す古典アルゴリズムを考える。このアルゴリズムは、すべてのビットが 0 の入力でだけ誤答する。したがって、一様分布の下での失敗率は \(2^{-M}\) であり、問い合わせ回数は 0 回である。

\[
\hat p_C(x)=1
\]

\[
\Pr_{X\sim U_M}
[\hat p_C(X)\ne\operatorname{OR}_M(X)]
=2^{-M}
\]

例えば \(M=20\) なら、失敗率は \(1/1048576\)、すなわち約 \(0.0000954\%\) になる。この方法は、正解が存在しない入力については必ず失敗する。しかし、一様分布ではその入力が現れる確率が非常に小さいため、問い合わせなしでも高い正解率を達成する。

これに対し、正解が 0 個または 1 個であるという約束を置くと、対象入力の集合は大きく変わる。すべて 0 の入力が 1 通り、1 が一つだけ存在する入力が \(M\) 通りあるため、約束を満たす入力は合計 \(M+1\) 通りである。全入力に占める割合は次のようになる。

\[
\rho=\frac{M+1}{2^M}
\]

この集合上で一様に入力を選び、常に 1 を返す古典アルゴリズムを実行すると、誤答するのは正解が存在しない 1 通りの入力である。したがって、この約束付き分布における失敗率は \(1/(M+1)\) となる。

さらに、すべての約束付き入力に対して一定以上の成功確率を保証する場合には、正解が存在しない入力と、正解が一つだけ存在する入力を区別しなければならない。この条件では、古典計算機に \(\Theta(M)\) の問い合わせが必要になる。全入力の一様分布に対する平均的な正解率と、約束付きの各入力に対する成功保証が、異なる制約を持つためである。

ここで、Aaronson–Ambainis 予想に基づく帰結は、量子アルゴリズムの受理確率を、全入力の一様分布における大部分で近似する古典的な決定木の存在を保証する。未整列探索の下界は、正解の位置を発見することや、約束を満たすすべての入力に対する成功確率を保証することに関係する。入力分布と成功条件を明示すれば、古典的な近似に多項式上界があるという結果と、量子探索で平方根の高速化が得られるという結果は両立する。

7.4 探索問題には超多項式的な量子優位性の例も存在する

未整列探索の平方根の高速化に加えて、量子計算と古典計算の間に超多項式的な差が生じる探索問題も研究されている。Yamakawa と Zhandry は、ランダムオラクルを利用できる計算モデルにおいて、量子多項式時間で解ける一方、古典的な確率的多項式時間では解けない NP 探索問題の存在を示した[18]。

ランダムオラクルとは、問い合わせ先の入力ごとにランダムな値が割り当てられ、同じ入力を再び問い合わせた場合には同じ値が返される理想化された関数である。古典計算機と量子計算機は同じ関数にアクセスするが、量子計算機は重ね合わせに対する問い合わせを利用できる。このモデルでは、具体的な関数の内部構造を利用する代わりに、オラクルへのアクセス能力が計算量にどのような差を生むかを調べられる。

Yamakawa と Zhandry の結果は、ランダムオラクルに相対化した世界での探索問題の分離である。すなわち、量子多項式時間で有効な解を出力できる問題が存在し、その解を古典的な確率的多項式時間で出力することはできない、という形で計算能力の差を示している。ここでの分離は、標準的な計算モデルにおける \(\mathsf{BQP}\ne\mathsf{BPP}\) を証明したという意味ではない。

この研究は、Aaronson–Ambainis 予想と矛盾しないことも論文中で説明している。理由の一つは、求める出力が異なることである。Aaronson–Ambainis 予想から導かれる古典的な近似は、量子アルゴリズムが 1 を出力する確率を、入力の大部分について近似する。探索問題では、検証条件を満たす具体的な解を出力する必要がある。量子アルゴリズムが有効な解を生成する確率を推定できても、その確率値だけから有効な解そのものを得られるとは限らない。

例えば、ある量子アルゴリズムが有効な解を高い確率で生成するとする。その成功確率を古典的に 0.9 と近似できたとしても、その値は解の位置や内容を指定しない。古典計算機が有効な解を得るためには、解を構成する情報を別途取得する必要がある。成功確率の推定と解の生成では、要求される出力情報が異なる。

また、探索問題で扱う入力集合は、全ビット列の一様分布と異なる制約を持つ場合がある。前節で示したように、全入力に対する近似保証を特定の入力集合へ移すには、その集合の密度や分布の構造を考慮しなければならない。出力形式と入力分布の両方が、どの計算量上の制約を適用できるかを決める。

7.5 並列問い合わせのラウンド数も計算モデルを制限する

量子アルゴリズムでは、問い合わせの総数だけでなく、問い合わせを何段階に分けて行うかも計算能力に関係する。複数の問い合わせを同じ段階で並列に行い、その結果に応じて次の段階の問い合わせを決めるモデルを考える。このとき、問い合わせを行う段階の数をラウンド数と呼ぶ。

問い合わせの総数を \(t\)、ラウンド数を \(r\) とすると、同じ \(t\) 回の問い合わせでも、すべてを少数の並列段階で実行する場合と、前の問い合わせの処理結果を利用しながら逐次実行する場合がある。ラウンド数は、問い合わせの間にどれだけ適応的な処理を行えるかを制限する。総問い合わせ回数だけでは、問い合わせの時間的な依存関係までは表せない。

Blanc、Docter、Strassle、Tan は、2026 年の研究で、量子的な問い合わせを \(r\) ラウンドで実行し、総問い合わせ回数が \(t\) 回である量子アルゴリズムについて、入力の大部分で古典的な近似を行うための問い合わせ回数に次の形の上界を与えた[19]。

\[
C_{\mathrm{cl}}=t^{O(r^2)}
\]

この式は、近似誤差や失敗率を固定したときの、問い合わせ回数 \(t\) とラウンド数 \(r\) に関する増加率を表している。\(O(r^2)\) は、指数がラウンド数の二乗に比例する定数倍の範囲で抑えられることを意味する。ラウンド数 \(r\) が入力規模によらない定数であれば、古典的な問い合わせ回数は \(t\) の多項式で抑えられる。

一方、ラウンド数が問い合わせ回数とともに増える場合には、指数 \(O(r^2)\) も増加する。例えば、\(r\) が \(t\) に比例するなら、得られる評価は \(t^{O(t^2)}\) という形になり、\(t\) に関する固定次数の多項式上界とは異なる。この研究では、問い合わせの総数に加えてラウンド数を制限することで、古典的な近似に関する多項式上界を導いていた。

これに対して、2026 年 11 月に提示された Aaronson–Ambainis 予想の証明では、量子アルゴリズムの問い合わせ回数 \(T\) に基づき、ラウンド数を追加の制約として固定せずに、古典的な近似の問い合わせ回数へ多項式上界を与える。並列ラウンド数を固定した場合の結果と、一般の問い合わせアルゴリズムに対する結果は、仮定の範囲が異なる。前者は問い合わせの適応性に制限を設けて成立する定理であり、後者はその制限を必要としない形で受理確率の近似を扱う。

ただし、ラウンド数に関する制約と、量子回路全体の実行時間や物理的な深さは同じ量ではない。問い合わせの間に行う量子ゲートや、問い合わせを実現するための回路の費用は別に存在する。ラウンド数を減らせることから、実際の量子計算機における総処理時間を同じ割合で減らせると結論するには、追加の費用モデルが必要となる。

計算問題と問い合わせモデルの違いは、次のように整理できる。

対象	求める出力と成功条件	計算量上の性質
未整列探索	正解が一つ存在するという条件の下で、その位置を出力する。	古典的な問い合わせ回数は \(\Theta(M)\)、量子的な問い合わせ回数は \(\Theta(\sqrt M)\) となる。
正解の存在判定	正解が 0 個または 1 個という条件の下で、存在するかどうかを 0 または 1 で答える。	一定以上の成功確率を全入力に要求すると、古典的な問い合わせ回数は \(\Theta(M)\)、量子的な問い合わせ回数は \(\Theta(\sqrt M)\) となる。
一様分布上の存在判定	全二値入力から一様に選び、一定割合の誤答を許して存在を判定する。	常に 1 を返す方法は、問い合わせ 0 回で失敗率 \(2^{-M}\) を達成する。
量子アルゴリズムの受理確率近似	一様分布の大部分の入力について、受理確率との差を許容誤差以内に抑える。	Aaronson–Ambainis 予想に基づく帰結では、古典的な問い合わせ回数が \((4T)^8\epsilon^{-14}\delta^{-8}\) 以下になる。
ランダムオラクル上の探索	指定された条件を満たす具体的な解を出力する。	量子多項式時間で解ける一方、古典的な確率的多項式時間では解けない探索問題が存在する。
ラウンド数を制限した量子問い合わせ	量子問い合わせの総数と並列ラウンド数を制限した上で、受理確率を近似する。	固定された近似条件の下で、古典的な問い合わせ回数に \(t^{O(r^2)}\) という上界が与えられる。

同じ量子計算の高速化であっても、探索では解の位置を出力する能力が問われ、決定問題では真偽を判定する能力が問われる。受理確率の近似では、確率値を一定の誤差以内で求める能力が問われる。さらに、入力分布を一様にするか、特定の条件を満たす入力へ制限するかによって、要求される成功保証が変わる。問い合わせの並列ラウンド数を制限すれば、アルゴリズムに許される適応性も変わる。

Aaronson–Ambainis 予想の証明が与える制約は、量子アルゴリズムの受理確率を一様分布の大部分の入力について古典的に近似する際の問い合わせ回数に関するものである。この条件の下では、量子問い合わせ回数に対して古典的な問い合わせ回数を多項式で抑えられる。一方、未整列探索の最悪入力に対する平方根の高速化や、ランダムオラクル上で有効な解そのものを出力する探索問題の分離は、それぞれ別の成功条件に基づいて成立する。量子高速化の限界は、計算方式だけでなく、出力として何を求めるか、どの入力に正しさを要求するか、どの問い合わせ操作を認めるかによって定まる。

8. 高速化の限界は定理の適用条件によって決まる

量子計算機と古典計算機の性能差は、一つの高速化倍率だけでは表せない。入力の長さが同じでも、求める出力、許容誤差、入力分布、計算資源の測定方法によって、比較する計算量が変わる。前節までに扱った不等式と反例は、これらの条件が計算量の上界にどのように作用するかを示している。特に、量子アルゴリズムの受理確率を古典的に近似する問題では、多項式の値域、分散、次数から変数の影響力を評価し、その結果を問い合わせ回数の上界へ結び付けられる。

この関係を数式で整理する。量子アルゴリズムが \(T\) 回の問い合わせを行い、入力 \(x\) に対して 1 を出力する確率を \(p_A(x)\) とする。受理確率は値域が \([0,1]\) に収まり、次数が高々 \(2T\) の実多項式で表現できる。次数が高々 \(d\) の有界多項式について、今回提示された Aaronson–Ambainis 予想の証明では、少なくとも一つの変数の影響力に次の下界が与えられる。

\[
\max_i I_i(p)\ge
\frac{8\sqrt{15}}{125\pi^4}
\frac{V(p)^{5/2}}{d^6}
\]

この式の \(V(p)\) は全入力を一様に選んだ場合の分散、\(I_i(p)\) は変数 \(i\) を反転させた場合の平均二乗変化である。分散が正で、次数が一定以下に抑えられていれば、入力数 \(N\) を増やしても、少なくとも一つの変数に正の影響力の下界が残る。分散が 0 なら関数値は全入力で一定となり、入力を問い合わせずにその値を返す方法が存在する。関数値に変動が残る場合に、どの変数がその変動に寄与するかが、問い合わせを行う決定木の構成に関係する。

この下界から、受理確率を近似する古典的な決定木の問い合わせ回数に上界を導ける。量子アルゴリズムの受理確率について、許容誤差を \(\epsilon>0\)、許容失敗率を \(0<\delta<1\) とすると、\(T\ge1\) の場合、論文が導く問い合わせ回数の上界は次の形になる。

\[
\boxed{
C_{\mathrm{cl}}\le
(4T)^8\epsilon^{-14}\delta^{-8}
}
\]

この不等式が保証するのは、全入力を一様に選んだとき、少なくとも \(1-\delta\) の割合で量子アルゴリズムの受理確率との差を \(\epsilon\) 以下に抑える古典的な決定木が存在することである。例えば、\(\delta=0.01\) なら、全入力の少なくとも 99% について近似誤差を指定した範囲に収める条件になる。残りの最大 1% に含まれる入力では、同じ精度が保証されるとは限らない。

この上界には、量子問い合わせ回数 \(T\) のほかに、許容誤差と失敗率が独立した変数として含まれる。両者を入力規模によらない正の定数に固定すれば、上界は \(T\) の 8 次多項式になる。しかし、近似条件を入力数に応じて厳しくすると、その増加率も変わる。例えば、許容誤差を \(\epsilon=2^{-N}\) とすれば、\(\epsilon^{-14}=2^{14N}\) となる。許容失敗率を \(\delta=2^{-N}\) とすれば、\(\delta^{-8}=2^{8N}\) となる。どちらの場合も、提示された上界には入力数について指数関数的に増える因子が現れる。

この指数関数的な因子は、近似アルゴリズムに指数関数的な問い合わせ回数が必要だという下界を表しているわけではない。入力が \(N\) ビットなら、すべてのビットを読む方法によって問い合わせ回数を \(N\) 以下に抑えられる。ここで明らかになるのは、誤差条件まで含めた一般的な上界を、\(T\) だけの固定次数の多項式として評価するには、誤差と失敗率をどのように固定するかが必要になるということである。

さらに、入力分布を変更した場合には、近似が失敗する入力の割合も変化する。一様分布における失敗集合を \(B\)、対象とする入力集合を \(S\)、全入力に占める \(S\) の割合を \(\rho\) とすると、\(S\) 内部での失敗率について次の不等式が成立する。

\[
\Pr[X\in B\mid X\in S]
\le
\min\left(1,\frac{\delta}{\rho}\right)
\]

この式では、対象集合の割合 \(\rho\) が小さくなるほど、一様分布上の失敗率から得られる条件付きの保証が悪化する。特に \(\rho\le\delta\) の場合、上界は 1 となり、対象集合内のすべての入力で失敗する可能性が残る。失敗する入力の総数が少なくても、それらが関心のある集合へ集中していれば、その集合に対する近似精度は保証されない。

一方、偏った独立ベルヌーイ分布や、1 の個数を固定したスライス分布については、分布の構造を直接利用する研究によって、一様分布上の Aaronson–Ambainis 予想と対応する予想の同値性が示されている。したがって、一様分布に対する特定の近似結果を別の分布へ移す方法が有効でなくなっても、その分布について別の数学的な保証が成立する場合がある。失敗率の換算による評価と、対象分布に関する定理の成立範囲は、分けて判断する必要がある。

計算の出力形式も同様である。量子アルゴリズムの受理確率を一定の誤差以内で近似することと、探索問題で正しい解の位置を出力することでは、要求される情報が異なる。例えば、ある量子アルゴリズムが正解を発見する確率を 0.9 と推定できても、それだけでは正解の位置を指定できない。受理確率を古典的に近似する問い合わせ回数の上界から、探索問題における解の出力に必要な問い合わせ回数を直接評価することはできない。

これらの条件と保証の関係は、次のように整理できる。

数学的な条件	成立する結論	追加の根拠が必要な判断
値域、分散、次数の制約	分散が正であれば、少なくとも一つの入力変数の平均二乗影響力に、入力数に直接依存しない正の下界を与えられる。	特定の入力でビットを反転させたときの変化量や、影響力の大きい変数を発見する計算時間には、別の評価が必要になる。
一様分布、誤差 \(\epsilon\)、失敗率 \(\delta\)	量子アルゴリズムの受理確率を、一様分布の大部分の入力について古典的に近似する問い合わせ回数へ上界を与えられる。	全入力に対する同じ精度の保証や、異なる入力分布での近似精度には、追加の解析が必要になる。
許容誤差と失敗率の固定	\(\epsilon\) と \(\delta\) を正の定数に固定すると、問い合わせ回数の上界は \(T\) の固定次数の多項式になる。	両者が入力数とともに小さくなる場合には、その変化を上界へ代入して増加率を評価する必要がある。
問い合わせ回数の比較	指定した問い合わせモデルにおいて、古典計算と量子計算の入力アクセス回数を比較できる。	変数の選択、受理確率の算出、量子ゲート、誤り訂正を含む実行時間には、別の費用モデルが必要になる。
受理確率の近似	量子アルゴリズムの受理確率を低次数多項式として表現し、古典的な近似の問い合わせ回数を評価できる。	探索問題で具体的な解を出力する能力や、その成功確率については、出力条件に対応した評価が必要になる。

表の各行は、異なる種類の制約を表している。値域、分散、次数は関数の数学的な形を制限する。一様分布と誤差条件は、近似結果の正しさをどの入力について要求するかを定める。問い合わせ回数は、入力から情報を得る費用を測る。出力形式は、アルゴリズムが最終的に何を計算したと認められるかを決める。これらを組み合わせた条件が一致して初めて、古典計算と量子計算の性能差を同一の基準で比較できる。

今回の研究成果については、数学的な命題の証明と、計算量に関する帰結の対応も確認対象になる。既稿「証明はいつ数学的知識になるのか」では、形式的な証明が検査された状態と、証明が主張する数学的な意味を検討し、研究共同体が評価する過程との違いを扱っている[20]。今回公開された公理監査資料でも、Lean の検査対象は形式化された命題とその証明であり、形式命題が元の Aaronson–Ambainis 予想と同じ数学的内容を表しているか、論文の説明が形式証明と対応しているかについては、別に確認する必要があると明示されている[21]。

ここで確認すべき対応には、複数の段階がある。第一に、Lean に記述された影響力の定義、分散の正規化、次数の条件、定数が、元の予想と一致する必要がある。第二に、その形式命題について証明検査が成立していることを確認する必要がある。第三に、得られた影響力の下界を量子問い合わせ回数の上界へ適用する際、受理確率の多項式表現と元の Aaronson–Ambainis の計算量上の帰結が、同じ条件の下で利用されていることを確かめる必要がある。

Lean による形式検証は、このうち形式命題に対する証明の妥当性を検査する根拠になる。一方、元の予想との意味上の一致や、外部の定理を利用して導く計算量上の帰結については、その接続を数学的に確認する作業が残る。研究側が公開した形式証明と監査資料は検証可能性を高めるが、それらが公開されていることだけをもって、すべての帰結について独立した検証が完了したと判断することはできない。

Aaronson–Ambainis 予想について今回提示された証明が妥当であれば、値域が有界で次数が制限された多項式には、分散に応じた影響力の下界が存在する。この結果を受理確率の多項式表現へ適用すると、量子アルゴリズムの受理確率を一様分布の大部分の入力で近似する古典的な決定木について、問い合わせ回数を量子問い合わせ回数の多項式で抑えられる。これは、指定した問題と成功条件において、問い合わせ回数に超多項式的な差が必要となる可能性を制限する結果である。

その一方、探索問題で有効な解を出力する場合には、量子計算による平方根の高速化や、ランダムオラクル上での超多項式的な分離が存在する。実行時間についても、問い合わせ以外の演算費用を含めた評価が必要になる。これらの結果は互いに矛盾するものではない。それぞれが別の入力条件、出力条件、費用モデルについて成立しているためである。

量子計算機が古典計算機より速く問題を解けるかという問いは、入力分布、出力の種類、誤差条件、計算資源を指定することで、数学的に判定できる形になる。今回の影響力の下界が制限するのは、低次数の有界多項式として表現される量子アルゴリズムの受理確率について、一様分布の大部分で古典的な近似を行うための問い合わせ回数である。量子計算の高速化の限界は、量子計算機という計算方式全体に一つの数値として与えられるのではなく、どの関数を、どの入力分布で、どの精度まで、どの計算資源を使って求めるかという条件の組によって定まる。

参考文献

id774, ソフトウェアの複雑性はどこへ移るのか（2026-11-06）. https://blog.id774.net/entry/2026/11/06/5613/
Ryan O’Donnell, Analysis of Boolean Functions, Cambridge University Press, 2014-06-05. https://www.cambridge.org/core/books/analysis-of-boolean-functions/B05A66E4DCC778E02B84C16376F4D1FD/listing
Robert Beals et al., Quantum Lower Bounds by Polynomials, Journal of the ACM, 2001-07. https://doi.org/10.1145/502090.502097
Noam Nisan, Mario Szegedy, On the degree of boolean functions as real polynomials, Computational Complexity, 1994-12. https://doi.org/10.1007/BF01263419
Ryan O’Donnell et al., Every decision tree has an influential variable（2005-08-16）. https://arxiv.org/abs/cs/0508071
Irit Dinur et al., On the Fourier tails of bounded functions over the discrete cube, Israel Journal of Mathematics, 2007-08. https://doi.org/10.1007/s11856-007-0068-9
Yuval Filmus et al., On the sum of the L1 influences of bounded functions（2014-04-13）. https://arxiv.org/abs/1404.3396
Scott Aaronson, Andris Ambainis, The Need for Structure in Quantum Speedups, Theory of Computing, 2014-08-12. https://www.theoryofcomputing.org/articles/v010a006/
Shachar Lovett, Jiapeng Zhang, Fractional Certificates for Bounded Functions, ITCS, 2023-02-01. https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.84
Avantika Agarwal, Shalev Ben-David, Oracle Separations for the Quantum-Classical Polynomial Hierarchy（2024-10-24）. https://arxiv.org/abs/2410.19062
Nikhil Bansal, Makrand Sinha, Ronald de Wolf, Influence in Completely Bounded Block-multilinear Forms and Classical Simulation of Quantum Algorithms（2022-03-01）. https://arxiv.org/abs/2203.00212
David Turturean, A proof of the Aaronson–Ambainis conjecture（2026-11）. https://github.com/physical-superintelligence/aaronson-ambainis/blob/main/paper/aaronson_ambainis_paper.pdf
Physical Superintelligence, AaronsonAmbainis/Conjecture.lean. https://github.com/physical-superintelligence/aaronson-ambainis/blob/main/AaronsonAmbainis/Conjecture.lean
id774, 量子計算機はなぜ壊れやすい情報で計算できるのか（2026-06-11）. https://blog.id774.net/entry/2026/06/11/4874/
Uma Girish et al., Distributional Variants of the Aaronson-Ambainis Conjecture（2026-09-28）. https://arxiv.org/abs/2609.35327
id774, 暗号はいずれ破られる（2026-06-01）. https://blog.id774.net/entry/2026/06/01/4831/
Lov K. Grover, A fast quantum mechanical algorithm for database search, STOC, 1996-07-01. https://doi.org/10.1145/237814.237866
Takashi Yamakawa, Mark Zhandry, Verifiable Quantum Advantage without Structure, Journal of the ACM, 2024-06-11. https://doi.org/10.1145/3658665
Guy Blanc et al., Quantum Speedups Require Structure or Depth（2026-08-19）. https://arxiv.org/abs/2608.19158
id774, 証明はいつ数学的知識になるのか（2026-10-09）. https://blog.id774.net/entry/2026/10/09/5760/
Physical Superintelligence, Axiom audit. https://github.com/physical-superintelligence/aaronson-ambainis/blob/main/notes/AXIOM_AUDIT.md