Amplitude Amplification for Optimization via Subdivided Phase Oracle

Naphan Benchasattabuse, Takahiko Satoh, Michal Hajdusek, Rodney Van Meter

研究成果: Conference contribution

1 被引用数 (Scopus)

抄録

We propose an algorithm using a modified variant of amplitude amplification to solve combinatorial optimization problems via the use of a subdivided phase oracle. Instead of dividing input states into two groups and shifting the phase equally for all states within the same group, the subdivided phase oracle changes the phase of each input state uniquely in proportion to their objective value. We provide visualization of how amplitudes change after each iteration of applying the subdivided phase oracle followed by conventional Grover diffusion in the complex plane. We then show via numerical simulation that for normal, skew normal, and exponential distribution of objective values, the algorithm can be used to amplify the probability of measuring the optimal solution to a significant degree independent of the search space size. In the case of skew normal and exponential distributions, this probability can be amplified to be close to unity, making our algorithm near deterministic. We then modify our algorithm in order to demonstrate how it can be extended to a broader set of objective value distributions. Finally, we discuss the speedup compared to classical schemes using the query complexity model, and show that our algorithm offers a significant advantage over these classical approaches.

本文言語English
ホスト出版物のタイトルProceedings - 2022 IEEE International Conference on Quantum Computing and Engineering, QCE 2022
出版社Institute of Electrical and Electronics Engineers Inc.
ページ22-30
ページ数9
ISBN(電子版)9781665491136
DOI
出版ステータスPublished - 2022
イベント3rd IEEE International Conference on Quantum Computing and Engineering, QCE 2022 - Broomfield, United States
継続期間: 2022 9月 182022 9月 23

出版物シリーズ

名前Proceedings - 2022 IEEE International Conference on Quantum Computing and Engineering, QCE 2022

Conference

Conference3rd IEEE International Conference on Quantum Computing and Engineering, QCE 2022
国/地域United States
CityBroomfield
Period22/9/1822/9/23

ASJC Scopus subject areas

  • 人工知能
  • 計算理論と計算数学
  • コンピュータ サイエンスの応用
  • 制御と最適化
  • 原子分子物理学および光学

フィンガープリント

「Amplitude Amplification for Optimization via Subdivided Phase Oracle」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。

引用スタイル