(57)【要約】  問題の大きさに対して計算時間の期待値が指数関数的に大きくなってしまう問題を回避するために、本発明の離散最適化問題を解くために量子アニーリング計算を行うための処理方法では、（ａ）同一の量子状態を持つ２つの物理系(u,d)間において、一方のエネルギー状態を低エネルギー状態にし、他方のエネルギー状態を高エネルギー状態に遷移させる操作を準備するステップと、（ｂ）複数の物理系間において、ステップ0から順次ステップを遷移させながら各ステップでの複数の物理系の各々の状態値を所定の規則下で設定し、同一の状態値を持つ物理系のペアを同一の状態値が無くなるステップに至るまで集めて集合を得るステップと、（ｃ）集合中の全ての物理系のペアに対して２つの物理系(u,d)を対応させながら（ａ）の操作を適用して、複数の物理系中の最小のエネルギー状態を持つ物を求めるステップを含む。
2018190064.tif 000002
【特許請求の範囲】
【請求項１】
離散最適化問題を解くために量子アニーリング計算を行うための処理方法であって、
（ａ）同一の量子状態を持つ２つの物理系(u,d)間において、一方のエネルギー状態を低エネルギー状態にし、他方のエネルギー状態を高エネルギー状態に遷移させる操作を準備するステップと、
（ｂ）複数の物理系間において、ステップ0から順次ステップを遷移させながら各ステップでの複数の物理系の各々の状態値を所定の規則下で設定し、同一の状態値を持つ物理系のペアを同一の状態値が無くなるステップに至るまで集めて集合を得るステップと、
（ｃ）前記集合中の全ての前記物理系のペアに対して前記２つの物理系(u,d)を対応させながら前記操作を適用して、前記複数の物理系中の最小のエネルギー状態を持つ物理系を求めるステップと、を含む処理方法。
【請求項２】
前記操作を準備するステップ（ａ）は、
（ａ１）前記２つの物理系(u,d)に初期状態として同一の量子状態を与えるステップと、
（ａ２）物理系uの量子状態をハミルトニアン(H)を用いて時間τ(>0)の間時間発展させるステップと、
（ａ３）物理系uと物理系dの間で量子スワッピング操作を時間Δt(>0)の間行うステップと、
（ａ４）物理系uの量子状態を反転したハミルトニアン（-H）を用いて時間τ(>0)の間時間発展させるステップと、を含む請求項１に記載の処理方法。
【請求項３】
前記集合を得るステップ（ｂ）は、
（ｂ１）2m個の物理系において、j番目の物理系jの状態値をＳｊ（step）とし、全ての物理系ｊについてＳｊ（0）=0にするステップと、
（ｂ２）j＜j’である全てのjとj’について、Ｓｊ（step）=Ｓｊ’（step）となる物理系jと物理系j’をペアとして選択するステップと、
（ｂ３）物理系jと物理系j’のペアを集めて集合Ω(step)とするステップと、
（ｂ４）集合Ω(step)に含まれるjとj’について、Ｓｊ（step+1）=Ｓｊ（step）-1、Ｓｊ’（step+1）=Ｓｊ’（step）+1とするステップと、
（ｂ５）集合Ω(step)に含まれないjについて、Ｓｊ（step+1）=Ｓｊ（step）とし、step+1をstepとするステップと、
（ｂ６）ステップ（ｂ２）からステップ（ｂ５）までを集合Ω(step)が空集合になるまで繰り返すステップと、
（ｂ７）集合Ω(step)が空集合になるstepから1減算したstepをstep*とするステップと、を含む請求項２に記載の処理方法。
【請求項４】
前記最小のエネルギー状態を持つ物理系を求めるステップ（ｃ）は、
（ｃ１）2m個の物理系に初期状態として同じ量子状態を与えるステップと、
（ｃ２）step=0とするステップと、  
（ｃ３）前記集合Ω(step)中の全ての前記物理系のペアj、j’に対して、前記物理系jを前記物理系uに対応させ、前記物理系j’を前記物理系dに対応させながら前記ステップ（ａ１）〜（ａ４）を含む操作を適用するステップと、を含む請求項３に記載の処理方法。
【請求項５】
各物理系jにおける状態値Ｓｊ（step*）は、
Ｓｊ（step*）=j-m-1  (j=1,2,・・・,m)
Ｓｊ（step*）=j-m    (j=m+1,m+2,・・・,2m)
で与えられる、請求項３に記載の処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、量子アニーリング計算に関し、より具体的には、離散最適化問題を解くために量子アニーリング計算を行うための処理方法に関する。
【背景技術】
【０００２】
離散最適化問題を、量子効果を利用して解く量子計算機として、量子アニーリング計算機が知られている。量子アニーリング計算機は、オペレーションリサーチ等に頻出する、評価関数を最小化（最適化に相当）する離散変数の組み合わせを求める問題（以下、「離散最適化問題」よ呼ぶ）を解くための計算機である。【０００３】
離散変数を物理状態に、およびその離散変数に対する評価関数の値がその状態のエネルギーとなる物理系を構成する。すなわち、エネルギーは状態の関数である。これにより、何らかの方法でその物理系をエネルギーが最も低い状態にすることができれば、その状態を測定することにより最適解が得られる。物理系をエネルギーが最も低い状態にするメカニズムとして、量子力学的効果を用いた量子アニーリングが知られている。量子アニーリングは、量子力学的効果を使わないものと比較して効率よく問題を解く場合があることが知られている。【０００４】
量子アニーリングでは、系に作用する外場（ポテンシャル）を制御することにより、エネルギーと状態の対応を時間的に徐々に変化させる。初期のポテンシャルは、自明な最低エネルギー状態を持つものが選ばれる。ポテンシャルを変化させ、最終的に実際に最適解を調べたい評価関数に対応したエネルギーと状態の関係が達成されるよう設計されている。系の初期状態を初期ポテンシャルで決定される最低エネルギー状態に準備し、ポテンシャルを十分ゆっくり変化させると、状態は各瞬間各瞬間のポテンシャルで決定される最低エネルギー状態をたどることが量子力学の結果として知られている。こうして、最終的に調べたい評価関数を最小化する状態を得ることができる。【０００５】
ポテンシャルの時間変化がゆっくりであれば、状態は最低エネルギー状態をたどることは、量子力学における断熱定理として一般的に知られており、この計算手法は断熱量子計算という呼び名でも知られている。一例として、特許文献１は、複数の超伝導キュビットを具備する量子システムを使用した断熱量子計算のための方法を開示する。断熱量子計算では、計算の過程に現れる状態に量子力学的な状態（通常の古典物理学では表現できない状態）が出現する。このため、この計算方法は古典物理学を実装原理とする通常のコンピュータよりも効率よく問題を解ける場合がある。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特表２００９−５２４８５７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
特許文献１等の従来の量子アニーリング計算では、断熱定理が成立するように、ポテンシャルの時間変化をゆっくりとしたものにしなければならない。このため、計算をその制限を超えて加速させることができない。特に、問題の規模が大きい場合、問題の大きさに対して計算時間の期待値が指数関数的に大きくなってしまうという問題（ボトルネック）がある。【０００８】
本発明は、物理状態を最低エネルギー状態に導くメカニズムとして、従来の断熱定理を用いた方法とは異なる方法を提案し、上述したボトルネック問題を回避できるようにすることを目的とする。
【課題を解決するための手段】
【０００９】
本発明は離散最適化問題を解くために量子アニーリング計算を行うための処理方法を提供する。その処理方法の概要は、
（ｉ）問題の解が最低エネルギー状態になるようにエネルギー関数（問題ハミルトニアンH）を構成し、
（ｉｉ）同じ量子状態を持つ２つの物理システム間で、一方を低エネルギー状態へ、もう一方を高エネルギー状態へ遷移させる方法を繰り返して複数のシステム間に適用して、
（ｉｉｉ）状態が問題の解である最低エネルギー状態を求めることを含む。【００１０】
より具体的には、本発明の処理方法は、その一実施態様として、
（ａ）同一の量子状態を持つ２つの物理系(u,d)間において、一方のエネルギー状態を低エネルギー状態にし、他方のエネルギー状態を高エネルギー状態に遷移させる操作を準備するステップと、
（ｂ）複数の物理系間において、ステップ0から順次ステップを遷移させながら各ステップでの複数の物理系の各々の状態値を所定の規則下で設定し、同一の状態値を持つ物理系のペアを同一の状態値が無くなるステップに至るまで集めて集合を得るステップと、
（ｃ）（ｂ）の集合中の全ての物理系のペアに対して（ａ）の２つの物理系(u,d)を対応させながら（ａ）の操作を適用して、複数の物理系中の最小のエネルギー状態を持つ物理系を求めるステップと、を含む。
【発明の効果】
【００１１】
本発明の方法を一例として探索空間2nの探索問題に適用した場合、計算ステップ数はnに対して高々多項式的（２次（n2））な増加に抑えられ、従来の量子アニーリング計算やゲート式の量子計算を適用した場合に計算ステップ数がnに対して指数関数的（2n/2）に増加するのに比べて、計算ステップ数を大幅に削減することができる。また、本発明の方法を用いた場合、計算ステップ数と必要な量子ビット数は、nに対して高々多項式的なサイズ（２次（n2））で問題を解くことができる。その結果、問題のサイズに従う計算時間の増加を抑制することができる。
【図面の簡単な説明】
【００１２】
【図１】本発明の処理方法の概要を示す図である。
【図２】本発明の処理方法の一実施態様のフローを示す図である。
【図３】本発明の処理方法の一実施態様のエネルギー状態を遷移させる操作（図２のステップＳ１０）の概念図である。
【図４】図３の概念図の略式図である。
【図５】本発明の処理方法の一実施態様の集合を得るステップＳ２０及び複数の物理系中の最小のエネルギー状態を持つ物理系を求めるステップＳ３０を説明するための図である。
【図６】本発明の処理方法の一実施態様を実施した場合（図５）のエネルギーの期待値の時間発展を示す図である。
【図７】本発明の処理方法をジョセフソン接合を用いた超伝導回路（CJJ-rf-SQUID）に適用する実装例（構成例）を示す図である。
【図８】図７の実施例の制御シーケンスを示す図である。
【図９】非線形方程式による探索問題の正解確率P(t)の時間的挙動のn依存性を示す図である。
【図１０】正解確率P(t)がP(t)≧0.9となる時間t*のn依存性を示す図である。
【図１１】Ω(step)が空集合になるstepから1を引いたstep*および量子操作の数C(m)のm依存性を示す図である。
【発明を実施するための形態】
【００１３】
図面を参照しながら本発明の実施形態について説明する。図１は、本発明の処理方法の概要を示す図である。その処理方法の概要は、最初に、問題の解が最低エネルギー状態になるようにエネルギー関数（問題ハミルトニアンH）を構成する（Ｓ１）。次に、同じ量子状態を持つ２つの物理システム間で、一方を低エネルギー状態へ、もう一方を高エネルギー状態へ遷移させる方法を繰り返して複数のシステム間に適用する（Ｓ２）。その結果、状態が問題の解である最低エネルギー状態が求められる（Ｓ３）。
【００１４】
図２は、本発明の処理方法の一実施態様のフローを示す図である。ステップＳ１０として、同一の量子状態を持つ２つの物理系(u,d)間において、一方のエネルギー状態を低エネルギー状態にし、他方のエネルギー状態を高エネルギー状態に遷移させる操作を準備する。ステップＳ２０として、複数の物理系間において、ステップ0から順次ステップを遷移させながら各ステップでの複数の物理系の各々の状態値を所定の規則下で設定し、同一の状態値を持つ物理系のペアを同一の状態値が無くなるステップに至るまで集めて集合を得る。ステップＳ３０として、その集合中の全ての物理系のペアに対して、２つの物理系(u,d)を対応させながらステップＳ１０のエネルギー状態を遷移させる操作を適用して、複数の物理系中の最小のエネルギー状態を持つ物理系を求める。
【００１５】
図３を参照しながら、図２のステップＳ１０のエネルギー状態を遷移させる操作について詳細に説明する。図３は、本発明の処理方法の一実施態様のエネルギー状態に遷移させる操作（図２のステップＳ１０）の概念図である。最初に、二つの物理系（u,d）に下記（１）で示す同じ量子状態を初期状態として準備する。
【数１】
2018190064.tif 000003
この時点で、uとdは下記（２）で示す同じエネルギーの期待値を持っている。
【数２】
2018190064.tif 000004
後のため、（１）の量子状態におけるエネルギーの分散を下記の式（３）で与えておく。
【数３】
2018190064.tif 000005
【００１６】
＜第１の操作＞として、uの量子状態を下記（４）で示すハミルトニアンを用いて時間τ（>0）の間時間発展させる。図３の符号１のブロックはこの第１の操作を示している。
【数４】
2018190064.tif 000006
＜第２の操作＞として、uとdの間で量子スワッピング操作を時間Δt（>0）の間実行する。図３の符号２のブロックはこの第２の操作を示している。
＜第３の操作＞として、uの量子状態を反転した下記（５）で示すハミルトニアンを用いて時間τ（>0）の間時間発展させる。図３の符号３のブロックはこの第３の操作を示している。
【数５】
2018190064.tif 000007
【００１７】
第１〜第３の一連の操作後のuとdの量子状態は、操作によって規定される量子力学的時間発展の結果、τとΔtの一次までの近似の範囲で、uの量子状態は下記の式（６）で表すことができ、dの量子状態は下記の式（７）で表すことができる。
【数６】
2018190064.tif 000008
【数７】
2018190064.tif 000009
ここで、下記の非線形方程式（８）の解（９）を考えると、
【数８】
2018190064.tif 000010
【数９】
2018190064.tif 000011
τとΔtの一次までの近似の範囲で、下記の式（１０）、（１１）が成立していることがわかる。
【数１０】
2018190064.tif 000012
【数１１】
2018190064.tif 000013
【００１８】
上記の（９）で与えられる状態における下記（１２）のエネルギーの期待値は、tについて単調減少である。
【数１２】
2018190064.tif 000014
第１〜第３の操作後の状態におけるエネルギーの期待値は、uについては下記の式（１３）となり、初期状態における期待値よりもΔEτΔtだけ高くなる。
【数１３】
2018190064.tif 000015
一方dについては下記の式（１４）となり、初期状態における期待値よりもΔEτΔtだけ低いものとなる。
【数１４】
2018190064.tif 000016
以上から、第１から第３までの一連の操作により、uはエネルギーの高い状態に、dはエネルギーの低い状態に遷移していることがわかる。
【００１９】
次に、図４〜図６を参照しながら図２のステップＳ２０、Ｓ３０について詳細に説明する。言い換えれば、図２のステップＳ１０の方法を複数のシステム間に適用することにより離散最適化問題を解くための量子計算機を構成するための処理方法を説明する。図４は、図３の概念図の略式図である。図４において、黒丸４と白丸５が、図３の操作ブロック１、２、及び３に対応している。図５は、本発明の処理方法の一実施態様の集合を得るステップＳ２０及び複数の物理系中の最小のエネルギー状態を持つ物理系を求めるステップＳ３０を説明するための図である。図５では、図４の略式記述（黒丸４と白丸５）を用いて表示している。図６は、本発明の処理方法の一実施態様を実施した場合（図５）のエネルギーの期待値の時間発展を示す図である。
【００２０】
mを整数として、2m個の物理系を考える。これらの物理系の間のネットワーク構造を以下の手順で導入する。図５ではm=4（システム1〜システム8）の場合を示している。
(1)0から始まる非負の整数stepを導入する。図５と図６では、step=0を初期状態とし、stepが順次１増える状態遷移を示している。
(2)j番目の物理系に以下の規則で決まる整数sj(step)を導入する。
(2-1) sj(0)はすべての物理系jについて0とする。
(2-2) j<j’である物理系jと物理系j’について、sj(step)= sj’(step)であれば物理系jと物理系j’をペアにする。図５では、黒丸と白丸を縦方向で結ぶが１つの線が１つのペアを示している。例えば、step=2のシステム1と3ではs1(2)= s3(2)=-1となりシステム1と3はペアとなる。同様に、step=7のシステム4と7ではs4(7)= s7(7)=+2となりシステム4と7はペアとなる。一度ペアとなった物理系jと物理系j’をのぞいて、可能な限りこのようなペアを集める。
(2-3) 上記で構成した物理系のペアを要素とする集合をΩ(step)とする。
【００２１】
(2-4) Ω(step)の中に現れる物理系jと物理系j’について、sj(step+1)とsj’(step+1)を下記の式（１５）、（１６）のように定義をする。
【数１５】
2018190064.tif 000017
【数１６】
2018190064.tif 000018
図５では、例えば、step=5のシステム3と6のペアにおいて、s3(6)= s3(5)-1=-1、s6(6)= s6(5)+1=0とする。他のペアも同様である。
(2-5) Ω(step)の中に現れないjについて下記の式（１７）の定義をする。
【数１７】
2018190064.tif 000019
図５では、例えば、システム1のstep=4からstep=7において、s1(7)= s1(6)=s1(5)= s1(4) s1(3)=-3とする。他も同様である。
【００２２】
(2-6) step+1をstepとして上記の(2-2)に戻り、Ω(step)が空集合となるまでこれを繰り返す。
(2-7) Ω(step)が空集合になるstepから1を引いたものをstep*と定義する。図５では、Ω(step)が空集合になるstep=12（終状態）から1を引いたstep=11がstep*となる。このとき下記（１８）をネットワーク構造と呼ぶ。このネットワーク構造（１８）は、最小固有状態を求めたいハミルトニアンHとは独立に決定できることが特徴である。
【数１８】
2018190064.tif 000020
また、このネットワークの構成法より各jにおけるsj(step*)の値は下記の式（１９）で求めることができる。
【数１９】
2018190064.tif 000021
図５では、例えば、システム4において、s4(step*)= s4(11)=j-m-1=4-4-1=-1となり、システム8において、s8(step*)= s8(11)=j-m=8-4=+4となる。
【００２３】
上記のネットワーク構造と、図２のステップＳ１０のエネルギー状態を遷移させる操作（同じ量子状態を持つ２つの物理システム間でのエネルギー交換方法）を用いて、量子状態を次のように時間発展させる。
(1)2m個の物理系に同じ量子状態を初期状態として準備する。
(2)step=0とする。
(3)Ω(step)に含まれる全てのペア{j,j’}（j<j’であることに注意）に対し、物理系jを図２のステップＳ１０（図３）における物理系u、物理系j’を物理系dにそれぞれ対応させ、ステップＳ１０のエネルギー状態を遷移させる操作を適用する。
(4)step+1を新たにstepとして(3)に戻り、step=step*に到達するまで繰り返す。
【００２４】
このとき、 上記の式（１０）と（１１）が繰り返し適用され、各物理系jにおける各stepの状態は、式（８）の解（９）を使って、τとΔtの一次までの近似の範囲で下記の（２０）で表される。
【数２０】
2018190064.tif 000022
このときのエネルギー期待値を厳密に計算した結果が、図６のエネルギーの期待値の時間発展を示す図である。図６において、破線７で囲まれる１つの領域がエネルギーの期待値を表し、白黒の濃淡がエネルギーの期待値の大小を表し、色が濃くなる程エネルギーの期待値が小さくなることを示している。図６は図５のm=4の物理系（システム）に対応しているので、システム８のstep=11においてエネルギーの期待値が最小となっていることがわかる。
【００２５】
step=step*では、式（１９と式（２０）および式（１２）がtについて単調減少であることより、各物理系jにおける状態でのエネルギーの期待値はjについて単調減少となる。その中でも特に、j=2mの物理系（図５の例ではシステム8）では、下記（２１）の最もエネルギーの期待値の低い状態が上記した一連の操作によって規定される量子力学的時間発展の結果、実現する。
【数２１】
2018190064.tif 000023
【実施例１】
【００２６】
実施例１として、図２のステップＳ１０の方法（操作）をジョセフソン接合を用いた超伝導回路（「CJJ-rf-SQUID」、Physical Review B 80,052506,2009）に適用した場合の実装例を以下に示す。図７は、その実装例（構成例）を示す図である。図７では、二つの量子ビット1,2の例を示している。物理システムu、dにおいて、量子ビット1,2を構成する超伝導ループ１０は、２つのジョセフソン接合（×）を含むミニループ１１を含む。超伝導ループ１０の各々は、同様な超伝導ループ同士が相互インダクタンスを介して磁気的に接合する。なお、以下の説明では、より一般的に二つの量子ビットi,jを想定した場合について説明する。【００２７】
CJJ-rf-SQUID系では、二つの量子ビットi,jの間に下記の式（２２）の形の相互作用を形成することができる。
【数２２】
2018190064.tif 000024
ただし、式（２２）中の下記（２３）の各係数は整数の値を取る時間の関数である。図８は、図７の実施例の制御シーケンス、すなわち、下記（２３）の各係数の値（-1,0,+1）の時間遷移を示す図である。
【数２３】
2018190064.tif 000025
さらに、下記（２４）の各係数は、量子ビットiのパウリ行列とする。
【数２４】
2018190064.tif 000026
【００２８】
上記の式（２２）の相互作用が実現された量子ビットの集合を考える。これらの量子ビットの集合を２つに分けて、１つを物理システムu、残りを物理システムdに対応させる。このとき、uに属する量子ビットiのラベルを(i,u)とし、同様にdに属する量子ビットiのラベルを(i,d)とする。すなわち、これらの量子ビット間の相互作用は下記の式（２５）のように表される。
【数２５】
2018190064.tif 000027
このとき、量子アニーリング計算の場合と同様に、t<0において数（２５）の相互作用において、下記の式（２６）を導入し、かつ、他の係数を0に設定して初期状態（図８のt<0の範囲）を用意する。
【数２６】
2018190064.tif 000028
【００２９】
上記した第１の操作に対応して、式（２５）中の物理系uを構成する量子ビット間の相互作用を用いて、量子アニーリング計算の場合と同様に、式（４）のハミルトニアンを下記の式（２７）のように実現する。
【数２７】
2018190064.tif 000029
すなわち、下記の式（２８）及び（２９）を時間τの間設定する（図８の時間τの間）ことで、第１の操作が完了する。
【数２８】
2018190064.tif 000030
【数２９】
2018190064.tif 000031
【００３０】
上記した第２の操作に対応して、スワッピングの操作を行う。スワッピングは式（２５）中の物理系uとdを構成する量子ビット間に、下記の式（３０）の相互作用を構成し、時間Δtの間設定することで第２の操作が完了する。
【数３０】
2018190064.tif 000032
しかし、式（３０）の相互作用は式（２５）の形をした相互作用では直接実現することができない。そこで、下記の式（３１）〜（３４）
【数３１】
2018190064.tif 000033
【数３２】
2018190064.tif 000034
【数３３】
2018190064.tif 000035
【数３４】
2018190064.tif 000036
に着目すると、式（６）や式（７）を成立させるΔtの１次までの範囲では、下記の(1)〜(3)の操作を順に行うことで、間接的に第２の操作を実装することができる。【００３１】
(1)式（３２）の操作:
式（２５）において、下記の式（３５）として、残りの係数は全て0を時間Δtの間設定する（図８の最初のΔtの間）。これにより式（３１）の操作が完了する。
【数３５】
2018190064.tif 000037
(2)式（３３）の操作:
式（２５）において、下記の式（３６）として、残りの係数は全て０を時間π/2の間設定する（図８の最初のπ/2の間）。その後、式（３５）として残りの係数は全て0を時間Δtの間設定する（図８の２番目のΔtの間）。
【数３６】
2018190064.tif 000038
さらに、下記の式（３７）として、残りの係数は全て0を時間π/2の間設定する（図８の２番目のπ/2の間）。これにより式（３３）の操作が完了する。
【数３７】
2018190064.tif 000039
【００３２】
(3)式（３４）の操作:
式（２５）において、下記の式（３８）として、残りの係数は全て０を時間π/2の間設定する（図８の３番目のπ/2の間）。
【数３８】
2018190064.tif 000040
その後、式（３６）として残りの係数を全て0に設定し時間π/2を経過させ（図８の４番目のπ/2の間）、続いて式（３５）として残りの係数は全て0を時間Δtの間設定する（図８の３番目のΔtの間）。さらに、式（３７）として、残りの係数を全て0として時間π/2を経過後（図８の５番目のπ/2の間）、さらに下記の式（３９）として、残りの係数の全て0を時間π/2の間設定する（図８の最後のπ/2の間）。
【数３９】
2018190064.tif 000041
これにより式（３４）の操作が完了する。以上の一連の(1), (2) 及び(3)の操作より、第２の操作が完了する。【００３３】
上記した第３の操作に対応して、式（２５）中の物理系uを構成する量子ビット間の相互作用を用いて、式（５）の相互作用を時間間隔τの間設定する。これは式（２７）を反転させたものであるから、式（２８）に対応して下記の式（４０）を設定すればよい。これにより、第３の操作が完了する。
【数４０】
2018190064.tif 000042
以上により、実装されるCJJ-rf-SQUIDによる図２のステップＳ１０の方法（操作）を2m個のシステムに繰り返して適用して量子計算に利用するには、図４〜図６を参照しながら上述した一連の処理を用いることにより利用（実装）することができる。
【実施例２】
【００３４】
次に、実施例２として、計算ステップ数および必要な量子ビット数の評価を行うために、本発明を探索空間2nの探索問題に適用した場合について説明する。最初に、探索問題に対応する下記の式（４１）のハミルトニアンを式（８）の非線形方程式に適用する。
【数４１】
2018190064.tif 000043
時刻tにおける下記の式（４２）の正解確率を計算すると解析解が存在して下記の式（４３）が得られる。図９は、式（４３）のP(t)をプロットして得られた、非線形方程式による探索問題の正解確率P(t)の時間的挙動のn依存性を示す図である。
【数４２】
2018190064.tif 000044
【数４３】
2018190064.tif 000045
【００３５】
ここで、解空間の大きさが下記の（４４）であって、初期の正解確率が下記の式（４５）となる場合を考える。
【数４４】
2018190064.tif 000046
【数４５】
2018190064.tif 000047
このとき、下記の式（４６）を満たす時刻tをt*と定義すると、t*は下記の式（４７）として得られる。図１０は、式（４７）のt*をプロットしたもので、グラフＡは正解確率P(t)≧0.9となる時間t*のn依存性を示す。
【数４６】
2018190064.tif 000048
【数４７】
2018190064.tif 000049
【００３６】
ここで本発明によって得られる状態が式（２１）であることより、式（４７）のt*に対応するmをm*とすれば、下記の式（４８）が得られる。
【数４８】
2018190064.tif 000050
step*とmの関係はハミルトニアン(H)の詳細によらず、下記の式（４９）であることに注目すると、m*で決まるstep*は下記の式（５０）となり、nの２次（n2）であることがわかる。
【数４９】
2018190064.tif 000051
【数５０】
2018190064.tif 000052
また、式（４３）の問題を表現するのに必要な１システムあたりの量子ビット数はn個であるから、2m*システム全体では下記の式（５１）となる。
【数５１】
2018190064.tif 000053
【００３７】
さらに、与えられたmに対し必要な量子操作の数C(m)は下記の式（５２）であることから、上記の探索問題に適用した場合には下記の式（５３）となる。図１１は、式（５０）をプロットして得られるstep*及び式（５３）をプロットして得られる量子操作の数C(m)のm依存性を示す図である。
【数５２】
2018190064.tif 000054
【数５３】
2018190064.tif 000055
【００３８】
上記した探索空間2nの探索問題に従来の量子アニーリング計算、およびゲート式の量子計算探索問題に適用した場合、（量子を使わない計算に比べて小さくはなるものの）その計算ステップ数は2n/2となり、nに対して指数関数的に振る舞うことが知られている。一方、本発明による計算ステップ数（step*）は、上述したように、nに対して高々多項式的（例えばn2）に抑えられる。同様に、計算に必要な量子ビットの数は、従来の計算手法がnに比例する程度だったのに対し、本発明ではn2に比例することになるが、計算ステップ数と必要な量子操作数（C(m)）がnに対して高々多項式的なサイズ（例えばn3）で問題を解くことができる。【００３９】
本発明の実施形態について、図を参照しながら説明をした。しかし、本発明はこれらの実施形態に限られるものではない。さらに、本発明はその趣旨を逸脱しない範囲で当業者の知識に基づき種々なる改良、修正、変形を加えた態様で実施できるものである。
【符号の説明】
【００４０】
１：第１の操作
２：第２の操作
３：第３の操作
４、５：第１〜第３の操作の略式記述
７：エネルギーの期待値
１０：超伝導ループ
１１：２つのジョセフソン接合を含むミニループ
【図１】
2018190064.tif 000056
【図２】
2018190064.tif 000057
【図３】
2018190064.tif 000058
【図４】
2018190064.tif 000059
【図５】
2018190064.tif 000060
【図６】
2018190064.tif 000061
【図７】
2018190064.tif 000062
【図８】
2018190064.tif 000063
【図９】
2018190064.tif 000064
【図１０】
2018190064.tif 000065
【図１１】
2018190064.tif 000066
【手続補正書】
【提出日】令和1年10月17日(2019.10.17)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、量子アニーリング計算に関し、より具体的には、離散最適化問題を解くために量子アニーリング計算を行うための処理方法に関する。
【背景技術】
【０００２】
離散最適化問題を、量子効果を利用して解く量子計算機として、量子アニーリング計算機が知られている。量子アニーリング計算機は、オペレーションリサーチ等に頻出する、評価関数を最小化（最適化に相当）する離散変数の組み合わせを求める問題（以下、「離散最適化問題」と呼ぶ）を解くための計算機である。
【０００３】
離散変数を物理状態に、およびその離散変数に対する評価関数の値がその状態のエネルギーとなる物理系を構成する。すなわち、エネルギーは状態の関数である。これにより、何らかの方法でその物理系をエネルギーが最も低い状態にすることができれば、その状態を測定することにより最適解が得られる。物理系をエネルギーが最も低い状態にするメカニズムとして、量子力学的効果を用いた量子アニーリングが知られている。量子アニーリングは、量子力学的効果を使わないものと比較して効率よく問題を解く場合があることが知られている。
【０００４】
量子アニーリングでは、系に作用する外場（ポテンシャル）を制御することにより、エネルギーと状態の対応を時間的に徐々に変化させる。初期のポテンシャルは、自明な最低エネルギー状態を持つものが選ばれる。ポテンシャルを変化させ、最終的に実際に最適解を調べたい評価関数に対応したエネルギーと状態の関係が達成されるよう設計されている。系の初期状態を初期ポテンシャルで決定される最低エネルギー状態に準備し、ポテンシャルを十分ゆっくり変化させると、状態は各瞬間各瞬間のポテンシャルで決定される最低エネルギー状態をたどることが量子力学の結果として知られている。こうして、最終的に調べたい評価関数を最小化する状態を得ることができる。
【０００５】
ポテンシャルの時間変化がゆっくりであれば、状態は最低エネルギー状態をたどることは、量子力学における断熱定理として一般的に知られており、この計算手法は断熱量子計算という呼び名でも知られている。一例として、特許文献１は、複数の超伝導キュビットを具備する量子システムを使用した断熱量子計算のための方法を開示する。断熱量子計算では、計算の過程に現れる状態に量子力学的な状態（通常の古典物理学では表現できない状態）が出現する。このため、この計算方法は古典物理学を実装原理とする通常のコンピュータよりも効率よく問題を解ける場合がある。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特表２００９−５２４８５７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
特許文献１等の従来の量子アニーリング計算では、断熱定理が成立するように、ポテンシャルの時間変化をゆっくりとしたものにしなければならない。このため、計算をその制限を超えて加速させることができない。特に、問題の規模が大きい場合、問題の大きさに対して計算時間の期待値が指数関数的に大きくなってしまうという問題（ボトルネック）がある。
【０００８】
本発明は、物理状態を最低エネルギー状態に導くメカニズムとして、従来の断熱定理を用いた方法とは異なる方法を提案し、上述したボトルネック問題を回避できるようにすることを目的とする。
【課題を解決するための手段】
【０００９】
本発明は離散最適化問題を解くために量子アニーリング計算を行うための処理方法を提供する。その処理方法の概要は、
（ｉ）問題の解が最低エネルギー状態になるようにエネルギー関数（問題ハミルトニアンH）を構成し、
（ｉｉ）同じ量子状態を持つ２つの物理システム間で、一方を低エネルギー状態へ、もう一方を高エネルギー状態へ遷移させる方法を繰り返して複数のシステム間に適用して、
（ｉｉｉ）状態が問題の解である最低エネルギー状態を求めることを含む。
【００１０】
より具体的には、本発明の処理方法は、その一実施態様として、
（ａ）同一の量子状態を持つ２つの物理系（u，d）間において、一方のエネルギー状態を低エネルギー状態にし、他方のエネルギー状態を高エネルギー状態に遷移させる操作を準備するステップと、
（ｂ）複数の物理系間において、ステップ0から順次ステップを遷移させながら各ステップでの複数の物理系の各々の状態値を所定の規則下で設定し、同一の状態値を持つ物理系のペアを同一の状態値が無くなるステップに至るまで集めて集合を得るステップと、
（ｃ）（ｂ）の集合中の全ての物理系のペアに対して（ａ）の２つの物理系（u，d）を対応させながら（ａ）の操作を適用して、複数の物理系中の最小のエネルギー状態を持つ物理系を求めるステップと、を含む。
【発明の効果】
【００１１】
本発明の方法を一例として探索空間2nの探索問題に適用した場合、計算ステップ数はnに対して高々多項式的（２次（n2））な増加に抑えられ、従来の量子アニーリング計算やゲート式の量子計算を適用した場合に計算ステップ数がnに対して指数関数的（2n/2）に増加するのに比べて、計算ステップ数を大幅に削減することができる。また、本発明の方法を用いた場合、計算ステップ数と必要な量子ビット数は、nに対して高々多項式的なサイズ（２次（n2））で問題を解くことができる。その結果、問題のサイズに従う計算時間の増加を抑制することができる。
【図面の簡単な説明】
【００１２】
【図１】本発明の処理方法の概要を示す図である。
【図２】本発明の処理方法の一実施態様のフローを示す図である。
【図３】本発明の処理方法の一実施態様のエネルギー状態を遷移させる操作（図２のステップＳ１０）の概念図である。
【図４】図３の概念図の略式図である。
【図５】本発明の処理方法の一実施態様の集合を得るステップＳ２０及び複数の物理系中の最小のエネルギー状態を持つ物理系を求めるステップＳ３０を説明するための図である。
【図６】本発明の処理方法の一実施態様を実施した場合（図５）のエネルギーの期待値の時間発展を示す図である。
【図７】本発明の処理方法をジョセフソン接合を用いた超伝導回路（CJJ-rf-SQUID）に適用する実装例（構成例）を示す図である。
【図８】図７の実施例の制御シーケンスを示す図である。
【図９】非線形方程式による探索問題の正解確率P(t)の時間的挙動のn依存性を示す図である。
【図１０】正解確率P(t)がP(t)≧0.9となる時間t*のn依存性を示す図である。
【図１１】Ω(step)が空集合になるstepから1を引いたstep*および量子操作の数C(m)のm依存性を示す図である。
【発明を実施するための形態】
【００１３】
図面を参照しながら本発明の実施形態について説明する。図１は、本発明の処理方法の概要を示す図である。その処理方法の概要は、最初に、問題の解が最低エネルギー状態になるようにエネルギー関数（問題ハミルトニアンH）を構成する（Ｓ１）。次に、同じ量子状態を持つ２つの物理システム間で、一方を低エネルギー状態へ、もう一方を高エネルギー状態へ遷移させる方法を繰り返して複数のシステム間に適用する（Ｓ２）。その結果、状態が問題の解である最低エネルギー状態が求められる（Ｓ３）。
【００１４】
図２は、本発明の処理方法の一実施態様のフローを示す図である。ステップＳ１０として、同一の量子状態を持つ２つの物理系（u，d）間において、一方のエネルギー状態を低エネルギー状態にし、他方のエネルギー状態を高エネルギー状態に遷移させる操作を準備する。ステップＳ２０として、複数の物理系間において、ステップ0から順次ステップを遷移させながら各ステップでの複数の物理系の各々の状態値を所定の規則下で設定し、同一の状態値を持つ物理系のペアを同一の状態値が無くなるステップに至るまで集めて集合を得る。言い換えると、ステップＳ２０では、ステップＳ１０の操作を複数の物理システムのうちの２つの物理系に適用する順序を示す、複数の物理系間のネットワーク構造（後述する図５参照）を構築する。ステップＳ３０として、その集合中の全ての物理系のペアに対して、２つの物理系（u，d）を対応させながらステップＳ１０のエネルギー状態を遷移させる操作を適用して、複数の物理系中の最小のエネルギー状態を持つ物理系を求める。言い換えれば、ステップＳ３０では、ステップＳ２０のネットワーク構造に示された順序に従って複数の物理系に対してステップＳ１０を適用して、複数の物理系中の最小のエネルギー状態を持つ物理系を求める。
【００１５】
図３を参照しながら、図２のステップＳ１０のエネルギー状態を遷移させる操作について詳細に説明する。図３は、本発明の処理方法の一実施態様のエネルギー状態に遷移させる操作（図２のステップＳ１０）の概念図である。最初に、二つの物理系（u，d）に下記（１）で示す同じ量子状態を初期状態として準備する。
【００１６】
【数１】
2018190064.tif 000067
この時点で、uとdは下記（２）で示す同じエネルギーの期待値を持っている。
【００１７】
【数２】
2018190064.tif 000068
後のため、（１）の量子状態におけるエネルギーの分散を下記の式（３）で与えておく。
【００１８】
【数３】
2018190064.tif 000069
＜第１の操作＞として、uの量子状態を下記（４）で示すハミルトニアンを用いて時間τ（＞0）の間時間発展させる。図３の符号１のブロックはこの第１の操作を示している。
【００１９】
【数４】
2018190064.tif 000070
＜第２の操作＞として、uとdの間で量子スワッピング操作を時間Δt（＞0）の間実行する。図３の符号２のブロックはこの第２の操作２を示している。
【００２０】
＜第３の操作＞として、uの量子状態を反転した下記（５）で示すハミルトニアンを用いて時間τ（＞0）の間時間発展させる。図３の符号３のブロックはこの第３の操作３を示している。
【００２１】
【数５】
2018190064.tif 000071
第１〜第３の一連の操作後のuとdの量子状態は、操作によって規定される量子力学的時間発展の結果、τとΔtの一次までの近似の範囲で、uの量子状態は下記の式（６）で表すことができ、dの量子状態は下記の式（７）で表すことができる。
【００２２】
【数６】
2018190064.tif 000072
【００２３】
【数７】
2018190064.tif 000073
ここで、下記の非線形方程式（８）の解（９）を考えると、
【００２４】
【数８】
2018190064.tif 000074
【００２５】
【数９】
2018190064.tif 000075
τとΔtの一次までの近似の範囲で、下記の式（１０）、（１１）が成立していることがわかる。
【００２６】
【数１０】
2018190064.tif 000076
【００２７】
【数１１】
2018190064.tif 000077
上記の（９）で与えられる状態における下記（１２）のエネルギーの期待値は、tについて単調減少である。
【００２８】
【数１２】
2018190064.tif 000078
第１〜第３の操作後の状態におけるエネルギーの期待値は、uについては下記の式（１３）となり、初期状態における期待値よりもΔEτΔtだけ高くなる。
【００２９】
【数１３】
2018190064.tif 000079
一方dについては下記の式（１４）となり、初期状態における期待値よりもΔEτΔtだけ低いものとなる。
【００３０】
【数１４】
2018190064.tif 000080
以上から、第１から第３までの一連の操作により、uはエネルギーの高い状態に、dはエネルギーの低い状態に遷移していることがわかる。
【００３１】
次に、図４〜図６を参照しながら図２のステップＳ２０、Ｓ３０について詳細に説明する。言い換えれば、図２のステップＳ１０の方法を複数の物理系間に適用することにより離散最適化問題を解くための量子計算機を構成するための処理方法を説明する。図４は、図３の概念図の略式図である。図４において、黒丸４と白丸５が、図３の第１の操作１〜第３の操作３に対応する略式記述である。図５は、本発明の処理方法の一実施態様の集合を得るための即ち複数の物理系間のネットワーク構造を構築するステップＳ２０及び複数の物理系中の最小のエネルギー状態を持つ物理系を求めるステップＳ３０を説明するために用いる図である。図５には、図４の略式記述（黒丸４と白丸５）を用いて複数の物理系の状態を表示している。図６は、図５に示したネットワーク構造中の全ての物理系のペアに対して、２つの物理系（u，d）を対応させてステップＳ１０の操作を適用し、複数の物理系中の最小のエネルギー状態を持つ物理系を求めた場合（図５）のエネルギーの期待値の時間発展を示す図である。
【００３２】
mを整数として、2m個の物理系を考える。これらの複数の物理系の間のネットワーク構造を以下の手順で構築する。図５ではm＝4（物理系1〜物理系8）の場合を示している。
【００３３】
(1) 0から始まる非負の整数stepを導入する。図５と図６では、step＝0を初期状態とし、stepが順次１増える状態遷移を示している。
【００３４】
(2) j番目の物理系に以下の規則で決まる整数ｓj(step)を導入する。
【００３５】
(2-1) ｓj(0)はすべての物理系jについて0とする。
【００３６】
(2-2) j＜j’であるすべての物理系jと物理系j’について、ｓj(step)＝ｓj'(step)であれば物理系jと物理系j’をペアにする。図５では、黒丸と白丸を縦方向で結ぶが１つの線が１つのペアを示している。例えば、step＝2の物理系1と3ではｓ1(2)＝ｓ3(2)＝-1となり物理系1と3はペアとなる。同様に、step＝7のシステム4と7ではｓ4(7)＝ｓ7(7)＝+2となり物理系4と7はペアとなる。一度ペアとなった物理系jと物理系j’をのぞいて、可能な限りこのようなペアを集める。
【００３７】
(2-3) 上記で構成した物理系のペアを要素とする集合をΩ(step)とする。
【００３８】
(2-4) Ω(step)の中に現れる物理系jと物理系j’について、ｓj(step+1)とｓj'(step+1)を下記の式（１５）、（１６）のように定義をする。
【００３９】
【数１５】
2018190064.tif 000081
【００４０】
【数１６】
2018190064.tif 000082
図５では、例えば、step＝5の物理系3と6のペアにおいて、ｓ3(6)＝ｓ3(5)-1＝-1、ｓ6(6)＝ｓ6(5)+1＝0とする。他のペアも同様である。
【００４１】
(2-5) Ω(step)の中に現れないjについて下記の式（１７）の定義をする。
【００４２】
【数１７】
2018190064.tif 000083
図５では、例えば、物理系1のstep＝4からstep＝7において、ｓ1(7)＝ｓ1(6)＝ｓ1(5)＝ｓ1(4) ｓ1(3)＝-3とする。他も同様である。
【００４３】
(2-6) step+1をstepとして上記の(2-2)に戻り、Ω(step)が空集合となるまでこれを繰り返す。
【００４４】
(2-7) Ω(step)が空集合になるstepから1を引いたものをstep*と定義する。図５では、Ω(step)が空集合になるstep＝12（終状態）から1を引いたstep＝11がstep*となる。このとき下記（１８）を複数の物理系間のネットワーク構造と呼ぶ。このネットワーク構造（１８）は、最小固有状態を求めたいハミルトニアンHとは独立に決定できることが特徴である。
【００４５】
【数１８】
2018190064.tif 000084
また、このネットワークの構成法より各jにおけるｓj(step*)の値は下記の式（１９）で求めることができる。
【００４６】
【数１９】
2018190064.tif 000085
図５では、例えば、物理系4において、ｓ4(step*)＝ｓ4(11)＝j-m-1＝4-4-1＝-1となり、物理系8において、ｓ8(step*)＝ｓ8(11)＝j-m＝8-4＝+4となる。
【００４７】
上記のネットワーク構造と、図２のステップＳ１０のエネルギー状態を遷移させる操作（同じ量子状態を持つ２つの物理システム間でのエネルギー交換方法）を用いて、量子状態を次のように時間発展させる。
【００４８】
(1) 2m個の物理系に同じ量子状態を初期状態として準備する。
【００４９】
(2) step＝0とする。
【００５０】
(3) 集合Ω(step)に含まれる全ての物理系のペア[j，j’]（j＜j’であることに注意）に対し、物理系jを図２のステップＳ１０（図３）における物理系uに、物理系j’を物理系dにそれぞれ対応させ、ステップＳ１０のエネルギー状態を遷移させる操作を適用する。
【００５１】
(4) step+1を新たにstepとして(3)に戻り、step＝step*に到達するまで繰り返す。
【００５２】
このとき、上記の式（１０）と（１１）が繰り返し適用され、各物理系jにおける各stepの状態は、式（８）の解（９）を使って、τとΔtの一次までの近似の範囲で下記の（２０）で表される。
【００５３】
【数２０】
2018190064.tif 000086
このときのエネルギー期待値を厳密に計算した結果が、図６のエネルギーの期待値の時間発展を示す図である。図６において、破線７で囲まれる１つの領域がエネルギーの期待値を表し、白黒の濃淡がエネルギーの期待値の大小を表し、色が濃くなる程エネルギーの期待値が小さくなることを示している。図６は図５のm＝4の物理系（システム）に対応しているので、物理系８のstep＝11においてエネルギーの期待値が最小となっていることがわかる。
【００５４】
step＝step*では、式（１９と式（２０）および式（１２）がtについて単調減少であることより、各物理系jにおける状態でのエネルギーの期待値はjについて単調減少となる。その中でも特に、j＝2mの物理系（図５の例では物理系8）では、下記（２１）の最もエネルギーの期待値の低い状態が上記した一連の操作によって規定される量子力学的時間発展の結果、実現する。
【００５５】
【数２１】
2018190064.tif 000087
［実施例１］
実施例１として、図２のステップＳ１０の方法（操作）をジョセフソン接合を用いた超伝導回路（「CJJ-rf-SQUID」、Physical Review B 80,052506,2009）に適用した場合の実装例を以下に示す。図７は、その実装例（構成例）を示す図である。図７では、二つの量子ビット1，2の例を示している。物理系u，dにおいて、量子ビット1，2を構成する超伝導ループ１０は、２つのジョセフソン接合（×）を含むミニループ１１を含む。超伝導ループ１０の各々は、同様な超伝導ループ同士が相互インダクタンスを介して磁気的に接合する。なお、以下の説明では、より一般的に二つの量子ビットi，jを想定した場合について説明する。
【００５６】
CJJ-rf-SQUID系では、二つの量子ビットi，jの間に下記の式（２２）の形の相互作用を形成することができる。
【００５７】
【数２２】
2018190064.tif 000088
ただし、式（２２）中の下記（２３）の各係数は整数の値を取る時間の関数である。図８は、図７の実施例の制御シーケンス、すなわち、下記（２３）の各係数の値（-1，0，+1）の時間遷移を示す図である。
【００５８】
【数２３】
2018190064.tif 000089
さらに、下記（２４）の各係数は、量子ビットiのパウリ行列とする。
【００５９】
【数２４】
2018190064.tif 000090
上記の式（２２）の相互作用が実現された量子ビットの集合を考える。これらの量子ビットの集合を２つに分けて、１つを物理系u、残りを物理系dに対応させる。このとき、物理系uに属する量子ビットiのラベルを（i，u）とし、同様に物理系dに属する量子ビットiのラベルを（i，d）とする。すなわち、これらの量子ビット間の相互作用は下記の式（２５）のように表される。
【００６０】
【数２５】
2018190064.tif 000091
このとき、量子アニーリング計算の場合と同様に、t＜0において数（２５）の相互作用において、下記の式（２６）を導入し、かつ、他の係数を0に設定して初期状態（図８のt＜0の範囲）を用意する。
【００６１】
【数２６】
2018190064.tif 000092
上記した第１の操作に対応して、式（２５）中の物理系uを構成する量子ビット間の相互作用を用いて、量子アニーリング計算の場合と同様に、式（４）のハミルトニアンを下記の式（２７）のように実現する。
【００６２】
【数２７】
2018190064.tif 000093
すなわち、下記の式（２８）及び（２９）を時間τの間設定する（図８の時間τの間）ことで、第１の操作が完了する。
【００６３】
【数２８】
2018190064.tif 000094
【００６４】
【数２９】
2018190064.tif 000095
上記した第２の操作に対応して、スワッピングの操作を行う。スワッピングは式（２５）中の物理系uと物理系dを構成する量子ビット間に、下記の式（３０）の相互作用を構成し、時間Δtの間設定することで第２の操作が完了する。
【００６５】
【数３０】
2018190064.tif 000096
しかし、式（３０）の相互作用は式（２５）の形をした相互作用では直接実現することができない。そこで、下記の式（３１）〜（３４）
【００６６】
【数３１】
2018190064.tif 000097
【００６７】
【数３２】
2018190064.tif 000098
【００６８】
【数３３】
2018190064.tif 000099
【００６９】
【数３４】
2018190064.tif 000100
に着目すると、式（６）や式（７）を成立させるΔtの１次までの範囲では、下記の(1)〜(3)の操作を順に行うことで、間接的に第２の操作を実装することができる。
【００７０】
(1)式（３２）の操作：
式（２５）において、下記の式（３５）として、残りの係数は全て0を時間Δtの間設定する（図８の最初のΔtの間）。これにより式（３１）の操作が完了する。
【００７１】
【数３５】
2018190064.tif 000101
(2)式（３３）の操作：
式（２５）において、下記の式（３６）として、残りの係数は全て０を時間π/2の間設定する（図８の最初のπ/2の間）。その後、式（３５）として残りの係数は全て0を時間Δtの間設定する（図８の２番目のΔtの間）。
【００７２】
【数３６】
2018190064.tif 000102
さらに、下記の式（３７）として、残りの係数は全て0を時間π/2の間設定する（図８の２番目のπ/2の間）。これにより式（３３）の操作が完了する。
【００７３】
【数３７】
2018190064.tif 000103
(3)式（３４）の操作：
式（２５）において、下記の式（３８）として、残りの係数は全て０を時間π/2の間設定する（図８の３番目のπ/2の間）。
【００７４】
【数３８】
2018190064.tif 000104
その後、式（３６）として残りの係数を全て0に設定し時間π/2を経過させ（図８の４番目のπ/2の間）、続いて式（３５）として残りの係数は全て0を時間Δtの間設定する（図８の３番目のΔtの間）。さらに、式（３７）として、残りの係数を全て0として時間π/2を経過後（図８の５番目のπ/2の間）、さらに下記の式（３９）として、残りの係数の全て0を時間π/2の間設定する（図８の最後のπ/2の間）。
【００７５】
【数３９】
2018190064.tif 000105
これにより式（３４）の操作が完了する。以上の一連の(1)，(2)及び(3)の操作より、第２の操作が完了する。
【００７６】
上記した第３の操作に対応して、式（２５）中の物理系uを構成する量子ビット間の相互作用を用いて、式（５）の相互作用を時間間隔τの間設定する。これは式（２７）を反転させたものであるから、式（２８）に対応して下記の式（４０）を設定すればよい。これにより、第３の操作が完了する。
【００７７】
【数４０】
2018190064.tif 000106
以上により、実装されるCJJ-rf-SQUIDによる図２のステップＳ１０の方法（操作）を2m個の物理系に繰り返して適用して量子計算に利用するには、図４〜図６を参照しながら上述した一連の処理を用いることにより利用（実装）することができる。
［実施例２］
次に、実施例２として、計算ステップ数および必要な量子ビット数の評価を行うために、本発明を探索空間2nの探索問題に適用した場合について説明する。最初に、探索問題に対応する下記の式（４１）のハミルトニアンを式（８）の非線形方程式に適用する。
【００７８】
【数４１】
2018190064.tif 000107
時刻tにおける下記の式（４２）の正解確率を計算すると解析解が存在して下記の式（４３）が得られる。図９は、式（４３）のP(t)をプロットして得られた、非線形方程式による探索問題の正解確率P(t)の時間的挙動のn依存性を示す図である。
【００７９】
【数４２】
2018190064.tif 000108
【００８０】
【数４３】
2018190064.tif 000109
ここで、解空間の大きさが下記の（４４）であって、初期の正解確率が下記の式（４５）となる場合を考える。
【００８１】
【数４４】
2018190064.tif 000110
【００８２】
【数４５】
2018190064.tif 000111
このとき、下記の式（４６）を満たす時刻tをt*と定義すると、t*は下記の式（４７）として得られる。図１０は、式（４７）のt*をプロットしたもので、グラフＡは正解確率P(t)≧0.9となる時間t*のn依存性を示す。
【００８３】
【数４６】
2018190064.tif 000112
【００８４】
【数４７】
2018190064.tif 000113
ここで本発明によって得られる状態が式（２１）であることより、式（４７）のt*に対応するmをm*とすれば、下記の式（４８）が得られる。
【００８５】
【数４８】
2018190064.tif 000114
step*とmの関係はハミルトニアン（H）の詳細によらず、下記の式（４９）であることに注目すると、m*で決まるstep*は下記の式（５０）となり、nの２次（n2）であることがわかる。
【００８６】
【数４９】
2018190064.tif 000115
【００８７】
【数５０】
2018190064.tif 000116
また、式（４３）の問題を表現するのに必要な１システムあたりの量子ビット数はn個であるから、2m*システム全体では下記の式（５１）となる。
【００８８】
【数５１】
2018190064.tif 000117
さらに、与えられたmに対し必要な量子操作の数C(m)は下記の式（５２）であることから、上記の探索問題に適用した場合には下記の式（５３）となる。図１１は、式（５０）をプロットして得られるstep*及び式（５３）をプロットして得られる量子操作の数C(m)のm依存性を示す図である。
【００８９】
【数５２】
2018190064.tif 000118
【００９０】
【数５３】
2018190064.tif 000119
上記した探索空間2nの探索問題に従来の量子アニーリング計算、およびゲート式の量子計算探索問題に適用した場合、（量子を使わない計算に比べて小さくはなるものの）その計算ステップ数は2n/2となり、nに対して指数関数的に振る舞うことが知られている。一方、本発明による計算ステップ数（step*）は、上述したように、nに対して高々多項式的（例えばn2）に抑えられる。同様に、計算に必要な量子ビットの数は、従来の計算手法がnに比例する程度だったのに対し、本発明ではn2に比例することになるが、計算ステップ数と必要な量子操作数（C(m)）がnに対して高々多項式的なサイズ（例えばn3）で問題を解くことができる。
【００９１】
本発明の実施形態について、図を参照しながら説明をした。しかし、本発明はこれらの実施形態に限られるものではない。さらに、本発明はその趣旨を逸脱しない範囲で当業者の知識に基づき種々なる改良、修正、変形を加えた態様で実施できるものである。
【符号の説明】
【００９２】
１：第１の操作
２：第２の操作
３：第３の操作
４、５：第１〜第３の操作の略式記述
７：エネルギーの期待値
１０：超伝導ループ
１１：２つのジョセフソン接合を含むミニループ
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
離散最適化問題を解くために量子アニーリング計算を行うための処理方法であって、
（ａ）同一の量子状態を持つ２つの物理系（u，d）間において、一方のエネルギー状態を低エネルギー状態にし、他方のエネルギー状態を高エネルギー状態に遷移させる操作を準備するステップと、
（ｂ）ステップ（ａ）の操作を複数の物理システムのうちの２つの物理系に適用する順序を示す、複数の物理系間のネットワーク構造を構築するステップと、
（ｃ）前記ステップ（ｂ）の前記ネットワーク構造に示された前記順序に従って前記複数の物理系に対して前記ステップ（ａ）の操作を適用して、前記複数の物理系中の最小のエネルギー状態を持つ物理系を求めるステップと、を含む処理方法。
【請求項２】
前記ステップ（ａ）は、
（ａ１）前記２つの物理系（u，d）に初期状態として同一の量子状態を与えるステップと、
（ａ２）物理系uの量子状態をハミルトニアン（H）を用いて時間τ（＞0）の間時間発展させるステップと、
（ａ３）物理系uと物理系dの間で量子スワッピング操作を時間Δt（＞0）の間行うステップと、
（ａ４）物理系uの量子状態を反転したハミルトニアン（-H）を用いて時間τ（＞0）の間時間発展させるステップと、を含む請求項１に記載の処理方法。
【請求項３】
前記ステップ（ｂ）は、
（ｂ１）2m個（ｍは正の整数）の物理系において、j番目（jは2m-1以下の正の整数）の物理系jの状態値をｓj(step)とし、全ての物理系ｊについてｓj(0)＝0にするステップと、
（ｂ２）j＜j’（j，j’は２ｍ以下の正の整数）である全ての物理系jと物理系j’から、ｓj(step)＝ｓj'(step)となる物理系jと物理系j’のペアを選択するステップと、
（ｂ３）複数の前記物理系jと物理系j’のペアを集めて集合Ω(step)とするステップと、
（ｂ４）前記集合Ω(step)に含まれる前記物理系jと物理系j’について、ｓj(step+1)＝ｓj(step)-1、ｓj'(step+1)＝ｓj'(step)+1とするステップと、
（ｂ５）前記集合Ω(step)に含まれない前記物理系jについて、ｓj(step+1)＝ｓj(step)とし、step+1をstepとするステップと、
（ｂ６）ステップ（ｂ２）からステップ（ｂ５）までを前記集合Ω(step)が空集合になるまで繰り返すステップと、
（ｂ７）集合Ω(step)が空集合になるstepから1減算したstepをstep*とするステップと、を含んで前記ネットワーク構造を制定する請求項１または２に記載の処理方法。
【請求項４】
前記ステップ（ｃ）は、
（ｃ１）2m個の物理系に初期状態として同じ量子状態を与えるステップと、
（ｃ２）step＝0とするステップと、
（ｃ３）前記集合Ω(step)中の全ての前記物理系のペアj，j’に対して、前記物理系jを前記物理系uに対応させ、前記物理系j’を前記物理系dに対応させながら前記ステップ（ａ１）〜（ａ４）を含む操作を適用するステップと、を含む請求項３に記載の処理方法。
【請求項５】
各物理系jにおける状態値ｓj(step*)は、
ｓj(step*)＝j-m-1 (j＝1，2，・・・，m) または
ｓj(step*)＝j-m (j＝m+1，m+2，・・・，2m)
で与えられる、請求項３に記載の処理方法。
【国際調査報告】
2018190064.tif 000120
2018190064.tif 000121