Fugu-MT 論文翻訳(概要): Solving boolean satisfiability problems with the quantum approximate optimization algorithm

論文の概要: Solving boolean satisfiability problems with the quantum approximate optimization algorithm

arxiv url: http://arxiv.org/abs/2208.06909v1
Date: Sun, 14 Aug 2022 20:39:48 GMT
ステータス: 処理完了
システム内更新日: 2023-01-31 03:55:14.279832
Title: Solving boolean satisfiability problems with the quantum approximate optimization algorithm
Title（参考訳）: 量子近似最適化アルゴリズムによるブール飽和問題の解法
Authors: Sami Boulebnane and Ashley Montanaro
Abstract要約: 量子コンピューティング問題とは対照的に,QAOAがハード制約満足度問題を解く能力について検討する。我々は,QAOAの平均成功確率を,満足度しきい値のランダムな式上で解析的に評価する。約14のアンザッツ層に対して、QAOAは高性能な古典解法のスケーリング性能と一致することがわかった。
参考スコア（独自算出の注目度）: 0.05076419064097732
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: The quantum approximate optimization algorithm (QAOA) is one of the most prominent proposed applications for near-term quantum computing. Here we study the ability of QAOA to solve hard constraint satisfaction problems, as opposed to optimization problems. We focus on the fundamental boolean satisfiability problem, in the form of random $k$-SAT. We develop analytic bounds on the average success probability of QAOA over random boolean formulae at the satisfiability threshold, as the number of variables $n$ goes to infinity. The bounds hold for fixed parameters and when $k$ is a power of 2. We complement these theoretical results with numerical results on the performance of QAOA for small $n$, showing that these match the limiting theoretical bounds closely. We then use these results to compare QAOA with leading classical solvers. In the case of random 8-SAT, we find that for around 14 ansatz layers, QAOA matches the scaling performance of the highest-performance classical solver we tested, WalkSATlm. For larger numbers of layers, QAOA outperforms WalkSATlm, with an ultimate level of advantage that is still to be determined. Our methods provide a framework for analysing the performance of QAOA for hard constraint satisfaction problems and finding further speedups over classical algorithms.
Abstract（参考訳）: 量子近似最適化アルゴリズム(QAOA)は、短期量子コンピューティングにおける最も顕著な応用の1つである。本稿では,最適化問題とは対照的に,制約満足度問題を解くqaoaの能力について検討する。我々は、ランダムな$k$-SATという形で、基本ブール整合性問題に焦点を当てる。我々は,変数数n$が無限に近づくにつれて,ランダムブール式に対するQAOAの平均成功確率に関する解析的境界を開発する。固定パラメータは有界であり、$k$ が 2 のパワーであるときである。これらの理論結果を, qaoa の性能に関する数値計算結果で補うことにより, 限界理論境界と密接に一致することを示す。次に、これらの結果を用いてQAOAと古典解法の比較を行う。ランダムな8-SATの場合、約14個のアンサッツ層に対して、QAOAは、我々がテストした最高性能の古典的ソルバ、WalkSATlmのスケーリング性能と一致している。多数のレイヤーに対して、QAOAはWalkSATlmより優れており、究極的に有利なレベルが決定される。本手法は,制約満足度問題に対するQAOAの性能解析と,古典的アルゴリズムのさらなる高速化を実現するためのフレームワークを提供する。

関連論文リスト

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)
Hybrid Classical-Quantum Simulation of MaxCut using QAOA-in-QAOA [0.0]
そこで本研究では,MaxCut問題のスケーラブルな解に対するQAOA2法の実装について述べる。 The limit of the Goemans-Williamson (GW) algorithm as a purely classical alternative to QAOA。最大33量子ビットの大規模シミュレーションの結果は、ある場合におけるQAOAの利点と実装の効率性を示す。
論文参考訳（メタデータ） (2024-06-25T09:02:31Z)
Quantum Approximate Optimisation for Not-All-Equal SAT [9.427635404752936]
変動量子アルゴリズムのQAOAを、満足度問題(SAT: Not-All-Equal SAT)の変種に適用する。両ソルバのランタイムは問題サイズとともに指数関数的にスケールするが,QAOAのスケーリングは回路深さが十分に大きい場合に小さくなることを示す。
論文参考訳（メタデータ） (2024-01-05T15:11:24Z)
Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem [8.738180371389097]
量子近似最適化アルゴリズム(QAOA)は、量子コンピュータにおける最適化問題を解くための主要な候補アルゴリズムである。本稿では,低自己相関二項列(LABS)問題に対するQAOAの広範な数値的な検討を行う。パラメータが固定されたQAOAのランタイムは、分岐とバウンドの解法よりも良くスケールする。
論文参考訳（メタデータ） (2023-08-04T14:17:21Z)
Amplitude amplification-inspired QAOA: Improving the success probability for solving 3SAT [55.78588835407174]
振幅増幅アルゴリズムは、可変代入を満たすために非構造化探索に適用することができる。 Quantum Approximate Optimization Algorithm (QAOA)は、ノイズのある中間量子デバイスのための3SATを解くための有望な候補である。振幅増幅によるQAOAの変種を導入し、3SATの成功確率を改善する。
論文参考訳（メタデータ） (2023-03-02T11:52:39Z)
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)
Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
我々は、様々なレベルの接続性を持つハードウェアアーキテクチャのための最適化回路により、期待されるリソース要求のスケーリングを定量化する。問題の大きさと問題グラフの次数で指数関数的に増大する。これらの問題は、ハードウェア接続性の向上や、より少ない回路層で高い性能を達成するQAOAの変更によって緩和される可能性がある。
論文参考訳（メタデータ） (2022-01-06T21:02:30Z)
Quantum Computational Phase Transition in Combinatorial Problems [0.966840768820136]
量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm, QAOA)は、量子コンピュータにおける離散最適化問題の近似解を求めることを目的としたアルゴリズムである。 SATのような難解な問題を解く際に,QAOAの計算位相遷移を同定する。本稿では,QAOAの性能に限界がある高問題密度領域が,実際はQAOAを利用するのに最適であることを示す。
論文参考訳（メタデータ） (2021-09-27T20:46:52Z)
Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
量子近似最適化アルゴリズム(RQAOA)をMAX-$k$-CUTに適用する方法を示す。任意のグラフに対するレベル-$1$QAOAとレベル-$1$RQAOAをシミュレートした,効率的な古典的シミュレーションアルゴリズムを構築する。
論文参考訳（メタデータ） (2020-11-26T18:22:21Z)
Evaluation of QAOA based on the approximation ratio of individual samples [0.0]
我々は、Max-Cut問題に適用されたQAOAの性能をシミュレートし、いくつかの古典的代替品と比較する。 QAOA計算複雑性理論のガイダンスが進化しているため、量子的優位性を求めるためのフレームワークを利用する。
論文参考訳（メタデータ） (2020-06-08T18:00:18Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。