.svg)
CLASSIQエンジン：私は満足を得ることができる
数独を解いたことがあるだろうか？2000年代前半のある時期にかなり流行った。なぜかみんな解いていた。スマートフォンが登場するずっと前のことだ。人々は他にすることがなかったのだ。数独を知らない人もいるかもしれないが、数独のゴールは9X9のマス目を数字で埋めることである。この種のパズルは制約充足問題（CSP）の一例である。CSPとは、ある可能性の集合（例えば1から9までの数字）から、あるアイテム（例えば数字）で「空白を埋め」なければならないが、あるルール（例えば数字を繰り返してはならない）には違反してはならないという問題である。
CSPのクラスには、ゲーム（あらゆるクロスワードパズル）、数学（地図の色付け[https://en.wikipedia.org/wiki/Four_color_theorem]）などの形で、他の、間違いなくもっと面白い例がある。しかし、この全体が我々にとって重要なのには理由があり、それは数学の定理を証明したいからではない。それよりももっと実用的なことなのだ。少なくとも、量子アルゴリズム設計の仕事をしているのであれば。
量子回路の最適化
タダ飯はないが、最高の利益を得るのはいいことだ。それが最適化技術のポイントだ。ある問題のメトリックを最大化（または最小化）する方法を見つけるのだ。このような問題には多くの種類がある。最適化しようとしているものが連続的な値をとることもあれば、離散的な値をとることもあります。最適化空間は有限にも無限にもなり、さまざまに変化します。CSPには制約のセットがあり、そのすべてを可能な限り満たすようにします。このCSPのサブクラスはCSOPと呼ぶことができる。"O "は "Optimization"（最適化）を意味する。
量子アルゴリズムを設計し、ビルディングブロックを "ハイレベル "にしたい。そのため、個々の量子ゲート以外のものを使いたい。その代わりに、正しいゲートシーケンスに変換される関数コールを使いたい。高レベルの関数コールをゲートシーケンスに置き換えるこのステップは、合成と呼ばれる。ここで行われることはこれだけではないが、簡単にするために、ある側面だけを考えてみよう。合成を行う場合、主に量子ハードウェアの制約を受ける。利用可能な量子ビット数には限りがあり、ノイズに圧倒される前に実行できる回路の深さには上限がある、などです。
私たちに残されたゲームは次のようなものです：リソース（量子ビット数、回路の深さなど）を、指定された制約を最適に満たすように関数に割り当てる。
目標は達成したが、地面は動いている
単純なケースでは、各関数呼び出しは「マスク」であり、固定のゲートシーケンスに置き換えることができる。これらのシーケンスを次々に配置し、回路を得る。これではつまらないし、合成の自由度も少ない。この場合、関数呼び出しのシーケンスが、結果として得られる回路を一意に決定する。幸運なことに、ここではもっと興味深く、もっと難しいことが実際に起こっている。
これは、あなたが想定している以上に興味深い問題である。なぜなら、いくつかの関数には正しい実装が1つ以上存在するからである。異なる実装は、さまざまな理由で生じます。一例として、ハードウェア依存の実装があります。これは、トラップドイオン型量子プロセッサーと中性原子型量子プロセッサー（または他の量子ビット型）のネイティブゲートセットが異なるために起こります。もう一つは、量子ビットの接続マップによるものである。このマップは、どの量子ビットのペアで条件演算を行うかを指定するもので、量子ビットチップアーキテクチャによって（同じ量子ビットタイプであっても）異なる。
複数の実装が存在するのは、ハードウェアの違いだけが原因ではない。その一例が加算回路である。この回路素子は、異なるレジスタ（量子ビットの集合）で表される数値を加算することができる。これは、古典的なものを含むあらゆるコンピュータの基本的な構成要素である。量子計算においても同様に価値がある。この要素を実装するには、量子論理ゲートとして複数の表現がある。加算器の目的は、リップルキャリー回路（https://en.wikipedia.org/wiki/Adder_(electronics)#Ripple-carry_adder）や量子フーリエ変換（本論文参照：https://arxiv.org/pdf/1411.5949.pdf）によって達成することができる。使用する量子ビットの数、回路の深さ、実行される2量子ビット演算の数など、異なる実装には異なる特徴があります。
リデュース、リユース、リサイクル
量子であれ何であれ、コンピューティングにおけるリソースは乏しい。本当に簡単な問題を解くのでなければ、通常、2つの壁のどちらかにぶつかる。十分なスピードがないか、十分なスペースがないかだ。多くの場合、これらの問題の一方をもう一方に変換することができるが、それは時々であり、時々しか役に立たない。
このため、リソースを倹約して利用する方法を開発することは、コンピューティングにおける古くからの（そして必要な）伝統である。効率的なメモリー管理やガベージ・コレクションは不可欠であり、プログラム内で同じビットの物理空間を繰り返し再利用することを可能にする。これらのタスクを自動化することは、電子設計自動化（EDA）ソフトウェアの領域であり、CLASSIQエンジンのインスピレーションの源となった。
量子プログラムを合成する際、特に厄介なのは補助量子ビットをどうするかである。
エンジンは高レベル関数の実装を選択し、それを次の関数の実装に "接続 "する。もしその関数が補助量子ビット（または量子ビット）を持っていれば、それは別の関数で再利用することができます。再利用できず、次の関数も補助量子ビットを必要とする場合、その関数に新しい量子ビットを割り当てなければなりません（手元にないかもしれません！）。
この補助量子ビットの再利用は、ある意味で、私たちが解こうとしている制約充足（と最適化）問題を「非局所的」にします。回路の最初に1つの実装（と補助量子ビットの配線）を選択した場合、その時点では良いアイデアだと思えたのですが、後になってあまり適切でない実装を選択せざるを得なくなったとしたらどうでしょう？私の目標を最適化するために、全体的に悪い実装を選ばざるを得なかったとしたら？選択した結果、最終的なゴールが一方向に動いてしまい、自分の決断を再評価し、遡及的に変更せざるを得なくなる。実生活でこのような自由が与えられていればいいのだが。
成功のためのシンプルな戦略
関数を並べ、それぞれにリソースを割り当てる方法はたくさんある。その数は、量子的なものがそうであるように、関数の数によって指数関数的にスケールする。つまり、総当たり的なアプローチでは、可能性の検索を効率化する量子コンピュータがない限り（おそらく）、関数呼び出しの数が多ければ問題は解決しないということだ。また、量子コンピューターがあっても十分ではないかもしれない！
この難問に取り組む方法はたくさんある。最初のアプローチは、時間はかかるが少なくとも方法論的には、バックトラック・アルゴリズム（https://en.wikipedia.org/wiki/Backtracking）である。これは、レイヤーごとに回路を構築するインクリメンタルな（再帰的な）方法である。これを改善するために、より優れたアルゴリズムがあり、巧妙なヒューリスティックに基づくものもある。そのようなテクニックについては、今後のブログ記事で詳しく述べる。
次はどうする？
今日はCSPの世界と、それが量子アルゴリズム回路合成の問題にどのように適用されるかを少し垣間見ることができた。CLASSIQでは「ブレッド＆バター」と呼んでいる。
問題の設定と、それに取り組むために素朴にできることを学んだ。しかしCLASSIQエンジンは、これらのアイデアをさらに発展させる。ブロック実装の選択を迅速かつ効率的に行うためのより複雑で巧妙な方法を適用するだけでなく、私たちが構築する必要がある回路の量子的性質によってもたらされる特定の課題による問題の拡張があります。
回路の途中で測定を行うことができる場合、CSOPをどのように解くのでしょうか？コヒーレントノイズやインコヒーレントノイズなどの考慮事項をどのように合成エンジンに組み込むべきか？古典と量子のハイブリッド計算ワークフローにおける情報処理は、実行時に回路合成や再合成にどのように反映させることができるのか？これらはすべて難しく、魅力的な質問である。今後の投稿では、回路合成の世界と、それがもたらすアルゴリズム的な挑戦について深く掘り下げていく予定である。
数独を解いたことがあるだろうか？2000年代前半のある時期にかなり流行った。なぜかみんな解いていた。スマートフォンが登場するずっと前のことだ。人々は他にすることがなかったのだ。数独を知らない人もいるかもしれないが、数独のゴールは9X9のマス目を数字で埋めることである。この種のパズルは制約充足問題（CSP）の一例である。CSPとは、ある可能性の集合（例えば1から9までの数字）から、あるアイテム（例えば数字）で「空白を埋め」なければならないが、あるルール（例えば数字を繰り返してはならない）には違反してはならないという問題である。
CSPのクラスには、ゲーム（あらゆるクロスワードパズル）、数学（地図の色付け[https://en.wikipedia.org/wiki/Four_color_theorem]）などの形で、他の、間違いなくもっと面白い例がある。しかし、この全体が我々にとって重要なのには理由があり、それは数学の定理を証明したいからではない。それよりももっと実用的なことなのだ。少なくとも、量子アルゴリズム設計の仕事をしているのであれば。
量子回路の最適化
タダ飯はないが、最高の利益を得るのはいいことだ。それが最適化技術のポイントだ。ある問題のメトリックを最大化（または最小化）する方法を見つけるのだ。このような問題には多くの種類がある。最適化しようとしているものが連続的な値をとることもあれば、離散的な値をとることもあります。最適化空間は有限にも無限にもなり、さまざまに変化します。CSPには制約のセットがあり、そのすべてを可能な限り満たすようにします。このCSPのサブクラスはCSOPと呼ぶことができる。"O "は "Optimization"（最適化）を意味する。
量子アルゴリズムを設計し、ビルディングブロックを "ハイレベル "にしたい。そのため、個々の量子ゲート以外のものを使いたい。その代わりに、正しいゲートシーケンスに変換される関数コールを使いたい。高レベルの関数コールをゲートシーケンスに置き換えるこのステップは、合成と呼ばれる。ここで行われることはこれだけではないが、簡単にするために、ある側面だけを考えてみよう。合成を行う場合、主に量子ハードウェアの制約を受ける。利用可能な量子ビット数には限りがあり、ノイズに圧倒される前に実行できる回路の深さには上限がある、などです。
私たちに残されたゲームは次のようなものです：リソース（量子ビット数、回路の深さなど）を、指定された制約を最適に満たすように関数に割り当てる。
目標は達成したが、地面は動いている
単純なケースでは、各関数呼び出しは「マスク」であり、固定のゲートシーケンスに置き換えることができる。これらのシーケンスを次々に配置し、回路を得る。これではつまらないし、合成の自由度も少ない。この場合、関数呼び出しのシーケンスが、結果として得られる回路を一意に決定する。幸運なことに、ここではもっと興味深く、もっと難しいことが実際に起こっている。
これは、あなたが想定している以上に興味深い問題である。なぜなら、いくつかの関数には正しい実装が1つ以上存在するからである。異なる実装は、さまざまな理由で生じます。一例として、ハードウェア依存の実装があります。これは、トラップドイオン型量子プロセッサーと中性原子型量子プロセッサー（または他の量子ビット型）のネイティブゲートセットが異なるために起こります。もう一つは、量子ビットの接続マップによるものである。このマップは、どの量子ビットのペアで条件演算を行うかを指定するもので、量子ビットチップアーキテクチャによって（同じ量子ビットタイプであっても）異なる。
複数の実装が存在するのは、ハードウェアの違いだけが原因ではない。その一例が加算回路である。この回路素子は、異なるレジスタ（量子ビットの集合）で表される数値を加算することができる。これは、古典的なものを含むあらゆるコンピュータの基本的な構成要素である。量子計算においても同様に価値がある。この要素を実装するには、量子論理ゲートとして複数の表現がある。加算器の目的は、リップルキャリー回路（https://en.wikipedia.org/wiki/Adder_(electronics)#Ripple-carry_adder）や量子フーリエ変換（本論文参照：https://arxiv.org/pdf/1411.5949.pdf）によって達成することができる。使用する量子ビットの数、回路の深さ、実行される2量子ビット演算の数など、異なる実装には異なる特徴があります。
リデュース、リユース、リサイクル
量子であれ何であれ、コンピューティングにおけるリソースは乏しい。本当に簡単な問題を解くのでなければ、通常、2つの壁のどちらかにぶつかる。十分なスピードがないか、十分なスペースがないかだ。多くの場合、これらの問題の一方をもう一方に変換することができるが、それは時々であり、時々しか役に立たない。
このため、リソースを倹約して利用する方法を開発することは、コンピューティングにおける古くからの（そして必要な）伝統である。効率的なメモリー管理やガベージ・コレクションは不可欠であり、プログラム内で同じビットの物理空間を繰り返し再利用することを可能にする。これらのタスクを自動化することは、電子設計自動化（EDA）ソフトウェアの領域であり、CLASSIQエンジンのインスピレーションの源となった。
量子プログラムを合成する際、特に厄介なのは補助量子ビットをどうするかである。
エンジンは高レベル関数の実装を選択し、それを次の関数の実装に "接続 "する。もしその関数が補助量子ビット（または量子ビット）を持っていれば、それは別の関数で再利用することができます。再利用できず、次の関数も補助量子ビットを必要とする場合、その関数に新しい量子ビットを割り当てなければなりません（手元にないかもしれません！）。
この補助量子ビットの再利用は、ある意味で、私たちが解こうとしている制約充足（と最適化）問題を「非局所的」にします。回路の最初に1つの実装（と補助量子ビットの配線）を選択した場合、その時点では良いアイデアだと思えたのですが、後になってあまり適切でない実装を選択せざるを得なくなったとしたらどうでしょう？私の目標を最適化するために、全体的に悪い実装を選ばざるを得なかったとしたら？選択した結果、最終的なゴールが一方向に動いてしまい、自分の決断を再評価し、遡及的に変更せざるを得なくなる。実生活でこのような自由が与えられていればいいのだが。
成功のためのシンプルな戦略
関数を並べ、それぞれにリソースを割り当てる方法はたくさんある。その数は、量子的なものがそうであるように、関数の数によって指数関数的にスケールする。つまり、総当たり的なアプローチでは、可能性の検索を効率化する量子コンピュータがない限り（おそらく）、関数呼び出しの数が多ければ問題は解決しないということだ。また、量子コンピューターがあっても十分ではないかもしれない！
この難問に取り組む方法はたくさんある。最初のアプローチは、時間はかかるが少なくとも方法論的には、バックトラック・アルゴリズム（https://en.wikipedia.org/wiki/Backtracking）である。これは、レイヤーごとに回路を構築するインクリメンタルな（再帰的な）方法である。これを改善するために、より優れたアルゴリズムがあり、巧妙なヒューリスティックに基づくものもある。そのようなテクニックについては、今後のブログ記事で詳しく述べる。
次はどうする？
今日はCSPの世界と、それが量子アルゴリズム回路合成の問題にどのように適用されるかを少し垣間見ることができた。CLASSIQでは「ブレッド＆バター」と呼んでいる。
問題の設定と、それに取り組むために素朴にできることを学んだ。しかしCLASSIQエンジンは、これらのアイデアをさらに発展させる。ブロック実装の選択を迅速かつ効率的に行うためのより複雑で巧妙な方法を適用するだけでなく、私たちが構築する必要がある回路の量子的性質によってもたらされる特定の課題による問題の拡張があります。
回路の途中で測定を行うことができる場合、CSOPをどのように解くのでしょうか？コヒーレントノイズやインコヒーレントノイズなどの考慮事項をどのように合成エンジンに組み込むべきか？古典と量子のハイブリッド計算ワークフローにおける情報処理は、実行時に回路合成や再合成にどのように反映させることができるのか？これらはすべて難しく、魅力的な質問である。今後の投稿では、回路合成の世界と、それがもたらすアルゴリズム的な挑戦について深く掘り下げていく予定である。
