(57)【要約】【課題】量子計算に必要な可干渉性（コヒーレンシー）時間利用のために量子計算に要する時間コスト減少する方法を提供する。【解決手段】最近隣接結合に限定されたキュービットの一次元配列における量子計算を出力キュービットの再順番、操作の再順番、及び同時操作を用いて最適化する。量子計算機のいくつかのデザインに使用できる論理ゲートの効率的な実現が量子計算に必要な時間を減少する。個々のキュービットについて同時操作を実行する可能性を考慮することにより、量子フーリエ変換を実現する効率的なネットワークの方法が提供される。【選択図】図１
2004531793.tif 000002
【特許請求の範囲】
【請求項１】
量子計算に必要な可干渉性時間を減少する方法であって、
量子計算を実行するキュービットに対する操作の第１シリーズを構成し、
操作の第２シリーズを完了するのに量子計算装置が必要な時間を減少するため交換可能操作の実行順番を変更することにより第１シリーズから操作の第２シリーズを構成する、
ことを含む方法。
【請求項２】
操作の第１シリーズから操作の第２シリーズを構成することが、第２シリーズにおいて２つ又はそれ以上の操作が同時に実行されるように第１シリーズの交換可能操作の実行順番を変更することを含む請求項１に記載の方法。
【請求項３】
操作の第１シリーズが、第１キュービット及び第２キュービットをそれぞれが第１状態と第２状態を有するものからそれぞれが第２状態と第１状態を有するものへ変更するスワップ操作を含む請求項２に記載の方法。
【請求項４】
交換可能操作の順番の変更がスワップ操作の必要を無くし、そして
第２シリーズを構成することが、操作の第２シリーズの実行が操作の第１シリーズの実行よりも早く量子計算を行うように第２シリーズからスワップ操作を無くすることをさらに含む請求項３に記載の方法。
【請求項５】
操作の第１シリーズが、第１キュービット及び第２キュービットをそれぞれが第１状態と第２状態を有するものからそれぞれが第２状態と第１状態を有するものへ変更するスワップ操作を含み、
第１シリーズ内の交換可能操作の順番の変更がスワップ操作の必要性を無くし、
操作の第２シリーズを構成することが、操作の第２シリーズの実行が操作の第１シリーズの実行よりも早く量子計算を行うように第２シリーズからスワップ操作を無くすることをさらに含む請求項１に記載の方法。
【請求項６】
量子計算装置でスワップ操作を実行する方法であって、
操作のシーケンスから操作を実行し、
交換可能な操作の二つを同時に実行する、
ことを含む方法。
【請求項７】
操作のシーケンスを実行することが、
キュービットｒについて第１操作Ｚr（π／２）及びキュービットｓについて第２操作Ｚs（π／２）を同時に実行し、
キュービットｓについて第３操作Ｘs（π／２）、キュービットｓについて第４操作Ｚs（π／２）、及びキュービットｒとｓについて第５操作ＣＰrs（π／２）を順次に実行し、
キュービットｓについて第６操作Ｘs（π／２）及びキュービットｒについて第７操作Ｘr（π／２）を同時に実行し、
キュービットｒについて第８操作Ｚr（π／２）及びキュービットｒとｓについて第９操作ＣＰrs（π／２）を順次に実行し、
キュービットｒについて第１０操作Ｘr（π／２）及びキュービットｓについて第１１操作Ｚs（π／２）を同時に実行し、
キュービットｓについて第１２操作Ｘs（π／２）、キュービットｓについて第１３操作Ｚs（π／２）、キュービットｒとｓについて第１４操作ＣＰrs（π／２）、及び第１６操作Ｘs（３π／２）を順次に実行すること、
を含む請求項６に記載の方法。
【請求項８】
第３、第６、第７、第１０、第１２、及び第１６操作が以下の式に従いそれぞれのキュービットの２つの状態に作用する請求項７に記載の方法。
2004531793.tif 000011
【請求項９】
第１、第２、第４、第８、第１１、及び第１３操作が以下の式に従いそれぞれのキュービットの２つの状態に作用する請求項７に記載の方法。
2004531793.tif 000012
【請求項１０】
第５、第９、及び第１４操作が以下の式に従いキュービットｒとｓの４つの組合された状態に作用する請求項６に記載の方法。
2004531793.tif 000013
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、量子計算に関し、特に、量子フーリエ変換又はどんな量子ネットワークなどの計算を実行する量子計算機に必要な可干渉性（コヒーレンシー）時間を減少する方法に関する。
【背景技術】
【０００２】
現在、量子計算と呼ばれるものの研究は、リチャード・フアイマン（リチャード・フアインマン、Ｉｎｔ．Ｊ．Ｔｈｅｏｒ．Ｐｈｙｓ．，２１，４６７−４８８（１９８２））に遡ることができる。フアインマンは、量子システムは本質的に通常の計算機をシミュレートすることは難しいが、量子システムの進展はある計算問題を解くためにずっと早い方法を提供することを見つけた。
【０００３】
量子計算は、一般に、１組のキュービット（量子ビット）の量子状態を初期化して、キュービットの量子状態を量子ゲートの影響下で進展させることを可能にし、そして進展後にキュービットを読取る。キュービットは通常２つの量子状態（典型的に、２つの縮退状態）を持つシステムであり、そしてキュービットの状態は典型的にどちらかの状態において見つけられる非ゼロ確率を持つ。Ｎキュービットは、２N状態の組合せの状態を持つシステムを与える。量子ゲートは、識別可能な量子状態の進展を制御し、そしてシステムの量子状態を進展に対応した計算を定義する。この進展は、実際に、２N同時計算を実行する。進展後のキュービットを読取ることは、キュービットの状態及び計算の結果を決定する。
【０００４】
因数分解のための効率的な量子プロセスについてのショアによる紹介（ピー・ダブリュ・ショア、「量子計算での素数因数分解及び離散対数のための多項式−時間アルゴリズム」、ＳＩＡＭ  Ｊ．Ｃｏｍｐ．，２６：１４８４，１９９７）は、量子計算についてのソフトウェアを開発することについて大きな興味に火をつけた。特に、量子計算機における効率的な計算及びエラー修正に関する方法の開発について大きな関心が払われた。
【０００５】
これと平行して、量子情報の可干渉性（コヒーレンシー）操作に必要な大変厳しい要件を満足する量子計算機の物理的な実現の開発に多くの努力が費やされた。このような量子計算機の最初の提案は、閉じ込められたイオン、キャビテイ量子エレクトロダイナミックス・システム及びＮＭＲスペクトロスコピイに基づいている。量子計算機のＮＭＲに基づいた実現は少なくとも限られた数のキュービットに関して成功している。ここに参照のために全部が組込まれたイー・ニル等、「量子プロセスに関するアルゴリスミック・ベンチマーク」、ネーチャア、４０４：３６８（２０００）を参照のこと。しかし、ＮＭＲに基づいた量子計算機の本質的な限界がより拡張可能な設計についての研究を促した。
【０００６】
ソリッドステートに基づいた技術において利用可能な高度の専門知識が、有用な（数千のキュービット）量子計算機の実現に関してソリッドステート・システムを第一の候補として確立した。ソリッド・ステート量子計算機は、キュービットとしてジョセフソン・ジャンクション、量子ドット、又はスピン共鳴トランジスタを含むことが提案された。例えば、ワイ・ナカムラ等、「シングル・クーパー対ボックス中の巨視的量子状態の干渉性制御」、ネーチャア（ロンドン）、３９８：７８６，１９９９に記載されているようなソリッドステート・キュービットの可干渉性操作の最近の実験的な成功は、ソリッドステート量子計算機が実用的であるという良い自信を与える。しかし、ソリッドステート量子計算機の多数の自由の程度は、典型的に、このような量子計算機が短い可干渉性（コヒーレンシー）時間を被ることになる。可干渉性（コヒーレンシー）時間は、外部の影響がキュービットの量子状態と干渉を生ずる前に量子計算機の量子状態が進展できる時間である。）ソリッド・ステート量子計算機の計算能力を最大に利用するために、特定の量子ハードウェアについてソフトウェアを最適化することが重要である。特に、計算機に必要な全可干渉性（コヒーレンシー）時間を減少する最適化されたソフトウェアは、量子計算機が特定の計算を完了できるかどうかを決定するだろう。
【０００７】
（発明の開示）
本発明によれば、量子フーリエ変換及び他の量子ネットワークに必要な基本的なゲートは、各々が完了するのに特定の時間を有する物理的に実現可能な操作から作られる。基本的なゲートとスワップ操作は、ゲートを使用するゲート及び量子計算プロセスの適用を最適化できる交換プロセス関係を有する。量子フーリエ変換アルゴリズムの場合は、従来の基本的なゲートの処理よりも、オーダーＯ（Ｎ2）のスピードアップが得られた。このような改良は、コヒーレント操作が短い可干渉性（コヒーレンシー）時間に制限されている場合の量子アルゴリズムの物理的な実現の文脈においては相当なものである。
【０００８】
本発明の１つの特定の実施の形態は、量子計算に必要な可干渉性（コヒーレンシー）時間を減少するための方法である。これは、同時的に実行できる操作の数を最大にするように交換可能操作の実行順序を変えることにより、第１シリーズから操作の第２シリーズを構成することで達成される。これは、操作の第２シリーズを完了するために量子計算装置に必要な時間を減少する。交換可能操作の実行順序を変えることにより、第２シリーズの同時的交換可能操作を可能にし、及び／又は、いくつかのスワップ操作をなくすることかできる。
【０００９】
本発明の第２の観点によれば、量子計算装置内のスワップ操作を実行する方法が、交換可能な基本的操作を同時的に実行することにより必要な計算時間を減少する。
【発明を実施するための最良の形態】
【００１０】
添付された図面中の異なる図において、同じ参照符号が同様又は同一の項目を示す。
本発明の１つの観点において、最近隣接相互作用を可能にするキュービットの一次元配列で同時操作を個別のキュービットについて実行し、これにより量子フーリエ変換などの量子ネットワークに必要な時間を短縮する。説明の目的のために、本発明による量子計算プロセスの実現に適した特定のソリッドステート量子レジスタが以下に説明される。しかし、以下に説明される量子計算プロセスは、現存する又は開発されるであろう他のソリッドステート量子レジスタ及びＮＭＲに基づいたシステムなどの他のタイプの量子計算機を含む他の量子計算構造で実現できる。
【００１１】
図１は、線形配列のキュービットを含むソリッドステート複数キュービットレジスタ１００の一例を示す。レジスタ１００などの量子レジスタは、ここに参照のために全体が組み入られる共通に所有する米国特許出願第０９／４５２７４９号及び第０９／４７９３３６号にさらに記載されている。レジスタ１００は、超伝導体バンク１１０とそれぞれのメゾスコピック超伝導体アイランド１２０−０乃至１２０−（Ｎ−１）との間の境界におけるジョゼフソン接合１３０−０乃至１３０−（Ｎ−１）に基づいたキュービットを含む。クーパー対が非ゼロ軌道角運動量の状態にあるｄ波超伝導体、例えば、ＹＢａ2Ｃｕ3Ｏ7-xなどの高Ｔｃ超伝導体又は他の超伝導体が、バンク１１０及びアイランド１２０−０乃至１２０−（Ｎ−１）の１つ又は両方を形成する。
【００１２】
一方又は両方の側にｄ波超伝導体を持つジョゼフソン接合は、二重に縮退したグランド状態電流を有する。特に、各ジョゼフソン接合１３０−０乃至１３０−（Ｎ−１）におけるグランド状態電流は非ゼロで、時計回り又は反時計回りのいずれかである。ｉ番目のジョゼフソン接合におけるグランド状態電流は、それぞれ時計回り及び反時計回り電流に対応した２つの基本量子状態｜ＣＷｉ＞及び｜ＣＣＷｉ＞を有する。一般に、各キュービットは現在状態の線形結合であるグランド状態にある。例えば、第１キュービットの状態は、ａ*｜ＣＷ０＞＋ｂ*｜ＣＣＷ０＞の結合である。ここで、ａ及びｂは複素数である。０から（Ｎ−１）の各値ｉについて、２つの基本状態｜ＣＷｉ＞＋｜ＣＣＷｉ＞をそれぞれ２進値０又は１に任意に割り当てることができる。
【００１３】
Ｎキュービット状態の結合であるレジスタ１００の量子状態は、｜Ｎ−１，・・・，０＞として表現される。状態｜Ｎ−１，・・・，０＞は、各キュービットにおける電流が時計回り又は反時計回りのどちらかに従い、２Nの異なるグランド状態電流構成を有するが、一般に、状態｜Ｎ−１，・・・，０＞は異なる電流状態の結合であり明確な電流構成を持たない。明確な電流構成（従って、明確な２進値に対応する）を持つＮキュービット状態は、ここで、｜ｘ＞又は｜ｙ＞として示される。ここで、ｘ及びｙは、０と２N−１との間のＮビット２進値である。従って、式１が状態｜Ｎ−１，・・・，０＞の一般的な表現を与える。
【００１４】
式１：
2004531793.tif 000003
式１において、係数ａyは一般に複素数である。
【００１５】
計算のために、レジスタ１００は、バンク１１０とアイランド１２０−０乃至１２０−（Ｎ−１）を超伝導にして、そしてキュービットの状態をかく乱する可干渉性の消失の熱源を抑制するために低温度（例えば、約１０°Ｋ以下）に冷却される。そして、キュービットの初期状態が、例えば、バンク１１０中に電流を流すことにより確立される。初期状態は、バンク１１０中の電流方向、バンク１１０及びアイランド１２０−０乃至１２０−（Ｎ−１）の結晶の向き、バンクとアイランド１２０−０乃至１２０−（Ｎ−１）との間の境界の形状及び性質、そしてどんな外部から加えられる磁場に依存する。
【００１６】
キュービットを初期化する別の方法は、状態を測定すること、すなわち、接合での電流が時計回り又は反時計回りかをどうかを決定することである。測定はキュービットを測定された値に対応する明確な状態にする。もし、測定が所望の結果を与えるならば、計算を開始することができる。もし、所望の状態が得られないならば、キュービットに加えられたＮＯＴゲートがキュービット状態を反転でき、そして、その後の測定がＮＯＴゲートガ正確に実現したかを確証するための一種のエラー修正として動作する。有用な計算を実行するためには、初期状態が知られていなければならず、そして、典型的に明確な２進値を持つ。普通、初期状態は２進値０を持つように選ばれる。すなわち、全てのキュービットは０に対応する状態にある。
【００１７】
初期状態が状態についてのさまざまな相互作用の影響下で進展する時、量子計算が実行される。これら相互作用は普通、量子ゲートと呼ばれる。量子レジスタ１００において、隣接するアイランド１２０−１乃至１２０−Ｎの間が単一電子トランジスタ（ＳＥＴ）１５０−２乃至１５０−Ｎである。ＳＥＴ１５０−２乃至１５０−Ｎがオフである時、キュービットの状態｜０＞乃至｜Ｎ−１＞が別々に進展する。１つ又は複数のＳＥＴ１５０−２乃至１５０−Ｎがオンの時、ＳＥＴ１５０−２乃至１５０−Ｎは隣接するキュービット量子状態に制御可能な絡み合いを生成する。レジスタ１００は一次元であり、絡み合いが単一線に沿って隣接するキュービット間でのみ生成される。
【００１８】
量子計算が完了する時、キュービットの現在状態が観察され、又は、結果を決定するために読み出される。結果を読み出すために、接地とそれぞれのアイランド１２０−０乃至１２０−（Ｎ−１）の間のＳＥＴ１５０−２乃至１５０−Ｎは、キュービットのそれぞれの現在状態を「凍結」するためにオンにできる。キュービットの現在状態は、測定装置（図示しない）により決定できる。例えば、磁力顕微鏡（ＭＦＭ）チップ又は超伝導量子干渉計（ＳＱＵＩＤ）ループが、現在状態を決定するために個々のジョゼフソン接合の磁気モーメントを測定できる。
【００１９】
量子レジスタの限界はキュービットの可干渉性（コヒーレンス）時間である。可干渉性（コヒーレンス）時間は一般に、量子状態を外部ファクターがかく乱する前にキュービットの量子状態を進展できる時間を示す。量子計算は可干渉性時間内に完了しなければならない。従って、量子計算の１つの目的は、量子計算を実行するプロセス又はネットワークの時間コストを最小にすることである。
【００２０】
１つの有用な量子計算は、量子フーリエ変換である。量子フーリエ変換は、古典的なフーリエ変換の量子的一般化である。量子計算の分野において、量子フーリエ変換は最も知られた量子計算の基礎である。特に、量子フーリエ変換はショアの因数分解アルゴリズムに使用されている（そして、この目的のためにショアにより開発された）。量子フーリエ変換は、以下の式２に示すように、Ｎキュービットレジスタの状態｜Ｎ−１，・・・，０＞に作用する。
【００２１】
式２
2004531793.tif 000004
【００２２】
式２において、状態｜ｘ＞及び各状態｜ｙ＞は正確な現在構成を持つ（すなわち、正確なＮビット値ｘ及びｙに対応する）。そして、状態｜ｙ＞の加算は全ての正確な現在状態（すなわち、全てのＮビット値ｙ）についての加算である。式２の量子フーリエ変換は、２つの基本的量子ゲート：ｉ番目のキュービットにはじめに対応する状態に作用する１キュービットゲートＡi及びはじめにｊ番目とｋ番目キュービットの状態に作用する２キュービットゲートＢjkを使用してＮキュービットレジスタ１００上で実行できる。
【００２３】
１キュービットゲートＡi（アダマール変換としても知られている）は式３に示される。
【００２４】
式３：
2004531793.tif 000005
【００２５】
式３において、演算子の基本ベクトルは、ｉ番目のキュービットの２つの基本状態｜ＣＷｉ＞又は（０１）及び｜ＣＣＷｉ＞又は（１０）である。１キュービットゲートは以下に説明するように量子レジスタ１００内に実現できる。
【００２６】
式４は、２つのキュービットゲートＢjkに対応する。
式４：
2004531793.tif 000006
【００２７】
式４において、演算子の基本ベクトルは、ｊ番目のキュービットの基本状態｜ＣＷｊ＞及び｜ＣＣＷｊ＞とｋ番目のキュービットの基本状態｜ＣＷｋ＞及び｜ＣＣＷｋ＞とのクロス乗積から作られた４つの基本状態である。係数ｊ及びｋは、量子ゲートＢjkが適用される一対のキュービットを指定する。角度θｊｋは、π／２k-jとして定義され、そのため量子ゲートＢjkが適用されるキュービット間の「距離」により決定される。２キュービットゲートＢjkは以下に説明するように量子ゲート１００内に実現できる。
【００２８】
式５は、４キュービットレジスタ内に実現される時、量子レジスタの状態について式１の量子フーリエ変換を実行する量子ゲートのシーケンスを示す。
式５：  ＱＦＴ4＝Ａ3Ｂ23Ａ2Ｂ13Ｂ12Ａ1Ｂ03Ｂ02Ｂ01Ａ0
【００２９】
図２は、式５に対応する量子ネットワークを示し、そして特定のキュービットに作用する量子ゲートを特に示す。４つのキュービットレジスタに関するこの量子フーリエ変換は、１０量子ゲートを使用するが、より一般的には、Ｎキュービット量子フーリエ変換ＱＦＴNの計算は、Ｎの１キュービット演算とＮ（Ｎ−１）／２の２キュービット演算を使用する。１０のキュービットゲートは１０の時間間隔２０１乃至２１０の間にそれぞれのキュービットに作用する。以下に詳細に説明するように、間隔２０１乃至２１０は一般に持続期間は等しくない。各間隔２０１乃至２１０の持続期間は、関連する量子ゲート及び関連するゲートを実現する下にある量子レジスタに依存する。
【００３０】
ある計算プロセスを最適化するため、一般に、使用される量子アーキテクチャのゲートの基本的組で計算プロセスを表すことが必要である。例えば、式６、７及び８は、演算子Ｘ（θ）、Ｚ（φ）及びＣＰ（ζ）のユニバーサルな組を与える。
【００３１】
式６：
2004531793.tif 000007
【００３２】
式７：
2004531793.tif 000008
【００３３】
式８：
2004531793.tif 000009
【００３４】
式６、７及び８において、σx及びσyはパウリ行列である。演算子Ｘ（θ）及びＺ（φ）は単一キュービット演算子であり、キュービットオペランドによりインデクッスできる。演算子ＣＰ（ζ）は２キュービット演算子でありキュービットオペランドを識別するために一対のインデックスを必要とする。
【００３５】
演算子Ｘ（θ）、Ｚ（φ）及びＣＰ（ζ）は多くのソリッドステート設計のゲートの基本的組に対応し、ＮＭＲに基づいた量子計算機で実現可能である。エヌ・エー・ガーシェンフェルド及びアイ・エル・チャン、「バルク・スピン共鳴量子計算」、サイエンス、２７５：３５１，１９９７を参照。図１に示すような量子レジスタで演算子Ｘ（θ）、Ｚ（φ）及びＣＰ（ζ）を実現することが、エー・ザゴスキン及びエー・ブレイスの論文「ｄ波超伝導体間の清浄なジョゼフソン接合に基づいたソリッドステート量子計算機中のユニバーサル・ゲートの操作」Ｐｈｙｓ．Ｒｅｖ．Ａ６１：０４２３０８（２０００）に記載されていて、ここに参照として全部を組み入れる。
【００３６】
Ｘ（θ）、Ｚ（φ）及びＣＰ（ζ）の基本的な操作は、式９及び１０に示すようにゲートＢｊｋ（２つの隣接するキュービットｊとｋについて）及びゲートＡｊ（キュービットｊについて）を実現する。
【００３７】
式９：  Ａｊ＝ｉＺｊ（π／２）Ｘｊ（π／２）Ｚｊ（π／２）
【００３８】
式１０：
2004531793.tif 000010
【００３９】
式１０において、位相ｅｘｐ｛ｉθk-j+1｝はキュービットｊ及びｋのどちらが演算子Ｂｊｋのオペランドであるかに依存するが、キュービットｊ及びｋの状態からは独立である。すなわち、位相ｅｘｐ｛ｉθk-j+1｝は重要でないグローバル位相要素であり、無視できる。
【００４０】
図２のネットワークは、ゲートＢｊｋを隣接しないキュービットに適用することが必要である。しかし、キュービットの一次元配列はキュービット間の相互作用を最近の隣接する結合に限定する。例えば、図１の量子レジスタ１００において、ＳＥＴ１３０−１乃至１３０−（Ｎ−１）の各々が２つの隣接キュービット間の制御された絡み合いを作る。従って、ゲートＢｊｋを隣接しないキュービットに適用することは、相互作用のために状態を隣接キュービットに移動するように隣接するキュービットの状態を繰り返してスワップすることが必要になる。
【００４１】
最初に位置ｊ及びｋにある量子ビットはキュービットを一緒にするために、｜ｊ−ｋ｜−１のスワップを必要とし、量子ビットをそれらの元の位置に戻すために別の｜ｊ−ｋ｜−１のスワップが必要である。例えば、図３Ａは、ｊが０そしてｋが３の時、Ｂjkを実現するネットワークを示す。時間間隔３０１と３０２の間の２つのスワップが状態をキュービット３からキュービット０に隣接したキュービット１に持って来る。量子ゲートＢは状態が隣接するビットにある間の時間３０３中であり、そして時間３０４と３０５の間の２つのスワップが進展された状態をキュービット１からキュービット３へ戻す。
【００４２】
それぞれ位置ｒ及びｓにあるキュービット間のスワップＳＷrsが、普通、式１１に示される制御ＮＯＴ（ＣＮ）ゲートのシーケンスにより実現される。
【００４３】
式１１：  ＳＷrs＝ＣＮrsＣＮsrＣＮrs
【００４４】
本発明の１つの観点によると、ＣＮゲートが式１２に示すような７つの基本ゲートのシーケンスにより実現できる。
【００４５】
式１２：  ＣＮｒｓ＝ｅ−ｉ３π／４Ｘｓ（３π／２）ＣＰｒｓ（π／２）Ｚｓ（π／２）Ｘｓ（π／２）Ｚｓ（π／２）Ｚｒ（π／２）ＣＰｒｓ（π／２）
【００４６】
この結果、単一スワップ操作ＳＷrsは、２１の基本ゲート（時間ステップ）を必要とする。式１２のこのシーケンスは普通、ＣＮゲートに使用されるものより短い。式１２と従来との主な相違は、ＣＮゲートを実現するために２つの２キュービットゲート（ＣＰ）を１つの代わりに使用することである。
【００４７】
スワップに必要な基本的操作の数は、基本的ゲート間の交換関係及び制御ＮＯＴゲートの対称性を使用して、顕著に減少できる。より詳細には、冗長なゲートの除去は、式１１のシーケンスに必要な時間ステップの数を減少できる。式１３は、１５の基本的操作で実現されるスワップ・シーケンスを示す。
【００４８】
式１３：  ＳＷrs＝ｅ-iπ/4Ｘs（３π／２）ＣＰrs（π／２）Ｚs（π／２）Ｘs（π／２）［Ｚs（π／２）Ｘr（π／２）］ＣＰrs（π／２）Ｚr（π／２）［Ｘr（π／２）Ｘs（π／２）］ＣＰrs（π／２）Ｚs（π／２）Ｘs（π／２）［Ｚs（π／２）Ｚr（π／２）］
【００４９】
さらに、異なるキュービットに同時に操作することにより、レジスタ中でキュービットを移動させるために使用される時間ステップ数をさらに減少する。実際、個別のキュービット交換の操作のため、式１３の角括弧中のゲートは同時に実行でき、完全なスワップのために必要な時間ステップの数を１２に減少する。
【００５０】
さらに、図３Ａに示すように、キュービットｊをキュービットｋの方向のみにスワップする代わりに、図３Ｂに示すようにキュービットｊ及びｋをそれらの隣接と同時的にスワップすることでさらに時間ステップ数を減少する。従って、最初にｊ番目とｋ番目のキュービットにキュービット状態を並置しそして相互作用された状態をそれらの元の位置に戻すために使用される時間ステップは、２┌｜ｊ−ｋ｜／２┐に減少される。ここで、┌ｘ┐は、ｘよりも大きい最小の整数である。
【００５１】
計算プロセスの追加の簡略化は並置されたキュービットの状態がそれらの元の位置に戻される必要がないことである。その代わり、２つのキュービット状態が一緒にされて相互作用をしたなら、次の再組織化は後の量子ゲートの実現を最適化する方法で行われる。量子レジスタ内のキュービット状態の位置は古典的に追跡ができ、そしてビットはキュービットの初期化の際又は量子レジスタから読み出された結果を解釈する時のいずれかで必要とされるとき、再順番することができる。
【００５２】
上記の量子計算の簡略化は、単一のスワップシーケンスがｊ番目及びｋ番目のキュービットを並置するための物理的時間ステップを４２（｜ｊ−ｋ｜−１）から１２┌｜ｊ−ｋ｜／２┐に減少する。
【００５３】
図４は、上述した方法でスワップ操作の数を減少した最適化された量子フーリエ変換ＱＦＴ4４００を示す。さらに、必要なスワップ操作は同時的スワップ操作及びキュービットの効率的再順番を使用して最適化される。特に、それぞれのキュービットＱ０、Ｑ１、Ｑ２及びＱ３の初期状態Ｓ０、Ｓ１、Ｓ２及びＳ３がそれぞれ結果状態Ｓ０’、Ｓ１’、Ｓ２’及びＳ３’に対応しており、そこにキュービットＱ０、Ｑ１、Ｑ２及びＱ３のそれぞれがある。図４のプロセスは、５４時間ステップを必要とする、１０論理ゲートと４スワップを含む。ある量子ネットワークの時間コストを評価すると、同時的操作が実行される時に、最も時間を費やす操作のステップ数が用いられる。最適化をしない場合、この変換は、１０論理ゲートに加えて８スワップを必要とし、全１２６物理的時間ステップとなる。
【００５４】
図４の計算プロセスは、交換するゲートの同時的実行と再順番を使用して、時間ステップの観点から、さらに最適化できる。特に、ゲートＡｉなどの１キュービットゲートがスワップ操作と交換される。ゲートＡｉは元がｉ番目のキュービットに対応する進展した状態を含むキュービットに実行され、そしてスワップ後に異なるキュービットに実行されることができる。１キュービットゲートはもし両方が同じキュービットに作用しなければスワップと同時的に実行できる。２キュービットゲートＢjkはもしそれらが同じキュービットに作用しなければスワップと交換される。例えば、図４では、進展された状態Ｓ２がキュービットＱ２の状態である時に操作Ａ２が時間間隔４０３で行われる。従って、操作Ａ２がキュービットＱ２に実行される。時間間隔４０４の間のスワップ操作がキュービットＱ１からの状態Ｓ１をキュービットＱ２にスワップし、キュービットＱ２からの状態Ｓ２をキュービットＱ１にスワップする。この結果、状態Ｓ３とＳ１とがレジスタ内で操作Ｂ１３のために隣接する。スワップ（時間間隔４０４）及びＡ２（時間間隔４０３）の適用の順序を変えることにより、Ａ２とＢ１３を同時に実行することができる。これが、図５の時間間隔５０３と５０４に示されている。
【００５５】
他の操作の交換可能性が同様な時間節約を可能にする。特に、式１４、１５及び１６の交換子により示されるように、もし、ｉとｊが等しくなければ、ゲートＡｉはゲートＡｊと交換可能で、もし、ｉがｊ又はｋと等しくなければ、ゲートＡｉはゲートＢｊｋと交換可能で、そして、全てのｊ、ｋ、ｒ及びｓに対して、ゲートＢｊｋはゲートＢｒｓと交換可能である。
【００５６】
式１４：    ［Ａｉ，Ａｊ］＝０    もし、ｉ≠ｊ
式１５：    ［Ａｉ，Ｂｊｋ］＝０    もし、ｉ≠ｊ又はｋ
式１６：    ［Ｂｊｋ，Ｂｒｓ］＝０    全てのｊ、ｋ、ｒ及びｓ
【００５７】
これらの交換関係は、図４の計算プロセスの論理的操作の順序の置換を可能にする。例えば、図４において、時間間隔４０８の間のスワップ操作は、時間間隔４０９の間の操作Ｂ０３のために、隣接するキュービットＱ１及びＱ２に状態Ｓ０及びＳ３から進展された状態を置く。時間間隔４１０間の後スワップは、操作Ｂ０２及びＢ０３後の時間間隔４１１での操作Ｂ０１のために、キュービットＱ２にＳ１から進展された状態を移動する。この操作の順番では、時間間隔４１０のスワップ操作が時間間隔４０８の１つのスワップ操作を元に戻す。
【００５８】
図５のプロセスは、操作Ｂ０１を時間間隔５０７の操作Ｂ０２及びＢ０３の前に置く。この再順番は、操作Ｂ０１のために隣接キュービットＱ１とＱ２に状態Ｓ０とＳ１から進展された状態があるため、スワップ操作を無くする。図４の間隔４０８のスワップ操作の内、図５のプロセスは１つを無くして、他を時間間隔５０６で操作Ａ１と同時に実行する。従って、再順番は図５のプロセスに必要な時間をさらに短くする。
【００５９】
図６は、ｎキュービットについての量子フーリエ変換（ＱＦＴ）のための改良されたネットワークを構築するプロセスを示す。図６において、ブロック６３０中の操作が３つのキュービットについて効率的なＱＦＴを実現する。４つの論理ゲートＡ３、Ｂ２３、Ｂ１３及びＢ０３と３つのスワップを３つのキュービットについてのＱＦＴへ加えると、ブロック６４０に含まれる４つのキュービットについてのＱＦＴを与える。ブロック６４０のＱＦＴ4を与える加えられたゲートとスワップは、ブロック６３０のＱＦＴ3に２９時間ステップを加える。５つの論理ゲートＡ４、Ｂ３４、Ｂ２４、Ｂ１４及びＢ０４と４つのスワップを加えると、５つのキュービットについてＱＦＴを与える。これらの加えられたゲートとステップは、さらに２９時間ステップを追加する。
【００６０】
図６のこの構成をＱＦＴn-1の操作ネットワークに繰り返し使用すると、ＱＦＴnについて最適化されたネットワークを与える。ＱＦＴn-1からＱＦＴnを構成するためには、ｎ論理ゲートＡn-1、Ｂ(n-2),(n-1)、・・・Ｂ0,(n-1)及びキュービットｎ−１とｎ−２、キュービットｎ−２とｎ−３、・・・及びキュービット１と０の間のｎ−１スワップの追加を必要とする。スワップは追加された２つのキュービット操作Ｂにインターリーブされる。しかし、追加される時間ステップの数はいまだ２９であり、ＱＦＴnのこのネットワーク構成に必要とされる時間ステップの数は、ｎ＞２について、８＋２９（ｎ−２）（≒Ｏ（ｎ））である。ＱＦＴnのストレイトフォワードな従来技術のネットワークに必要とされる時間ステップの数は、１０ｎ−１１ｎ2＋４ｎ3（≒Ｏ（ｎ3））である。従って、ここに開示されたネットワークは顕著な性能利得を与える。
【００６１】
図８は、改良されたネットワーク（黒丸）と従来の非改良ネットワーク（白四角）の両方について対数スケールで３００キュービットまでのキュービット数の関数として量子フーリエ変換の時間コストを示す。改良されたネットワークは上述の方法を使用して数値的に得られた。特に、同様なキュービットに作用しない間に交換される操作の並行実行とグループ化は、与えられたネットワークについて必要な時間を最小化するために並行操作の性能を最大化できる。このような最適化は効率的に実行することができ、通常のデスクトップコンピュータで３００キュービットネットワークについて数分を要する。
【００６２】
大変小さなネットワークについては、図６で両方の曲線は一致するが、より大きいネットワークについては、回路に対応する数値データがより効率的なことが明確である。
【００６３】
数値データの対数図表から、１０キュービット以上を含むネットワークについて１．０８±０．０１の傾きを得る。これは、量子フーリエ変換がｎ量子ビットについてＯ（ｎ）の時間ステップで実行できることを確認する。これは、非最適化ネットワークと比べてオーダーＯ（ｎ2）の高速化に対応している。スワップ及び大きい（古典的）並列の効率的使用がこの高速化に寄与している。実際、Ｏ（ｎ）の要素による高速化は、Ｏ（ｎ3）のスワップが非最適化回路で必要であるが、最適化された場合はＯ（ｎ2）だけが必要である事実から生ずることが理解される。他のＯ（ｎ）の要素は、ｎキュービットについてｎまでの同時操作が実現できるという事実から生ずる。古典的並列計算機の場合と同様に、これはオーダーＯ（ｎ）の高速化を与える。
【００６４】
図６の構成を持つネットワークは、スワップ数を減少し、そして操作の並列性能を最大化するために、論理操作の置換によりさらに短くできる。図７はさらに最適化した後のＱＦＴ5を示す。
【００６５】
ネットワークに必要とされる時間を最小にすることは、束縛最適化問題を解くことに対応し、ＶＬＳＩ関連技術で生ずる配置問題と多くの類似性を持つ。配置では、古典的回路の部品の配列を回路面積と相互接続線の長さを最小にする方法で求める。模擬されたアニーリング又はタブ探索のような発見法がこのような問題によい結果を与えることを知られている。量子計算のためのネットワークの最適化問題は大変類似するが、しかし、回路内の与えられた場所で２つの論理操作を再順番するとシーケンスが変更されそしてこの回路のさらなる全ての点で必要とされるスワップ数が変更されるという追加の複雑性を持つ。これは発見法プロセスなので、プログラムは最適解決を与えないが、最適解決に近い解決を与える。
【００６６】
本発明が特定の実施の形態の量子計算機及び特定のアルゴリズムについて説明されたが、説明は本発明の応用の一例にしかすぎす、限定的に解すべきではない。上述の開示の大部分は量子フーリエ変換（ＱＦＴ）を実現する例に向けられたが、他の量子計算プロセスも同様に開示された手順により利益を得ることができる。さらに、開示された量子計算はキュービットの線形配列を使用したシステムについてであったが、本発明の実施の形態は最近隣接相互作用を持つキュービットの二次元配列を限定的でなく含む他の量子計算アーキテクチャにも適用できる。開示された実施の形態の特徴のさまざまな他の適用と組合せも特許請求の範囲に定義される本発明の範囲内にある。
【図面の簡単な説明】
【００６７】
【図１】本明細書に説明される計算に適した複数キュービット量子レジスタのブロック図。
【図２】４キュービット・レジスタで量子フーリエ変換を実現するネットワークを示す図。
【図３Ａ】非隣接キュービット間の制御された相互作用を提供するため逐次的スワップ操作の使用を示す図。
【図３Ｂ】非隣接キュービット間の制御された相互作用を提供するため同時的スワップ操作の使用を示す図。
【図４】４キュービット・レジスタ及びスワップ操作を含む同時操作を使用して量子フーリエ変換を実行するネットワークを示す図。
【図５】最近隣接相互作用及び同時操作を可能にする４キュービット配列のための量子フーリエ変換ネットワークを示す図。
【図６】どんな数のキュービットのための改良されたフーリエ変換ネットワークを構成するプロセスを示す図。
【図７】量子フーリエ変換のためのネットワークの別の最適化を示す図。
【図８】本発明による最適化された量子計算プロセス及び従来の量子計算プロセスの時間コストを比較するグラフ。
【図８】
2004531793.tif 000014
【国際公開パンフレット】
2004531793.tif 000015
2004531793.tif 000016
2004531793.tif 000017
2004531793.tif 000018
2004531793.tif 000019
2004531793.tif 000020
2004531793.tif 000021
2004531793.tif 000022
2004531793.tif 000023
2004531793.tif 000024
2004531793.tif 000025
2004531793.tif 000026
2004531793.tif 000027
2004531793.tif 000028
2004531793.tif 000029
2004531793.tif 000030
2004531793.tif 000031
2004531793.tif 000032
2004531793.tif 000033
2004531793.tif 000034
2004531793.tif 000035
2004531793.tif 000036
【国際公開パンフレット（コレクトバージョン）】
2004531793.tif 000037
2004531793.tif 000038
【国際調査報告】
2004531793.tif 000039
2004531793.tif 000040