008240612s2023      us  |||||||||||||||c||eng  d
■001000016934770
■00520240214101652
■006m          o    d                
■007cr#unu||||||||
■020    ▼a9798380327909
■035    ▼a(MiAaPQ)AAI30634434
■040    ▼aMiAaPQ▼cMiAaPQ
■0820  ▼a004
■1001  ▼aTang,  Ewin.
■24510▼aQuantum  Machine  Learning  Without  Any  Quantum▼h[electronic  resource]
■260    ▼a[S.l.]:▼bUniversity  of  Washington.  ▼c2023
■260  1▼aAnn  Arbor  :▼bProQuest  Dissertations  &  Theses,  ▼c2023
■300    ▼a1  online  resource(169  p.)
■500    ▼aSource:  Dissertations  Abstracts  International,  Volume:  85-03,  Section:  B.
■500    ▼aAdvisor:  Lee,  James.
■5021  ▼aThesis  (Ph.D.)--University  of  Washington,  2023.
■506    ▼aThis  item  must  not  be  sold  to  any  third  party  vendors.
■520    ▼aCould  quantum  machine  learning  someday  run  faster  than  classical  machine  learning?  Over  the  past  decade,  the  field  of  QML  has  produced  many  proposals  for  attaining  large  quantum  speedups  for  computationally  intensive  tasks  in  machine  learning  and  data  analysis.  However,  it  was  unclear  whether  these  speedups  could  be  realized  in  end-to-end  applications,  as  there  had  been  no  rigorous  way  to  analyze  such  speedups.  We  remedy  this  issue  by  presenting  a  framework  of  classical  computation  to  serve  as  an  analogue  to  quantum  linear  algebra:  in  particular,  we  give  a  classical  version  of  the  quantum  singular  value  transformation  (QSVT)  framework  of  Gilyen,  Su,  Low,  and  Wiebe.  Within  this  framework,  we  observe  that  the  space  of  QML  algorithms  splits  into  two  classes:  either  input  data  is  sparse  or  given  in  a  quantum-accessible  data  structure,  which  implicitly  requires  such  matrices  to  have  low  rank.  The  former  class  is  BQP-complete,  meaning  that  it  must  give  exponential  speedups;  otherwise,  exponential  quantum  speedups  don't  exist  at  all.  On  the  other  hand,  the  latter  class  can  be  "dequantized,"  meaning  that  our  classical  framework  produces  algorithms  to  perform  computations  in  this  class  at  most  polynomially  slower  than  QSVT.We  give  two  forms  of  evidence  for  this  claim.  First,  we  prove  that  our  framework  has  extensibility  properties,  showing  that  we  can  compute  the  same  type  of  matrix  arithmetic  expressions  that  QSVT  can  compute.  Second,  with  our  framework,  we  dequantize  eight  QML  algorithms  appearing  in  the  literature,  including  recommendation  systems  and  low-rank  semidefinite  programming,  which  were  previously  believed  to  be  among  the  best  candidates  for  exponential  quantum  speedup.  We  can  then  conclude  that  these  candidates  do  not  give  exponential  speedups  when  run  on  classical  data,  radically  limiting  the  space  of  settings  where  we  could  hope  for  exponential  speedups  from  QML.The  classical  algorithms  presented  here  center  around  one  key  idea:  data  structures  that  support  efficient  quantum  algorithms  for  preparing  an  input  quantum  state  also  admit  efficient  classical  algorithms  for  measuring  that  quantum  state  in  the  computational  basis.  As  observed  in  the  classical  sketching  literature,  these  measurements,  ℓ₂²  importance  samples,  can  be  used  to  approximate  a  product  of  matrices  by  a  product  of  "sketched"  matrices  of  far  lower  dimension.  This  simple  idea  turns  out  to  be  extremely  extensible  when  input  matrices  are  sufficiently  low-rank.  Our  work  forms  the  beginning  of  a  theory  of  quantum-inspired  linear  algebra,  demonstrating  that  we  can  compute  a  large  class  of  linear  algebraic  expressions  in  time  independent  of  input  dimension,  provided  that  weak  sampling  assumptions  on  the  input  are  satisfied.
■590    ▼aSchool  code:  0250.
■650  4▼aComputer  science.
■650  4▼aMathematics.
■650  4▼aPhysics.
■650  4▼aQuantum  physics.
■653    ▼aNumerical  linear  algebra
■653    ▼aQuantum  computing
■653    ▼aQuantum  machine  learning
■653    ▼aQuantum-inspired  algorithms
■690    ▼a0984
■690    ▼a0405
■690    ▼a0605
■690    ▼a0599
■690    ▼a0800
■71020▼aUniversity  of  Washington▼bComputer  Science  and  Engineering.
■7730  ▼tDissertations  Abstracts  International▼g85-03B.
■773    ▼tDissertation  Abstract  International
■790    ▼a0250
■791    ▼aPh.D.
■792    ▼a2023
■793    ▼aEnglish
■85640▼uhttp://www.riss.kr/pdu/ddodLink.do?id=T16934770▼nKERIS▼z이  자료의  원문은  한국교육학술정보원에서  제공합니다.
■980    ▼a202402▼f2024