論文の概要: Quantum-Relaxation Based Optimization Algorithms: Theoretical Extensions
- arxiv url: http://arxiv.org/abs/2302.09481v1
- Date: Sun, 19 Feb 2023 05:31:21 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-21 18:18:57.399030
- Title: Quantum-Relaxation Based Optimization Algorithms: Theoretical Extensions
- Title（参考訳）: 量子緩和に基づく最適化アルゴリズム:理論的拡張
- Authors: Kosei Teramoto and Rudy Raymond and Eyuri Wakakuwa and Hiroshi Imai
- Abstract要約: 量子ランダムアクセスコード(QRAC)は、バイナリ最適化の複数の変数を1量子ビットでエンコードする。
本研究では3つの古典的ビットを2つの量子ビットにエンコードする別のQRACを用いて量子緩和を拡張する。
また,新しい量子緩和法を設計し,量子ビット間圧縮比を常に2ドル(約2,300円)で保証する。
- 参考スコア（独自算出の注目度）: 10.44923461503086
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Quantum Random Access Optimizer (QRAO) is a quantum-relaxation based
optimization algorithm proposed by Fuller et al. that utilizes Quantum Random
Access Code (QRAC) to encode multiple variables of binary optimization in a
single qubit. The approximation ratio bound of QRAO for the maximum cut problem
is $0.555$ if the bit-to-qubit compression ratio is $3$x, while it is $0.625$
if the compression ratio is $2$x, thus demonstrating a trade-off between space
efficiency and approximability. In this research, we extend the
quantum-relaxation by using another QRAC which encodes three classical bits
into two qubits (the bit-to-qubit compression ratio is $1.5$x) and obtain its
approximation ratio for the maximum cut problem as $0.722$. Also, we design a
novel quantum relaxation that always guarantees a $2$x bit-to-qubit compression
ratio which is unlike the original quantum relaxation of Fuller~et~al. We
analyze the condition when it has a non-trivial approximation ratio bound
$\left(>\frac{1}{2}\right)$. We hope that our results lead to the analysis of
the quantum approximability and practical efficiency of the quantum-relaxation
based approaches.
- Abstract（参考訳）: 量子ランダムアクセス最適化アルゴリズム(Quantum Random Access Optimizer, QRAO)は、フラーらによって提案された量子ランダムアクセス符号(QRAC)を用いて、単一量子ビットでバイナリ最適化の複数の変数を符号化する最適化アルゴリズムである。
最大カット問題に対するqraoの近似比率は、ビット対キュービットの圧縮比が3ドルxである場合0.555ドル、圧縮比が2ドルxであれば0.625ドルであり、空間効率と近似可能性の間のトレードオフを示す。
本研究では,3つの古典ビットを2つの量子ビット(ビット対量子ビット圧縮比は1.5$x)にエンコードする別のQRACを用いて量子緩和を拡張し,最大カット問題に対する近似比を0.722$とする。
また、フラー=et~alの当初の量子緩和と異なり、常に2xビット対量子ビットの圧縮比を保証する新しい量子緩和も設計する。
非自明な近似比が$\left(>\frac{1}{2}\right)$ のときの状態を分析する。
この結果が量子近似可能性の解析と,量子緩和に基づくアプローチの実用化に繋がることを期待している。
関連論文リスト
- Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games [102.46640028830441]
最適行列乗算重み更新(OMMWU)アルゴリズムを導入し,平均収束複雑性を$mathcalO(d/epsilon)$ to $epsilon$-Nash equilibriaとする。
この二次的なスピードアップは、量子ゼロサムゲームにおける$epsilon$-Nash平衡の計算のための新しいベンチマークを定めている。
論文 参考訳（メタデータ） (2023-11-17T20:38:38Z) - Alleviating the quantum Big-$M$ problem [0.237499051649312]
古典的には "Big-$M$" 問題として知られており、物理的エネルギースケールに影響を与える。
我々は、量子ビッグ-M$問題を体系的に包含し、最適の$M$を見つけるのにNPハードネスを明らかにする。
本稿では,SDP緩和に基づく実用的な翻訳アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-07-19T18:00:05Z) - QAOA with $N\cdot p\geq 200$ [2.926192989090622]
我々は、高Ncdot p$のハイブリッド量子/古典最適化アルゴリズムの実行を実演する。
これは、これまでハードウェア上で実証された最高額の$Ncdot p$だ。
論文 参考訳（メタデータ） (2023-03-03T16:32:49Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Exploring the neighborhood of 1-layer QAOA with Instantaneous Quantum
Polynomial circuits [0.0]
我々は1層QAOA回路をパラメータ化即時量子多項式回路のより大きなクラスに埋め込む。
最適パラメータを求めるために解析式を用いることで、我々のプロトコルはバレンプラトーやハードウェアノイズに対して堅牢である。
我々のプロトコルは、最近リリースされたQuantinuum H2トラップイオン量子ハードウェアとエミュレータの1層QAOAよりも優れている。
論文 参考訳（メタデータ） (2022-10-11T15:16:44Z) - 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) - Sampling Frequency Thresholds for Quantum Advantage of Quantum
Approximate Optimization Algorithm [0.7046417074932257]
量子近似最適化アルゴリズム(QAOA)の性能を最先端の古典解法と比較する。
古典的解法は線形時間複雑性において高品質な近似解を生成することができる。
異なるグラフ、重み付けされたMaxCut、最大独立集合、および3-SATといった他の問題は、短期量子デバイスにおける量子優位性を達成するのに適しているかもしれない。
論文 参考訳（メタデータ） (2022-06-07T20:59:19Z) - 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) - Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
本稿では,最適化問題における短期量子優位性の提案に着想を得た高忠実度ゲートセットを提案する。
3つのトランペット四重項のコヒーレントな多レベル制御を編成することにより、自然な3量子ビット計算ベースで作用する決定論的連続角量子位相ゲートの族を合成する。
論文 参考訳（メタデータ） (2021-08-03T17:49:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。