論文の概要: Quantum optimization with arbitrary connectivity using Rydberg atom
arrays
- arxiv url: http://arxiv.org/abs/2209.03965v1
- Date: Thu, 8 Sep 2022 18:00:00 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-27 07:44:09.133781
- Title: Quantum optimization with arbitrary connectivity using Rydberg atom
arrays
- Title(参考訳): rydberg原子アレイを用いた任意接続による量子最適化
- Authors: Minh-Thi Nguyen, Jin-Guo Liu, Jonathan Wurtz, Mikhail D. Lukin,
Sheng-Tao Wang, Hannes Pichler
- Abstract要約: 元の問題から明示的な写像を構築することにより、Rydberg配列に効率的にエンコードできる問題のクラスを拡張する。
任意の接続を持つグラフ上の最大重み付き独立集合、任意の接続または制限された接続を持つ2次非制約バイナリ最適化問題、整数分解など、いくつかの例を分析する。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Programmable quantum systems based on Rydberg atom arrays have recently been
used for hardware-efficient tests of quantum optimization algorithms [Ebadi et
al., Science, 376, 1209 (2022)] with hundreds of qubits. In particular, the
maximum independent set problem on the so-called unit-disk graphs, was shown to
be efficiently encodable in such a quantum system. Here, we extend the classes
of problems that can be efficiently encoded in Rydberg arrays by constructing
explicit mappings from the original computation problems to maximum weighted
independent set problems on unit-disk graphs, with at most a quadratic overhead
in the number of qubits. We analyze several examples, including: maximum
weighted independent set on graphs with arbitrary connectivity, quadratic
unconstrained binary optimization problems with arbitrary or restricted
connectivity, and integer factorization. Numerical simulations on small system
sizes indicate that the adiabatic time scale for solving the mapped problems is
strongly correlated with that of the original problems. Our work provides a
blueprint for using Rydberg atom arrays to solve a wide range of combinatorial
optimization problems with arbitrary connectivity, beyond the restrictions
imposed by the hardware geometry.
- Abstract(参考訳): Rydberg 原子配列に基づくプログラム可能な量子システムは、最近数百の量子ビットを持つ量子最適化アルゴリズム(Ebadi et al., Science, 376, 1209 (2022))のハードウェア効率試験に使用されている。
特に、いわゆる単位ディスクグラフ上の最大独立集合問題は、そのような量子系において効率的にエンコード可能であることを示した。
ここでは、元の計算問題から単位-ディスクグラフ上の最大重み付き独立集合問題への明示的なマッピングを構築して、rydberg配列で効率的に符号化できる問題のクラスを拡張し、少なくとも量子ビット数の2次オーバーヘッドを持つ。
例えば、任意の接続を持つグラフ上の最大重み付き独立集合、任意の接続または制限された接続を持つ2次非制約バイナリ最適化問題、整数分解などである。
小さなシステムサイズに関する数値シミュレーションは、マッピングされた問題を解くための断熱時間スケールが、元の問題のそれと強く相関していることを示している。
我々の研究は、ハードウェア幾何による制約を超えて、任意の接続で幅広い組合せ最適化問題を解決するために、rydberg atom配列を使用するための青写真を提供します。
関連論文リスト
- Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳(メタデータ) (2024-01-17T18:59:38Z) - Hardness of the Maximum Independent Set Problem on Unit-Disk Graphs and
Prospects for Quantum Speedups [9.927706464212168]
ライドバーグ原子配列は量子スピードアップの実証において主要な候補の一つである。
古典的解法を幅広く含む単位ディスクグラフ上での最大独立集合問題について検討する。
Union-Jackのような接続性を持つ準平面インスタンスは、最大数千のノードを数分で最適に処理できる。
論文 参考訳(メタデータ) (2023-07-18T17:16:42Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳(メタデータ) (2022-12-06T22:01:49Z) - Symmetric Tensor Networks for Generative Modeling and Constrained
Combinatorial Optimization [72.41480594026815]
ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。
これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。
本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
論文 参考訳(メタデータ) (2022-11-16T18:59:54Z) - Embedding the MIS problem for non-local graphs with bounded degree using
3D arrays of atoms [0.0]
最大独立集合(英: Maximum Independent Set、MIS)は、リンドバーグ原子配列に自然に符号化できるNPハード問題である。
我々は3次元原子配列に非局所グラフの大きな族を埋め込む決定論的かつ効率的な構成を提案する。
この構成は、古典的な効率的なエプシロン近似スキームが存在しない量子コンピュータ上のタスクに取り組むための最初の重要なステップである。
論文 参考訳(メタデータ) (2022-09-12T11:46:10Z) - Solving Larger Optimization Problems Using Parallel Quantum Annealing [0.0]
並列量子アニールとグラフ分解を組み合わせたハイブリッドアプローチにより、より大規模な最適化問題を正確に解けることを示す。
最大傾き問題を最大120ノードと6395エッジのグラフに適用する。
論文 参考訳(メタデータ) (2022-05-24T15:56:15Z) - 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) - Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
ヒルベルト空間全体の部分空間への発展を制限する混合作用素を構築するための枠組みを提案する。
我々は,「ワンホット」状態の部分空間を保存するために設計された「XY」ミキサーを,多くの計算基底状態によって与えられる部分空間の一般の場合に一般化する。
我々の分析は、現在知られているよりもCXゲートが少ない"XY"ミキサーのトロタライズも有効である。
論文 参考訳(メタデータ) (2022-03-11T17:19:26Z) - Quantum Optimization of Maximum Independent Set using Rydberg Atom
Arrays [39.76254807200083]
最大独立集合問題の解法として量子アルゴリズムを実験的に検討する。
問題の難易度は解の縮退と局所ミニマの数によって制御される。
最も難しいグラフでは、正確な解を見つける際に超線形量子スピードアップを観測する。
論文 参考訳(メタデータ) (2022-02-18T19:00:01Z) - Rydberg Quantum Wires for Maximum Independent Set Problems with
Nonplanar and High-Degree Graphs [0.7046417074932257]
我々は、非決定論的時間ハード(NP-hard)問題を解くために、Rydberg原子を用いて実験を行った。
補助原子を用いたRydberg量子ワイヤスキームを導入し、量子ビット原子の長距離ネットワークを設計する。
3次元(3次元)リードバーグ原子配列は、2次元アレイの本質的な限界を克服して構築される。
論文 参考訳(メタデータ) (2021-09-08T09:37:18Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳(メタデータ) (2021-07-08T17:59:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。