量子計算とプログラムの不動点意味論

http://alohakun.blog7.fc2.com/blog-entry-321.html

関数の情報がどんどん増えていって，その単調増加列 (近似) の極限 (という用語を使ってよいのか ? ですが) で，目的の関数 (最小不動点) に収束する，という概念が面白かった．

せっかくなので反応しておくと、Keye Martinさんという人が2004年1月頃にPennへ来たときに

古典計算機では計算の反復ないし再帰の回数xは自然数で、xが増加すれば情報量も増加する。量子計算機では、xが実数や複素数になって「√ｎ回の反復」「ｉ回の再帰」などが実現でき、xと情報量との関係は放物線などになる。

みたいな不動点意味論の話をしていてビビリました。この↑説明はスーパー劣化コピーですが、talkのアナウンスから引用すると

`Entropy' is to quantum state as `length' is to list

とか

Grover's algorithm for quantum searching is like a projectile fired into the air which reaches its zenith and then falls back to the ground -- the amount of time required for the projectile to reach its maximum height is the complexity of the algorithm.

みたいな（projectile = 放物線、zenith = 頂点）。

しかも、（僕にはまったくわかりませんが）その不動点意味論で量子力学の計算も簡単になり、Physical Review Lettersにも論文が採録されたとか（追記：あれ、それらしい論文がないな…??）。いや、まったく理解していないのでリンクしか情報のないエントリですみませんが。