Variational Quantum Algorithmによる幾何学的最適化

　量子コンピューティングによって、「アメーバ」のような形の閉曲線に内接する正五角形を見つけ出そう！（→英語版はこちらです。）

🟠閉曲線の内接正五角形を探す

　どんな単純閉曲線の上にも、正方形の4頂点となる点の組が存在することが（一部の例外を除いて）、すでに証明されています。これは内接正方形問題として知られています。では、正方形ではなく、正五角形（およびそれ以上の角数の正多角形）は必ず存在するのか？実は、それは未だ数学的に明らかにされていないようです。ここでは、量子コンピューティングの手法によって、具体的にそのような５角形を探します。もちろん、数学的証明ではなく、数値的に一定の誤差の範囲内でそれを求めます。

🟠変分量子アルゴリズム（VQA）の応用

　今回は、量子・古典ハイブリッドアルゴリズムであるVQA (Variational Quantum Algorithm)を採用します。概要は以下のとおりです。

・Ansatz (量子回路): 

　5つの頂点を表す変数（その値は、曲線を一周する 0〜2π）を、量子回路の回転ゲート（Ryなど）のパラメータとします。

・コスト関数 (古典側): 

　5辺の長さが等しいこと（隣接する点間の距離の分散を最小化）と、5本の対角線の長さが等しいこと（対角線距離の分散を最小化）を表現します。

・最適化: 

　量子回路側からの勾配を要求しない、古典オプティマイザ（COBYLA等）を用いて、量子回路の期待値が最小（正五角形にできるだけ近づくよう）になるようパラメータを更新します。

・実装：

　Qiskit 2.xの Sampler を使い、量子回路の状態を座標に直接対応させ、Ansatzにより、5つの量子ビットの回転角θiを、曲線上のパラメータ tiとみなします。そして、古典側で、Samplerでの実測から、期待値の近似値、すなわち、得られた準位（状態）から現在の幾何学的配置を評価します。

　VQA以外に、QAOAという方法もあります。QAOAの方は曲線上の点を離散化して、そのうちの最適な５点の組み合わせを求めるのに対して、今回のVQAは「連続的な探索」に特徴があります。さらに詳しいことは、別記事で書きたいと思います。

🟠VQAの動作の可視化

　最初に、下図のアニメーションをご覧ください。閉曲線がアメーバのように動き回る中で、VQAは正五角形を追い続けている様子が分かります。これを眺めていると、量子アルゴリズムは、化学計算や金融最適化だけでなく、こうした純粋幾何学の探索においても強力なツールとなるように思えます。

　さらに、閉曲線を一つ固定して、VQAがどのように正五角形を探索しているかを見ることにします。以下のアニメーションがその一例です。

🟠VQAが求めてた正五角形の精度

　以下の図に、VQAで求めた、正三角形、正方形、正五角形の精度を示します。角数が増えると、次第に高精度を求めることが難しくなって行きます。それでも、左下の正五角形の場合、かなり高い精度になっています。具体的には、５つの辺の長さの平均値=1.096、標準偏差=0.00016でした。また、５つの対角線の長さについても、平均値=1.773、標準偏差=0.00043です。

🟠量子コンピュータ実機を使う場合

　今回は、Qiskitによるシミュレータでの実行でした。実機でもやってみたいのですが、無料ユーザ（Open Plan）はsession機能を使えないので、上記のような量子/古典ハイブリッドジョブをそのまま投入することができません。そのため、かなりの部分をシミュレータで実行して、それを利用して、最後の１回か２回程度の評価をジョブとして実機に投入する、などの工夫が必要になります。この件も、後日報告したいと思います。

Geometric Optimization with a Variational Quantum Algorithm

Let’s use quantum computing to find a regular pentagon inscribed in an “amoeba-shaped” closed curve! （→日本語版はこちらです）

🟠 Searching for an Inscribed Regular Pentagon

It has already been proven (with some exceptions) that for any simple closed curve, there exists a set of four points that form a square. This is known as the inscribed square problem. But what about a regular pentagon—or regular polygons with even more sides? Do they always exist on any closed curve? In fact, this question has not yet been fully resolved in mathematics.

    In this article, instead of pursuing a formal proof, we take a computational approach. Using quantum computing techniques, we attempt to numerically find such a pentagon—within a certain tolerance of error.

🟠 Applying a Variational Quantum Algorithm (VQA)

We use a hybrid quantum-classical method known as a Variational Quantum Algorithm (VQA). The basic idea is as follows:

Ansatz (quantum circuit):

We represent the five vertices of the pentagon by parameters 𝑡𝑖∈[0,2π], which correspond to positions along the curve. These parameters are encoded as rotation angles (e.g., 𝑅𝑦 gates) in a quantum circuit.

Cost function (classical side):

We define a function that enforces the geometry of a regular pentagon:

All five edges should have equal length (minimize the variance of distances between adjacent points)

All five diagonals should also have equal length (minimize the variance of diagonal distances)

Optimization:

A gradient-free classical optimizer (such as COBYLA) updates the circuit parameters to minimize the cost function—i.e., to make the shape as close as possible to a regular pentagon.

Implementation:

Using the Qiskit 2.x Sampler, we interpret the quantum circuit state as geometric coordinates. The Ansatz produces five angles 𝜃𝑖, which are treated as curve parameters 𝑡𝑖. From measurement results, we estimate expectation values and evaluate the current geometric configuration on the classical side.

🟠 Why VQA (and not QAOA)?

Another approach would be QAOA (Quantum Approximate Optimization Algorithm). QAOA would discretize the curve and search for the best combination of five points. In contrast, VQA performs a continuous search over the curve. This continuous nature is a key advantage of VQA in this setting. I plan to discuss this distinction in more detail in a future article.

🟠 Visualizing the VQA Process

First, take a look at the animation below.

    As the closed curve moves and deforms like an amoeba, the VQA continuously tracks and updates the candidate pentagon. Watching this process, one gets the impression that quantum algorithms are not only useful for chemistry or finance, but also for exploring problems in pure geometry.

    Next, we fix a single closed curve and observe how the VQA searches for a regular pentagon. The following animation shows a representative example.

🟠 Accuracy of the Discovered Pentagon

The figure below shows the accuracy achieved by VQA for an equilateral triangle, square, and regular pentagon.

    As the number of sides increases, achieving high precision becomes more difficult. Nevertheless, the pentagon case still reaches a high level of accuracy. 

For the edges:

Mean edge length: 1.096

Standard deviation: 0.00016

For the diagonals:

Mean length: 1.773

Standard deviation: 0.00043

    These results indicate that the obtained shape is very close to a true regular pentagon.

🟠 Running on Real Quantum Hardware

In this work, all experiments were performed using the Qiskit simulator. Running this on real quantum hardware is more challenging. For example, under the free-tier Open Plan, session-based execution is not available. This makes it difficult to directly run hybrid quantum-classical loops like VQA. So, a practical workaround is:

Perform most of the optimization on a simulator, Then submit only the final few evaluations as jobs to real hardware. I plan to report on this approach in a future post.

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