MARC

 008240612s2023      us  |||||||||||||||c||eng  d
■001000016933565
■00520240214101305
■006m          o    d                
■007cr#unu||||||||
■020    ▼a9798380413787
■035    ▼a(MiAaPQ)AAI30531414
■040    ▼aMiAaPQ▼cMiAaPQ
■0820  ▼a004
■1001  ▼aZhan,  Wei.
■24510▼aRandomness  and  Quantumness  in  Space-Bounded  Computation▼h[electronic  resource]
■260    ▼a[S.l.]:▼bPrinceton  University.  ▼c2023
■260  1▼aAnn  Arbor  :▼bProQuest  Dissertations  &  Theses,  ▼c2023
■300    ▼a1  online  resource(222  p.)
■500    ▼aSource:  Dissertations  Abstracts  International,  Volume:  85-04,  Section:  B.
■500    ▼aAdvisor:  Raz,  Ran.
■5021  ▼aThesis  (Ph.D.)--Princeton  University,  2023.
■506    ▼aThis  item  must  not  be  sold  to  any  third  party  vendors.
■520    ▼aIn  the  field  of  computational  complexity  theory,  we  study  the  power  and  limits  of  different  computational  resources  and  the  interplay  between  them.  The  constraints  on  space  complexity  provide  a  natural  and  interesting  setting,  that  is  often  more  tractable  than  the  time-restricted  counterparts.  In  this  dissertation,  we  specifically  study  how  randomness  and  quantumness  interact  with  space  complexity.Our  results  consist  of  two  parts.  In  the  first  part,  we  present  our  algorithmic  results.  We  show  that  randomness  used  for  BPL  algorithms  can  be  reduced  to  logarithmic  with  the  access  to  untrusted  random  bits.  Consequentially,  every  BPL  algorithm  can  be  certifiably  derandomized  using  presumably  hard  functions.  For  quantum  computing,  we  show  how  to  eliminate  intermediate  measurement  in  logspace  quantum  circuits,  and  simulate  general  quantum  algorithms  in  BQL  with  only  unitaries.In  the  second  part,  we  present  our  lower  bound  results.  For  decision  problems,  we  propose  the  coupon-collector  model  where  one  receives  random  coordinates  of  the  input,  and  prove  a  quadratic  time-space  tradeoff  lower  bound  in  the  model.  For  computing  multi-output  functions,  we  prove  the  first  polynomial  separation  between  randomized  and  deterministic  oblivious  computation  for  total  functions.  And  for  learning,  we  prove  an  exponential  time  lower  bound  against  classical-quantum  hybrid  learners  with  sub-quadratic  classical  memory  and  sublinear  quantum  memory.
■590    ▼aSchool  code:  0181.
■650  4▼aComputer  science.
■650  4▼aSystems  science.
■653    ▼aQuantum  computing
■653    ▼aRandomness
■653    ▼aSpace-bounded  computation
■690    ▼a0984
■690    ▼a0790
■71020▼aPrinceton  University▼bComputer  Science.
■7730  ▼tDissertations  Abstracts  International▼g85-04B.
■773    ▼tDissertation  Abstract  International
■790    ▼a0181
■791    ▼aPh.D.
■792    ▼a2023
■793    ▼aEnglish
■85640▼uhttp://www.riss.kr/pdu/ddodLink.do?id=T16933565▼nKERIS▼z이  자료의  원문은  한국교육학술정보원에서  제공합니다.
■980    ▼a202402▼f2024

Preview

Export

ChatGPT Discussion

AI Recommended Related Books