Finding an inscribed rectangle using VQA (Variational Quantum Algorithm) No.2

This article is a continuation of the previous article.

We've created an animation showing how the inscribed rectangle is found. Enjoy!

Initially, it's a quadrilateral with a blue frame, but as it approaches a rectangle, the frame changes to orange. Finally, when it reaches a nearly perfect rectangle, the frame turns red.

この記事は、前回の記事の続編です。内接長方形が見つかるまでのアニメーションを作りました。おたのしみください！最初は青色枠の四辺形ですが、長方形に近づくとオレンジ色の枠になります。そして、最終的にほぼ完璧な長方形に至った場合は、赤色の枠になります。

Initial Guess

In Progress

Final Result

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

量子コンピューティングの学びに関する短い講演

　神奈川工科大学で「ITを活用した教育研究シンポジウム」（2026-3-18）が開催されました。今回は、第20回という記念すべきイベントとなりました。先進AIに関する、オーガナイズドセッションも設けられました。

中央左は、3Dプリンタによるロゴ（門田和雄教授ご提供）

　ここで、下図のタイトルで短い講演を行いました。量子力学100年、量子コンピューティング40年、量子クラウドサービス10年というこの時代。How Quantum Era Crept Up While You Were Busy Watching AI the Whole Year（年中AIに夢中になっている間に、量子の時代は忍び寄ってきた）という、SNS投稿もありました。私の今回の講演タイトルは、"AI時代に量子コンピューティングを学ぶ"というものです。

　大勢の方々に聴いていただき、ありがとうございました。短い時間ながら、以下のような質疑やコメントもありとても有意地でした。

-----------------------------------------------------------------

・ある種のタンパク質に「量子もつれ」の電子対が作られる研究をしている。

・数学が得意でない学生は、量子コンピューティングをどのように学ぶか。

・初心者は量子コンピュータ実機を使うことに強い関心はあるのか。

・量子カーネルによって、こんなにうまく分類できるものなのか。

-----------------------------------------------------------------

　誰かこの講演の写真を撮ってくれたかな、と思ってネットを調べたら、ここにありましたので、以下に引用させていただきます。

　この講演の練習用に作成したパワーポイントビデオは以下にあります。実講演とは若干異なりますが、大筋は変わりません。ご参考までに。

https://www.youtube.com/watch?v=LporJ_dVe-s

　以下に、いくつかのスライドを抜粋して載せます。

新刊洋書"Quantum Algorithms and Applications"に書評

　本日（2026-03-14）"量子アルゴリズムと応用"と題する分厚い専門書（洋書）が、下記の通り発売になりました。その中に、私のレビュー（書評）を載せていただきました。これだけの大著を完成させた著者のDr. Peter Y. Leeらに大いなる敬意を表したい。

書名：Quantum Algorithms and Applications

著者：Dr. Peter Y. Lee (Ph.D., Princeton University), Dr. Ran Cheng, Dr. Huiwen Ji

出版：Polaris QCI Publishing, March 2026（全630ページ）

https://polarisqci.com/qci-601-textbook

販売：Amazon（ここです）

　上記は電子版（Kindle版）です。Kindle版の先頭50ページほどは無料でダウンロードできます。紙版は、分厚くなったためか、Vol.1とVol.2の２分冊になっているので、購入する場合は注意が必要です。

謝辞にも神奈川工科大学名を載せていただきました

書評を掲載していただきました

[小生の書評]

This book begins with a review of the fundamental concepts of quantum algorithms, followed by detailed explanations of key techniques such as the Quantum Fourier Transform (QFT) and Quantum Phase Estimation (QPE). It then bridges these foundations to Shor’s factoring algorithm. After demonstrating Shor’s algorithm through concrete examples, the discussion expands into the more general framework of Hidden Subgroup Problems.

The book also highlights the importance of Hamiltonian simulation, explaining time evolution as governed by the Schrödinger equation. And Variational algorithms based on Ansatz are treated with a rigor and depth that is particularly commendable.

Unlike many CS-oriented books, this book devotes substantial space to simulations in physics and chemistry. The Hamiltonian introduced earlier plays a central role here as well. In doing so, the book provides a concrete and efficient approach to simulating nature, staying true to the vision originally envisioned by Feynman.

In addition, readers can explore modern applications such as quantum optimization and quantum machine learning. Together with the other two volumes in the Scaffolding series, this book is likely to become a definitive reference in quantum computing for researchers, engineers, and students alike.

- Yamamoto Fujio

   Professor Emeritus, Kanagawa Institute of Technology, Japan

---------  和文 ---------

　本書は、先頭部分で、量子アルゴリズムの基本概念を復習し、続けて、量子フーリエ変換（QFT）や量子位相l推定（QPE）などの重要なアルゴリズムを詳しく説明している。それらを、Shorの因数分解アルゴリズムにつなげている。Shorのアルゴリズムについては、具体例を使って詳しく説明した後、それをさらに一般化する隠れ部分群問題（Hidden Subgroup problems）にまで言及している。

　また、ハミルトニアン（Hamiltonian simulation）の重要性を示し、シュレディンガー方程式に則って、それを時間発展させる説明が含まれる。Ansatz（パラメータ付き仮説量子回路）を使った変分アルゴリズム（Variational Algorithms）も丁寧に扱われているのは素晴らしい。

　他のコンピュータサイエンス寄りのテキストにはあまり出てこないような、物理と化学のシミュレーションにも多くのページを費やしている。その前に説明されていたハミルトニアンが、ここでも、うまく機能している。これは、まさに、ファインマン（Feynman）が当初構想したような自然界のシミュレーションを効率的に実現する具体的な方法を与えてくれる。

　これ以外に、量子最適化（Quantum Optimization）や量子機械学習（Quantum Machine Learning）など、最新の応用を知ることができる。この本を含む、Scaffoldingシリーズの３冊は、研究者、技術者、学生にとって、量子コンピューティングにおける新たなバイブルとなるであろう。

Fujio Yamamoto

Professor Emeritus, Kanagawa Institute of Technology, Japan

------------------------