論文の概要: Finding Small and Large k-Clique Instances on a Quantum Computer

• arxiv url: http://arxiv.org/abs/2008.12525v1
• Date: Fri, 28 Aug 2020 07:40:44 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-04 11:51:10.465916
• Title: Finding Small and Large k-Clique Instances on a Quantum Computer
• Title（参考訳）: 量子コンピュータによる小型・大型k-Cliqueインスタンスの探索
• Authors: Sara Ayman Metwalli, Francois Le Gall, Rodney Van Meter
• Abstract要約: 三角フィニング問題とそのNP-ハードk-斜め一般化に対するゲートベースアプローチを提案する。 本研究では,雑音型中間規模量子コンピュータ(NISQ)デバイス上での短期的実装のための定数要因と,量子コンピュータの長期使用評価における問題のスケーリングについて検討する。
• 参考スコア（独自算出の注目度）: 1.1602089225841632
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Algorithms for triangle-finding, the smallest nontrivial instance of the k-clique problem, have been proposed for quantum computers. Still, those algorithms assume the use of fixed access time quantum RAM (QRAM). We present a practical gate-based approach to both the triangle-finding problem and its NP-hard k-clique generalization. We examine both constant factors for near-term implementation on a Noisy Intermediate Scale Quantum computer (NISQ) device, and the scaling of the problem to evaluate long-term use of quantum computers. We compare the time complexity and circuit practicality of the theoretical approach and actual implementation. We propose and apply two different strategies to the k-clique problem, examining the circuit size of Qiskit implementations. We analyze our implementations by simulating triangle finding with various error models, observing the effect on damping the amplitude of the correct answer, and compare to execution on six real IBMQ machines. Finally, we estimate the date when the methods proposed can run effectively on an actual device based on IBM's quantum volume exponential growth forecast and the results of our error analysis.
• Abstract（参考訳）: k-クリケ問題の最小の非自明な例である三角探索アルゴリズムが量子コンピュータで提案されている。 それでもこれらのアルゴリズムは、固定アクセス時間量子RAM(QRAM)を前提としている。 三角フィニング問題とNP-ハード k-clique 一般化に対する実用的なゲートベース手法を提案する。 ノイズの多い中間スケール量子コンピュータ (nisq) デバイス上での短期的実装のための定数要因と, 量子コンピュータの長期使用を評価するための問題のスケーリングについて検討した。 理論的アプローチと実際の実装の時間複雑性と回路実用性を比較した。 我々は,Qiskit実装の回路サイズについて検討し,k-clique問題に対して2つの異なる戦略を提案し,適用する。 我々は,様々な誤差モデルを用いて三角形探索をシミュレートし,正解の振幅を減衰させる効果を観察し,実際の6台のIBMQマシン上での実行との比較を行った。 最後に,IBMの量子体積指数成長予測と誤差解析の結果に基づいて,提案手法が実装置上で有効に動作可能な日時を推定する。

関連論文リスト

• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  d可変RZゲートとG-dクリフォードゲートを含む量子回路を与えられた場合、学習者は純粋に古典的な推論を行い、その線形特性を効率的に予測できるだろうか? 我々は、d で線形にスケーリングするサンプルの複雑さが、小さな予測誤差を達成するのに十分であり、対応する計算の複雑さは d で指数関数的にスケールすることを証明する。 我々は,予測誤差と計算複雑性をトレードオフできるカーネルベースの学習モデルを考案し,多くの実践的な環境で指数関数からスケーリングへ移行した。
  論文  参考訳（メタデータ） (2024-08-22T08:21:28Z)
• Compact quantum algorithms for time-dependent differential equations [0.0]
  我々は、ユニタリの線形結合に基づくアイデアに基づいて、非ユニタリで非エルミート量子系をシミュレートする。 我々は,反復行列ベクトル乗算と行列逆演算を効率的に行うハイブリッド量子古典アルゴリズムを生成する。
  論文  参考訳（メタデータ） (2024-05-16T02:14:58Z)
• Realistic Runtime Analysis for Quantum Simplex Computation [0.4407851469168588]
  重要な最適化問題の現実のインスタンスを解く際に,古典的ランタイム解析のための量子アナログを提案する。 現実的な問題サイズに対する現実的な量子的優位性は、現在の物理的な制限よりもかなり低い量子ゲート演算時間を必要とすることを示します。
  論文  参考訳（メタデータ） (2023-11-16T16:11:44Z)
• Trainable Variational Quantum-Multiblock ADMM Algorithm for Generation Scheduling [0.0]
  本稿では、量子コンピューティング、機械学習、分散最適化による生成スケジューリングのための2ループ量子解アルゴリズムを提案する。 この目的は、実用的な電力系統の問題を解決するために、限られた量子ビット数を持つ短期量子機械の雑音を緩和することである。
  論文  参考訳（メタデータ） (2023-03-28T21:31:39Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。 我々は距離の計算を高速化するために量子現象を利用する。 我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
  論文  参考訳（メタデータ） (2022-12-13T16:04:16Z)
• End-to-end resource analysis for quantum interior point methods and portfolio optimization [63.4863637315163]
  問題入力から問題出力までの完全な量子回路レベルのアルゴリズム記述を提供する。 アルゴリズムの実行に必要な論理量子ビットの数と非クリフォードTゲートの量/深さを報告する。
  論文  参考訳（メタデータ） (2022-11-22T18:54:48Z)
• Demonstration of algorithmic quantum speedup [0.0]
  証明可能なアルゴリズム量子スピードアップの実験的実証は、いまだ解明されていない。 隠れビットストリングを識別する問題を解く単発ベルンシュタイン・ヴァジラニアルゴリズムを実装した。 スピードアップは2つのQCのうちの1つで観測される。
  論文  参考訳（メタデータ） (2022-07-15T17:59:47Z)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。 これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。 本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
  論文  参考訳（メタデータ） (2022-02-17T18:59:20Z)
• Benchmarking Small-Scale Quantum Devices on Computing Graph Edit Distance [52.77024349608834]
  グラフ編集距離(GED: Graph Edit Distance)は、2つのグラフ間の(異なる)相似性の度合いを測定する。 本稿では、GED計算における2つの量子アプローチの比較研究について述べる。
  論文  参考訳（メタデータ） (2021-11-19T12:35:26Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。 本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。 提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
  論文  参考訳（メタデータ） (2021-07-08T17:59:55Z)
• Large-scale quantum hybrid solution for linear systems of equations [0.0]
  指数的高速化を伴う方程式の線形系を解くためのハイブリッド量子アルゴリズムを導入,実装する。 我々は、量子コンピュータ上での線形システム解の記録である超伝導IBMQデバイスにおける217ドルの次元問題を実験的に解決した。
  論文  参考訳（メタデータ） (2020-03-28T11:23:05Z)

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

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