The information-theoretical viewpoint on the physi

arXiv:quant-ph/0210148v528Jul2004Theinformation-theoreticalviewpointonthephysicalcomplexityofclassicalandquantumobjectsandtheirdynamicalevolutionGavrielSegre∗(Dated:30-5-2004)CharlesBennett’smeasureofphysicalcomplexityforclassicalobjects,namelylogical-depth,isusedinordertoprovethatachaoticclassicaldynamicalsystemisnotphysicallycomplex.Thenaturalmeasureofphysicalcomplexityforquantumobjects,quantumlogical-depth,isthenintroducedinordertoprovethatachaoticquantumdynamicalsystemisnotphysicallycomplextoo.∗Electronicaddress:[e-mail];URL:finitionofthephysicalcomplexityofstringsandsequencesofcbits4III.Thedefinitionofthephysicalcomplexityofclassicaldynamicalsystems7IV.Thedefinitionofthephysicalcomplexityofstringsandsequencesofqubits14V.Thedefinitionofthephysicalcomplexityofquantumdynamicalsystems17VI.Acknoledgements19VII.Notation20References233I.INTRODUCTION:THESHALLOWNESSOFRANDOMOBJECTSDespitedenotingitwiththeterm”complexity”,AndreˇiNikolaevichKolmogorov[1],[2],[3],[4],[5]introducedthenotiondenotednowadaysbytheschoolofPaulVitanyi[6]as”plain-Kolmogorov-complexity”(thatIwilldenotewiththeletterKfromhereandbeyond)inorderofobtaininganintrinsicmeasureoftheamountofinformationofthatobjectandnotasameasureoftheamountofphysical-complexityofthatobject.ThattheamountofinformationandtheamountofphysicalcomplexityofanobjectaretwocompletelydifferentconceptsbecamefurtherclearaftertheintroductionbyGregoryJosephChaitinofthenotiondenotednowadaysbytheschoolofPaulVitanyi[6]as”prefix-Kolmogorov-complexity”anddenotedbytheschoolofChaitinandCristianS.Caludesimplyasalgorithmicinformation[7](andthatIwilldenotewiththeletterIfromhereandbeyond)andtheinducednotionofalgorithmic-randomness:analgorithmicallyrandomobjecthasaveryhighalgorithmicinformationbutiscertainlynotphysically-complex.Suchasimpleconsiderationisindeedsufficienttoinferthatalgorithmicinformationcanbeseeninnowayasameasureofphysicalcomplexity.AnaturalmeasureofphysicalcomplexitywithintheframeworkofAlgorithmicInformationTheory,thelogicaldepth,waslaterintroducedbyGregoryChaitinandCharlesBennett[8],constitutingwhatisnowadaysgenerallyconsideredasthealgorithmicinformationtheoreticviewpointastophysicalcomplexity,thoughsomeauthorcanstillbefoundwhonotonlyignoresthat,asitwasclearlyrealizedbyBrudnohimself[9],[10],[11],thechaoticityofadynamicalsystem(definedasthestrictpositivityofitsKolmogorov-Sinaientropy)isequivalenttoitsweakalgorithmicchaoticity(definedastheconditionthatalmostallthetrajectories,symbolicallycodified,areBrudno-algorithmicallyrandom)butisweakerthanitsstrongalgorithmicchaoticity(definedastheconditionthatalmostallthetrajectories,symbolicallycodified,areMartin-L¨of-Solovay-Chaitin-algorithmicallyrandom),butusesthenotionsofchaoticityandcomplexityasiftheyweresynonymous,athingobviouslyfalsesince,aswehaveseen,the(weak)algorithmicrandomnessofalmostallthetrajectoriesofachaoticdynamicalsystemimpliesexactlytheopposite,namelythatitstrajectoriesarenotcomplexatall.Indeeditisnaturaltodefinecomplexadynamicalsystemsuchthatalmostallitstrajectories,symbolicallycodified,arelogicaldeep.So,despitethethestillcommonfashiontoadopttheterms”chaoticity”and”complexity”assynomymous,onehasthatthateverychaoticaldynamicalsystemisshallow,asIwillshowinsectionIIandsectionIII.ThekeypointofsuchanissueissoimportanttodeserveafurtherrepetitionwiththeownwordsofCharlesBennett[8]illustratingthephysicalmeaningofthenotionoflogicaldepthandthereasonwhyitisagoodmeasureofphysicalcomplexity:”Thenotionoflogical-depthdevelopedinthepresentpaperwasfirstdescribedin[12],andatgreaterlengthin[13]and[14];similarnotionshavebeenindependentlyintroducedby[15](”potential”),[16](”incompletesequence”),[17](”hittingtime”)andKoppel,thisvolume(”sophistication”).SeealsoWolfram’sworkon”computationalirreducibility”[18]andHartmanis’workontime-andspace-boundedalgorithmicinformation[19]”Weproposedepthasaformalmeasureofvalue.Fromtheearliestdaysofinformationtheoryithasbeenappreciatedthatinformationperseisnotagoodmeasureofmessagevalue.Forexampleatypicalsequenceofcointosseshashighinformationcontentbutlittlevalue;anephemeresis,givingthepositionsofthemoonandplanetseverydayforahundredyears,hasnomoreinformationthantheequationsofmotionsandinitialconditionsfromwhichitwascalculated,butsavesitsownertheeffortofrecalculatingthesepositions.Thevalueofamessagethusappearstoresidenotinitsinformation(itsabsolutelyunpredictableparts),norinitsobviousredudancy(verbatimrepetitions,unequaldigitfrequencies),butratherinwhatmightbecalleditsburiedredudancy-partspredictableonlywithdifficulty,thingsthereceivercouldinprinciplehavefiguredoutwithoutbeingtold,butonlyatconsiderablecostinmoney,timeorcomputation.Inotherwordsthevalueofamessageistheamountofmathematicalorotherworkplausiblydonebyitsoriginator,whichitsreceiverissavedfromhavingtorepeat”Thequantumanalogueofsuchanotion,i.e.quantumlogicaldepth,isintroducedinsectionIV.ThedefinitionofthephysicalcomplexityofaquantumdynamicalsystemisthenintroducedinsectionVwhere