論文の概要: Quantum Speedup of the Dispersion and Codebook Design Problems
- arxiv url: http://arxiv.org/abs/2406.07187v1
- Date: Tue, 11 Jun 2024 12:00:50 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-12 16:13:39.193454
- Title: Quantum Speedup of the Dispersion and Codebook Design Problems
- Title（参考訳）: 分散とコードブック設計問題の量子スピードアップ
- Authors: Kein Yukiyoshi, Taku Mikuriya, Hyeon Seok Rou, Giuseppe Thadeu Freitas de Abreu, Naoki Ishikawa,
- Abstract要約: 分散問題はNPハードに分類される最適化問題である。
本稿では,Grover Adaptive Search(GAS)量子アルゴリズムによる解を実現するために,最大値と最大値の分散問題の新しい定式化を提案する。
- 参考スコア（独自算出の注目度）: 6.735173690339397
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: We propose new formulations of max-sum and max-min dispersion problems that enable solutions via the Grover adaptive search (GAS) quantum algorithm, offering quadratic speedup. Dispersion problems are combinatorial optimization problems classified as NP-hard, which appear often in coding theory and wireless communications applications involving optimal codebook design. In turn, GAS is a quantum exhaustive search algorithm that can be used to implement full-fledged maximum-likelihood optimal solutions. In conventional naive formulations however, it is typical to rely on a binary vector spaces, resulting in search space sizes prohibitive even for GAS. To circumvent this challenge, we instead formulate the search of optimal dispersion problem over Dicke states, an equal superposition of binary vectors with equal Hamming weights, which significantly reduces the search space leading to a simplification of the quantum circuit via the elimination of penalty terms. Additionally, we propose a method to replace distance coefficients with their ranks, contributing to the reduction of the number of qubits. Our analysis demonstrates that as a result of the proposed techniques a reduction in query complexity compared to the conventional GAS using Hadamard transform is achieved, enhancing the feasibility of the quantum-based solution of the dispersion problem.
- Abstract（参考訳）: 本稿では,Grover Adaptive Search(GAS)量子アルゴリズムによる解を実現するために,最大値と最大値の分散問題の新しい定式化を提案する。
分散問題はNPハードに分類される組合せ最適化問題であり、コーディング理論や最適なコードブック設計を含む無線通信アプリケーションによく現れる。
言い換えると、GASは量子的排他的探索アルゴリズムであり、完全な最大形最適解を実装できる。
しかし、従来のナイーブな定式化では、二進ベクトル空間に依存するのが一般的であり、その結果、GASに対しても探索空間のサイズが禁止される。
この問題を回避するために、ディック状態に対する最適分散問題の探索を定式化し、同じハミング重みを持つ二進ベクトルの等重重畳を定式化し、ペナルティ項の排除による量子回路の単純化につながる探索空間を著しく減らした。
さらに,距離係数をランクに置き換える手法を提案し,量子ビット数の削減に寄与する。
提案手法により, 従来のアダマール変換を用いたGASと比較して, クエリ複雑性の低減が達成され, 分散問題の量子ベース解の実現可能性が高まった。
関連論文リスト
- Quantum Speedup for the Quadratic Assignment Problem [6.106029308649016]
そこで我々は,Dicke状態演算子を用いたGrover Adaptive Search (GAS)を用いて,二次代入問題の探索空間を小さくすることができることを示す。
また、GASの位相ゲートをZ軸の回転ゲートに置き換えることで、ペナルティを伴わずに量子回路を簡素化できることを示す。
論文 参考訳（メタデータ） (2024-10-16T03:00:37Z) - Compressed space quantum approximate optimization algorithm for constrained combinatorial optimization [6.407238428292173]
圧縮された空間を設計する手法を導入し,その実現可能な解空間を元より少ない量子ビットで表現する。
次に、この縮小空間内の準最適解を求める圧縮空間 QAOA を提案する。
論文 参考訳（メタデータ） (2024-10-08T05:48:46Z) - Quantum Semidefinite Programming with Thermal Pure Quantum States [0.5639904484784125]
行列乗法重み付けアルゴリズムの量子化'''は、古典的アルゴリズムよりも2次的に高速なSDPの近似解が得られることを示す。
この量子アルゴリズムを改良し、ギブス状態サンプリング器を熱純量子(TPQ)状態に置き換えることで、同様のスピードアップが得られることを示す。
論文 参考訳（メタデータ） (2023-10-11T18:00:53Z) - Accelerating Grover Adaptive Search: Qubit and Gate Count Reduction Strategies with Higher-Order Formulations [2.9564164925541503]
グロバー適応探索(Grover Adaptive Search、GAS)は、二項最適化問題の解法として設計された量子抜粋探索アルゴリズムである。
キュービット数と必要ゲート数を同時に削減できる高階二項式を提案する。
論文 参考訳（メタデータ） (2023-08-03T07:20:24Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Quantum-inspired optimization for wavelength assignment [51.55491037321065]
波長割当問題を解くための量子インスピレーションアルゴリズムを提案し,開発する。
本研究は,電気通信における現実的な問題に対する量子インスパイアされたアルゴリズムの活用の道筋をたどるものである。
論文 参考訳（メタデータ） (2022-11-01T07:52:47Z) - Qubit Reduction and Quantum Speedup for Wireless Channel Assignment
Problem [2.840363325289377]
NPハード無線チャネル割り当て問題を高階非制約バイナリ最適化(HUBO)として定式化する方法を提案する。
我々は、チャネルインデックスの昇降二進符号化を考案し、特定の量子回路を構築し、Grover Adaptive Search(GAS)に必要なキュービットとゲートの正確な数を導出する。
解析により,提案するHUBOの定式化により,従来の2次定式化と比較して,キュービット数やクエリの複雑さが著しく減少することが明らかとなった。
論文 参考訳（メタデータ） (2022-08-10T06:59:43Z) - Bregman divergence based em algorithm and its application to classical
and quantum rate distortion theory [61.12008553173672]
本稿では,Bregman分散系における指数サブファミリーと混合サブファミリー間のBregman分散の最小化問題に対処する。
このアルゴリズムを量子設定を含む歪みとその変種の評価に適用する。
論文 参考訳（メタデータ） (2022-01-07T13:33:28Z) - Quadratic Unconstrained Binary Optimisation via Quantum-Inspired
Annealing [58.720142291102135]
本稿では,2次非制約二項最適化の事例に対する近似解を求める古典的アルゴリズムを提案する。
我々は、チューニング可能な硬さと植え付けソリューションを備えた大規模問題インスタンスに対して、我々のアプローチをベンチマークする。
論文 参考訳（メタデータ） (2021-08-18T09:26:17Z) - Polynomial unconstrained binary optimisation inspired by optical
simulation [52.11703556419582]
制約のないバイナリ最適化の問題を解決するために,光コヒーレントIsingマシンにヒントを得たアルゴリズムを提案する。
提案アルゴリズムを既存のPUBOアルゴリズムに対してベンチマークし,その優れた性能を観察する。
タンパク質の折り畳み問題や量子化学問題へのアルゴリズムの適用は、PUBO問題による電子構造問題の近似の欠点に光を当てる。
論文 参考訳（メタデータ） (2021-06-24T16:39:31Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。
また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
論文 参考訳（メタデータ） (2020-09-15T18:17:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。