2022-12-06
PCCC22（第22回PCクラスタシンポジウム）「HPCシステム技術の最前線」

量子古典融合コンピューティングに向けた
量子アルゴリズム開発

藤堂眞治 <wistaria@phys.s.u-tokyo.ac.jp>
東京大学大学院理学系研究科

1

2• analyzing data from 57
textbooks and 1137 research
papers• almost half of all algorithm
By YASH SHERRYMIT Computer Science & Artificial Intelligence Laboratory, Cambridge, MA 02139 USA
families little or no
NEIL C. THOMPSONMIT Computer Science & Artificial Intelligence Laboratory, Cambridge, MA 02139 USA
improvement
MIT Initiative on the Digital Economy, Cambridge, MA 02142 USA
Is progress faster in most algo- • 14% of algorithmic families
rithms? Just some? How muchon average?
transformative improvements
A variety of research has
quantified progress for partic• 30%-43% of algorithmicular algorithms, including for
maximum flow [5], Boolean
families improvements
satisfiability and factoring [6],and (many times) for linear
comparable or greater thansolvers [4], [6], [7]. Others inacademia [6], [8]–[10] and theprivate sector [11], [12] have
Moore’s Law
looked at progress on benchmarks, such as computer chess• “Algorithms are one of theratings or weather prediction,that is not strictly comparable tomost important sources ofalgorithms since they lack either
mathematically defined problem
statements or verifiably optimal
improvement in computing..."How Fast Do Algorithms
Improve?

Point of View

A

answers. Thus, despite substantial interest in the question,
lgorithms determine which calculations computers use to solve
existing research provides only
problems and are one of the central pillars of computer science.
a limited, fragmentary view of
As algorithms improve, they enable scientists to tackle larger
algorithm progress.
problems and explore new domains and new scientific techIn this article, we provide theniques [1], [2]. Bold claims have been made about the pace of algorithmic
first comprehensive analysis ofprogress. For example, the President’s Council of Advisors on Science andalgorithm progress ever assemTechnology (PCAST), a body of senior scientists that advise the U.S. President,
bled. This allows us to look syswrote in 2010 that “in many areas, performance gains due to improvements intematically at when algorithms
algorithms have vastly exceeded even the dramatic performance gains due towere discovered, how they haveincreased processor speed” [3]. However, this conclusion was supported based
Fig. 1. Algorithm discovery and improvement. (a) Number of new algorithm families discovered each decade. (b) Share of known algorithm
improved,
and how the scalefamilies
improved each decade. (c) of
Asymptotic
complexity 109,
class of algorithm
families at first discovery.
(d) Average yearly probability
on data from progress in linear solvers [4], whicha single example.
Y.is justSherry,N.C.WithThompson,Proceedings
thetimeIEEE,
1768–1777(2021)of these
improvements
comthat an algorithm in one time complexity class transitions to another (average family complexity improvement). In (c) and (d) “>n3 ” includes
no guarantee that linear solvers are representative of algorithms in general,parestime
to complexities
other sourcesof superpolynomial
innothat are
but subexponential.
it is unclear how broadly conclusions, such as PCAST’s, should be interpreted.
vation. Analyzing data from 57

3Will we run out of data? An analysis of the limitsof scaling datasets in Machine Learning

11.04325v1 [cs.LG] 26 Oct 2022

Pablo Villalobos⇤ , Jaime Sevilla⇤† , Lennart Heim⇤§ , Tamay Besiroglu⇤‡ , Marius Hobbhahn ⇤¶ , Anson Ho⇤
Abstract—We analyze the growth of dataset sizes used inmachine learning for natural language processing and computer
vision, and extrapolate these using two methods; using the historical growth rate and estimating the compute-optimal dataset sizefor future predicted compute budgets. We investigate the growthin data usage by estimating the total stock of unlabeled data
available on the internet over the coming decades. Our analysis
indicates that the stock of high-quality language data will be
exhausted soon; likely before 2026. By contrast, the stock of lowquality language data and image data will be exhausted only
much later; between 2030 and 2050 (for low-quality language)
and between 2030 and 2060 (for images). Our work suggeststhat the current trend of ever-growing ML models that rely
on enormous datasets might slow down if data efficiency is not
drastically improved or new sources of data become available.

K EY TAKEAWAYS• We project the growth of training datasets for vision andlanguage models using both the historical growth rate andthe compute-optimal dataset size given current scalinglaws and existing compute availability estimates (Section
III-A).
• We also project the growth in the total stock of unlabeled
data, including high-quality language data (Section III-B).
• Language datasets have grown exponentially by morethan 50% per year, and contain up to 2e12 words as of
October 2022. (section IV-A)• The stock of language data currently grows by 7% yearly,
but our model predicts a slowdown to 1% by 2100. This
stock is currently between 7e13 and 7e16 words, whichis 1.5 to 4.5 orders of magnitude larger than the largest

seems likely to be around 18% to 31% per year. The
current largest dataset is 3e9 images (Section IV-A).
• The stock of vision data currently grows by 8% yearly,
but will eventually slow down to 1% by 2100. It iscurrently between 8.11e12 and 2.3e13 images – three tofour orders of magnitude larger than the largest datasets
used today (Section IV-C).
• Projecting these trends highlights that we will likely run
out of vision data between 2030 to 2070 (Section IV-D).
I. I NTRODUCTION
Training data is one of the three main factors that determine
the performance of Machine Learning (ML) models, together
with algorithms and compute. Current understanding of scalinglaws suggests that future ML capabilities will strongly dependon the availability of large amounts of data to train large
models [2, 3].
Previous work compiled a database of more than 200 training datasets used in ML models [1] and estimated historicalrates of growth in dataset size for vision and language models.
To learn about the limits of this trend, we developed
probabilistic models to estimate the total amount of image andlanguage data that will be available between 2022 and 2100.
Based on our dataset size trend projections, we then estimatedVillalobos,
al, arXiv:2211.04325
the limit of theseP.trends
due to theetexhaustionof available
data.

4

量子機械学習の可能性• 量子・古典ハイブリッド画像認識• 従来、画像認識はデータが大きすぎるため、量子機械学習は不可能であると考えられていた

A. Sakurai, et al. arXiv:2108.12131• 古典検出器データの量子機械学習• 少数データ・少数パラメータ量子機械学習

K. Terashi, et al. Comput. Softw. Big Sci. 5, 2 (2021)

共創の場形成⽀援プログラム（COI-NEXT）【政策重点分野（量⼦技術分野）】

拠点名称︓量⼦ソフトウェアとHPC・シミュレーション技術の共創によるサスティナブルAI研究拠点
プロジェクトリーダー

藤堂眞治
東京⼤学⼤学院理学系研究科 教授

代表機関

東京⼤学

参画機関

（⼤学等）慶應義塾⼤学、理化学研究所、沖縄科学技術⼤学院⼤学、シカゴ⼤学（企業等）川崎市、Amoeba Energy株式会社、SCSK株式会社、株式会社Quemix、京セラ株式会社、JSR株式会社、株式会社TIER
IV、凸版印刷株式会社、トヨタ⾃動⾞株式会社、⽇鉄ソリューションズ株式会社、International Business Machines Corporation、株式会社三井住友フィナンシャルグループ、株式会社⽇本総合研究所、株式会社バイトルヒクマ、BIPROGY株式会社、blueqat株式会社、みずほリ
サーチ&テクノロジーズ株式会社、三菱ケミカル株式会社、株式会社三菱UFJフィナンシャル・グループ、村⽥機械株式会社

プロジェクトの概要

量⼦ソフトウェアとHPC・シミュレーション技術の融合により、サスティ
ナブルなAI技術を開拓する。具体的には、少数データ・少数パラメータでも有効な量⼦機械学習⼿法と、固体・原⼦核・実時間ダイ
ナミクスを扱える多体問題量⼦シミュレーション⼿法を開発し、テン
ソルネットワークなどの量⼦埋め込み技術とさまざまな量⼦最適化技術を駆使することで、量⼦機械学習・量⼦シミュレーション・量
⼦計測デバイスを結合した量⼦AI技術を創出する。さらに、量⼦
オフローディングや量⼦AIエッジコンピューティングのための量⼦HPC
基盤を構築・展開する。それによりクラウドからエッジまで誰もがシー
ムレスに量⼦AI技術を利⽤できる融合環境を実現し、健康・福祉、エネルギー問題といった重要な社会課題の解決に貢献する。
量⼦HPC基盤の活⽤が進むことで、新しいアイデアに基づく新規ビ
ジネス・企業の参⼊が促され、新たに直⾯する課題が次の世代の量⼦AI技術の研究開発を加速する。このような量⼦AI技術に⽀えられた「創発を⽣み出すサスティナブルな好循環」を実装することで、我が国の⽣産性⾰命の促進や新産業創出・国際競争⼒が持続する社会の実現を⽬指す。

実施期間: 2022年10月〜2032年3月

https://www.jst.go.jp/pf/platform/file/2022/2022_kyotengaiyou_2221.pdf

5

COI-NEXT「量子ソフトウェアとHPC・シミュレーション技術の共創によるサスティナブルAI研究拠点」

6

古典AIの課題を克服し「サスティナブルAI」の創出へ• AIの「スケーラビリティ」• 従来の機械学習：精度を上げるにはより大量の学習データと複雑な学習モデルが必要• ムーアの法則の終焉：HPC技術における微細化・高速化の限界• 量子AIの可能性・将来性• 近年の量子デバイス技術の進展• 少数データ、少数パラメータによる高度な量子機械学習• 古典計算が難しい量子多体問題の量子シミュレーション• 量子シミュレーション・量子計測と量子機械学習の直接結合• 古典HPC基盤との融合• 拠点ビジョン ⇒ ３つのターゲット ⇒ ５つの研究開発課題
ビジョン

量子ソフトウェアとHPC・シミュレーション技術の共創によるサスティナブルAIが拓く未来・ エネルギーの不安なしに情報技術を存分に活用できる社会・ 携帯端末にいたるまで量子技術が普及し数千万人の人々がその恩恵を受けられる社会
・ 量子AIに支えられた生産性革命や新産業創出が持続する社会ターゲット

研究開発課題サスティナブル量子
機械学習手法の創出

1. 量子機械学習による高汎化技術と最適化の統合 (量子機械学習)

量子AIにむけた多体問題量子シミュレーション手法の革新
量子HPC基盤の構
築と展開

2. 物質・材料科学のための多体問題量子シミュレーション
手法開発 （量子シミュレーション)
3. 量子埋め込みに基づく量子古典融合アルゴリズム開発(量子埋め込み)4. 量子機械学習/量子シミュレーションの高度化のための最適化技術開発 (量子最適化)
5. CPU〜GPU〜QPUの統合による量子HPC基盤構築(量子HPC)

持続可能な量子AI技術と量子HPC基盤の社会への展開

7

創薬

金融
ライフサイエンス

素粒子・原子核物理

自動運転
プラント最適化

プロセス最適化

マテリアル開発

量子機械学習による高汎化技術と最適化の統合物質・材料科学のための多体問題
量子シミュレーション手法開発

・少数データ・少数パラメータに対する量子機械
学習手法の開発
・データの符号化と学習・推論結果の統合技術の開発

・周期系、格子系に対する多体問題量子シミュレーション手法
・量子機械学習とのダイレクト結合によるマテリアルズ・
インフォマティクス

量子埋め込みに基づく量子古典融合アルゴリズム開発量子機械学習/量子シミュレーションの高度化のための最適化技術開発

・テンソルネットワーク・サンプリングによる新しい量子/古典
アルゴリズム・テンソルネットワークの枠組みによる量子埋め込み・ゲート式量子コンピュータ/量子アニーリングマシン/
イジングマシンと機械学習の融合アルゴリズム
・量子回路のゲート最適化・量子コンパイラ

CPU～GPU～QPUの統合による量子HPC基盤構築
・新しいデータやアルゴリズム表現形式によるシームレスな統合
・量子コンピュータと次世代HPCIの統合環境構築とユーザへの展開

8

多体波動関数とテンソル• N 量子ビット(spin-1/2スピン)系の多体波動関数| Ψ⟩ =
NN∑

σ1,σ2,⋯,σN

Cσ1,σ2,⋯,σN | σ1σ2⋯σN⟩N• 2 状態の重ね合わせ → 2 個の係数(Cσ1,σ2,⋯,σN)を決める必要がある → データ量2• C はN本脚(階数N、N階)のテンソルとみなすことができる
・
・
・

C

σ1

σ2

σ3

σN

• テンソル = 多次元配列 = ベクトルや行列の一般化• 0本脚のテンソル → スカラー
• 1本脚のテンソル → ベクトル
• 2本脚のテンソル → 行列
• ...

• N本脚のテンソル → データ量、計算量ともNに関して指数関数的に増加

さまざまなテンソル
NATURE COMPUTATIONAL SCIE
• テンソルによる表現

P(s1, s2, ⋯, sN ) b• 確率分布関数

0.8• 多次元データ
0.2

0.5

• グリッドデータ、画像

t /T0
0

0.8

g(x, y) = g(x1, x2, ⋯, xN, y1, y2, ⋯, yN )DNS

y/Lbox

.5

9

0.5

1.0

0.7
0.5

• (x1, x2, ⋯, xN ) と (y1, y2, ⋯, yN ) はそれぞれ x と y の2進数表現
１６ (16本脚)のテンソルとみなせる• 例) 256x256の画像は、256x256の行列あるいは 20.3

0.7

χ = 118

0.5
0.3• ニューラルネットワーク

0.7• 重み行列 → 多数の脚からなるテンソルχ = 74

0.5

・
・
・

・
・
・

W

1.5

10

テンソル分解・・・• 大きな(=脚の多い)テンソルを小さな(=脚の少ない)テンソルの積に分解

・
・
・

・
・
・

C

σ1

σ2

σ3

σN

σ1

σ2

σ3

• テンソルをつなぐ線は脚の添字を揃えて和をとることを意味する（=縮約)• テンソル ⇒ テンソル分解 ⇒ テンソルネットワーク• 他にも、ボルツマンマシン、経路積分、DNNなどさまざまな分解/表現手法• テンソルネットワークの利点• データ量の圧縮によるコンパクトな表現 O(exp(N )) → O(N )• 縮約順序に関する自由度• 特異値分解に基づく高精度近似• テンソルネットワーク表現• もともとの大きなテンソルの高精度近似(例: 変分波動関数)• 厳密に分解できる場合もある(例: GHZ状態、AKLT状態)• 問題そのものがテンソルネットワークで表現されている場合• 古典統計力学•量子統計力学、量子回路

σN

11

量子コンピュータの古典シミュレーション• 量子ソフトウェア・アルゴリズムの精度・性能評価• 古典/量子ハイブリッドアルゴリズム、量子機械学習、量子誤り訂正• 古典計算の限界を知る• 量子超越の本当の境界はどこか？

• 量子回路は典型的な量子多体系• 量子回路のシミュレーション技術 → 物理やその他の分野への展開• 超伝導・量子液体・素粒子・原子核• 複雑系・時系列データ・機械学習• 量子コンピューティングの本質を知る• 別の形に書き直してはじめて理解できる• 量子技術の古典コンピュータ上での利用• 量子コンピュータが普及する前に誰もがどこでも量子計算を利用できるように• 旧来のシミュレーション手法 (N qbit系)• シュレディンガーシミュレーション(状態ベクトルシミュレーション): メモリ・計算量 ∼ exp N• ファインマンシミュレーション(経路数え上げ): 計算量 ∼ exp N• ファインマンサンプリング(量子モンテカルロ): 負符号問題

10 >

国

10 >

は>

•

1.net
国

一

一

12

は>

•

1.net11量子回路のテンソルネットワークシミュレーション
10
朝 11
10 >

-

>

10 >

| 0⟩

| 1⟩

H

| 0⟩
| 0⟩

| 1⟩
H

H

⑧

→

| 1⟩

11
朝
国學

-

国學

-

一

10 >

• 量子回路 ⇒ テンソルネットワーク

>

一

⑧

-

-

>

〉
11 〉

①
①
縮約

⑥
⑧

⑥

-

-

⑧

-

④

-

④

-

-

-

④

④

一

一

-

-

• 1ビットゲート → 2脚テンソル• 2ビットゲート → 4脚テンソル• 初期状態・出力状態 → 1脚テンソル(ベクトル)の組• 出力状態の振幅 → テンソルネットワークを縮約することで得られる• 量子回路では必ず左から右に時間が進む• テンソルネットワークの縮約はどのような順番で計算しても結果は同じ• テンソルネットワークの古典コンピュータでの計算は非常にコストが高い• 縮約順序を工夫することで計算量を劇的に減らせる可能性• 近似的な縮約も可能（低ランク近似、テンソルくりこみ群）

①
①

-

①

①

はは
○
○
→
1 11 1 >
は
は

>

13

量子回路のテンソルネットワークシミュレーション• Y. A. Liu et al., Closing the “quantum supremacy” gap: Achieving realTime simulation of a random quantum circuit using a new sunway
supercomputer. International Conference for High Performance
Computing, Networking, Storage and Analysis, SC (2021)• Gordon Bell Prize Winner in 2021

• しかしながらテンソルネットワーク
規模が大きくなると厳密な縮約は結局不可能に• 情報圧縮(SVD)を使った高精度近似• テンソルネットワーク繰り込み群

https://awards.acm.org/bell

14

手描き文字認識• 畳み込みニューラルネットワーク(CNN)による機械学習

https://www.kaggle.com/cdeotte/how-to-choose-cnn-architecture-mnist• 入力: グレースケール画像• 出力: 10次元ベクトル• 認識精度 > 99.5% (MNIST)rks
in physics
usedperformancein a context wherecombiningsmall
N independent
systemsdigit
set and are
findtypicallyvery goodfor remarkably
MPS bond
dimensions.
o takingthe
a tensor
productof afunctions
vector describing
system.
With thegoal of applying
discuss
structureof therealizedeachby our
proposedmodels.
networks to machine learning, we choose a feature map of the form

15

ers interested
we have madeour codes publicly available at:
s1 s2in···sreproducing
s1 our results,
s2
sN
N
(x)
=
(x
)
⌦
(x
)
⌦
·
·
·
(x
(2)
1The codes2are based on theN ) .ITensor library [19].
b.com/emstoudenmire/TNML.
テンソルネットワークによる教師あり学習

is the tensor product of a local feature map sj (xj ) applied to each input
N -dimensional vector x (where j = 1, 2, . . . , N ). The indices sj run from 1• テンソルネットワークは多重線形性をもつ
j of the
ding
Input
Data
is known
thelocal dimension and is a hyper-parameter defining the classification•asいかにして非線形性を入れて表現能力を高めるか？
gh one could use a different local feature map for each input component xj , we will
入力データのエンコード
orks
in• physics
are typicallyuseda context
where
N independent
systemsthe caseof homogeneous
inputswithinthesame local
mapcombining
applied to eachxj . Thus eachto ataking
productand
a vector
describing
eachsystem.
With asthea goaltod-dimensional
vector,thefull feature(x) canbe viewed
vectorofinapplyinga2Nmap•aNtensor
次元ベクトル(
Nof
ピクセル画像)を次元の特徴ベクトルに変換
s3 Thisor
toanmachinewetensorchoosea feature
form
s2 2.
s4 s5 s6
sin1 Fig.
nalnetworks
space or as
order-Nlearning,
tensor. The
diagramfor map(x)ofis theshowns s2 s3 s4 s5 s6
is said be rank-1
since
the productof·N
s1 s2 ···ss2sN
N it is manifestly(x) = s1 (x1 ) ⌦(x2 ) ⌦
· · order-1(xN1tensors.
) .=
(2)
s
s
s
s
s
1
2
3
example of this type of feature map, which we will use later, =consider inputs
which
are4 5 s6

s1 s2 ···sN

s
s
s
s
s
s
is the tensor product of a local feature map sj (xj ) applied to each input
ges with N pixels, where each pixel value ranges from 0.0 for white to 1.0 for black. If
xj of the •NΦ(x)-dimensional
vector x (wherej=
1, 2,mapped. . . , tomapped
Na normalized). Theaorderindicessjorder
runNfrom
1structure.
は2次元局所特徴ベクトルのテンソル積jFigure2: Inputdata is data
Nstensor
productwith
Figure2:
Input
normalized
tensora rank-1 prvalue of pixel number
j is xj 2 [0, 1], a simple
choicefor isthelocaltomap(xjwith) isa rank-1
d is known as the local dimension
andisa
hyper-parameter
defining
theclassificationh ⇣⇡ ⌘⇣ ⇡ ⌘is, we willugh one could use ja(xdifferent
localxfeaturemap
xj for each input component xj (3)j ) = cosj , sin
2 local map applied to each xj . Thus eachr the case of homogeneous inputs 2with the same
3. The full image
is andrepresented
a tensor
product
these
vectors.
The in a
dedtoinaFig.
d-dimensional
vector,the fullasfeaturemap(x)ofcanbe localviewedas a vector
mapspace
is somewhat
andtensor.
is motivatedby “spin”
vectors
encounteredin quantum
onal
or as anad-hoc,order-N
The tensor
diagramfor(x) is shownin Fig. 2. Thiss
re isresearchneededsince
to understandthe best
but themost crucial
or
said beisrank-1
it is manifestly
thechoices
productforof N(x),order-1
tensors.

s1 s2 ···sN

1

2

3

4

5

6

0
For the caseof a grayscale
image and dof= 2,xeachpixelxvalue
is mapped to a normalized
ms to be that ~ (x) · ~ (x0 ) is a smooth Figureand 3:slowly
varyingfunctionand, andtwo-component vector. The full image is mapped to the tensor product of all the local pixel vectors
teexampletypespaceof feature
map,towhich
welater,together.
consider inputs which are
as shown
in Fig.
2. will use
ance
metric ofin thisfeaturethat tends
clustersimilarimagesFor the fromcase of0.0
a grayscale
image
each pixel
ages with N pixels, where each pixel Figure
value 3:ranges
for white
toand
1.0d =
for2, black.
Ifvalue is mappe
sjthe
two-component
vector. The
full
image
is mappedtotensorproductof all thefeaturemap Eq.choice(2) defines fora kernelwhichis themap
product of N
local
kernels,
one for each
e value of pixel number j is xj 2 [0, The1],asimple
the
local
(x
)
is
j
as shown
Fig.
2. data.
component
xj in
of
input
Kernels of thisProcessing
type have been Systems,
discussed previously
in Vapnik[20, p.
E. M. Stoudenmire and D. J. Schwab,
Advances
inthe
NeuralInformation
29, 4799.
(2016)
h 2 ⇣ 193]
⌘
⇣
⌘i
and
have
been
arguedbyWaegeman
et
al.
[21]
to
be
useful
for
data
where
no
relationship
is
⇡
⇡
sj
assumedbetweendifferent
components
of
the
input
vectorprior
tolearning.
(xj ) = cos xj , sin xj(3)and classifying an input x by choosing
the label ` for which |f (x)| is largest.
represent W ` as a tensor network, namely as an MPS which have the key advantage that methods forand optimizing them are well understood and highly efficient. An MPS decomposition
Since we apply the same featuremanipulating
map
to
all W
input
data,
the only quantity that depends on the label16`
oftheweighttensorhas
theform` is the weight vector W ` . Though one can view W ` asXa collection of vectors labeled by `, we↵↵↵
edwillin classifying
data
pre-assigned
labels,for ↵which
`
A↵
· ·we
· A`;↵···A
Ws` wheres ···s = ` isAas tensorssprefer to view
Wwith
as an
order N + 1hidden
tensorindexandfs` (x) is a function(5){↵}gy,mappingwhich
wetaketotoa set
of functionsindexedby a f ` (x) for a particular input
分類モデル
inputsthemeanspaceoptimizingof labels. The
tensordiagram forevaluating
is depicted in Fig. 4.
`(4)• f ` (x) = W ` · (x) `N`
Because the weight tensor Ws1 s2 ···sN has NL · d components, where` NL is the number of labels,W
N and` optimize this tensor efficiently. The =
we
need
a
way
to
regularize
strategy
we will use is tof ` (x)
•
は巨大な(
)行列
W
10
×
2
(x)|
is
largest.
oosing the label
`
for
which
|f
(x)
represent W ` as a tensor network, namely as an MPS which have the key advantage that methods fore map
to all and
input
data, thethem
only
quantitythat
depends
onW thelabel
manipulating
optimizing
wellunderstoodandhighlyefficient.
Anvector
MPS (x)decomposition`
Figureare
4: Theoverlapof the weighttensorwitha specific input
defines the decision``•をテンソルネットワーク（行列積状態)に分解
W
`
`
ough
one
can
view
W
as
a
collectionofvectors
labeledby`,weof the weight tensor W has thefunction
formf (x). The label ` for which f (x) has maximum magnitude is the predicted label for x.
der N + 1 tensor where ` is a tensor
Xindex and f ` (x) is a function↵1` ↵1 ↵2`;↵j ↵j+1
↵N 1
=
A
A
·
·
·
A
·
·
·
A
(5)
Ws`1 for3s2 ···sevaluatingssssN
abels. The tensor diagram
f
(x)
for
a
particular
input
1
2
j
N
1 2

N

1
1

1
2

2

j

j

j+1

N
N

1

{↵}

`
`
components, where
NL is the numberof labels,
nd optimize this tensor efficiently. `The strategy we will use is to` fork, namely as an MPS which have the key advantage that methods`
Figure 5: Approximationof2 theweight tensor
W `MPSbyW
a matrix
product state. The label index ` isem are wellunderstoodandhighlyefficient.
Andecomposition`• それぞれのテンソルは個の要素をもつ（はテンソル間のボンド次元)
2mmplaced arbitrarily on one of the N tensors but can be moved to other locations.f (x)
form
(x)
X
2
and↵
is illustrated`;↵in Fig.
5. Each A tensor↵1 ↵↵Nhas1d m elements which are the latent variables parame1 2
j ↵j+1of ·W·;·the=As1 Asterizing·the· ·approximation
Asj
AAsNtensors(5)be constrained to` are in general not unique and can
2Ns2 ···sN has NL · d

N=Figure 4: The overlap
ofproperties
the weighttensorwith
specific
vector (x) defines the decision
bestow niceon the MPS,
likeW
makingthe Aatensors
partialinput
isometries.
{↵} `functionf (x).The
The
label `offorf ` (x)maximummagnitude
is theandpredicted
label for x.
dimensions
eachwhichinternal index↵j ofhasan MPS
are known as
the bond dimensions
are the`(hyper) parameters controlling complexity of the MPS approximation. For sufficiently large bonddimensions an MPS can represent any tensor [22]. The name matrix product state refers to the factthat any specific component of the full tensor Ws`1 s2 ···sN can be recovered efficiently by summingover the {↵andleft to right
via a sequenceof matrix
products (theProcessing
term “state” referstoj } indices
3 NeuralE. M. Stoudenmire
D. J.from
Schwab,Advancesin
Information
Systems,
29, 4799. (2016)
the original use of MPS to describe quantum states of matter).

`In the above`decomposition Eq. (5), the label index ` was arbitrarily placed on the tensor at some

等
i
国
誤 と無
テンソルネットワークの量子回路への変換
→

→

17

• N = 8, m = 8 の場合

灩
鍤
Im

T

Me

:

:

of

of

o

• テンソルの最適化 → 量子回路のパラメータの最適化 → 量子・古典ハイブリッドアルゴリズム

W. Huggins, et al.Quantum Science and Technology, 4, 1 (2019)誤.li#tEt
等i国
量子ビット効率のよい実装
と無
→

→

国

• 量子ビットを初期化して再利用

(a)

→

誤

→

等
i
と無

灩
灩
鍤 鍤
Im

Im

T
Me

T
Me

:

(a)

:

of

of

of

7

:

:

(b)

18

of

(b)
o

o

• 必要となる物理量子ビット数は、入力サイズ N に依存しない！
FIG. 11. Qubit-efficient scheme for evaluating (a) discriminative and (b) generative matrix product state models foran arbitrary number of inputs or outputs. The figure shows
the case of V = 3 qubits connecting each node of the network. When evaluating the discriminative model, one of thequbits is measured after each unitary is applied and the result discarded; the qubit is then prepared with the next input
component. To implement the generative model, one of thequbits is measured after each unitary operation and the result
recorded. The qubit is then reset to the state h0|.

FIG. 10. Qubit-efficient scheme for evaluating (a) discriminative and (b) generative tree models with V = 2 virtual qubits
and N = 16 inputs or outputs. Note that the two patterns are
the reverse of each other. In (a) qubits indicated with hashmarks are measured and the measurement results discarded.
These qubits are then reset and prepared with additional
inW. Huggins,
et al.Quantum Science and Technology, 4, 1 (2019)
put states. In (b) measured qubits are recorded and reset toputs with V virtual qubits requires the same number ofa reference state h0|.

physical qubits as for the discriminative case; this can be19

量子アルゴリズムの本質• アダマールゲートなどを使い、多くの状態の重ね合わせを準備• この状態で非選択的射影測定を行うとエントロピーは O(N ) (量子ビット数に比例)• 欲しい答えが大きな振幅を持つように状態をユニタリー操作し干渉させる• 量子状態のエントロピーはゼロのまま• 非選択的射影測定をした場合のエントロピーは減少• 一種のデータ圧縮?

• 選択的射影測定する(測定して結果を見る)と正解が高い確率で得られる• エントロピーのできるだけ小さな状態からのサンプリング• 一種の情報抽出• ⇒ 量子インスパイアードアルゴリズム

20

テンソルネットワーク形式でのモンテカルロ法• 経路積分に基づく従来の量子モンテカルロ法• 実時間発展の場合には深刻な負符号問題に直面• 量子回路をテンソルネットワークとして表現• テンソルネットワーク表現のままサンプリングを実行• 精度を落とさず高速化• 並列性• 特異値分解に起因する系統誤差を消去• 実時間発展・フラストレーション・フェルミ統計における負符号問題を解決
1

D=1
D=2
1
D=3
D=4
exact
0.8
TNMC (D=4)

0.8
average signspecific heat

1.2

0.6
0.4

0.4

standard
D=2
D=3
D=4
D=6
D=8

0.2

0.2
0

0.6

0
1

1.5

2
T

2.5

3

1

1.5

2
T

2.5

3

21

まとめ「量子埋め込み」• 「大きなテンソル」に「テンソルネットワーク」を埋め込む• 「大きなテンソル」 =• 量子状態、量子回路、古典コンピュータ、機械学習...
• 「テンソルネットワーク」 「ボルツマンマシン」=• 近似波動関数・試行波動関数、古典模型・量子模型、量子回路...

• 古典コンピュータに量子回路を埋め込む• 量子回路シミュレータ ⇒ 量子コンピュータを使わずに量子AIを• 量子状態を量子状態として取り出す ⇒ 量子・古典インターフェース• 量子回路にテンソルネットワークを埋め込む• 多項式時間で縮約可 ⇒ 古典・量子模型の量子シミュレーション• 異なる量子回路間の接続• 前処理・変換の重要性• 量子回路やテンソルネットワークの書き換え、確率的な表現、観測との組み合わせ...

• 量子コンピュータのロードマップ