OnquantumKolmogorov
Onquantum Kolmogorov complexity
complexity
andtheirrelationships
pResearchInstituteforMathematical
ResearchInstitute for Mathematical
Sciences,KyotoUniversityT
ToruTakisaka
T ki k
ELCWorkshoponRandomnessandProbability ThroughComputability
2013/5/15

Preface• WhyQKC?
h?
– Itcanbeanewtooltoanalyzequantumstatein
informationtheoritical pointofview(ex.
Miyadera[2012])– Itcanbeabasicnotiontoconsider“quantumrandomness”• TodayIwilltalkaboutoday
ta about– TwodefinitionofQKCbyBerthiaume etal.andGács
and some known facts about them,andsomeknownfactsaboutthem,– Myconjecture(quantumLevin’scodingtheorem).

Axioms for quantum mechanics
Axiomsforquantummechanics• ToeveryquantumsystemS uniquelypcalledthestate
associatedisaHilbertspaceH
spaceofS.StatesofSarerepresentedbyunit
vectors \ in H
vectorsinH.
Ex.)Qubit system…C2, ^ 0 , 1 `• Foreveryunitvectorin H,there existsastate
representedbythatvector.
db hEx.)

0 12

Axioms for quantum mechanicsAxiomsforquantummechanics• Thestatespaceofthecompositesystem
S =S1 +S2 consistingofthesystemSgy
1 withthestatespaceH1 andofthesystemS2 withthestate space H2 isthetensorproductHstatespaceH
is the tensor product H11 H2.
Ex.)thespaceofnͲletterqubit strings…{C2}ٔn^ 0...0 , ... , 1...1 `f2}ٔnї thespaceofallqubit strings…{Cn 0

Axioms for quantum mechanics
Axiomsforquantummechanics• (discrete)Timeevolutionofquantumstatesispyy pexpressedbyaunitaryoperatorU:\їU\ї U 2 \ї …

Several definitions of QKC
SeveraldefinitionsofQKC• UsequantumTuringmachine– Vitányiy [[2001]]– Berthiaume etal.[2001]• “Quantize”universalsemimeasure– Gács [2001]

Quantum Turing machine (QTM)
QuantumTuringmachine(QTM)• M=(Q,є,ɷ)~• ɷ :Q: Q 㽢 є
є 㽢QQ㽢 єє 㽢 {L,R}їC{L , R} ї C• ɷ uniquelydefinesanoperatorU onHqtm:
U q, T , ]¦W

G q, T ] , p,W , d p, T]W , ]  d( p , ,d )
Qu6u^1,1`• WecallthismachineQTMonlyifU isunitary.

Existence of universal QTM
ExistenceofuniversalQTM
Theorem(Bernstein–Theorem(Bernstein – Vazirani,1997)
Vazirani 1997) Thereexists
There existsaQTMM0 suchthatM sm T G ! 0  \M 0 sm , T , G , \  M \Tr G.

ThismachinesimulateseachQTMwithpolynomial
slowdown.
l dQubit complexity(Berthiaumecomplexity (Berthiaume etal.2001)
et al 2001)^`•

QC G \min l MM0 M  \•QC \­min ® l M¯

1½
k M 0 M , k  \ Tr  ¾k¿

pTr

G

Problem (invariance of QC)
Problem(invarianceofQC)• (Classicalcase)foruniversalTMM0 andany
TMM,thereexistsaconstantcM suchthat
C M w d C M 0 w  cM .
M 0)((Justinputto)p sM , w• Bernstein– Vazirani UQTMrequirestheH lti ti
Haltingtimeasaninput
it …can’tshowthe’t h thinvarianceofqubit complexityinthesame
mannerasabove.

Strongly UQTM (Müller 2007)
StronglyUQTM(Müller,2007)
Theorem(Müller,2007)
Theorem(Müller 2007) Thereexists
There exists aQTMMa QTM M1suchthatM  \  \ M G ! 0

M1 \ M ,G  M \Tr\M \foreachforwhichisdefined,wherel \M

d l \  cM .

QCM' 0 \ d QCMG \  c' ,G , M

ї

QCMp 1 \ d QCMp \  cM

G '

G

Relation between classical complexity
Relationbetweenclassicalcomplexity
Theorem (Müller 2009)
Theorem(Müller,2009)
QC p xQC x O 1.

Question: IsthenotionofQTMindispensablefor
the definition of qubit complexity?
thedefinitionofqubitIsthereanequivalentdefinitionofqubit complexity
on the notion of classical Turing machine?
onthenotionofclassicalTuringmachine?

Density matrix
Densitymatrix• U  MN iscalledDensitymatrixlliff
U t 0, Tr U
N

1.
NU ¦ Oi \ i \ i ,їwherei 1

Oi t 0, ¦ Oi 1.
i 1

ї Densitymatrixrepresentsaprobability
distributionofquantumstates,^O , ... , O ; \ , ... , \ `.
1N1N

Universal semi density matrix (Gács 2001)
UniversalsemiͲdensitymatrix(Gács,2001)
U ( hU  Nwith• SemiͲdensitymatrix(thatis,Mh

U t 0, Tr U d 1 )islower) is lowerͲsemicomputablesemicomputable if
if^U n `
thereisasequenceofelementarymatrix
such thatsuchthatU n d U n 1 , U n o U n o f .
P• LowerͲsemicomputable semiͲdensitymatrix
is universal ifforanyLSCͲSDMthereisa
isuniversal
if for any LSCͲSDM U there is acU ! 0constantsuchthatU d cU P .

References• Mi
Miyadera,T.QuantumKolmogorov
dTQ
t
K l
complexityandiInformationͲ
l it
diI f
ti
disturbancetheorem.Entropy2011,13,778–789.
• Vitányi,P.M.B.QuantumKolmogorov complexitybasedonclassical
ddescriptions.IEEETrans.Inform.Theory.2001,47,2464–2479.
i ti
IEEE T
I f
Th
2001 47 2464 2479
• Berthiaume,A.;vanDam,W.;Laplante,S.QuantumKolmogorov
complexity.J.Comput.SystemSci.2001,63,201–221.
• Gács,P.Quantumalgorithmicentropy.J.Phys.A:Math.Gen.2001,
34,6859Ͳ6880.
• Bernstein,E.;Vazirani,U.Quantumcomplexitytheory.SIAMJ.
, ;
, Q
pyy
Comput.1997,26,5,1411–1473.
• Müller,M.StronglyuniversalquantumTuringmachinesand
invarianceofKolmogorov
gcomplexity.IEEETrans.Inform.Theory.
pyy
2008,54,763–780.
• Müller,M.OnthequantumKolmogorov complexityofclassical
strings. Int. J. Quant. Inf. 2009, 7, 701–712.
strings.Int.J.Quant.Inf.2009,7,701712.