.svg)
学術的な量子アルゴリズムの自動実行を実現
量子モデリング構造と強力な合成能力は、学術論文で発表された量子アルゴリズム設計者の意図と、量子コンピュータ、シミュレータ、リソース推定装置で実行可能な実際の実装とのギャップを埋める。
はじめに
量子アルゴリズムは、過去30年間、その大部分が学術的な取り組みであった。理論家は十分に定義され証明されたアルゴリズムを発表し、それらを健全な科学的言語で記述してきた。この記述には、図、キャプション、テキスト、方程式、その他、科学者が自分の研究の正しさを正式に記述し証明するために利用できるツールが含まれる。残念ながら、このような記述は学者間の相互理解に依存しており、形式的な科学 言語に基づいている。このような言語は、コンパイラが量子アルゴリズムを理解し、量子コンピュータで実行可能な記述を生成するのに十分な形式ではありません。
本論文では、長年にわたって発表されてきた多くの量子アルゴリズムとその実装を徹底的に検討した結果得られた、新しいモデリング構成とイディオムを紹介する。Shorのアルゴリズム、Groverのアルゴリズム、HHLのアルゴリズムのような特異なアルゴリズムであっても、内部構造をすべて抽象化することで比較的シンプルに記述することが可能であるが、Shorのアルゴリズムにおけるモジュラー指数関数、Groverのアルゴリズムにおけるオラクル、HHLのアルゴリズムにおける線形方程式の形など、次のレベルの詳細を調べると、複雑な問題が豊富に発生する。量子アルゴリズムの入門コースを受講している人なら誰でも理解できるように、Shorのアルゴリズムの例を以下に示します。マイクロソフト社のAzure Quantum Resource Estimatorを使用して、Shorのアルゴリズムを4つのモジュール加算で実行するには354,562個の物理量子ビットが必要であることを示し、必要なゲート数を特定します。この例では、幅広い量子アルゴリズムに関連するモデリング構成要素のみを示します。
私たちの手法の総合的なメリットは、設計者が学術論文などで記述した量子回路にどれだけ近いモデルを作成できるか、また、回路に要求されるすべての形式的要件をモデルが明確に捕らえることができるかによって決まります。
Classiqの量子アルゴリズムデザインプラットフォームは、このようなモデリングと、そのモデルを理解し、具体的で最適化された量子回路実装を生成する合成エンジンをすべて実装しているため、複雑な量子アルゴリズムを思考から実行まで一貫して作成することができます。Classiqプラットフォームで作成された量子アルゴリズム（例えば、Shorのアルゴリズムの実装）は、これまでに作成された量子アルゴリズムの中で最も複雑で大規模なものです。
ショールのアルゴリズムの実装
Classiqのグラフィカル・モデリングで使われる主な概念とツールについて説明し、nビットで表される数Nを因数分解するShorのアルゴリズムを実装した回路を生成します。この回路はBeauregard(https://arxiv.org/pdf/quant-ph/0205095[1])の実装に従い、4n+2 量子ビットを必要とします。2つの回路の違いは、Beauregardの元の回路は、1つの量子ビットを2n回測定し、再準備することにより、1つの量子ビット上で最終的な逆QFT回路を実装している（したがって、2n+3個の量子ビットを必要とする）のに対し、我々の実装では、2n個の量子ビット上の「通常の」QFTが使用されていることです。
この回路は、Shorのアルゴリズムの量子部分を実装している。与えられたn量子ビット数Nの因数を求めるShorのアルゴリズムでは、Nより小さい乱数aが選択され、gcd (a,N)が計算される。gcd(a,N)が1以上であれば、gcd(a,N)がNの因数であると判断して終了です。そうでない場合は、アルゴリズムの量子部分（主な部分は$|a^xmodNrangle$の計算）を実行します（量子部分には、測定結果の古典的な後処理が追加されます）。
このような回路を任意のnに対して構成するためには、最下層の基本的な量子ビルディング・ブロック（量子ビルディング・ブロックとは、合成エンジンが認識する基本的なゲートや関数のこと）から最上層の回路全体までを階層的に表現できなければならない。さらに、単一の量子ビットではなくレジスタを扱うことができる必要がある。つまり、レジスタをスライスして選択した量子ビットにゲートを適用する機能を維持したまま、レジスタにゲートを適用することができる。このような回路のモデリングを可能にするツールは、回路の主な階層／レイヤーごとに示されている：
- 基本ゲート（主に位相ゲート、制御位相ゲート、二重制御位相ゲート）とQFTから構成されるフーリエ空間のモジュラー加算器。
- n個のモジュラー加算器から構成されるモジュラー乗算。
- n個のモジュラー乗算回路から構成されるモジュラー指数関数。
制御モジュラー加算回路
モジュラー加算器では、数値aが (n+1)量子ビットレジスタ(bレジスタ)に加算される。レジスタの入力状態は、bレジスタの最上位ビット（MSB）がゼロの状態である。この量子ビットはオーバーフロービットとして使用される。さらに、この回路には2つの制御ビットと、入力時と出力時にゼロとなる補助ビットが含まれる。モジュラー加算器は次の回路で与えられる。黒い太いバーは、加算器（右のバー）とその逆を実装した減算器（左のバー）を区別する：
c1=c2=1の場合、回路動作は以下のようになる（ciが他の値の場合、制御された動作は作動せず、それ以外の動作は相殺される）。
o サブ回路A：(n+1)量子ビットbレジスタに$Phi(b)$を持つaを追加する。
o Sub-circuit B: Subtracts N from a+b and then adds N again if N < a+b – this is done by checking the MSB of a+b-N.
1,1, \Phi (b),0rangle ￤ライトアロー ￤1,1,￤Phi (b+a),0rangle$$ ￤ライトアロー
この時点でbレジスタは(a+b)mod Nの状態にあるが、一般に補助量子ビットとエンタングルされていることに注意。
o サブ回路C：レジスタからaを減算し、bレジスタの最上位ビットをチェック(必要であれば補助ビットを反転)してレジスタにaを戻すことにより、最後/最下位の補助量子ビットを$|0rangle$にリセット(bレジスタから切り離す)。
合法的な」入力状態（bのMSBがゼロ）での回路全体の動作が要求される：
Phi ((b+a) mod N),0rangle .$$.
モジュラー加算器の主な構成要素は、(n+1)量子ビット量子レジスタに(Nより小さい)数aを加算する加算回路(フーリエ基底)と、その逆数(制御あり/なし)である。(制御なし)加算器は単一量子ビット位相ゲート(ここでは$|Phi(b)Γ=QFT|bΓΓ$)のみで構成される：
ここでの数aは、量子レジスタによって運ばれるのではなく、位相にエンコードされるという意味で「古典的」である。私たちのプラットフォームでは、加算器はカスケードモデリングツールによって簡単に実現され、演算は垂直方向に複製されます。
上記の入力と出力は、W-qubitレジスタであり、Wは 階層内の上位から設定されたパラメータです。カスケード命令は、レジスタ内の各qubitに単一qubit位相ゲートを適用します。 それぞれの量子ビットに異なる位相が導入されます。こ れ ら の位相は、 ユーザーがモデル化の一環として回路に導入します。ゲー ト の正式なポー ト 名はtarget_inおよびtarget_outです。
モジュラー加算器サブサーキット（図1）で使用されるもう1つの構成ブロックは、位相ゲートを制御位相（CPhase）ゲートに置き換えた制御加算器と二重制御加算器である。このゲートでは、1つの量子ビットが対象の量子ビットの位相を制御します。ゲートを同じレジスタに繰り返し適用するには、インスタンス命令を使用します。しかし、制御された加算器の実装では、位相はターゲット・レジスタ内のすべての量子ビットに順次導入されるため、カスケード （量子ビット上の繰り返し）とインスタンス （ゲートの繰り返し）の両方を併用する必要があります。
コントロール・レジスタ内の1つの量子ビットは、シーケンス内のW個のCPフェーズ・ゲート全てに参加し、ターゲット・レジスタ内のW個の量子ビットは、それぞれ正確に1つのゲートに参加する。
図1のモジュラー加算回路を実現する全体のスキームを以下に示す。この回路が図1の学術的な図面といかに似ているかに注目してほしい。もちろん、主な違いは、この回路が完全に実行可能であり、合成エンジンによって最適な具体的実装に最適化可能であることだ。
この回路は、5つの加算器（制御加算器と逆加算器を含む）と2つの "twoQFT "関数から構成され、bレジスタのMSB量子ビットをチェックし、必要に応じて補助量子ビットを反転させるという、上記の回路の2つの構成を実装しています（このような構成にはそれぞれ、bレジスタをフーリエ空間へ、またはフーリエ空間から取り出す2つのQFT関数が含まれます）。この命名規則を図5に示し、以下の凡例で説明します。
制御モジュラー乗算回路
モジュラー乗算を実現する回路は、モジュラー加算器の関数をn回繰り返すことで以下のように構成できる：
図6では、$Phi$ADD(2j )mod Nサブ回路内のすべてのゲートに制御が適用されず、正しい制御された進化は、オーバーフ ロー・ビットが0である「合法的な」入力に対してのみ得られるので、$Phi$ADD(2j )mod N上の制御は、完全に「合法的」ではない（図1の回路として[1]でグラフィカルによく定義されているが）ことに注意。
n個のモジュラー加算器の全動作はフーリエ空間で行われるため、フーリエ空間の内外にQFTと逆QFTを追加する必要がある。この回路は、グラフィカルモデラーによって以下のように簡単に実装できます：
モジュラー加算回路（図5）は、2つの単一量子ビット・レジスタを制御として受け取るが、上の乗算層（図7）では、c2レジスタがn個の量子ビットを含み、それが下のモジュラー加算層でカスケード接続されることに注意されたい。
モジュラー乗算回路では、レジスタbは初期状態0であり、2n回のモジュラー乗算のそれぞれで再利用するためには、0に戻す必要がある。これは、レジスタbと xの間に制御されたスワップを適用し、適切なaのべき乗の逆数に対して逆モジュラー乗算を適用することによって行うことができる。
モジュラー指数化
モジュラー指数化は、レジスタbに数1を入力し、（ハダマード変換によって）上位2n量子ビットレジスタを準備し、上記のモジュラー乗算の組を直接2n回適用することによって実行されます。レジスタ内の各量子ビットが適切なモジュラー乗算演算を制御するように、上位2n量子ビットレジスタをカスケードし、上位レジスタに逆QFTを適用します（量子部分の結果は、このレジスタを測定することによって得られます）。主なモデル化部分がモジュラー指数計算であるShorのアルゴリズム全体を図8に示します。
合成
合成エンジンは、上記のモデルを入力とし、機能モデルに準拠した最適な実装回路を生成します。ここでは、モデルの各機能ブロックについて、機能的に等価な実装が多数存在すること（例えば、そのブロックを実装する補助量子ビットの数、その深さ、そのブロックが含む2量子ビットゲートの数、およびその全体的な精度の間のトレードオフを明示する）についてのみ言及します。量子ビット数、深さ、実行時間、全体的な忠実度、アルゴリズム精度、および全体的な目的の予算の下で回路全体の最適な実装を見つけることは、合成エンジンのタスクです。また、この機能レベルでの最適化は、トランスパイラレベルでの最適化よりもはるかに強力です。トランスパイラは、回路の低レベルのセマンティクスをそのまま維持する必要があるため、これらのセマンティクスにアクセスできる場合は、回路の機能セマンティクスのみを維持するのとは対照的です。Shorのアルゴリズムの最終的な実装を図9に示す。
Shorの回路の耐故障性実現のための資源推定
上記の実装のように、モジュラー指数化とショールのアルゴリズムを実装した回路は、ゲート数と回路の深さの点で多大なリソースを必要とする。その結果、このような回路を実現するには、必然的に誤り訂正符号を使用する必要があり、必要なリソースは桁違いに増大する。
量子アルゴリズムのフォールトトレラント実装のリソースを見積もるために最近利用できるようになったツール、Azure Quantum Resource Estimatorを上記の回路に適用し、「通常の」ノイズのある回路の実現に必要なリソースと、フォールトトレラントな回路の実現に必要なリソースを比較した。この解析にはサーフェスコードが使用された。
通常の実施に必要なリソース
Beauregard回路[1]の実装には4n+2個の量子ビットが必要です。この回路には、4n2個のモジュラー加算器サブ回路（逆回路を含む）が含まれます。各モジュラー加算器には、n+1個の位相ゲート、n+1個のc相ゲート、3(n+1)個のcc相ゲート、さらに4個のQFT（および逆QFT）関数が含まれます。各QFTにはn(n+1)/2個のc相ゲートとn個のハダマードゲートが含まれるため、回路全体は以下のようになる：
o $O(n^4)$相ゲート
o $O(n^3)$ccフェーズ、フェーズ、ハダマードゲート
o$O(n^2)$ccx, cx, xゲート。
n=4のAzureリソース推定結果
Classiqグラフィカルモデリングと合成エンジンを使用して、QIRフォーマットでn=4（合計18個の量子ビットを必要とする）のShor実装が生成された。この回路には以下のフェーズゲートが含まれています：
o 3,244個の位相ゲート
o920ccフェーズ・ゲート
o320フェーズゲート。
Azure Resource Estimatorをデフォルトの引数で回路に適用し、1量子ビットゲートと2量子ビットゲート、およびTゲートと1量子ビット測定のエラーレートを0.001と仮定した。回路に必要な総合誤差（総誤差バジェット）は0.33でした。
リソース見積りによると、このエラーバジェットを満たすために必要な表面コード距離はd=13 であり、論理量子ビットに必要なエラーレートは$5.1 * 10^{-9}$である。さらに、25個のT-stateファクトリー（並列動作）が必要です。T-ステートに必要なエラーレートは$1.35 * 10^{-7}$です。
論理量子ビットの物理量子ビット数は2d2 = 338で与えられる。フォールト・トレラント回路の論理量子ビットの総数は16,562個である（元の回路の平面レイアウトでは49個の量子ビットが必要で、それぞれ338個の物理量子ビットを必要とする）。これらの量子ビットは、計算全体を通して情報を伝達する。さらに、TファクトリーによるT状態の生成と抽出のために、さらに多くの量子ビットが必要となる。これらのT状態は、フォールト・トレラント回路にTゲートが適用されるたびに使用される（つまり、T状態は論理回路量子ビットと相互作用して絡み合い、論理回路量子ビットからそれらを切り離して測定する）。 必要なエラー率でT状態を抽出するためには、T状態あたり13,520個の物理量子ビットが必要である。したがって、T-状態に必要な物理量子ビットの総数は338,000となる。
物理量子ビットの総数（T状態量子ビット＋回路量子ビット）は354,562である。T-state量子ビットは、回路の適用中に何度も再利用されることに注意してください。
リソース見積もり結果による重要な点は、フォールトトレラントな回路には、元の回路の様々な位相ゲート（cphaseとccphaseを含む）に由来する50,471個の単一量子ビット回転が含まれることである。これらの単一量子ビットの回転は、回路全体に必要なT状態のほとんどすべてを消費することになる。この結果は、回路内の様々な位相ゲートの数を減らすことが有益であることを示唆している。これは、例えば、回路に（正確なQFTではなく）近似QFT関数を使用することで実現できます。あるいは、フーリエ基底での加算ではなく、他のタイプの加算回路に基づくShorのアルゴリズムの別の実装も有利に働く可能性がある。
概要
我々は、量子アルゴリズムの学術的な記述が、科学的に発表されたアルゴリズムの構造や考え方を保ちながら、形式的な方法でシームレスにモデル化できることを示した。この記事では、ほとんどの量子アルゴリズムで見られる、カスケードと インスタンスという2つの主要なモデル構成要素について説明した。カスケード」と「インスタンス」である。このような構成要素は10個ほどあり、どれも理解しやすく、現在までに発表されたほとんどのアルゴリズムをカバーしている。このようなモデリング構造を持つことで、アルゴリズムの科学的なプレゼンテーションと、ハードウェアやシミュレータ上での実際の実行とのギャップを埋めることができる。例えば、量子アルゴリズムモデルから具体的な回路を構築するためのシンセサイザなどのアルゴリズムツールと、最近発表されたマイクロソフト社のツールのようなリソース見積もりツールとの連携が可能になる。
量子モデリング構造と強力な合成能力は、学術論文で発表された量子アルゴリズム設計者の意図と、量子コンピュータ、シミュレータ、リソース推定装置で実行可能な実際の実装とのギャップを埋める。
はじめに
量子アルゴリズムは、過去30年間、その大部分が学術的な取り組みであった。理論家は十分に定義され証明されたアルゴリズムを発表し、それらを健全な科学的言語で記述してきた。この記述には、図、キャプション、テキスト、方程式、その他、科学者が自分の研究の正しさを正式に記述し証明するために利用できるツールが含まれる。残念ながら、このような記述は学者間の相互理解に依存しており、形式的な科学 言語に基づいている。このような言語は、コンパイラが量子アルゴリズムを理解し、量子コンピュータで実行可能な記述を生成するのに十分な形式ではありません。
本論文では、長年にわたって発表されてきた多くの量子アルゴリズムとその実装を徹底的に検討した結果得られた、新しいモデリング構成とイディオムを紹介する。Shorのアルゴリズム、Groverのアルゴリズム、HHLのアルゴリズムのような特異なアルゴリズムであっても、内部構造をすべて抽象化することで比較的シンプルに記述することが可能であるが、Shorのアルゴリズムにおけるモジュラー指数関数、Groverのアルゴリズムにおけるオラクル、HHLのアルゴリズムにおける線形方程式の形など、次のレベルの詳細を調べると、複雑な問題が豊富に発生する。量子アルゴリズムの入門コースを受講している人なら誰でも理解できるように、Shorのアルゴリズムの例を以下に示します。マイクロソフト社のAzure Quantum Resource Estimatorを使用して、Shorのアルゴリズムを4つのモジュール加算で実行するには354,562個の物理量子ビットが必要であることを示し、必要なゲート数を特定します。この例では、幅広い量子アルゴリズムに関連するモデリング構成要素のみを示します。
私たちの手法の総合的なメリットは、設計者が学術論文などで記述した量子回路にどれだけ近いモデルを作成できるか、また、回路に要求されるすべての形式的要件をモデルが明確に捕らえることができるかによって決まります。
Classiqの量子アルゴリズムデザインプラットフォームは、このようなモデリングと、そのモデルを理解し、具体的で最適化された量子回路実装を生成する合成エンジンをすべて実装しているため、複雑な量子アルゴリズムを思考から実行まで一貫して作成することができます。Classiqプラットフォームで作成された量子アルゴリズム（例えば、Shorのアルゴリズムの実装）は、これまでに作成された量子アルゴリズムの中で最も複雑で大規模なものです。
ショールのアルゴリズムの実装
Classiqのグラフィカル・モデリングで使われる主な概念とツールについて説明し、nビットで表される数Nを因数分解するShorのアルゴリズムを実装した回路を生成します。この回路はBeauregard(https://arxiv.org/pdf/quant-ph/0205095[1])の実装に従い、4n+2 量子ビットを必要とします。2つの回路の違いは、Beauregardの元の回路は、1つの量子ビットを2n回測定し、再準備することにより、1つの量子ビット上で最終的な逆QFT回路を実装している（したがって、2n+3個の量子ビットを必要とする）のに対し、我々の実装では、2n個の量子ビット上の「通常の」QFTが使用されていることです。
この回路は、Shorのアルゴリズムの量子部分を実装している。与えられたn量子ビット数Nの因数を求めるShorのアルゴリズムでは、Nより小さい乱数aが選択され、gcd (a,N)が計算される。gcd(a,N)が1以上であれば、gcd(a,N)がNの因数であると判断して終了です。そうでない場合は、アルゴリズムの量子部分（主な部分は$|a^xmodNrangle$の計算）を実行します（量子部分には、測定結果の古典的な後処理が追加されます）。
このような回路を任意のnに対して構成するためには、最下層の基本的な量子ビルディング・ブロック（量子ビルディング・ブロックとは、合成エンジンが認識する基本的なゲートや関数のこと）から最上層の回路全体までを階層的に表現できなければならない。さらに、単一の量子ビットではなくレジスタを扱うことができる必要がある。つまり、レジスタをスライスして選択した量子ビットにゲートを適用する機能を維持したまま、レジスタにゲートを適用することができる。このような回路のモデリングを可能にするツールは、回路の主な階層／レイヤーごとに示されている：
- 基本ゲート（主に位相ゲート、制御位相ゲート、二重制御位相ゲート）とQFTから構成されるフーリエ空間のモジュラー加算器。
- n個のモジュラー加算器から構成されるモジュラー乗算。
- n個のモジュラー乗算回路から構成されるモジュラー指数関数。
制御モジュラー加算回路
モジュラー加算器では、数値aが (n+1)量子ビットレジスタ(bレジスタ)に加算される。レジスタの入力状態は、bレジスタの最上位ビット（MSB）がゼロの状態である。この量子ビットはオーバーフロービットとして使用される。さらに、この回路には2つの制御ビットと、入力時と出力時にゼロとなる補助ビットが含まれる。モジュラー加算器は次の回路で与えられる。黒い太いバーは、加算器（右のバー）とその逆を実装した減算器（左のバー）を区別する：
c1=c2=1の場合、回路動作は以下のようになる（ciが他の値の場合、制御された動作は作動せず、それ以外の動作は相殺される）。
o サブ回路A：(n+1)量子ビットbレジスタに$Phi(b)$を持つaを追加する。
o Sub-circuit B: Subtracts N from a+b and then adds N again if N < a+b – this is done by checking the MSB of a+b-N.
1,1, \Phi (b),0rangle ￤ライトアロー ￤1,1,￤Phi (b+a),0rangle$$ ￤ライトアロー
この時点でbレジスタは(a+b)mod Nの状態にあるが、一般に補助量子ビットとエンタングルされていることに注意。
o サブ回路C：レジスタからaを減算し、bレジスタの最上位ビットをチェック(必要であれば補助ビットを反転)してレジスタにaを戻すことにより、最後/最下位の補助量子ビットを$|0rangle$にリセット(bレジスタから切り離す)。
合法的な」入力状態（bのMSBがゼロ）での回路全体の動作が要求される：
Phi ((b+a) mod N),0rangle .$$.
モジュラー加算器の主な構成要素は、(n+1)量子ビット量子レジスタに(Nより小さい)数aを加算する加算回路(フーリエ基底)と、その逆数(制御あり/なし)である。(制御なし)加算器は単一量子ビット位相ゲート(ここでは$|Phi(b)Γ=QFT|bΓΓ$)のみで構成される：
ここでの数aは、量子レジスタによって運ばれるのではなく、位相にエンコードされるという意味で「古典的」である。私たちのプラットフォームでは、加算器はカスケードモデリングツールによって簡単に実現され、演算は垂直方向に複製されます。
上記の入力と出力は、W-qubitレジスタであり、Wは 階層内の上位から設定されたパラメータです。カスケード命令は、レジスタ内の各qubitに単一qubit位相ゲートを適用します。 それぞれの量子ビットに異なる位相が導入されます。こ れ ら の位相は、 ユーザーがモデル化の一環として回路に導入します。ゲー ト の正式なポー ト 名はtarget_inおよびtarget_outです。
モジュラー加算器サブサーキット（図1）で使用されるもう1つの構成ブロックは、位相ゲートを制御位相（CPhase）ゲートに置き換えた制御加算器と二重制御加算器である。このゲートでは、1つの量子ビットが対象の量子ビットの位相を制御します。ゲートを同じレジスタに繰り返し適用するには、インスタンス命令を使用します。しかし、制御された加算器の実装では、位相はターゲット・レジスタ内のすべての量子ビットに順次導入されるため、カスケード （量子ビット上の繰り返し）とインスタンス （ゲートの繰り返し）の両方を併用する必要があります。
コントロール・レジスタ内の1つの量子ビットは、シーケンス内のW個のCPフェーズ・ゲート全てに参加し、ターゲット・レジスタ内のW個の量子ビットは、それぞれ正確に1つのゲートに参加する。
図1のモジュラー加算回路を実現する全体のスキームを以下に示す。この回路が図1の学術的な図面といかに似ているかに注目してほしい。もちろん、主な違いは、この回路が完全に実行可能であり、合成エンジンによって最適な具体的実装に最適化可能であることだ。
この回路は、5つの加算器（制御加算器と逆加算器を含む）と2つの "twoQFT "関数から構成され、bレジスタのMSB量子ビットをチェックし、必要に応じて補助量子ビットを反転させるという、上記の回路の2つの構成を実装しています（このような構成にはそれぞれ、bレジスタをフーリエ空間へ、またはフーリエ空間から取り出す2つのQFT関数が含まれます）。この命名規則を図5に示し、以下の凡例で説明します。
制御モジュラー乗算回路
モジュラー乗算を実現する回路は、モジュラー加算器の関数をn回繰り返すことで以下のように構成できる：
図6では、$Phi$ADD(2j )mod Nサブ回路内のすべてのゲートに制御が適用されず、正しい制御された進化は、オーバーフ ロー・ビットが0である「合法的な」入力に対してのみ得られるので、$Phi$ADD(2j )mod N上の制御は、完全に「合法的」ではない（図1の回路として[1]でグラフィカルによく定義されているが）ことに注意。
n個のモジュラー加算器の全動作はフーリエ空間で行われるため、フーリエ空間の内外にQFTと逆QFTを追加する必要がある。この回路は、グラフィカルモデラーによって以下のように簡単に実装できます：
モジュラー加算回路（図5）は、2つの単一量子ビット・レジスタを制御として受け取るが、上の乗算層（図7）では、c2レジスタがn個の量子ビットを含み、それが下のモジュラー加算層でカスケード接続されることに注意されたい。
モジュラー乗算回路では、レジスタbは初期状態0であり、2n回のモジュラー乗算のそれぞれで再利用するためには、0に戻す必要がある。これは、レジスタbと xの間に制御されたスワップを適用し、適切なaのべき乗の逆数に対して逆モジュラー乗算を適用することによって行うことができる。
モジュラー指数化
モジュラー指数化は、レジスタbに数1を入力し、（ハダマード変換によって）上位2n量子ビットレジスタを準備し、上記のモジュラー乗算の組を直接2n回適用することによって実行されます。レジスタ内の各量子ビットが適切なモジュラー乗算演算を制御するように、上位2n量子ビットレジスタをカスケードし、上位レジスタに逆QFTを適用します（量子部分の結果は、このレジスタを測定することによって得られます）。主なモデル化部分がモジュラー指数計算であるShorのアルゴリズム全体を図8に示します。
合成
合成エンジンは、上記のモデルを入力とし、機能モデルに準拠した最適な実装回路を生成します。ここでは、モデルの各機能ブロックについて、機能的に等価な実装が多数存在すること（例えば、そのブロックを実装する補助量子ビットの数、その深さ、そのブロックが含む2量子ビットゲートの数、およびその全体的な精度の間のトレードオフを明示する）についてのみ言及します。量子ビット数、深さ、実行時間、全体的な忠実度、アルゴリズム精度、および全体的な目的の予算の下で回路全体の最適な実装を見つけることは、合成エンジンのタスクです。また、この機能レベルでの最適化は、トランスパイラレベルでの最適化よりもはるかに強力です。トランスパイラは、回路の低レベルのセマンティクスをそのまま維持する必要があるため、これらのセマンティクスにアクセスできる場合は、回路の機能セマンティクスのみを維持するのとは対照的です。Shorのアルゴリズムの最終的な実装を図9に示す。
Shorの回路の耐故障性実現のための資源推定
上記の実装のように、モジュラー指数化とショールのアルゴリズムを実装した回路は、ゲート数と回路の深さの点で多大なリソースを必要とする。その結果、このような回路を実現するには、必然的に誤り訂正符号を使用する必要があり、必要なリソースは桁違いに増大する。
量子アルゴリズムのフォールトトレラント実装のリソースを見積もるために最近利用できるようになったツール、Azure Quantum Resource Estimatorを上記の回路に適用し、「通常の」ノイズのある回路の実現に必要なリソースと、フォールトトレラントな回路の実現に必要なリソースを比較した。この解析にはサーフェスコードが使用された。
通常の実施に必要なリソース
Beauregard回路[1]の実装には4n+2個の量子ビットが必要です。この回路には、4n2個のモジュラー加算器サブ回路（逆回路を含む）が含まれます。各モジュラー加算器には、n+1個の位相ゲート、n+1個のc相ゲート、3(n+1)個のcc相ゲート、さらに4個のQFT（および逆QFT）関数が含まれます。各QFTにはn(n+1)/2個のc相ゲートとn個のハダマードゲートが含まれるため、回路全体は以下のようになる：
o $O(n^4)$相ゲート
o $O(n^3)$ccフェーズ、フェーズ、ハダマードゲート
o$O(n^2)$ccx, cx, xゲート。
n=4のAzureリソース推定結果
Classiqグラフィカルモデリングと合成エンジンを使用して、QIRフォーマットでn=4（合計18個の量子ビットを必要とする）のShor実装が生成された。この回路には以下のフェーズゲートが含まれています：
o 3,244個の位相ゲート
o920ccフェーズ・ゲート
o320フェーズゲート。
Azure Resource Estimatorをデフォルトの引数で回路に適用し、1量子ビットゲートと2量子ビットゲート、およびTゲートと1量子ビット測定のエラーレートを0.001と仮定した。回路に必要な総合誤差（総誤差バジェット）は0.33でした。
リソース見積りによると、このエラーバジェットを満たすために必要な表面コード距離はd=13 であり、論理量子ビットに必要なエラーレートは$5.1 * 10^{-9}$である。さらに、25個のT-stateファクトリー（並列動作）が必要です。T-ステートに必要なエラーレートは$1.35 * 10^{-7}$です。
論理量子ビットの物理量子ビット数は2d2 = 338で与えられる。フォールト・トレラント回路の論理量子ビットの総数は16,562個である（元の回路の平面レイアウトでは49個の量子ビットが必要で、それぞれ338個の物理量子ビットを必要とする）。これらの量子ビットは、計算全体を通して情報を伝達する。さらに、TファクトリーによるT状態の生成と抽出のために、さらに多くの量子ビットが必要となる。これらのT状態は、フォールト・トレラント回路にTゲートが適用されるたびに使用される（つまり、T状態は論理回路量子ビットと相互作用して絡み合い、論理回路量子ビットからそれらを切り離して測定する）。 必要なエラー率でT状態を抽出するためには、T状態あたり13,520個の物理量子ビットが必要である。したがって、T-状態に必要な物理量子ビットの総数は338,000となる。
物理量子ビットの総数（T状態量子ビット＋回路量子ビット）は354,562である。T-state量子ビットは、回路の適用中に何度も再利用されることに注意してください。
リソース見積もり結果による重要な点は、フォールトトレラントな回路には、元の回路の様々な位相ゲート（cphaseとccphaseを含む）に由来する50,471個の単一量子ビット回転が含まれることである。これらの単一量子ビットの回転は、回路全体に必要なT状態のほとんどすべてを消費することになる。この結果は、回路内の様々な位相ゲートの数を減らすことが有益であることを示唆している。これは、例えば、回路に（正確なQFTではなく）近似QFT関数を使用することで実現できます。あるいは、フーリエ基底での加算ではなく、他のタイプの加算回路に基づくShorのアルゴリズムの別の実装も有利に働く可能性がある。
概要
我々は、量子アルゴリズムの学術的な記述が、科学的に発表されたアルゴリズムの構造や考え方を保ちながら、形式的な方法でシームレスにモデル化できることを示した。この記事では、ほとんどの量子アルゴリズムで見られる、カスケードと インスタンスという2つの主要なモデル構成要素について説明した。カスケード」と「インスタンス」である。このような構成要素は10個ほどあり、どれも理解しやすく、現在までに発表されたほとんどのアルゴリズムをカバーしている。このようなモデリング構造を持つことで、アルゴリズムの科学的なプレゼンテーションと、ハードウェアやシミュレータ上での実際の実行とのギャップを埋めることができる。例えば、量子アルゴリズムモデルから具体的な回路を構築するためのシンセサイザなどのアルゴリズムツールと、最近発表されたマイクロソフト社のツールのようなリソース見積もりツールとの連携が可能になる。
