.svg)
CLASSIQエンジン：満足のいく開発体験
数独パズルを解いたことはありますか？スマートフォンの登場よりずっと前の2000年代初頭に流行し、当時は多くの人たちが夢中になって解いたものでした。これほどまで流行したのは、人々が他にすることがなかったからかもしれませんが（笑）。数独をご存じない方のために説明すると、数独は9X9のマス目を、各行と各列に1-9の数字を一度ずつだけ使って埋めるゲームです。このパズルは「制約充足問題（Constraint Satisfaction Problem：CSP）」と呼ばれるものです。CSPとは、あるルール（例えば、ある数字を繰り返してはいけない）に違反しないように、アイテム（例えば1から9までの数字）を「空欄」に埋める問題です。このような問題は私たちが思っているよりも身近で、他にもクロスワードパズルのようなゲームや地図の色分け問題[https://en.wikipedia.org/wiki/Four_color_theorem]）など、さまざまな面白い問題があります。しかし、私たちがCSPに注目しているのは数学的な定理を証明したいからではなく、もっと実用的な理由からです。少なくとも、量子アルゴリズム設計の分野においては。
量子回路の最適化
「フリーランチはない」という格言がありますが、効率良く成果を得るのは悪いことではありません。そしてこれは何かの問題指標を最大化（または最小化）する方法を見つけるという、最適化技術の目的でもあります。こうした問題には様々な種類があり、最適化の対象が連続的な値の場合もあれば、離散的な値の場合もあります。さらに最適化空間は有限にも無限にもなり、さまざまに変化します。CSPには一連の制約があり、それらすべてをできるだけ満たすという目標があります。このようなCSPのサブクラスは「CSOP（Constraint Satisfaction Optimization Problem）」と呼ばれ、「O」は「最適化（Optimization）」を意味します。量子アルゴリズムを設計する際、私たちは構成要素を「高レベル」で構築したいと考えます。つまり、個々の量子ゲートを直接扱うのではなく、関数呼び出しをゲートシーケンスに変換する形で扱いたいのです。これは高レベルの関数呼び出しをゲートシーケンスに置き換えるプロセスであり、「合成（Synthesis）」と呼ばれます。このプロセスで行われることは他にもいろいろとありますが、話を簡単にするため、ここではその一部だけを取り上げます。合成の際には、主に量子ハードウェアの制約を受けます。具体的には使用可能な量子ビットの数や、ノイズが制御不能になる前に実行できる回路の深さの上限などが挙げられます。こうして残される課題は、指定された制約を最適に満たすように、関数に対してリソース（量子ビット数、回路の深さなど）を割り当てることです。
目標達成後も、基盤は動き続ける
単純なケースでは、各関数呼び出しは「マスク」として扱われ、決まったゲートシーケンスに置き換えることができます。そのシーケンスを順に並べていくと回路ができあがります。しかし、それではあまりに単調で、合成する余地はほとんどありません。このケースでは、関数呼び出しのシーケンスが回路の結果を一意に決定します。幸いにも、実際にはもっと奥が深く、より難しい問題がここで起きています。というのも、関数によっては正しい実装が複数存在するからです。異なる実装が生まれる理由は様々で、例えば、ハードウェアに依存する実装などが考えられます。これは、イオントラップ型量子プロセッサと中性原子型量子プロセッサ（または他の量子ビット型）のゲートセットが異なるために発生します。もう一つの理由は、量子ビットの接続マップによるものです。これらのマップは、どの量子ビットのペアで条件演算ができるかを指定するものですが、量子ビットチップのアーキテクチャによって異なります（同じ量子ビットタイプでも異なるアーキテクチャが存在する場合があります）。複数の実装が生まれる要因は、ハードウェアの違いだけではありません。その一例として、加算回路の例が挙げられます。この回路要素は、異なるレジスタ（量子ビットのセット）で表される数値を加算する機能を持っており、古典コンピュータでも必須の構成要素です。量子計算においても同様に価値があり、この要素を実装するには、リップルキャリー回路（https://en.wikipedia.org/wiki/Adder_(electronics)#Ripple-carry_adder）や量子フーリエ変換（https://arxiv.org/pdf/1411.5949.pdf）を用いるなど、複数の量子論理ゲートによる表現が存在します。それぞれの実装は、使用する量子ビット数や回路の深さ、実行される二量子ビット演算の数など、異なる特徴を持っています。
リソースの節約と再利用
コンピューティングにおけるリソースは、量子に限らず、限られています。本当に簡単な問題でなければ、通常はスピードが足りないか、スペースが足りないかのどちらかの壁にぶつかるでしょう。多くの場合、これらの問題の一方を他方に変換することができますが、必ずしも上手くいくわけではありません。このため、リソースを節約する方法を開発することは、コンピューティングにおいて長い伝統であり、重要な取り組みです。効率的なメモリ管理やガベージコレクションは不可欠であり、プログラム内で同じビットの物理空間を繰り返し再利用することを可能にします。これらのタスクを自動化することは、電子設計自動化（EDA）ソフトウェアの領域であり、CLASSIQエンジンのインスピレーションの源にもなりました。
量子プログラムの合成では、特に難しい部分が補助量子ビットの取り扱いです。ここで再び、合成エンジンが行うべきタスクに注目してみましょう。 エンジンは高レベル関数の実装を選択し、それを後続の関数実装に「接続」します。その関数が補助量子ビット（または量子ビット）を持ち、使用後に不要になった場合、別の関数で再利用できます。もし再利用できず、次の関数が補助量子ビットを必要な場合は、その関数に新しい量子ビットを割り当てなければなりません（が、必ずしも手持ちがあるとは限りません！）。この補助量子ビットの再利用は、私たちが解こうとしている制約満足（および最適化）問題をある意味「非局所的」にします。例えば、回路の最初の段階で行った実装（および補助量子ビットの配線）の選択が、一見良い考えのように思えても、のちにそれがより適した実装の選択を妨げる可能性があります。目標を最適化するために、全体的に良いとはいえない実装を選ばざるを得ないこともあるかもしれません。最終的な目標は変動し続けるため、選択を見直し、遡って変更することになるでしょう。現実世界でもこのような自由があれば良いのですが。
成功のためのシンプルな戦略
関数を配置し、それぞれにリソースを割り当てる方法は無数に存在します。その数は、量子がそうであるように、関数の数が増えるにつれて、その組み合わせも指数関数的に増えていきます。つまり、関数呼び出しが多数ある場合、総当たり的なアプローチでは可能性の検索を効率化する量子コンピュータがない限り、（おそらく）問題を解決できません。たとえ量子コンピュータを使えたとしても、探索結果をどこかに保存する必要があるため、それだけでは足りないでしょう。
この難題に取り組む方法は様々あります。最初のアプローチは時間はかかりますが、少なくとも体系的な方法であるバックトラッキングアルゴリズム（（https://en.wikipedia.org/wiki/Backtracking）を使うことです。これはレイヤーごとに回路を構築する、インクリメンタル（再帰的）な方法です。これをさらに改良するための、巧妙なヒューリスティクスに基づく、より優れたアルゴリズムが存在します。こうした手法については、今後のブログ記事で紹介していきます。
次にくるのは？
今回は、CSPの世界と、それが量子アルゴリズムの回路合成の問題にどのように応用されるか、その一部をご紹介しました。CLASSIQでは、これを「ブレッド＆バター（欠かせない基本的なもの）」と呼んでいます。私たちは問題の設定と、それに取り組み始めるための単純な方法について学びました。しかし、CLASSIQエンジンはこれらのアイデアをさらに発展させています。ブロックの実装選択を迅速かつ効率的に行うための、より複雑で巧妙な手法を適用するだけでなく、構築すべき回路の量子固有の特性がもたらす課題に応じた問題の拡張も行われています。例えば、CSOPの問題を解決する際に、回路途中での測定が可能な場合はどうでしょうか？コヒーレントノイズやインコヒーレントノイズなどの考慮事項をどのように合成エンジンに組み込むべきでしょうか？また、古典と量子のハイブリッド計算ワークフローにおける情報処理を、実行時に回路の合成や再合成にどのように取り込むべきでしょうか？これらはどれも難しく、興味深い課題です。今後の記事では、回路合成の世界とそのアルゴリズム的な課題についてさらに深く掘り下げていく予定です。
数独パズルを解いたことはありますか？スマートフォンの登場よりずっと前の2000年代初頭に流行し、当時は多くの人たちが夢中になって解いたものでした。これほどまで流行したのは、人々が他にすることがなかったからかもしれませんが（笑）。数独をご存じない方のために説明すると、数独は9X9のマス目を、各行と各列に1-9の数字を一度ずつだけ使って埋めるゲームです。このパズルは「制約充足問題（Constraint Satisfaction Problem：CSP）」と呼ばれるものです。CSPとは、あるルール（例えば、ある数字を繰り返してはいけない）に違反しないように、アイテム（例えば1から9までの数字）を「空欄」に埋める問題です。このような問題は私たちが思っているよりも身近で、他にもクロスワードパズルのようなゲームや地図の色分け問題[https://en.wikipedia.org/wiki/Four_color_theorem]）など、さまざまな面白い問題があります。しかし、私たちがCSPに注目しているのは数学的な定理を証明したいからではなく、もっと実用的な理由からです。少なくとも、量子アルゴリズム設計の分野においては。
量子回路の最適化
「フリーランチはない」という格言がありますが、効率良く成果を得るのは悪いことではありません。そしてこれは何かの問題指標を最大化（または最小化）する方法を見つけるという、最適化技術の目的でもあります。こうした問題には様々な種類があり、最適化の対象が連続的な値の場合もあれば、離散的な値の場合もあります。さらに最適化空間は有限にも無限にもなり、さまざまに変化します。CSPには一連の制約があり、それらすべてをできるだけ満たすという目標があります。このようなCSPのサブクラスは「CSOP（Constraint Satisfaction Optimization Problem）」と呼ばれ、「O」は「最適化（Optimization）」を意味します。量子アルゴリズムを設計する際、私たちは構成要素を「高レベル」で構築したいと考えます。つまり、個々の量子ゲートを直接扱うのではなく、関数呼び出しをゲートシーケンスに変換する形で扱いたいのです。これは高レベルの関数呼び出しをゲートシーケンスに置き換えるプロセスであり、「合成（Synthesis）」と呼ばれます。このプロセスで行われることは他にもいろいろとありますが、話を簡単にするため、ここではその一部だけを取り上げます。合成の際には、主に量子ハードウェアの制約を受けます。具体的には使用可能な量子ビットの数や、ノイズが制御不能になる前に実行できる回路の深さの上限などが挙げられます。こうして残される課題は、指定された制約を最適に満たすように、関数に対してリソース（量子ビット数、回路の深さなど）を割り当てることです。
目標達成後も、基盤は動き続ける
単純なケースでは、各関数呼び出しは「マスク」として扱われ、決まったゲートシーケンスに置き換えることができます。そのシーケンスを順に並べていくと回路ができあがります。しかし、それではあまりに単調で、合成する余地はほとんどありません。このケースでは、関数呼び出しのシーケンスが回路の結果を一意に決定します。幸いにも、実際にはもっと奥が深く、より難しい問題がここで起きています。というのも、関数によっては正しい実装が複数存在するからです。異なる実装が生まれる理由は様々で、例えば、ハードウェアに依存する実装などが考えられます。これは、イオントラップ型量子プロセッサと中性原子型量子プロセッサ（または他の量子ビット型）のゲートセットが異なるために発生します。もう一つの理由は、量子ビットの接続マップによるものです。これらのマップは、どの量子ビットのペアで条件演算ができるかを指定するものですが、量子ビットチップのアーキテクチャによって異なります（同じ量子ビットタイプでも異なるアーキテクチャが存在する場合があります）。複数の実装が生まれる要因は、ハードウェアの違いだけではありません。その一例として、加算回路の例が挙げられます。この回路要素は、異なるレジスタ（量子ビットのセット）で表される数値を加算する機能を持っており、古典コンピュータでも必須の構成要素です。量子計算においても同様に価値があり、この要素を実装するには、リップルキャリー回路（https://en.wikipedia.org/wiki/Adder_(electronics)#Ripple-carry_adder）や量子フーリエ変換（https://arxiv.org/pdf/1411.5949.pdf）を用いるなど、複数の量子論理ゲートによる表現が存在します。それぞれの実装は、使用する量子ビット数や回路の深さ、実行される二量子ビット演算の数など、異なる特徴を持っています。
リソースの節約と再利用
コンピューティングにおけるリソースは、量子に限らず、限られています。本当に簡単な問題でなければ、通常はスピードが足りないか、スペースが足りないかのどちらかの壁にぶつかるでしょう。多くの場合、これらの問題の一方を他方に変換することができますが、必ずしも上手くいくわけではありません。このため、リソースを節約する方法を開発することは、コンピューティングにおいて長い伝統であり、重要な取り組みです。効率的なメモリ管理やガベージコレクションは不可欠であり、プログラム内で同じビットの物理空間を繰り返し再利用することを可能にします。これらのタスクを自動化することは、電子設計自動化（EDA）ソフトウェアの領域であり、CLASSIQエンジンのインスピレーションの源にもなりました。
量子プログラムの合成では、特に難しい部分が補助量子ビットの取り扱いです。ここで再び、合成エンジンが行うべきタスクに注目してみましょう。 エンジンは高レベル関数の実装を選択し、それを後続の関数実装に「接続」します。その関数が補助量子ビット（または量子ビット）を持ち、使用後に不要になった場合、別の関数で再利用できます。もし再利用できず、次の関数が補助量子ビットを必要な場合は、その関数に新しい量子ビットを割り当てなければなりません（が、必ずしも手持ちがあるとは限りません！）。この補助量子ビットの再利用は、私たちが解こうとしている制約満足（および最適化）問題をある意味「非局所的」にします。例えば、回路の最初の段階で行った実装（および補助量子ビットの配線）の選択が、一見良い考えのように思えても、のちにそれがより適した実装の選択を妨げる可能性があります。目標を最適化するために、全体的に良いとはいえない実装を選ばざるを得ないこともあるかもしれません。最終的な目標は変動し続けるため、選択を見直し、遡って変更することになるでしょう。現実世界でもこのような自由があれば良いのですが。
成功のためのシンプルな戦略
関数を配置し、それぞれにリソースを割り当てる方法は無数に存在します。その数は、量子がそうであるように、関数の数が増えるにつれて、その組み合わせも指数関数的に増えていきます。つまり、関数呼び出しが多数ある場合、総当たり的なアプローチでは可能性の検索を効率化する量子コンピュータがない限り、（おそらく）問題を解決できません。たとえ量子コンピュータを使えたとしても、探索結果をどこかに保存する必要があるため、それだけでは足りないでしょう。
この難題に取り組む方法は様々あります。最初のアプローチは時間はかかりますが、少なくとも体系的な方法であるバックトラッキングアルゴリズム（（https://en.wikipedia.org/wiki/Backtracking）を使うことです。これはレイヤーごとに回路を構築する、インクリメンタル（再帰的）な方法です。これをさらに改良するための、巧妙なヒューリスティクスに基づく、より優れたアルゴリズムが存在します。こうした手法については、今後のブログ記事で紹介していきます。
次にくるのは？
今回は、CSPの世界と、それが量子アルゴリズムの回路合成の問題にどのように応用されるか、その一部をご紹介しました。CLASSIQでは、これを「ブレッド＆バター（欠かせない基本的なもの）」と呼んでいます。私たちは問題の設定と、それに取り組み始めるための単純な方法について学びました。しかし、CLASSIQエンジンはこれらのアイデアをさらに発展させています。ブロックの実装選択を迅速かつ効率的に行うための、より複雑で巧妙な手法を適用するだけでなく、構築すべき回路の量子固有の特性がもたらす課題に応じた問題の拡張も行われています。例えば、CSOPの問題を解決する際に、回路途中での測定が可能な場合はどうでしょうか？コヒーレントノイズやインコヒーレントノイズなどの考慮事項をどのように合成エンジンに組み込むべきでしょうか？また、古典と量子のハイブリッド計算ワークフローにおける情報処理を、実行時に回路の合成や再合成にどのように取り込むべきでしょうか？これらはどれも難しく、興味深い課題です。今後の記事では、回路合成の世界とそのアルゴリズム的な課題についてさらに深く掘り下げていく予定です。
