論文の概要: Noisy intermediate-scale quantum computing algorithm for solving an
$n$-vertex MaxCut problem with log($n$) qubits
- arxiv url: http://arxiv.org/abs/2110.10788v3
- Date: Wed, 15 Feb 2023 16:06:33 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-10 23:42:27.447448
- Title: Noisy intermediate-scale quantum computing algorithm for solving an
$n$-vertex MaxCut problem with log($n$) qubits
- Title（参考訳）: log(n$) qubitsを用いたn$-vertex maxcut問題を解くための雑音中規模量子コンピューティングアルゴリズム
- Authors: Marko J. Ran\v{c}i\'c
- Abstract要約: 本稿ではQAOAと比較して指数的に少ない量子ビットを用いる新しい量子最適化アルゴリズムを提案する。
これらの結果は、ゲートベースの量子コンピュータにおける最先端の実験と比較して、グラフサイズが40%増加することを示している。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Quantum computers are devices, which allow more efficient solutions of
problems as compared to their classical counterparts. As the timeline to
developing a quantum-error corrected computer is unclear, the quantum computing
community has dedicated much attention to developing algorithms for currently
available noisy intermediate-scale quantum computers (NISQ). Thus far, within
NISQ, optimization problems are one of the most commonly studied and are quite
often tackled with the quantum approximate optimization algorithm (QAOA). This
algorithm is best known for computing graph partitions with a maximal
separation of edges (MaxCut), but can easily calculate other problems related
to graphs. Here, I present a novel quantum optimization algorithm, which uses
exponentially less qubits as compared to the QAOA while requiring a
significantly reduced number of quantum operations to solve the MaxCut problem.
Such an improved performance allowed me to partition graphs with 32 nodes on
publicly available 5 qubit gate-based quantum computers without any
preprocessing such as division of the graph into smaller subgraphs. These
results represent a 40% increase in graph size as compared to state-of-art
experiments on gate-based quantum computers such as Google Sycamore. The
obtained lower bound is 54.9% on the solution for actual hardware benchmarks
and 77.6% on ideal simulators of quantum computers. Furthermore, large-scale
optimization problems represented by graphs of a 128 nodes are tackled with
simulators of quantum computers, again without any predivision into smaller
subproblems and a lower solution bound of 67.9% is achieved. The study
presented here paves way to using powerful genetic optimizer in synergy with
quantum computers
- Abstract（参考訳）: 量子コンピュータは、従来のコンピュータに比べてより効率的な問題の解法を可能にするデバイスである。
量子エラー修正コンピュータの開発スケジュールは不明だが、量子コンピューティングコミュニティは現在利用可能なノイズの多い中間規模量子コンピュータ(NISQ)のためのアルゴリズムの開発に多くの注意を払っている。
これまでのところ、nisqでは最適化問題は最もよく研究されており、量子近似最適化アルゴリズム (quantum approximation optimization algorithm,qaoa) に取り組まれていることが多い。
このアルゴリズムは、エッジの最大分離(MaxCut)を持つグラフ分割の計算でよく知られているが、グラフに関連する他の問題を簡単に計算できる。
本稿では,qaoaと比較して指数関数的に少ない量子ビットを用いる新しい量子最適化アルゴリズムを提案する。
このようなパフォーマンスの改善により、公開可能な5量子ビットゲートベースの量子コンピュータ上で、32ノードのグラフを分割できるようになりました。
これらの結果は、Google Sycamoreのようなゲートベースの量子コンピュータにおける最先端の実験と比較して、グラフサイズが40%増加することを示している。
得られた下限は、実際のハードウェアベンチマークのソリューションでは54.9%、理想的な量子コンピュータのシミュレータでは77.6%である。
さらに、128ノードのグラフで表される大規模な最適化問題は、量子コンピュータのシミュレータに取り組み、再びより小さなサブプロブレムに分割することなく67.9%の低い解が得られる。
量子コンピュータのシナジーにおける強力な遺伝的最適化手法に関する研究
関連論文リスト
- A Variational Qubit-Efficient MaxCut Heuristic Algorithm [0.0]
グラフサイズに対して対数的な量子ビット数を必要とする新しい変分Qubit-Efficient MaxCut (QEMC)アルゴリズムを提案する。
実超伝導ハードウェア上では最大32ノード(5キュービット)のグラフインスタンスに対して,ノイズレスシミュレーションを用いて最大2048ノード(11キュービット)のグラフに対して,最先端の性能を示す。
論文 参考訳（メタデータ） (2023-08-20T23:06:18Z) - Large-scale quantum approximate optimization on non-planar graphs with machine learning noise mitigation [0.46040036610482665]
誤差軽減は、ノイズの多いデバイスが有意義に実行できる量子回路のサイズを拡大する。
機械学習に基づく誤差軽減により最大40ノードの非平面ランダム正規グラフ上で量子近似最適化アルゴリズム(QAOA)を示す。
論文 参考訳（メタデータ） (2023-07-26T18:00:07Z) - NISQ-compatible approximate quantum algorithm for unconstrained and
constrained discrete optimization [0.0]
本稿では,振幅符号化を用いたハードウェア効率の高い回路に対する近似勾配型量子アルゴリズムを提案する。
目的関数にペナルティ項を加えることなく, 単純な線形制約を回路に直接組み込むことができることを示す。
論文 参考訳（メタデータ） (2023-05-23T16:17:57Z) - Solving various NP-Hard problems using exponentially fewer qubits on a
Quantum Computer [0.0]
NPハード問題は、一般時間アルゴリズムで正確に解けるとは考えられていない。
本稿では,問題のサイズに応じて対数的にスケールする独自手法を構築した。
これらのアルゴリズムは、100以上のノードのグラフサイズを持つ量子シミュレータと、256のグラフサイズまでの実際の量子コンピュータでテストされる。
論文 参考訳（メタデータ） (2023-01-17T16:03:33Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Iterative Qubits Management for Quantum Index Searching in a Hybrid
System [56.39703478198019]
IQuCSは、量子古典ハイブリッドシステムにおけるインデックス検索とカウントを目的としている。
我々はQiskitでIQuCSを実装し、集中的な実験を行う。
その結果、量子ビットの消費を最大66.2%削減できることが示されている。
論文 参考訳（メタデータ） (2022-09-22T21:54:28Z) - 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) - Multiple Query Optimization using a Hybrid Approach of Classical and
Quantum Computing [1.7077661158850292]
データ集約的な問題領域において重要なNPハード問題である多重クエリ最適化問題(MQO)に取り組む。
ゲート型量子コンピュータ上でMQOを解くために,新しい古典量子アルゴリズムを提案する。
提案アルゴリズムでは, クビット効率が99%に近づき, ほぼ2倍に向上した。
論文 参考訳（メタデータ） (2021-07-22T08:12:49Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳（メタデータ） (2021-07-08T17:59:55Z) - Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
マルチバスグラフ複雑性と非線形活性化関数の2つの革新の恩恵を受ける新しい変分量子アルゴリズムを導入する。
その結果,最適化性能が向上し,有効景観が2つ向上し,測定の進歩が減少した。
論文 参考訳（メタデータ） (2021-06-24T20:16:02Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。
また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
論文 参考訳（メタデータ） (2020-09-15T18:17:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。