論文の概要: Optimization of Quadratic Constraints by Decoded Quantum Interferometry
- arxiv url: http://arxiv.org/abs/2510.08061v1
- Date: Thu, 09 Oct 2025 10:49:17 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-10 17:54:15.022033
- Title: Optimization of Quadratic Constraints by Decoded Quantum Interferometry
- Title（参考訳）: Decoded Quantum Interferometry による二次制約の最適化
- Authors: Daniel Cohen Hillel,
- Abstract要約: Decoded Quantum Interferometry (DQI) を2次制約を含む最適化問題に拡張する。
我々は、最大QDSATに対してDQI状態を作成するための効率的なアルゴリズムを提供する。
2次OPIがmax-QUADSATのインスタンスであることを示し、アルゴリズムを用いて最適化する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: A recent paper by Jordan et al. introduced Decoded Quantum Interferometry (DQI), a novel quantum algorithm that uses the quantum Fourier transform to reduce linear optimization problems -- max-XORSAT and max-LINSAT -- to decoding problems. In this paper, we extend DQI to optimization problems involving quadratic constraints, which we call max-QUADSAT. Leveraging a connection to quadratic Gauss sums, we give an efficient algorithm to prepare the DQI state for max-QUADSAT. To demonstrate that our algorithm achieves a quantum advantage, we introduce the Quadratic Optimal Polynomial Intersection (quadratic-OPI) problem, a restricted variant of OPI for which, to our knowledge, the standard DQI framework offers no algorithmic speedup. We show that quadratic-OPI is an instance of max-QUADSAT and use our algorithm to optimize it. Lastly, we present a new generalized proof of the "semicircle law" for the fraction of satisfied constraints, generalizing it to any DQI state of problems where the distribution of the number of satisfied constraints for a random assignment is sufficiently close to a binomial distribution. This condition holds exactly for the DQI state of max-LINSAT, and approximately holds in the max-QUADSAT case, with the approximation becoming exponentially better as the problem size increases. This establishes performance guarantees for our algorithm.
- Abstract（参考訳）: Jordanらが最近発表したDecoded Quantum Interferometry (DQI)は、量子フーリエ変換を用いて線形最適化問題(max-XORSATとmax-LINSAT)をデコード問題に還元する新しい量子アルゴリズムである。
本稿ではDQIを拡張して2次制約を含む問題を最適化する。
2次ガウス和への接続を利用して、最大QDSATに対してDQI状態を作成する効率的なアルゴリズムを与える。
このアルゴリズムが量子優位性を実現することを証明するために,OPIの制限された変種である四進多言語間(四進法-OPI)問題を導入し,その上で,標準のDQIフレームワークはアルゴリズムの高速化を提供しない。
2次OPIがmax-QUADSATのインスタンスであることを示し、アルゴリズムを用いて最適化する。
最後に,制約分数に対する「半円法則」を新たに一般化し,ランダムな代入に対する制約数の分布が二項分布に十分近いような問題DQI状態に一般化する。
この条件は、max-LINSAT の DQI 状態に対して正確に成り立ち、max-QUADSAT の場合では、問題のサイズが大きくなるにつれて近似が指数関数的に良くなる。
これにより,アルゴリズムの性能保証が確立される。
関連論文リスト
- Decoded Quantum Interferometry Requires Structure [1.121518046252855]
MAX-$k$-XOR-SATの典型例における復号量子干渉法(DQI)の性能について検討した。
DQI は、多くの標準的な符号のアンサンブルに対して、量子ワッサーシュタイン計量の下ではおよそリプシッツであることが証明されている。
論文 参考訳（メタデータ） (2025-09-18T00:51:36Z) - Learning Feasible Quantum States for Quadratic Constrained Binary Optimization Problems [41.23247424467223]
我々はQCBOの制約を満たす量子状態の同値重ね合わせを生成する変動的アプローチを開発する。
結果として生じる同値な重ね合わせは、QUBO/QCBOを解く量子アルゴリズムの初期状態として使用できる。
論文 参考訳（メタデータ） (2025-08-04T16:44:53Z) - Optimization by Decoded Quantum Interferometry [42.169154389732036]
Decoded Quantum Interferometry (DQI) という量子アルゴリズムを導入する。
有限体上のデータに近似するために、DQIは我々の知るどの時間よりも良い近似比を達成する。
論文 参考訳（メタデータ） (2024-08-15T17:47:42Z) - 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) - Quantum Approximate Optimisation for Not-All-Equal SAT [9.427635404752936]
変動量子アルゴリズムのQAOAを、満足度問題(SAT: Not-All-Equal SAT)の変種に適用する。
両ソルバのランタイムは問題サイズとともに指数関数的にスケールするが,QAOAのスケーリングは回路深さが十分に大きい場合に小さくなることを示す。
論文 参考訳（メタデータ） (2024-01-05T15:11:24Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。
補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。
各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文 参考訳（メタデータ） (2022-06-30T03:15:23Z) - QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum
machines [81.4597482536073]
量子近似最適化アルゴリズム(QAOAs)は、量子マシンのパワーを利用し、断熱進化の精神を継承する。
量子マシンを用いて任意の大規模MaxCut問題を解くためにQAOA-in-QAOA(textQAOA2$)を提案する。
提案手法は,大規模最適化問題におけるQAOAsの能力を高めるために,他の高度な戦略にシームレスに組み込むことができる。
論文 参考訳（メタデータ） (2022-05-24T03:49:10Z) - Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
この研究は、未知の報酬関数が非可逆であるようなバンドイット問題の大群を考察する。
我々のアルゴリズムは、非常に一般化されたゼロ階最適化のパラダイムに基づいている。
標準的な楽観的アルゴリズムは次元因子によって準最適であることを示す。
論文 参考訳（メタデータ） (2021-07-09T16:04:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。