めもめも

このブログに記載の内容は個人の見解であり、必ずしも所属組織の立場、戦略、意見を代表するものではありません。

「ITエンジニアのための強化学習理論入門」が発売されます

www.amazon.co.jp

表題の書籍が技術評論社より発売されることになりました。執筆にご協力いただいた方々には、あらためてお礼を申し上げます。販売開始に先立って、「はじめに」「目次」「図表サンプル」を掲載させていただきますので、先行予約される方の参考にしていただければと思います。

はじめに

 「Q LearningとSARSAの違いを説明してください。」皆さんは、この質問に即答できるでしょうか? 本書を読めば、自信を持って答えられます! —— と、謎の宣伝文句(?)から始まりましたが、少しばかり背景を説明しておきましょう。
 2015年に『ITエンジニアのための機械学習理論入門』(技術評論社)を出版させていただいた後、驚くほどの勢いで機械学習の入門書が書店にあふれるようになりました。そしてまた、回帰モデルによる数値予測、分類モデルによる画像データの識別など、教師データを用いた機械学習モデル、いわゆる「教師あり学習」は、一般企業における活用が進みました。その一方で、エージェントが学習データを収集しながら学習処理を進める「強化学習」の利用は未だ敷居が高く、一般企業における活用は「まだこれから」という状況です。本書では、今後のスキルアップや強化学習の活用に向けた準備をしようと考える ITエンジニアの方々に向けて、強化学習のアルゴリズムを基礎から解説しています。
 動的計画法による厳密解の導出方法から始まり、ニューラルネットワークと強化学習を組み合わせた「DQN(Deep Q Network)」まで、「強化学習がなぜうまくいくのか」という基本原理を解説します。Pythonで実装したコードをGoogle Colaboratoryで実行しながら、それぞれのアルゴリズムがどのように機能するのかを「実感して理解する」ことが本書の一貫したテーマです。既存の機械学習ライブラリをブラックボックスとして用いるのではなく、具体的な動作原理が確認できるように、すべてのアルゴリズムを一から実装しています。「三目並べ」や「あるけあるけゲーム」など、シンプルな題材を用いて、エージェント同士の対戦による相互学習や、実行時の先読みによる性能向上など、より実践的なテクニックにも触れています。
 冒頭の「Q Learning」と「SARSA」は、どちらも強化学習の基礎的なアルゴリズムですが、機械学習の活用が広がるスピードを考えると、近い将来、機械学習に関わるITエンジニアの採用面接では、冒頭のような質問が「あたりまえ」になる日が近いのかも知れません。試験対策が本書の目的ではありませんが、一般的な「教師あり学習」の仕組みを学んだ上で、次のステップとして「強化学習」に取り組みたいと考える皆さんの知的好奇心を満たし、ITエンジニアとしての活動の幅を広げるきっかけが提供できれば、筆者にとってこの上ない喜びです。

目次

第1章 強化学習のゴールと課題
1.1 強化学習の考え方
1.2 実行環境のセットアップ
1.3 バンディットアルゴリズム(基本編)
1.4 バンディットアルゴリズム(応用編)

第2章 環境モデルを用いた強化学習の枠組み
2.1 マルコフ決定過程による環境のモデル化
2.2 エージェントの行動ポリシーと状態価値関数
2.3 動的計画法による状態価値関数の決定

第3章 行動ポリシーの改善アルゴリズム
3.1 ポリシー反復法
3.2 価値反復法
3.3 より実践的な実装例

第4章 サンプリングデータを用いた学習法
4.1 モンテカルロ法
4.2 TD(Temporal-Difference)法

第5章 ニューラルネットワークによる関数近似
5.1 ニューラルネットワークによる状態価値関数の計算
5.2 ニューラルネットワークを用いたQ-Learning

図表サンプル





Google App Engine (Standard Environment, 2nd Generation) で Golang の Web Application を作る方法

これは何?

Google App Engine (Standard Environment) は 2nd Generation にアップグレードして、GAE 専用の実行モジュール(各言語で用意された GAE 対応の専用ライブラリ等)が不要になり、一般的なライブラリやフレームワークが比較的自由に使えるようになりました。

cloud.google.com

ここでは、Go 1.13 と軽量 Web Framework の Echo を用いて、GAE 上で Web Application を作る方法(主要なポイント)をまとめて紹介します。

echo.labstack.com

大事な宣伝

ここで利用するサンプルコードは、下記の書籍のサンプルアプリ(Python + Flask)を Golang で書き直したものです。GAE そのものの説明や今風な Web Application の作り方については、こちらの書籍をぜひ参考にしてください。

gihyo.jp

この記事のサンプルコード全体はこちらで公開しています。(package path にアンスコが入っており、Golang 的にはイケテないですが、Python 版のオリジナルのディレクトリ構成に合わせているためですのでご容赦ください。)

github.com

とりあえず動かす

GOPATH の通ったいつもの開発環境に Google Cloud SDK をインストールします。GCP の Cloud Shell 環境であれば、初めから ~/gopath に GOPATH が通っているのでここを開発用ディレクトリにするとよいでしょう。Cloud SDK のお約束で、Project ID の設定と Google account の認証を行っておきます。

$ gcloud config set project [Your Project ID]
$ gcloud auth login

次の gcloud コマンドで、自分の GCP Project 上に App Engine の環境を用意します。(利用するリージョンを聞かれるので、よしなに選んでください。)

$ gcloud app create

このあとは、最低限、次の app.yaml と main.go があれば、Hello World! 的な Web サーバーが起動します。

github.com

go.main は、ローカルでも動く様に作ってあるので、まずはローカルで動作確認しましょう。(go get すると「package github.com/enakai00/gae_basics_webapp_golang: no Go files in /home/enakai/gopath/src/github.com/enakai00/gae_basics_webapp_golang」と出ますが、これは問題ありません。)

$ go get github.com/enakai00/gae_basics_webapp_golang
$ cd ~/gopath/src/github.com/enakai00/gae_basics_webapp_golang/guestbook/04_helloworld/guestbook_deploy/
$ go run main.go
2020/04/15 23:46:15 Defaulting to port 8080
2020/04/15 23:46:15 Listening on port 8080

http://localhost:8080 にアクセスすると「Hello, World!」が表示されます。確認できたら Ctrl + C で停止します。

続いて、次のコマンドでこのアプリを App Engine の環境にデプロイします。(確認メッセージが出るので、元気よく「Y」で答えます。)

$ gcloud app deploy

https://hogehoge.appspot.com 的な URL が自動で割り当てられるので、ここにアクセスすると、先ほどと同様に「Hello, World!」が表示されます。

main.go の内容を簡単に確認します。

package main

import (
    "log"
    "net/http"
    "os"

    "github.com/labstack/echo"
)

var e = createMux()

func createMux() *echo.Echo {
    e := echo.New()
    http.Handle("/", e)
    return e
}

func init() {
    e.GET("/", home)
}

func home(c echo.Context) error {
    return c.String(http.StatusOK, "Hello, World!")
}

func main() {
    port := os.Getenv("PORT")
    if port == "" {
        port = "8080"
        log.Printf("Defaulting to port %s", port)
    }

    log.Printf("Listening on port %s", port)
    if err := http.ListenAndServe(":"+port, nil); err != nil {
        log.Fatal(err)
    }
}

init() と home() 以外は「おまじない」と思って大丈夫です。Golang 標準の http パッケージでリクエストを受けて(http.ListenAndServe())、それを Echo のインスタンスで処理する様に仕込んであります(http.Handle("/", e))。このあとは、init() でアクセス先の URL パスごとにハンドラー関数を設定して、Echo のお作法に従ってハンドラー(この例では、「Hello, World!」を表示する home())を書いていきます。

log パッケージで stderr に出力したログは、Stackdriver から確認できます。

Template の使い方

github.com

main.go から関連する部分を抜き出します。コード全体は上記を参照してください。

type Template struct {
    templates *template.Template
}

func (t *Template) Render(w io.Writer, name string, data interface{}, c echo.Context) error {
    return t.templates.ExecuteTemplate(w, name, data)
}

func init() {
    t := &Template{
        templates: template.Must(template.ParseGlob("templates/*.html")),
    }
    e.Renderer = t

    e.GET("/", home)
}

// e.GET("/", home)
func home(c echo.Context) error {
    type Data struct {
        Message string
    }
    data := Data{Message: "App Engine 勉強会 にようこそ"}
    return c.Render(http.StatusOK, "index", data)
}

home() 以外の部分は「おまじない」と思って大丈夫です。これによって、./templates 以下の .html ファイルがテンプレートの定義ファイルとして扱われます。home() の最後の return では、"index" という名前で定義されたテンプレートに構造体 Data に詰め込んだデータを受け渡してレンダリングします。

対応するテンプレートの定義は、ここでは、./templates/index.html にあります。1行目で "index" という名前をつけています。

{{define "index"}}
<!DOCTYPE html>
<html>
<head lang="ja">
  <meta charset="UTF-8">
  <title>GuestBook</title>
</head>
<body>
{{.Message}}
</body>
</html>
{{end}}

テンプレート内部では、 {{.}} によって受け取ったデータが参照できます。構造体のフィールドには、{{.Message}} のようにアクセスします。

エラーハンドラーのカスタマイズ

github.com

まず、main.go から関連する部分を抜き出します。コード全体は上記を参照してください。

package main

func init() {
    t := &Template{
        templates: template.Must(template.ParseGlob("templates/*.html")),
    }
    e.Renderer = t
    handler.Register(e)

    e.GET("/", home)
    e.GET("/err500", err500)
}

// e.GET("/err500", err500)
func err500(c echo.Context) error {
    return echo.NewHTTPError(http.StatusInternalServerError, "Server Error")
}

init() の中で(この後で説明する)エラーハンドラーの登録を行っています(handler.Register(e))。また、テスト用に /err500 にアクセスすると強制的に 500 エラーを発生するように仕込んであります。ハンドラーの本体は handler/handler.go にあります。主要部分を下記に抜粋します。

package handler

func Register(e *echo.Echo) {
    e.HTTPErrorHandler = JSONErrorHandler
}

type apiError struct {
    Status  int    `json:"status"`
    Message string `json:"message"`
}

func JSONErrorHandler(err error, c echo.Context) {
    code := http.StatusInternalServerError
    if he, ok := err.(*echo.HTTPError); ok {
        code = he.Code
    }
    switch code {
    case 404:
        c.JSON(code, apiError{
            Status:  code,
            Message: "Error: Resource not found.",
        })
    case 500:
        c.JSON(code, apiError{
            Status:  code,
            Message: "Please contact the administrator.",
        })
    default:
        c.JSON(code, apiError{
            Status:  code,
            Message: "Unknown Error",
        })
    }
}

JSONErrorHandler() では、構造体 apiError に格納したエラーメッセージを JSON 形式でクラインアントに返します。apiError の定義を見ると、各フィールドに `json:"stutus"` と行ったメタ情報が付与されており、これが JSON に変換する時の Key になります。

クライアントとのパラメーターの受け渡し

github.com

上記のコードでは、/api/greetings というパスでアクセスする REST API を実装しています。実装部分はパッケージを分けており、main.go の init() の中でハンドラの登録(greetings.Register(e))を行っています。

package main

func init() {
    t := &Template{
        templates: template.Must(template.ParseGlob("templates/*.html")),
    }
    e.Renderer = t
    handler.Register(e)
    greetings.Register(e)

    e.GET("/", home)
    e.GET("/err500", err500)
}

パッケージ本体は greetings/api.go にあります。こちらも主要部分の抜粋です。

package greetings

func Register(e *echo.Echo) {
    e.GET("/api/greetings", getAllGuests)
    e.POST("/api/greetings", addGuest)
    e.GET("/api/greetings/:id", getGuest)
}

type GuestData struct {
    Name    string    `json:"author"`
    Message string    `json:"message"`
    Created time.Time `json:"created"`
    ID      int64     `json:"id"`
}

// e.GET("/api/greetings", getAllGuests)
func getAllGuests(c echo.Context) error {
    type response struct {
        Guests []GuestData `json:"greetings"`
    }

    igarashi := GuestData{
        ID:      1,
        Name:    "Tuyushi Igarashi",
        Message: "Hello",
    }
    miyayama := GuestData{
        ID:      2,
        Name:    "Ryutaro Miyayama",
        Message: "Looks good to me",
    }
    data := response{Guests: []GuestData{igarashi, miyayama}}
    return c.JSON(http.StatusOK, data)
}

// e.GET("/api/greetings/:id", getGuest)
func getGuest(c echo.Context) error {
    id, err := strconv.Atoi(c.Param("id"))
    if err != nil {
        return echo.NewHTTPError(http.StatusInternalServerError, "Server Error")
    }
    igarashi := GuestData{
        ID:      int64(id),
        Name:    "Tuyushi Igarashi",
        Message: "Hello",
    }
    return c.JSON(http.StatusOK, igarashi)
}

// e.POST("/api/greetings", addGuest)
func addGuest(c echo.Context) error {
    type postData struct {
        Name    string `json:"author" form:"author" query:"author"`
        Message string `json:"message" form:"message" query:"message"`
    }

    data := new(postData)
    if err := c.Bind(data); err != nil {
        return echo.NewHTTPError(http.StatusInternalServerError, "Server Error")
    }

    response := GuestData{
        ID:      999,
        Name:    data.Name,
        Message: data.Message,
    }
    return c.JSON(http.StatusCreated, response)
}

Register() は main から呼び出していたハンドラーの登録処理です。ここでは、単なる GET(e.GET("/api/greetings", getAllGuests))、POST によるデータ受け取り(e.POST("/api/greetings", addGuest))、URI パラメーターによるデータ受け取り(e.GET("/api/greetings/:id", getGuest))の3種類を実装しています。クライアントに返送するデータは決め打ちのスタブ実装になっています。

単なる GET を実装した getAllGuests() では、構造体 response を JSON に変換して返却します。各フィールドのメタ情報(`json:"greetings"`)で JSON に変換する際の Key を指定します。

POST によるデータ受け取りを実装した addGuest では、クライアントからのデータを構造体 postData に変換して受け取ります。引数で受けたコンテキストの Bind メソッドで構造体にデータを格納します。各フィールドのメタ情報では、クライアントが送信したデータ形式(JSON, Form, Queryパラメーター)ごとのデータ名を指定しています。(今回は、クラインアントは JSON でデータを送信しているので `json:"author" などが適用されます。)

URI パラメーターによるデータ受け取りを実装した getGuest() では、引数で受けたコンテキストの Param メソッドでデータを取り出します。

Cloud Datastore を使う方法

Cloud Datastore は GCP 独自の NoSQL データベースで、Ancestor Query と呼ばれる強整合性を持った独自のクエリをサポートします。(現在は、「Firestore の Datastore モード」というややこしい正式名称になっていますが、通常、単に Datastore と呼びます。)詳細は、下記を参照してください。

cloud.google.com

GAE 上で Datastore にアクセスする例はこちらにあります。

github.com

実装部分は、ds/client.go ですが、パッケージ cloud.google.com/go/datastore をインポートして、クライアントインスタンスを取得すれば、あとは(Datastore の仕組みを知っている方には)だいたい想像通りの使い方です。

package ds

import (
    "context"
    "log"
    "os"
    "time"

    "cloud.google.com/go/datastore"
    "google.golang.org/api/iterator"
)

var projectID = os.Getenv("GOOGLE_CLOUD_PROJECT")
var ctx = context.Background()
var client, _ = datastore.NewClient(ctx, projectID)

type GuestEntity struct {
    Name    string         `datastore:"author"`
    Message string         `datastore:"message"`
    Created time.Time      `datastore:"created"`
    Key     *datastore.Key `datastore:"__key__"`
}

type CommentEntity struct {
    Message string         `datastore:"message"`
    Created time.Time      `datastore:"created"`
    Key     *datastore.Key `datastore:"__key__"`
}

func Insert(author, message string) GuestEntity {
    key := datastore.IncompleteKey("Greeting", nil)
    data := GuestEntity{
        Name:    author,
        Message: message,
        Created: time.Now(),
    }
    key, err := client.Put(ctx, key, &data)
    if err != nil {
        log.Fatalf("Failed to store data: %v", err)
    }
    data.Key = key

    return data
}

func GetAll() []GuestEntity {
    entities := []GuestEntity{}
    query := datastore.NewQuery("Greeting").Order("-created")
    it := client.Run(ctx, query)
    for {
        var entity GuestEntity
        _, err := it.Next(&entity)
        if err == iterator.Done {
            break
        }
        if err != nil {
            log.Fatalf("Error fetching next entity: %v", err)
        }
        entities = append(entities, entity)
    }
    return entities
}

func GetByID(id int64) GuestEntity {
    key := datastore.IDKey("Greeting", id, nil)
    query := datastore.NewQuery("Greeting").Filter("__key__ =", key)
    it := client.Run(ctx, query)

    var entity GuestEntity
    _, err := it.Next(&entity)
    if err != iterator.Done && err != nil {
        log.Fatalf("Error fetching next entity: %v", err)
    }
    return entity
}

func Update(entity GuestEntity) GuestEntity {
    _, err := client.Put(ctx, entity.Key, &entity)
    if err != nil {
        log.Fatalf("Failed to store data: %v", err)
    }
    return entity
}

func Delete(id int64) {
    key := datastore.IDKey("Greeting", id, nil)
    err := client.Delete(ctx, key)
    if err != nil {
        log.Fatalf("Failed to delete data: %v", err)
    }
}

func InsertComment(parentID int64, message string) CommentEntity {
    parentKey := datastore.IDKey("Greeting", parentID, nil)
    key := datastore.IncompleteKey("Comment", parentKey)
    data := CommentEntity{
        Message: message,
        Created: time.Now(),
    }
    key, err := client.Put(ctx, key, &data)
    if err != nil {
        log.Fatalf("Failed to store data: %v", err)
    }
    data.Key = key

    return data
}

func GetComments(parentID int64) []CommentEntity {
    entities := []CommentEntity{}
    ancestor := datastore.IDKey("Greeting", parentID, nil)
    query := datastore.NewQuery("Comment").Ancestor(ancestor)
    it := client.Run(ctx, query)
    for {
        var entity CommentEntity
        _, err := it.Next(&entity)
        if err == iterator.Done {
            break
        }
        if err != nil {
            log.Fatalf("Error fetching next entity: %v", err)
        }
        entities = append(entities, entity)
    }
    return entities
}

Datastore 固有の事情で Key の取り扱いが特殊なので、そこだけ補足しておきます。

たとえば、Insert() では、新しいエンティティを登録するために、datastore.IncompleteKey("Greeting", nil) で Kind(Datastore におけるテーブルみたいなもの)"Greeting" に対する新しいキーを取得しています。1つのエンティティに対応する構造体は GuestEntity ですがフィールド Key はメタ情報に `datastore:"__key__"` という記載があり、これがキーに対応することを示します。client.Put でエンティティを登録すると、キーに対して新しい ID がアサインされて、ID を不可したキーが返ってきます。ただし、対応する構造体の変数には、その情報は書き込まれないので、ここでは、明示的に書き込んでいます(data.Key = key)。

Cloud Storage を使う方法

コードのサンプルはこちらです。

github.com

ここでは、クライアントが Form でアップロードした画像ファイルを Cloud Storage に保存する処理を実装しています。実装の本体は、photos/handler.go にあります。

package photos

import (
    "context"
    "io"
    "log"
    "net/http"
    "os"

    "cloud.google.com/go/storage"
    "github.com/labstack/echo"
    "google.golang.org/api/iterator"
)

var projectID = os.Getenv("GOOGLE_CLOUD_PROJECT")
var ctx = context.Background()
var client, _ = storage.NewClient(ctx)
var bucketName = projectID

func Register(e *echo.Echo) {
    e.GET("/photos", getPhotos)
    e.POST("/photos", addPhoto)
}

// e.GET("/photos", getPhotos)
func getPhotos(c echo.Context) error {
    type PhotoData struct {
        PublicURL string
        Name      string
    }

    it := client.Bucket(bucketName).Objects(c.Request().Context(), nil)
    data := []PhotoData{}
    baseURL := "https://storage.cloud.google.com/" + bucketName + "/"
    for {
        attrs, err := it.Next()
        if err == iterator.Done {
            break
        }
        if err != nil {
            log.Fatalf("Failed to read bucket: %v", err)
        }

        item := PhotoData{
            PublicURL: baseURL + attrs.Name,
            Name:      attrs.Name,
        }
        data = append(data, item)
    }
    return c.Render(http.StatusOK, "photos", data)
}

// e.POST("/photos", addPhoto)
func addPhoto(c echo.Context) error {
    file, _ := c.FormFile("file")
    src, err := file.Open()
    if err != nil {
        log.Fatalf("Failed to open file: %v", err)
    }
    defer src.Close()

    bucket := client.Bucket(bucketName)
    dst := bucket.Object(file.Filename).NewWriter(c.Request().Context())
    defer dst.Close()

    if _, err := io.Copy(dst, src); err != nil {
        log.Fatalf("Failed to upload file: %v", err)
    }
    return c.Render(http.StatusOK, "complete", nil)
}

パッケージ cloud.google.com/go/storage をインポートして、クライアントインスタンスを取得して利用します。addPhoto() がファイルを保存する例で、getPhotos() はバケット内のファイル一覧を取得する例になっています。

Quantum Phase Estimation による Order finding アルゴリズム

複数固有値に対する推定

enakai00.hatenablog.com

上記の記事で解説した位相推定の量子回路(下図)では、状態 {\mid u\rangle} はユニタリ演算子 U の特定の固有値に属する固有状態でした。

それでは、複数の固有値に対する固有状態の重ね合わせの場合、どうなるでしょうか?

結論から言うと、最後の逆フーリエ変換の出力は、それぞれの固有値に対応する状態の重ね合わせになります。

たとえば、\varphi_0 = [0.j_1^{(0)}\cdots j_n^{(0)}]\varphi_1 = [0.j_1^{(1)}\cdots j_n^{(1)}] の固有状態 {\mid u_0\rangle}{\mid u_1\rangle} の重ね合わせ \displaystyle {\mid u\rangle} = \frac{1}{\sqrt{2}}\left({\mid u_0\rangle}+{\mid u_1\rangle}\right) に対しては、最後の出力は、

 \displaystyle \frac{1}{\sqrt{2}}\left({\mid j_1^{(0)}\rangle}\otimes\cdots\otimes{\mid j_n^{(0)}\rangle} + {\mid j_1^{(1)}\rangle}\otimes\cdots\otimes{\mid j_n^{(1)}\rangle} \right)

となります。従って、これを観測すると等確率で [j_1^{(0)}\cdots j_n^{(0)}] もしくは [j_1^{(1)}\cdots j_n^{(1)}] という結果が得られます。

これは次の簡単な計算で確認できます。たとえば、先の量子回路の一番下の量子ビット(および Second register)の変化は次になります。

 \displaystyle {\mid 0\rangle}\otimes {\mid u\rangle} \longrightarrow \frac{1}{\sqrt{2}}\left({\mid 0\rangle}+{\mid 1\rangle}\right)\otimes {\mid u\rangle}H 演算)

  \displaystyle \longrightarrow \frac{1}{2}\left\{
{\mid 0\rangle} \otimes \left({\mid u_0\rangle} + {\mid u_1\rangle}\right)+ {\mid 1\rangle}\otimes
\left(e^{2\pi i \times [j_1^{(0)}\cdots j_n^{(0)}]} {\mid u_0\rangle} + e^{2\pi i \times [j_1^{(1)}\cdots j_n^{(1)}]}{\mid u_1\rangle}\right)
\right\}(Controlled-U 演算)

    =\displaystyle \frac{1}{2}\left\{
\left(
{\mid 0\rangle} + e^{2\pi i \times [j_1^{(0)}\cdots j_n^{(0)}]}
{\mid 1\rangle}\right)\otimes {\mid u_0\rangle}+
\left({\mid 0\rangle} + e^{2\pi i \times [j_1^{(1)}\cdots j_n^{(1)}]}
{\mid 1\rangle}\right)\otimes {\mid u_1\rangle}
\right\}

他の量子ビットについても同様で、全体として、2種類の計算を個別に行って、結果を重ね合わせたものと同じになります。(量子回路演算の線形性を考えると、実は当たり前なのですが。。。。)

これから位相情報を取り出す逆フーリエ変換もまた、線形変換なので、結果は、個別に計算したものの重ね合わせと同じにものになります。

Cirq による実験例はこちらにあります。

github.com

Order finding

x,\,N を適当な自然数として、 x^r = 1\mod N となる最小の自然数 r を発見する」という問題を考えます。

これは、「\mod Nx 倍する」というユニタリ演算 U に対する固有値から解くことができます。{\mid x\rangle} を自然数 x の各桁を量子ビットで表現した状態として、U は次で定義されます。

  U {\mid y\rangle} = {\mid xy\mod N\rangle}

これは、s = 0,\cdots r-1 として、次の r 個の固有状態を持ちます。

 \displaystyle {\mid u_s\rangle} := \frac{1}{\sqrt{r}}\sum_{k=0}^{r-1}\exp\left(-2\pi i\frac{sk}{r}\right){\mid x^k\mod N\rangle}

直接計算から分かるように、固有値は \displaystyle\exp\left(2\pi i\frac{s}{r}\right) です。

そして、これらの固有状態をすべて重ね合わせると、ちょうど {\mid 1 \rangle} になります。これも直接計算でわかります。

 \displaystyle \frac{1}{\sqrt{r}}\sum_{s=0}^{r-1}{\mid u_s\rangle} = {\mid 1 \rangle}

したがって、冒頭の量子回路で、Second registor を {\mid 1 \rangle} に初期化して、演算子 U に対する位相推定を行うと、\displaystyle\frac{s}{r}s=0,\cdots,r-1)のいずれか1つが得られます。得られた値に対して、「互いに素な値による既約分数として表す」ための既知のアルゴリズム(Continued fractions)を適用すると、sr が個別に決定されます。これで、先ほどの問題の解 r が得られます。(運悪く \displaystyle\frac{s}{r}=0 が観測された場合は、測定をやり直します。)