論文の概要: Optimization by Decoded Quantum Interferometry

• arxiv url: http://arxiv.org/abs/2408.08292v1
• Date: Thu, 15 Aug 2024 17:47:42 GMT
• ステータス: 処理完了
• システム内更新日: 2024-08-16 13:05:43.289129
• Title: Optimization by Decoded Quantum Interferometry
• Title（参考訳）: デコード量子干渉計による最適化
• Authors: Stephen P. Jordan, Noah Shutty, Mary Wootters, Adam Zalcman, Alexander Schmidhuber, Robbie King, Sergei V. Isakov, Ryan Babbush,
• Abstract要約: 本稿では,古典的復号化問題に対する古典的最適化問題を減じるための量子アルゴリズムを提案する。 DQIは、既知の量子時間古典アルゴリズムよりも近似比が良いことを示す。
• 参考スコア（独自算出の注目度）: 43.55132675053983
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce 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. DQI reduces sparse max-XORSAT to decoding LDPC codes, which can be achieved using powerful classical algorithms such as Belief Propagation (BP). As an initial benchmark, we compare DQI using belief propagation decoding against classical optimization via simulated annealing. In this setting we present evidence that, for a certain family of max-XORSAT instances, DQI with BP decoding achieves a better approximation ratio on average than simulated annealing, although not better than specialized classical algorithms tailored to those instances. We also analyze a combinatorial optimization problem corresponding to finding polynomials that intersect the maximum number of points. There, DQI efficiently achieves a better approximation ratio than any polynomial-time classical algorithm known to us, thus realizing an apparent exponential quantum speedup. Finally, we show that the problem defined by Yamakawa and Zhandry in order to prove an exponential separation between quantum and classical query complexity is a special case of the optimization problem efficiently solved by DQI.
• Abstract（参考訳）: 目的関数のフーリエスペクトルの構造を利用して、古典的最適化問題を古典的復号問題に還元する量子アルゴリズムであるDecoded Quantum Interferometry (DQI)を導入する。 DQIは、Sparse max-XORSATをLDPCコードに還元し、Belief Propagation (BP)のような強力な古典的アルゴリズムで実現できる。 最初のベンチマークとして、シミュレートされたアニールによる古典的最適化に対して、DQIを信念伝搬復号法を用いて比較する。 この設定では、最大XORSATインスタンスの特定のファミリーに対して、BPデコードを持つDQIは、それらのインスタンスに合わせた特殊な古典的アルゴリズムよりも、シミュレーションアニーリングよりも平均的な近似比が良いことを示す。 また、最大点数と交差する多項式の探索に対応する組合せ最適化問題を解析する。 そこで、DQIは、我々の既知の多項式時間古典アルゴリズムよりも効率よく近似比を達成し、明らかな指数的量子スピードアップを実現する。 最後に、量子と古典的なクエリの複雑性を指数的に分離することを証明するために、山川とZhandryによって定義された問題は、DQIによって効率的に解かれる最適化問題の特別な場合であることを示す。

関連論文リスト

• Classical optimization with imaginary time block encoding on quantum computers: The MaxCut problem [2.4968861883180447]
  対角ハミルトニアンの基底状態解を見つけることは、金融、物理学、計算機科学など多くの分野に関心を持つ理論的および実践的な問題の両方に関係している。 ここでは、新しいブロック符号化方式を用いて、これらの問題の基底状態を取得し、この手法をMaxCutに例証として応用する。
  論文  参考訳（メタデータ） (2024-11-16T08:17:36Z)
• Performance Benchmarking of Quantum Algorithms for Hard Combinatorial Optimization Problems: A Comparative Study of non-FTQC Approaches [0.0]
  本研究は、4つの異なる最適化問題にまたがっていくつかの非フォールト耐性量子コンピューティングアルゴリズムを体系的にベンチマークする。 我々のベンチマークには、変分量子固有解法など、ノイズの多い中間スケール量子(NISQ)アルゴリズムが含まれている。 以上の結果から,FTQC以外のアルゴリズムは全ての問題に対して最適に動作しないことが明らかとなり,アルゴリズム戦略の調整の必要性が浮き彫りになった。
  論文  参考訳（メタデータ） (2024-10-30T08:41:29Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• Digitized-counterdiabatic quantum approximate optimization algorithm [3.0638256603183054]
  そこで本研究では, 短絡を用いて拡張したQAOAのディジタル化バージョンを提案する。 我々は,Isingモデル,古典最適化問題,P-スピンモデルにディジタルカウンセバティックQAOAを適用し,すべての場合において標準QAOAより優れていることを示す。
  論文  参考訳（メタデータ） (2021-07-06T17:57:32Z)
• Accelerating variational quantum algorithms with multiple quantum processors [78.36566711543476]
  変分量子アルゴリズム(VQA)は、特定の計算上の利点を得るために、短期量子マシンを利用する可能性がある。 現代のVQAは、巨大なデータを扱うために単独の量子プロセッサを使用するという伝統によって妨げられている、計算上のオーバーヘッドに悩まされている。 ここでは、この問題に対処するため、効率的な分散最適化手法であるQUDIOを考案する。
  論文  参考訳（メタデータ） (2021-06-24T08:18:42Z)
• Classically optimal variational quantum algorithms [0.0]
  変分量子アルゴリズム(VQA)のようなハイブリッド量子古典アルゴリズムは、NISQコンピュータ上での実装に適している。 このレターでは、VQAの暗黙的なステップを拡張します。古典的なプリ計算サブルーチンは、古典的なアルゴリズムを非自明に使用して、問題インスタンス固有の変動量子回路を単純化、変換、特定することができます。
  論文  参考訳（メタデータ） (2021-03-31T13:33:38Z)
• Adaptive pruning-based optimization of parameterized quantum circuits [62.997667081978825]
  Variisyハイブリッド量子古典アルゴリズムは、ノイズ中間量子デバイスの使用を最大化する強力なツールである。 我々は、変分量子アルゴリズムで使用されるそのようなアンサーゼを「効率的な回路訓練」(PECT)と呼ぶ戦略を提案する。 すべてのアンサッツパラメータを一度に最適化する代わりに、PECTは一連の変分アルゴリズムを起動する。
  論文  参考訳（メタデータ） (2020-10-01T18:14:11Z)
• Warm-starting quantum optimization [6.832341432995627]
  最適化問題の緩和解に対応する初期状態を用いて量子最適化を温める方法について論じる。 これにより、量子アルゴリズムは古典的なアルゴリズムの性能保証を継承することができる。 同じ考えを他のランダム化ラウンドスキームや最適化問題に適用するのは簡単である。
  論文  参考訳（メタデータ） (2020-09-21T18:00:09Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。 また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
  論文  参考訳（メタデータ） (2020-09-15T18:17:27Z)
• Cross Entropy Hyperparameter Optimization for Constrained Problem Hamiltonians Applied to QAOA [68.11912614360878]
  QAOA(Quantum Approximate Optimization Algorithm)のようなハイブリッド量子古典アルゴリズムは、短期量子コンピュータを実用的に活用するための最も奨励的なアプローチの1つである。 このようなアルゴリズムは通常変分形式で実装され、古典的な最適化法と量子機械を組み合わせて最適化問題の優れた解を求める。 本研究では,クロスエントロピー法を用いてランドスケープを形作り,古典的パラメータがより容易により良いパラメータを発見でき,その結果,性能が向上することを示す。
  論文  参考訳（メタデータ） (2020-03-11T13:52:41Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。