論文の概要: Utilizing Novel Quantum Counters for Grover's Algorithm to Solve the
Dominating Set Problem
- arxiv url: http://arxiv.org/abs/2312.09388v1
- Date: Thu, 14 Dec 2023 23:00:35 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-18 17:51:31.159092
- Title: Utilizing Novel Quantum Counters for Grover's Algorithm to Solve the
Dominating Set Problem
- Title（参考訳）: グルーバーのアルゴリズムにおける新しい量子カウンタを用いた支配集合問題の解法
- Authors: Jehn-Ruey Jiang and Qiao-Yi Lin
- Abstract要約: グロバーのアルゴリズムは、量子コンピュータ上で実行されるよく知られた非構造量子探索アルゴリズムである。
本稿では、Groverのアルゴリズムのオラクルを構成するために、3つの優れた性質を持つ新しい量子カウンタを利用する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Grover's algorithm is a well-known unstructured quantum search algorithm run
on quantum computers. It constructs an oracle and calls the oracle O($\sqrt N$)
times to locate specific data out of N unsorted data. This represents a
quadratic speedup compared to the classical unstructured data sequential search
algorithm, which requires to call the oracle O(N) times. We are currently in
the noisy intermediate-scale quantum (NISQ) era in which quantum computers have
a limited number of qubits, short decoherence time, and low gate fidelity. It
is thus desirable to design quantum components with three good properties: (i)
a reduced number of qubits, (ii) shorter quantum depth, and (iii) fewer gates.
This paper utilizes novel quantum counters with the above-mentioned three good
properties to construct the oracle of Grover's algorithm to efficiently solve
the dominating set problem (DSP), as defined below. For a given graph G=(V, E),
a dominating set (DS) D is a subset of the vertex set V, such that every vertex
is in D or has an adjacent vertex in D. The DSP is to decide for a given graph
G and an integer k whether there exists a DS with size k. Algorithms solving
the DSP have many applications. For example, they can be applied to check
whether k routers suffice to connect all computers in a computer network. The
DSP is an NP-complete problem, indicating that no classical algorithm exists to
solve the DSP with polynomial time complexity in the worst case. Therefore,
using quantum algorithms, such as Grover's algorithm, to exploit the potent
computational capabilities of quantum computers to solve the DSP is highly
promising. We execute the whole quantum circuit of Grover's algorithm using
novel quantum counters through the IBM Quantum Lab service to validate that the
circuit can solve the DSP efficiently and correctly.
- Abstract（参考訳）: グロバーのアルゴリズムは、量子コンピュータ上で動作するよく知られた非構造量子探索アルゴリズムである。
これはoracleを構成し、n個の未ソートデータから特定のデータを見つけるためにoracle o($\sqrt n$) を呼び出します。
これは、oracle o(n) を呼び出しなければならない従来の非構造化データシーケンシャル検索アルゴリズムと比較して、2倍のスピードアップを示している。
現在我々は、量子コンピュータが限られたキュービット数、短いデコヒーレンス時間、低いゲート忠実度を持つノイズの多い中間スケール量子(NISQ)時代にいる。
したがって、3つの良い性質を持つ量子成分を設計することが望ましい。
(i)少人数のキュービット。
(ii)より短い量子深度、そして
(iii)少ないゲート。
本稿では,上述の3つの良い性質を持つ新しい量子カウンタを用いてグロバーのアルゴリズムのオラクルを構築し,支配集合問題(dsp)を効率的に解く。
与えられたグラフ G=(V, E) に対して、支配集合(DS) D は頂点集合 V の部分集合であり、すべての頂点が D 内にあるか、あるいは D 内に隣接する頂点を持つ。
DSPを解くアルゴリズムには多くの応用がある。
例えば、kルータがコンピュータネットワーク内のすべてのコンピュータを接続するのに十分かどうかをチェックできる。
DSPはNP完全問題であり、最悪の場合、DSPを多項式時間で解くために古典的なアルゴリズムは存在しないことを示す。
したがって、Groverのアルゴリズムのような量子アルゴリズムを用いて量子コンピュータの強力な計算能力を利用してDSPを解くことは、非常に有望である。
我々はIBM Quantum Labサービスを通じてGroverのアルゴリズムの量子回路全体を新しい量子カウンタを用いて実行し、回路がDSPを効率的に正しく解けることを検証する。
関連論文リスト
- Opening the Black Box Inside Grover's Algorithm [0.0]
グロバーのアルゴリズムは、量子コンピュータが古典的コンピュータよりも有利であることを示す主要なアルゴリズムである。
我々は,古典的コンピュータ上で動作可能な量子インスパイアされたアルゴリズムを構築し,Groverのタスクを,オラクルへの(シミュレーションの)呼び出し数で線形に実行する。
論文 参考訳（メタデータ） (2023-03-20T17:56:20Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。
我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。
我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文 参考訳（メタデータ） (2022-09-28T17:53:25Z) - Iterative Qubits Management for Quantum Index Searching in a Hybrid
System [56.39703478198019]
IQuCSは、量子古典ハイブリッドシステムにおけるインデックス検索とカウントを目的としている。
我々はQiskitでIQuCSを実装し、集中的な実験を行う。
その結果、量子ビットの消費を最大66.2%削減できることが示されている。
論文 参考訳（メタデータ） (2022-09-22T21:54:28Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - A Scalable 5,6-Qubit Grover's Quantum Search Algorithm [0.0]
グロバーの量子探索アルゴリズムは量子コンピューティングのよく知られた応用の1つである。
本稿では,5量子ビットと6量子ビットの量子回路を用いて,スケーラブルな量子グロバー探索アルゴリズムを導入,実装する。
提案した5-qubitと6-qubitの回路の精度を3-qubitと4-qubitの最先端実装と比較した。
論文 参考訳（メタデータ） (2022-04-30T00:35:54Z) - Quantum State Preparation with Optimal Circuit Depth: Implementations
and Applications [10.436969366019015]
我々は、$Theta(n)$-depth回路は、$O(ndlog d)$ acillary qubitsを持つ$Theta(log(nd))で作成可能であることを示す。
我々は、ハミルトンシミュレーション、方程式の線形系解法、量子ランダムアクセスメモリの実現など、異なる量子コンピューティングタスクにおける結果の適用について論じる。
論文 参考訳（メタデータ） (2022-01-27T13:16:30Z) - Benchmarking Small-Scale Quantum Devices on Computing Graph Edit
Distance [52.77024349608834]
グラフ編集距離(GED: Graph Edit Distance)は、2つのグラフ間の(異なる)相似性の度合いを測定する。
本稿では、GED計算における2つの量子アプローチの比較研究について述べる。
論文 参考訳（メタデータ） (2021-11-19T12:35:26Z) - Polynomial T-depth Quantum Solvability of Noisy Binary Linear Problem:
From Quantum-Sample Preparation to Main Computation [0.0]
雑音二元線形問題(NBLP)の量子可解性について完全解析する。
NBLPの解くコストは、指数関数的に増大する論理量子ビットを犠牲にして、問題の規模で解決できることが示される。
論文 参考訳（メタデータ） (2021-09-23T07:46:20Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳（メタデータ） (2021-07-08T17:59:55Z) - Hardware Efficient Quantum Search Algorithm [17.74233101199813]
本稿では,この課題を克服するために,ハードウェアの効率的な量子探索アルゴリズムを提案する。
我々の鍵となる考え方は、グローバル拡散操作を低コストな局所拡散に置き換えることである。
回路コストの削減は、システムの成功率を著しく向上させる。
論文 参考訳（メタデータ） (2021-03-26T01:08:50Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。
また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
論文 参考訳（メタデータ） (2020-09-15T18:17:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。