論文の概要: A Constant Measurement Quantum Algorithm for Graph Connectivity
- arxiv url: http://arxiv.org/abs/2411.15015v1
- Date: Fri, 22 Nov 2024 15:44:00 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-25 15:01:02.184607
- Title: A Constant Measurement Quantum Algorithm for Graph Connectivity
- Title（参考訳）: グラフ接続性のための定値量子アルゴリズム
- Authors: Maximilian Balthasar Mansky, Chonfai Kam, Claudia Linnhoff-Popien,
- Abstract要約: 定数数を用いてグラフ接続性を決定する新しい量子アルゴリズムを提案する。
これはZX計算から取られた非単位アーベルゲートに依存している。
このアルゴリズムは、アシラ量子ビットで修復できる状態崩壊を示す。
- 参考スコア（独自算出の注目度）: 4.900041609957432
- License:
- Abstract: We introduce a novel quantum algorithm for determining graph connectedness using a constant number of measurements. The algorithm can be extended to find connected components with a linear number of measurements. It relies on non-unitary abelian gates taken from ZX calculus. Due to the fusion rule, the two-qubit gates correspond to a large single action on the qubits. The algorithm is general and can handle any undirected graph, including those with repeated edges and self-loops. The depth of the algorithm is variable, depending on the graph, and we derive upper and lower bounds. The algorithm exhibits a state decay that can be remedied with ancilla qubits. We provide a numerical simulation of the algorithm.
- Abstract（参考訳）: 定数数を用いてグラフ接続性を決定する新しい量子アルゴリズムを提案する。
このアルゴリズムは、線形な数の測定で接続されたコンポーネントを見つけるために拡張することができる。
これはZX計算から取られた非単位アーベルゲートに依存している。
融合規則により、2ビットのゲートはキュービット上の大きな単一作用に対応する。
このアルゴリズムは汎用的で、エッジと自己ループの繰り返しを含む任意の非方向グラフを処理できる。
アルゴリズムの深さはグラフによって変動し、上下境界を導出する。
このアルゴリズムは、アシラ量子ビットで修復できる状態崩壊を示す。
アルゴリズムの数値シミュレーションを行う。
関連論文リスト
- Quantum Algorithm for Testing Graph Completeness [0.0]
グラフ完全性をテストすることは、コンピュータ科学とネットワーク理論において重要な問題である。
Szegedy量子ウォークと量子位相推定(QPE)を用いた効率的なアルゴリズムを提案する。
このアプローチは、ネットワーク構造解析、古典的なルーティングアルゴリズムの評価、ペア比較に基づくシステム評価に有用である。
論文 参考訳（メタデータ） (2024-07-29T14:56:25Z) - An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
我々は、QUBO問題として表されるグラフ上の最大傾きを見つける量子D波アンナーの能力を解析する。
本稿では, 相補的な最大独立集合問題に対する分解アルゴリズムと, ノード数, 傾き数, 密度, 接続率, 解サイズの他のノード数に対する比を制御するグラフ生成アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-06-11T04:40:05Z) - Full Characterization of the Depth Overhead for Quantum Circuit
Compilation with Arbitrary Qubit Connectivity Constraint [6.799314463590596]
量子コンピュータのいくつかの物理的実装では、2量子ビット演算は特定の量子ビットのペアにのみ適用できる。
本稿では、基礎となる制約グラフのルーティング数によって、深さオーバーヘッドを完全に特徴づける。
論文 参考訳（メタデータ） (2024-02-04T08:29:41Z) - Generalized quantum Arimoto-Blahut algorithm and its application to
quantum information bottleneck [55.22418739014892]
量子アリーモト・ブラフトアルゴリズムをRamakrishnanらにより一般化する。
3つの量子系を持つ量子情報ボトルネックに対して,我々のアルゴリズムを適用した。
数値解析により,我々のアルゴリズムはアルゴリズムよりも優れていることが示された。
論文 参考訳（メタデータ） (2023-11-19T00:06:11Z) - A simple quantum algorithm to efficiently prepare sparse states [0.0]
ゲートの複雑性は状態の非零振幅数において線形であり、キュービット数では2次であることを示す。
これは、スパース状態の準備のための最もよく知られたアルゴリズムと競合する。
論文 参考訳（メタデータ） (2023-10-30T07:05:15Z) - Compilation of algorithm-specific graph states for quantum circuits [55.90903601048249]
本稿では,高レベル言語で記述された量子回路から,アルゴリズム固有のグラフ状態を作成する量子回路コンパイラを提案する。
この計算は、このグラフ状態に関する一連の非パウリ測度を用いて実装することができる。
論文 参考訳（メタデータ） (2022-09-15T14:52:31Z) - Benchmarking Small-Scale Quantum Devices on Computing Graph Edit
Distance [52.77024349608834]
グラフ編集距離(GED: Graph Edit Distance)は、2つのグラフ間の(異なる)相似性の度合いを測定する。
本稿では、GED計算における2つの量子アプローチの比較研究について述べる。
論文 参考訳（メタデータ） (2021-11-19T12:35:26Z) - On Applying the Lackadaisical Quantum Walk Algorithm to Search for
Multiple Solutions on Grids [63.75363908696257]
不足量子ウォーク(英: lackadaisical quantum walk)は、頂点が重量$l$の自己ループを持つグラフ構造を探索するために開発されたアルゴリズムである。
本稿では,グリッド上の複数解の探索に不連続な量子ウォークを適用した際の問題に対処する。
論文 参考訳（メタデータ） (2021-06-11T09:43:09Z) - An Online Algorithm for Maximum-Likelihood Quantum State Tomography [6.261444979025642]
最大類似量子状態トモグラフィのための最初のオンラインアルゴリズムを提案する。
アルゴリズムの期待される数値誤差は$o(sqrt ( 1 / t ) d log d )$であり、ここで$t$は反復数を表す。
論文 参考訳（メタデータ） (2020-12-31T08:21:50Z) - Laplacian Eigenmaps with variational circuits: a quantum embedding of
graph data [0.0]
量子変分回路を用いたラプラシアン固有写像の計算法を提案する。
量子シミュレータを用いた32ノードグラフ上でのテストでは,古典的なラプラシアン固有写像アルゴリズムと同様の性能が得られた。
論文 参考訳（メタデータ） (2020-11-10T14:51:25Z) - Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。
ラグランジアン分解に基づく新しい手法を提案する。
ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
論文 参考訳（メタデータ） (2020-02-24T17:55:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。