125th RQC Seminar

• 講演者

  Dr. Stephen Jordan
  ( Google )

• 日程

  2024年7月29日（月） 16:00-17:00 （4:00 p.m.-5:00 p.m.）

• 開催場所

  ハイブリッド（ZOOM・ Wako Main Research 3F 345-347 Seminar Room/ 研究本館3階 セミナー室(345-347) C01）

• 講演タイトル

  Optimization by Decoded Quantum Interferometry

• お問合せ

  rqc_info[at]ml.riken.jp

講演概要
In this talk I will describe Decoded Quantum Interferometry (DQI), a quantum algorithm for reducing classical optimization problems to classical decoding problems by exploiting structure in the Fourier spectrum of the objective function. For a problem of optimal polynomial intersection we believe DQI achieves an exponential quantum speedup. We also investigate the application of DQI to average-case instances of max-k-XORSAT. DQI reduces max-k-XORSAT to decoding LDPC codes, which can be achieved using powerful classical algorithms such as belief propagation. As an initial investigation, we benchmark DQI using belief propagation decoding against classical optimization via simulated annealing. In this setting we identify a family of max-XORSAT instances where DQI achieves a better approximation ratio than simulated annealing, although not better than specialized classical algorithms tailored to those instances. The recent quantum query complexity speedup of Yamakawa and Zhandry can also be obtained as a special case of DQI. This is joint work with Noah Shutty, Mary Wootters, Adam Zalcman, and Ryan Babbush.