Finding an inscribed rectangle using VQA (Variational Quantum Algorithm)

Finding an inscribed rectangle using VQA (Variational Quantum Algorithm)

量子変分法で閉曲線の内接長方形を見つける

Abstract: For any simple closed curve, it is known that four points on the curve can form (at least one) rectangle. This was proven by Herbert Vaughan (1977). In this article, we numerically searched for such an inscribed rectangle using a Variational Quantum Algorithm (VQA). In many cases, a nearly perfect rectangle was found with only about 50 calls to the Ansatz.

     However, this does not mean that quantum methods are superior to classical methods. In fact, this problem can be solved classically as well, and it is merely an example problem to help understand quantum methods.

【要旨】どんな単純閉曲線においても、その上の４点で（少なくとも一つの）長方形を作れることが分かっている。これは、Herbert Vaughan（1977年）によって証明された。ここでは、そのような内接長方形を、量子変分法で求めた。多くの場合、Ansatzの呼び出し回数50回程度で、ほぼ完璧な長方形を見つけることができた。だが、これをもって、量子的方法が古典的方法に勝るとは言えない。実際、この問題は、古典的にも十分解けるものであり、量子方法を理解するための例題に過ぎない。

🟢An Intuitive Picture of the Existence Proof

Consider a chord AB on a simple closed curve (identifying AB with BA). As illustrated in Fig.1, each such chord corresponds one-to-one to a point on a Möbius strip (right panel), while the original closed curve corresponds to the boundary of the strip. Next, we construct a surface from these chords. As shown in Fig.2 (upper right), for each chord we take its midpoint and place a point above it whose height equals the length of the chord. Repeating this for all chords produces a surface in three-dimensional space. Points on this surface are again in one-to-one correspondence with points on the Möbius strip.

     Now consider mapping the boundary of the Möbius strip onto the base of this surface (i.e., the original curve). Due to the topology of the Möbius strip, it is unavoidable that two distinct points on the strip coincide under this mapping. Consequently, two points on the constructed surface (for example, the red and blue triangles in the figure) must also coincide somewhere. At such a coincidence, the corresponding four points on the curve form a rectangle.

     Although the full proof requires more rigor, this construction captures the essential idea behind the existence of an inscribed rectangle. The reference [1] and the video[2] were particularly helpful in understanding this argument.

🟢内接長方形が存在することの証明のイメージ

　Fig.1の左図の線分AB（線分BAと同一視する）は、右側のメビウスの帯上の点と1対１に対応づけられる。閉曲線はメビウスの帯の縁に対応する。

　さらに、Fig.2の右上の図は、そのような線分の中点において、その上方向に、高さが線分の長さとなる点を描いている。そのようにしてできる曲面上の点と、メビウスの帯の点がまた１対１に対応する。

　メビウスの縁の線を、この曲面の底辺（すなわち元の曲線）に当てはめる際、メビウス上のどれかの２点はどうしても重なってしまう。すなわち、曲面上の点（赤い三角と青い三角）も、どこかで必ず重なる。その場合に長方形を形成する。詳細は略すが、これが長方形存在証明のポイントである。こちらの資料[1]とこちらのビデオ[2]はとても参考になった。

🟢Finding an Inscribed Rectangle via a Variational Quantum Algorithm

Let us now attempt to find such rectangles using quantum computing. At first, one might consider applying Grover’s search. However, constructing a suitable Oracle that detects rectangles within a quantum circuit is currently impractical. Instead, we adopt a Variational Quantum Algorithm (VQA). This method does not evaluate whether a candidate is a solution, as in Grover's algorithm; instead, it guides the quantum state toward the configuration that is closest to a rectangle.

     A necessary and sufficient condition for two chords to form the diagonals of a rectangle is:(1)The two chords have equal length, and (2)Their midpoints coincide.

     We encode these conditions into a cost function and use VQA to minimize it. Some examples of a rectangle obtained via VQA are shown in Fig.3. The optimization method and Ansatz used in the computation are indicated at the top of the figure. Remarkably, with only about 50 Ansatz evaluations, the algorithm finds an almost perfect rectangle. 

🟢量子変分法で内接長方形を見つける

　任意の単純閉曲線において、そのような長方形を、量子コンピューティングで見つけよう。まず最初に、Groverの探索で見つけることを考えた。しかし、そのためのOracleを量子回路で作ることは、現状では困難と判断した。そこで、別の方法として、VQA（Variational Quantum Algoritm）を用いた。この方法は、Groverのように「解であるか否か」を判定するのではなく、「最も長方形に近い状態」に量子状態をガイドする。２つの線分が長方形を成すための必要十分条件は、(1)対角線となる線分の長さが一致し、かつ、(2)対角線の中点同士が重なることである。

　VQAで求めた長方形の例をFig.3に示した。VQAで使う最適化方法や、Ansatzの情報は図の上部に示した。Ansatzの呼び出しは、わずか50回程度で、ほぼ完璧な長方形が見つかった。

The animation showing how the rectangle is found is available here.

長方形が見つかるまでのアニメーションはこちらにあります。

References:

[1] https://www.3blue1brown.com/lessons/inscribed-rect-v2

[2] https://www.youtube.com/watch?v=AmgkSdhK4K8

ショアの素因数分解に親しむためのスマホアプリ

 【要旨】著名なShor's Factoring Algorithmの本格的な実行には、大規模な誤り耐性量子コンピュータが必要であり、現時点の量子コンピュータでは、その実現がほとんど望めない。だが、理想的な量子コンピュータが出現した時には、このアルゴリズムが与えるインパクトは、サイバーセキュリティ上、非常に大きいと考えられている。ここでは、小さな整数（２つの素数の積）に対して、このショアのアルゴリズムを適用するためのスマホアプリを作成した。それによって、Shor'sに親しみを持ち、理解を深めることができた。

🔴Shor's Factoringの概要
　ショアのアルゴリズムの解説は多数存在するが、私は、Fig.1に示したElucyda氏によるYoutubeビデオに注目した。約25分で、白板１枚だけを使って、鮮明に手書きしながら、分かりやすくstep by stepで説明している。これは上手、素晴らしい！

　難解と言われるショアのアルゴリムだが、概要はこの１枚（８行）である。２つの素数の積である整数Nを逆に素因数分解するのである。小さなNであれば、この図の手順に従って、パソコンなどで独自にプログラムを作って確かめることは難しくない。ただし、注意すべきは、Fig.1の赤枠で囲った部分、"Find MIN r>0 such that a^r=1 mod N"である。これは、因数分解したい整数Nに対して、別のある整数aをもってきた時に、a^r = 1 mod Nとなる最小の整数r（位数）を求めるのである。これは、a^r mod Nの値の繰り返しの最小周期を求めることに他ならない。

　非常に大きなNに対しては、この位数探索がショアのアルゴリズムの根幹であり、量子コンピュータの出番となるところなのである。（この記事は初級レベルに過ぎない。位数探索のための量子アルゴリズムの完全理解無しでは、中級レベル以上と言えないのである。）今回は、小さなNを想定するので、Fig.1の処理全体をスマホのアプリとして実現した。ショアのアルゴリズムに親しむとともに、この後の量子プログラム作成の準備ともなる。

🔴スマホアプリの作成
　本来は、量子アルゴリズムとして上記の位数rの探索を行うのだが、ここではスマホアプリとして作るので、この部分も古典コンピュータで動く原始的な（ナイーブな）プログラムとした。Fig.2は、MIT App Inventorで作った位数計算関数である。

　注意点として、a^rの計算で、特にrの値が大きくなるとオーバーフローを起こす恐れがある。そこで、一定程度それを抑止するため、a^r mod Nの計算をダイレクトに行わずに、小さなrを使った繰り返し計算で実現している。

🔴実行結果の検討
　早速だが、このスマホアプリで、小さな整数、例えばN=247を素因数分解してみる。（このNは２つの素数p=19とq=13の積として与えた。）成功した２例をFig.3に示す。このうち、図(a)は、Fig.1においてランダムに設定した整数aが、たまたまGCD(q, a)>1となったので、因数分解はすぐに完了した。Fig.1のCase1に該当する。また、図(b)の方はFig.1のCase2に該当し、正常に因数分解ができた。

　一方、失敗した場合をFig.4に示す。このうち図(a)は、当方で適宜設定した、ランダムな整数aと求める位数rの値の制限範囲内においては、値rの探索に失敗した場合である。また、図(b)の方は、ランダムな整数aと位数rは設定できたものの、素因数分解に失敗したケースである。これは、Fig.1でのCase3に該当する。Shorのアルゴリズムは、このように、確率的（発見的）に成功するものである。ただし、その成功確率はかなり高いことが分かっている。

🔴なぜこのアルゴリズムで素因数分解できるのか
　本記事は、なぜショアのアルゴリズムで因数分解できるのか、ではなく、どのように働いているのかを中心に述べている。とはいえ、whyについても以下にポイントを簡単に述べてみたい。意外かもしれないが、その一つは、以下の計算式（中学校数学）にあった。

a² - 1 = (a + 1)(a - 1)

　これを使うと、Fig.1の説明にある、a^r-1 = 0 mod Nは、(a^r/2 + 1)(a^r/2 - 1) = 0 mod Nとなる。すなわち、=の左辺は、Nで割り切れる。だから、Nを構成する一つの素数は左辺のどちらかの因子を割り切る。このことから、GCD(N, a^r/2 + 1)とGCD(N, a^r/2 -1)がNの素因数となるはずである。Fig.3(b)の場合（a = 30, r = 6）を計算してみると、以下の通り

確かにそうなる。

     GCD(30^6/2+1, 247) = GCD(27001, 247) = 13

     GCD(30^6/2 -1, 247) = GCD(26999, 247) = 19

　ところで、根幹をなす位数rを見つけるアルゴリズム（finding the order）は、すでにこことここに述べた（精密な）量子位相推定とほぼ同等であることが分かっている。このことからも、Shor'sアルゴリズムへの親しみは増すのである。