sparse-dense by FoYo: 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. In this article, we numerically searched for such an inscribed rectangle using a Variational Quantum Algorithm (VQA). When 1,500 sample points were prepared on the curve, a nearly perfect rectangle was found with only about 50 calls to the Ansatz.

【要旨】どんな単純閉曲線においても、その上の４点で（少なくとも一つの）長方形を作ることができる。ここでは、そのような内接長方形を、量子変分法で求めた。曲線上に1500点のサンプル点を用意した場合、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). Unlike Grover’s algorithm, which determines whether a solution exists, VQA guides the quantum state toward configurations that are “closest” to forming 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. In all cases, 1,500 sample points were taken along the curve.

Remarkably, with only about 50 Ansatz evaluations, the algorithm finds an almost perfect rectangle. For comparison, a purely classical brute-force search would, in the worst case, require examining on the order of 1500⁴（=10¹²）combinations of four points. In contrast, the VQA-based approach efficiently converges to a valid solution, making it a very promising method for this type of geometric search problem.

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

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

　VQAで求めた長方形の例をFig.3に示した。VQAで使う最適化方法や、Ansatzの情報は図の上部に示した。いずれも、曲線状に1500点のサンプル点を用意した。Ansatzの呼び出しは、わずか50回程度で、ほぼ完璧な長方形が見つかった。古典的方法で全く無作為に長方形を探すとしたら、最悪の場合、1500の4乗（=10の12乗）のオーダー組み合わせを探すことになる。それに比べると、このVQAによる方法はとても良いのではないか！