量子回路の同じ計算を、もっと少ない操作で実行したい。少しの誤差を許せば、候補は増え、短い回路を見つけやすくなるように思えます。それでも、どんな入力回路に対しても、許容範囲内の最良の短縮を判定することには、強い計算上の難しさが残ります。
2026年11月3日に公開された、オーフス大学のAdam Husted Kjelstrøm氏、Jaco van de Pol氏、Andreas Pavlogiannis氏の論文は、この量子回路の近似最適化を計算量の観点から調べています。距離の測り方や削減する資源を分けたうえで、広い誤差許容範囲でPP困難という結果を示すプレプリントです。コンパイラの処理時間を測った実験ではなく、一般的な判定問題の難しさを示す理論研究です。
簡単にまとめると？
- 「少し短くできた」と「これ以上短くできないと保証する」は、別の課題です。論文は後者にもつながる一般的な判定の難しさを扱います。
- 回路全体を何もしない操作へ置き換えられるか、という特別な場合だけでも、近似を許した判定はPP困難になります。
- 難しさは、距離の定義と入力への条件を含む結果です。実用的な局所最適化が役に立たないことや、すべての回路が同じだけ難しいことを意味しません。
誤差の予算と、操作数の予算を分ける
論文が考える問題には、二つの上限があります。一つは元の回路と新しい回路の動作の違いを測る距離の上限ε、もう一つは新しい回路に使えるコストの上限kです。コストには、総ゲート数や、並列に実行できる段階を数えた回路の深さなどを選べます。
問うのは、「元の回路との距離がε以下で、コストがk以下の回路が存在するか」です。ここでの近似は、回路の動作を少し変えることを許すという意味です。最適化プログラムが、判定をときどき間違えてよいという条件とは異なります。
たとえば、同じ量子ビットへXゲートを続けて二回かける部分は、二回の反転で元に戻るので削除できます。このように局所的な規則だけで分かる簡単な例はあります。難しさの主張は、あらゆる回路に対して同じように判定できる一般的な手順へ向けられています。
何もしない回路に近いか、だけでも難しい
総ゲート数の予算をk＝0にすると、候補はゲートを一つも使わない回路になります。その動作は、入力をそのまま返す恒等変換Iです。つまり、一般的な最適化を解けるなら、「この回路は、何もしない動作に十分近いか」という問いも解けなければなりません。
著者らは、この近似恒等性の判定へ、別の難しい問題を変換して埋め込みます。その一つが、論理式を満たす0と1の入力の割合が、指定した閾値以下かどうかを判定する問題です。入力がnビットなら組み合わせは2のn乗通りありますが、論点は単に全列挙が多いことではありません。この割合の判定を解けることが、PPという計算量クラスに属する問題を解けることにつながります。
PPは、確率的な多項式時間の計算で、受理する確率が半分を超えるかどうかによって答えを定める問題のクラスです。半分からどれだけ離れているかという余裕は要求されません。したがって、少しだけ半分を超える場合まで含めて判定する必要があり、通常の少数回の無作為な試行で安定して答えが得られるという意味ではありません。
PP困難とは、このクラスのどの問題も、効率よく対象の問題へ変換できるという性質です。対象を一般に効率よく解けるなら、元の広い問題群も効率よく解けてしまいます。ただし、それだけで、すべての個別回路に指数時間が必要だと証明したことにはなりません。
入力の割合が、回路の距離へ現れる
論文のトレースに基づく距離の場合は、変換の仕組みを比較的簡単に追えます。論理式が真になる入力xのときだけ、もう一つの出力ビットbを反転する可逆回路を作ります。動作は「xはそのまま、bは条件に応じて反転」です。
論理式を満たす入力の割合をγとすると、反転しない基底状態の割合は1−γになります。この回路と恒等変換とのSine距離は、√（1−（1−γ）²）と表せます。γが大きいほど距離も大きくなるため、回路が閾値以内の距離にあるかという判定に、入力割合の判定を移せます。
この構成は、X、CNOT、Toffoliという古典可逆ゲートでも実現できます。少なくとも、この距離に関する近似恒等性の難しさは、重ね合わせを新たに作るゲートだけが原因ではないことが分かります。ほかの距離や資源については、論文中で別の構成と条件が使われています。
同じεでも、距離の意味が違う
回路の「似ている」をどう測るかは、結果の適用範囲に直結します。論文は三つの距離を区別しています。
| 論文の距離 | 捉える違い | 全体の位相 |
|---|---|---|
| Sine距離 | 二つの変換のトレースの重なりに基づく、全体を平均する性格の指標 | 全体の位相だけの違いは数えない |
| Spectral距離 | 入力状態について最も大きくなる、状態ベクトルの違い | 全体の位相の違いも数える |
| Operator距離 | 全体の位相をそろえたうえで、最も大きくなる違い | 全体の位相だけの違いは数えない |
たとえばIと−Iは、状態全体に同じ位相が付く点だけが違います。論文のSpectral距離では2ですが、全体の位相を調整するOperator距離では0です。Sine距離でも0になります。同じ数値のεを置いても、同じ誤差条件を課したことにはなりません。
主定理は、Clifford＋Tを厳密に実装できるゲート集合と、必要な精度まで効率よく計算できるεを対象にします。恒等変換への近似や総ゲート数・総深さの最適化では、それぞれの距離の自明でない許容範囲全体でPP困難性が示されます。一方、非Cliffordゲートなど特定の資源だけを削る場合には、証明が届くεの範囲が異なります。すべての資源、すべての許容誤差で同じ結論が出た、と広げることはできません。
境界に近い入力を除くかどうかも条件になる
従来の近似恒等性の研究には、入力回路が「十分近い」か「十分遠い」かのどちらかで、中間の曖昧な領域には入らないという約束を置く設定があります。近い側と遠い側の間に、入力サイズに対して一定以上の隙間を持たせることで、判定する課題を定めます。
今回の主結果は、そのような隙間を保証しない入力を扱います。εのすぐ近くにある回路も除外せず、どちら側かを判定する課題です。近似を認めることと、判定の境界に余裕を設けることは別であり、この条件の違いを落とすと、過去の結果との比較を誤ります。
実用的なコンパイラを評価する際には、まずどの距離で誤差を確かめ、どの資源を減らすのかを明示します。そのうえで、改善した回路が得られたことと、最良だと保証できたことを分けます。特定の構造に絞る、局所的な置換を使う、時間を決めて良い候補を探す、といった方法の価値は、この最悪時の難しさによって失われません。
この論文が示すのは、近似を許せば最適化の根本的な難しさも消える、とは限らないという境界です。回路を短くする成果を読むときも、短縮率とあわせて、許した誤差、対象とした入力、保証した範囲を見ることが大切になります。
出典
- Adam Husted Kjelstrøm, Jaco van de Pol, Andreas Pavlogiannis, On the Hardness of Approximate Quantum Circuit Membership and Optimization, arXiv:2611.04381v1（2026年11月3日公開）。問題設定・主定理・許容範囲は第1節とTable 1、距離とPPの定義は第2節、可逆回路によるSine距離の構成は第3.2.1節、最適化への帰結はCorollary 1、未解決範囲は第5節。