論文の概要: Robust Quantum Circuit for Clique Problem with Intermediate Qudits
- arxiv url: http://arxiv.org/abs/2211.07947v1
- Date: Tue, 15 Nov 2022 07:23:32 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-19 12:48:10.156034
- Title: Robust Quantum Circuit for Clique Problem with Intermediate Qudits
- Title（参考訳）: 中間quditを持つクランク問題に対するロバスト量子回路
- Authors: Arpita Sanyal (Bhaduri), Amit Saha, Banani Saha and Amlan Chakrabarti
- Abstract要約: この記事では、$k$-clique問題と最大clique問題に対する量子回路実装の改善について述べる。
k$-clique問題に対する最先端量子回路のコストは、膨大な数の$n$-qubitトフォリゲートのために余剰である。
- 参考スコア（独自算出の注目度）: 3.154269505086154
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Clique problem has a wide range of applications due to its pattern matching
ability. There are various formulation of clique problem like $k$-clique
problem, maximum clique problem, etc. The $k$-Clique problem, determines
whether an arbitrary network has a clique or not whereas maximum clique problem
finds the largest clique in a graph. It is already exhibited in the literature
that the $k$-clique or maximum clique problem (NP-problem) can be solved in an
asymptotically faster manner by using quantum algorithms as compared to the
conventional computing. Quantum computing with higher dimensions is gaining
popularity due to its large storage capacity and computation power. In this
article, we have shown an improved quantum circuit implementation for the
$k$-clique problem and maximum clique problem (MCP) with the help of
higher-dimensional intermediate temporary qudits for the first time to the best
of our knowledge. The cost of state-of-the-art quantum circuit for $k$-clique
problem is colossal due to a huge number of $n$-qubit Toffoli gates. We have
exhibited an improved cost and depth over the circuit by applying a generalized
$n$-qubit Toffoli gate decomposition with intermediate ququarts (4-dimensional
qudits).
- Abstract（参考訳）: clique問題には、パターンマッチング能力のため、幅広いアプリケーションがある。
k$-clique問題やmaximum clique問題など、いくつかのclique問題の定式化がある。
k$-クライク問題は、任意のネットワークがクライクを持つかどうかを判断するが、最大クライク問題はグラフで最大のクライクを見つける。
k$-clique または maximum clique problem (np-problem) は、従来の計算に比べて量子アルゴリズムを用いて漸近的に高速に解くことができることが文献に既に示されている。
高次元の量子コンピューティングは、大きなストレージ容量と計算能力のために人気を博している。
本稿では,k$-clique問題とmaximum clique問題(mcp)に対する量子回路実装の改善を,高次元の中間的一時的quditを用いて初めて,我々の知識を最大限に活用した。
k$-clique問題に対する最先端の量子回路のコストは、n$-qubit の toffoli ゲートが大量に存在するため、非常に高くつく。
一般化された$n$-qubit Toffoliゲートを中間クォート(4次元キューディット)で分解することにより,回路のコストと深さが向上した。
関連論文リスト
- Searching Weighted Barbell Graphs with Laplacian and Adjacency Quantum Walks [0.0]
離散空間におけるシュル・オーディンガー方程式によって進化する量子粒子は、グラフ上の連続時間量子ウォークを構成する。
ラプラシアの量子ウォークの挙動は、橋の重みがあっても変化しないので、単一の橋は歩行に影響を与えるには制限的すぎる。
論文 参考訳（メタデータ） (2024-08-15T16:24:47Z) - A Faster Branching Algorithm for the Maximum $k$-Defective Clique Problem [18.720357905876604]
未分岐グラフの$k$-defective cliqueは、$G$は、最大で$k$の欠損エッジを持つほぼ完全なグラフを誘導する。
与えられたグラフから最大の$k$$-defective Cliqueを求める最大$k$-defective Clique問題は、社会的および生物学的ネットワーク分析のような多くのアプリケーションにおいて重要である。
論文 参考訳（メタデータ） (2024-07-23T15:40:35Z) - An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
我々は、QUBO問題として表されるグラフ上の最大傾きを見つける量子D波アンナーの能力を解析する。
本稿では, 相補的な最大独立集合問題に対する分解アルゴリズムと, ノード数, 傾き数, 密度, 接続率, 解サイズの他のノード数に対する比を制御するグラフ生成アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-06-11T04:40:05Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - New Approaches to Complexity via Quantum Graphs [0.0]
量子グラフに対するclique問題を紹介し,研究する。
我々の問題に対する入力は、回路によって誘導される量子チャネルとして表現される。
言語内のチャネルのコレクションを変更することで、これらがクラス$textsfNP$, $textsfMA$, $textsfQMA$, $textsfQMA(2)$の完全な問題を引き起こします。
論文 参考訳（メタデータ） (2023-09-22T14:20:14Z) - Using 1-Factorization from Graph Theory for Quantum Speedups on Clique
Problems [0.0]
完全グラフの一因子化に基づく新しい量子オラクル設計を提供する。
また、Triangle Findingの時間複雑性を$O(n2.25 poly(log n))$に下げる際の、これらのオラクルの1つの利用についても論じる。
論文 参考訳（メタデータ） (2023-08-31T15:59:35Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - 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) - Quantum Distributed Algorithms for Detection of Cliques [1.8374319565577157]
本稿では,高速な量子分散傾き検出のためのフレームワークを提案する。
我々の主な技術的貢献は、より小さな斜めに付加できるノードの探索タスクとしてカプセル化することで、斜めを検出するための新しいアプローチである。
Omega(n3/5+epsilon)$ for $K_p$-detection for any $p geq 4$, even the classical (non-quantum) distributed CONGEST set。
論文 参考訳（メタデータ） (2022-01-09T12:57:02Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳（メタデータ） (2021-07-08T17:59:55Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。