Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Sign up for free
Menu
Search
Features
All features
Private URLs
Password Protection
Custom URLS
Scheduled publishing
Remove Branding
Restrict embedding
Deck Collections
Notes
Features
All features
Private URLs
Password Protection
Custom URLS
Scheduled publishing
Remove Branding
Restrict embedding
Deck Collections
Notes
Explore
Featured decks
Featured speakers
Programming
Technology
Storyboards
Explore
Featured decks
Featured speakers
Programming
Technology
Storyboards
Pricing
Search
Sign in
Sign up for free
PLDI '21論文読み会: Quantum Abstract Interpretation
Search
Idein
June 08, 2022
Research
1.7k
0
Share
Embed
Copy iframe code
Copy JS code
Copy link
Start on current slide
PLDI '21論文読み会: Quantum Abstract Interpretation
Idein
June 08, 2022
Transcript
30 slides
தଜߊҰ 2VBOUVN"CTUSBDU*OUFSQSFUBUJPO 1-%*จಡΈձBU*EFJO
ಡΜͩจ w 2VBOUVN"CTUSBDU*OUFSQSFUBUJPO w ྔࢠϓϩάϥϜͷநղऍख๏ΛఏҊ͢Δจ /FOHLVO:VBOE+FOT1BMTCFSH2VBOUVNBCTUSBDUJOUFSQSFUBUJPO *O1SPDFFEJOHTPGUIFOE"$.4*(1-"/*OUFSOBUJPOBM$POGFSFODFPO1SPHSBNNJOH -BOHVBHF%FTJHOBOE*NQMFNFOUBUJPO 1-%*
"TTPDJBUJPOGPS$PNQVUJOH.BDIJOFSZ /FX:PSL /: 64" r %0*IUUQTEPJPSH
ΞδΣϯμ w நղऍͱ w ྔࢠܭࢉͱ w ຊจͷհ
w ϓϩάϥϜͷ੩తղੳͷϑϨʔϜϫʔΫͷҰͭ w ϓϩάϥϜΛԿΒ͔ͷநྖҬ BCTUSBDUEPNBJO ͷ্Ͱ࣮ߦ w நྖҬଋ MBUUJDF ͱͯ͠දݱ͞ΕΔ
நղऍ "CTUSBDU*OQUFSQSFUBUJPO \Y Z^ [Y Z \Y Z [^ நత ۩ମత
ྔࢠϏοτ 2VBOUVN#JU 2CJU w RVCJUೋ͕ͷෳૉͭͰදݱ w ͜ͷRVCJUΛ؍ଌ͢Δͱɺ֬ Ͱঢ়ଶ ɺ֬ Ͱঢ়ଶ
͕ಘΒΕΔ |α2 | |0⟩ |β2 | |1⟩ α|0⟩ + β|1⟩ = (α, β)T (α2 + β2 = 1) |0⟩ = (1,0)T, |1⟩ = (0,1)T
༧උࣝϒϥͱέοτ w Λέοτ LFU ϕΫτϧͱݺͿɻ w ͜ΕͷਵΛϒϥ CSB ϕΫτϧͱݺͼ ͱॻ͘
w ௨ৗͷੵʹͳΔ |ψ⟩ ⟨ψ| ⟨ψ|ϕ⟩ |ψ⟩ = ( α β), ⟨ψ| = (α* β*)
ྔࢠϏοτ 2VBOUVN#JU 2CJU w RVCJUෳૉ ݸͰද͞ΕΔ n 2n α|00⟩ +
β|01⟩ + γ|10⟩ + δ|11⟩ (α2 + β2 + γ2 + δ2 = 1) ྫRCJUঢ়ଶͷॏͶ߹Θͤ
ิෳ2VCJUͷܭࢉ |ϕ, ψ⟩ > = |ϕ⟩ ⊗ |ψ⟩ = (
α β) ⊗ ( γ δ) = αγ αδ βγ βδ
ྔࢠήʔτ 2VBOUVN-PHJD(BUF w ྔࢠϏοτͷঢ়ଶΛม͑Δૢ࡞ XJLJQFEJB2VBOUVNMPHJDHBUFΑΓҾ༻ |ψ⟩ |ψ′  ⟩
ྔࢠήʔτ 2VBOUVN-PHJD(BUF w ྔࢠϏοτͷঢ়ଶΛม͑Δૢ࡞ w ྫ)BEBNBSE(BUF XJLJQFEJB2VBOUVNMPHJDHBUFΑΓҾ༻ |0⟩ 1 2
|0⟩ + 1 2 |1⟩ H
ྔࢠճ࿏ 2VBOUVN$JSDVJU w ྔࢠήʔτΛΈ߹Θͤͯɺճ࿏Λߏͨ͠ͷ w ճ࿏Λతؒతʹදݱ͢Δͷ͕ྔࢠϓϩάϥϜ w ֤ԋࢉճ࿏શମϢχλϦߦྻ 6OJUBSZ.BUSJY
Λຬͨ͢ ͱͯ͠දݱ͞ΕΔ UU† = U†U = I U |ψ′  ⟩ = U|ψ⟩
ຊจͷऔΓΉ՝ w ྔࢠϓϩάϥϜͷ੩తղੳΛ͍ͨ͠ʂ w RVCJUΛදݱ͢Δͷʹ ݸͷෳૉ͕ඞཁɻετϨʔδɾԋࢉྔڞʹେɻ n 2n ܭࢉ݁ՌͲͷΑ͏ͳ ঢ়ଶϕΫτϧ
ࢀߟຊ࣌Ͱͷ ଟ ੈք࠷େͷྔࢠίϯϐϡʔλͷن w (PPHMFͷ#SJTUMFDPOF RVCJU w ݹయܭࢉػͰγϛϡϨʔτ͢Δʹ w
ঢ়ଶ ݸͷෳૉͰදݱ w ແཧͰ͢ 4.7 × 1021
ຊจͷߩݙ w ྔࢠϓϩάϥϜʹର͢Δநղऍख๏ΛఏҊ w RVCJUʹରͯ͠ଟ߲ࣜ࣌ؒͰ࣮ߦՄೳͰ͋Δ
ཧղ͢Δ্ͰͷϙΠϯτ w நྖҬ "CTUSBDU%PNBJO ΛͲ͏ఆΊΔ͔ʁ w ෦ઢܗۭࣹؒӨߦྻͷͳ͢ଋΛݩʹBCTUSBDUEPNBJOΛߏ͢Δ
ࣹӨߦྻ QSPKFDUJPONBUSJY w Λຬͨ͢ਖ਼ํߦྻ w ϕΫτϧΛ͋Δ෦ઢܗۭؒ ʹҠ͢ w ͱ ҰରҰʹରԠ
w ྫҎԼͷ ฏ໘ͱରԠ P = P† = P2 P SP P SP P xy P = 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
۩ମతঢ়ଶࣹӨߦྻͱͯ͠දݱ͞ΕΔ w ࣹӨߦྻͱͯ͠ͷੑ࣭Λຬͨ͢ ρ = |ψ⟩⟨ψ|
ࣹӨߦྻͷॱং P ⊆ Q J ff SP ⊆ SQ
நྖҬͷߏ w ORVCJUͷঢ়ଶʹରͯ͠ |ψ⟩⟨ψ| (Ps1 , ⋯, Psm ) ͷڊେߦྻ
2n × 2n Nݸͷখ͞ͳࣹӨ ߦྻͰۙࣅ
நྖҬͷఆٛ w ʹରͯ͠ ͱ͢Δɻͨͩ͠ w ORVCJUͷͷ͢ΔϏοτͷू߹Λදݱ w ͷॱংҎԼͰఆΊΔ 0
< m ≤ 2n S = (s1 , …, sm ) si ⊆ {0,…, n − 1} si P, Q ∈ AbsDom(S) AbsDom(S) = {(Ps1 , …, Psm ) ∣ Psi 2|si |ࣹ࣍Өߦྻ} P ⊑ Q J ff ∀i, Psi ⊆ Qsi
'JOFS"CTUSBDU%PNBJO AbsDom({0,1}, {1,2}) AbsDom({0,1,2}, {1,2}) AbsDom(S) ⊴ AbsDom(T) J ff
∀i si ⊆ ti
۩ମྖҬ $PODSFUF%PNBJO w நྖҬͷಛผͳ߹ɻ࠷ fi OFɻ ͱͯ͠ [n] = {0,…,
n − 1} AbsDom([n]m) = {2nࣹ࣍Өߦྻmݸͷ}
நԽࣸ૾ͱ۩ମԽࣸ૾ நԽ ۩ମԽ
ΨϩΞଓ (BMPJT$POOFDUJPO
ΨϩΞଓ (BMPJT$POOFDUJPO "CTUSBDU%PNBJOͰܭࢉͯ͠ಘͨॱংͱ $PODSFUF%PNBJOͰܭࢉͯ͠ಘͨॱংҰக
நԋࢉ RVCJUͷू߹'ʹର͢ΔϢχλϦߦྻ6ͰͷநԋࢉΛߦ͏ʹɺ 'ΛؚΉ fi OFͳEPNBJOʹҠͬͯ۩ମతʹܭࢉͯ͠ɺ"CTUSBDUEPNBJOʹΔ S = (s1 , …,
sm ) ⇒ T = (s1 ∪ sF , …, sm ∪ sF )
ओఆཧ நྖҬઢܗ෦ۭؒ ͷ ͷ-BUUJDFͩͬͨͷͰܭࢉ݁Ռͷ ͷ ʹؚ·ΕΔϏοτ෦ۭؒ ͷுΔۭؒʹؚ·ΕΔ ͱ͍ͬͨBTTFSUJPO͕ࣔͤΔ si Psi
ܭࢉྔ w ͭͷࣹӨߦྻͷαΠζΛLRVCJUͱͨ͠߹ w ۭؒܭࢉྔ w ࣌ؒܭࢉྔ ϓϩάϥϜͷήʔτ
O(|S| × (2k+3 × 2k+3)) O(|p| × 8k) |p|
ϕϯνϚʔΫ w #7G Y BY CͷB CΛݟ͚ͭΔ w ();શͯɺશ͕ͯॏͳͬͨঢ়ଶΛ࡞Δ w
(SPWFSG Y ͱͳΔYΛ୳ࡧ w .BD#PPL1SP $PSFJ()[ (#
݁ w ྔࢠܭࢉͷҝͷநղऍख๏ΛఏҊͨ͠ 4DBMBCMFͰ͋ΔRVCJUنͷγϛϡϨʔγϣϯग़དྷͨ 6TFGVMͰ͋ΔͭͷॏཁͳͰBTTFSUJPODIFDL͕ग़དྷͨ 'MFYJCMFͰ͋Δ"CTUSBDU%PNBJOͷઃܭࣗ༝͕ߴ͍
More Decks by Idein
See All by Idein
会社紹介資料/Idein株式会社
ideininc
0
1.4k
会社紹介資料/Idein株式会社 ※URLが変わりました
ideininc
0
65k
PLDI '21論文読み会: DNNFusion: Accelerating Deep Neural Networks Execution with Advanced Operator Fusion
ideininc
1
2.1k
PLDI '21論文読み会: AKG: Automatic Kernel Generation for Neural Processing Units using Polyhedral Transformations
ideininc
0
1.8k
PLDI '21論文読み会: Specification Synthesis with Constrainted Horn Clauses
ideininc
0
1.7k
PLDI '21論文読み会: Cyclic Program Synthesis
ideininc
0
1.7k
PLDI '21論文読み会: High Performance Correctly Rounded Math Libraries for 32-bit Floating Point Representations
ideininc
0
1.7k
PLDI '21論文読み会: Provable Repair of Deep Neural Networks
ideininc
2
1.9k
Other Decks in Research
See All in Research
Développer des solutions de réduction des émissions de méthane entérique : 1ers résultats Méthane 2030
institutdelelevage
PRO
0
290
[UAI2026, Tutorial Talk] Tensor Networks for Density Estimation: The merits of low-rank structures, tractable inference, and uncertainty quantification
gkazunii
0
130
Adapter les bergeries aux fortes chaleurs
institutdelelevage
PRO
0
180
HackSick vol.7 LT資料【LLMアーキテクチャ入門・事前学習時の躓き所解説】 スパースなAttention・状態空間モデル
rikkabotan7
0
240
フィジカルAIの社会実装に向けて -AIエージェントからAgentic Roboticsへ-
hf149
1
2.8k
超効率化への挑戦:1bit LLMの現状と展望
yumaichikawa
1
1k
Prithvi-EO-2.0
satai
3
120
L’albédo:levier d’atténuation du changement climatique dans les systèmes fourragers
institutdelelevage
PRO
0
170
就労支援の現場での生成AI活用
enochan
0
220
[SNLP2026] Scaling up Test-Time Compute with Latent Reasoning: A Recurrent Depth Approach
wataruuuuu
0
370
Karkada さんの論文 × 2 の紹介: (1) Closed-Form Training Dynamics Reveal Learned Features and Linear Structure in Word2Vec-like Models, (2) Symmetry in language statistics shapes the geometry of model representations
eumesy
PRO
1
1k
GeoAgent勉強会 論文紹介と強い推論モデルが与えるインパクト
satai
5
490
Featured
See All Featured
SEO Brein meetup: CTRL+C is not how to scale international SEO
lindahogenes
2
3k
HU Berlin: Industrial-Strength Natural Language Processing with spaCy and Prodigy
inesmontani
PRO
0
810
Code Review Best Practice
trishagee
74
20k
AI Search: Implications for SEO and How to Move Forward - #ShenzhenSEOConference
aleyda
1
1.4k
The Illustrated Children's Guide to Kubernetes
chrisshort
51
53k
Let's Do A Bunch of Simple Stuff to Make Websites Faster
chriscoyier
508
140k
Are puppies a ranking factor?
jonoalderson
2
4.2k
CoffeeScript is Beautiful & I Never Want to Write Plain JavaScript Again
sstephenson
162
16k
Site-Speed That Sticks
csswizardry
13
1.6k
Unlocking the hidden potential of vector embeddings in international SEO
frankvandijk
0
1k
The AI Search Optimization Roadmap by Aleyda Solis
aleyda
2
6.4k
GitHub's CSS Performance
jonrohan
1033
470k