論文の概要: Complexity of graph-state preparation by Clifford circuits
- arxiv url: http://arxiv.org/abs/2402.05874v1
- Date: Thu, 8 Feb 2024 18:08:09 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-09 13:37:23.639136
- Title: Complexity of graph-state preparation by Clifford circuits
- Title（参考訳）: クリフォード回路によるグラフ状態形成の複雑さ
- Authors: Soh Kumabe, Ryuhei Mori, Yusei Yoshimura
- Abstract要約: グラフ状態の CZ-複素性は、|Grangle$ とグラフのランク幅 $G$ との接続を示す。
我々は、グラフの特殊クラスに$G$が含まれているとき、$|Grangle$を$O(n)$ CZ-複雑度で作成する量子アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 2.7010154811483167
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this work, we study a complexity of graph-state preparation. We consider
general quantum algorithms consisting of the Clifford operations on at most two
qubits for graph-state preparations. We define the CZ-complexity of graph state
$|G\rangle$ as the minimum number of two-qubit Clifford operations (excluding
single-qubit Clifford operations) for generating $|G\rangle$ from a trivial
state $|0\rangle^{\otimes n}$. We first prove that a graph state $|G\rangle$ is
generated by at most $t$ two-qubit Clifford operations if and only if
$|G\rangle$ is generated by at most $t$ controlled-Z (CZ) operations. We next
prove that a graph state $|G\rangle$ is generated from another graph state
$|H\rangle$ by $t$ CZ operations if and only if the graph $G$ is generated from
$H$ by some combinatorial graph transformation with cost $t$. As the main
results, we show a connection between the CZ-complexity of graph state
$|G\rangle$ and the rank-width of the graph $G$. Indeed, we prove that for any
graph $G$ with $n$ vertices and rank-width $r$,
1. The CZ-complexity of $|G\rangle$ is $O(rn\log n)$.
2. If $G$ is connected, the CZ-complexity of $|G\rangle$ is at least $n + r -
2$.
We also show the existence of graph states whose CZ-complexities are close to
the upper and lower bounds. Finally, we present quantum algorithms preparing
$|G\rangle$ with $O(n)$ CZ-complexity when $G$ is included in special classes
of graphs, namely, cographs, interval graphs, permutation graphs and circle
graphs.
- Abstract（参考訳）: 本研究では,グラフ状態準備の複雑さについて検討する。
グラフ状態の準備のために少なくとも2つの量子ビット上のクリフォード演算からなる一般量子アルゴリズムを考える。
グラフ状態 $|G\rangle$ の CZ-複素性を、自明な状態 $|0\rangle^{\otimes n}$ から $|G\rangle$ を生成する2量子クリフォード演算の最小数として定義する。
グラフ状態 $|g\rangle$ が最大$t$ two-qubit clifford演算によって生成されることを最初に証明するのは、$|g\rangle$ が少なくとも$t$ controlled-z (cz)演算によって生成されるときである。
次に、グラフ状態 $|g\rangle$ が別のグラフ状態 $|h\rangle$ by $t$ cz 演算から生成されることを証明します。
主な結果として、グラフ状態のCZ-複素度$|G\rangle$とグラフのランク幅$G$との接続を示す。
実際、任意のグラフ $G$ に対して $n$ vertices と rank-width $r$, 1 に対して $|G\rangle$ の CZ-複素性は $O(rn\log n)$ であることを示す。
2.$G$ が連結であれば、$|G\rangle$ の CZ-複素性は少なくとも $n + r2$ である。
また、CZ-複雑度が上界と下界に近いグラフ状態の存在を示す。
最後に、$g$ がグラフの特別なクラス、すなわちコグラフ、区間グラフ、置換グラフ、円グラフに含まれる場合、$|g\rangle$ を$o(n)$ cz-複素性で作成する量子アルゴリズムを示す。
関連論文リスト
- Implementation of Continuous-Time Quantum Walk on Sparse Graph [0.0]
連続時間量子ウォーク(CTQW)は、量子コンピューティングにおいて重要な役割を果たす。
CTQWを効率的に実装する方法は難しい問題である。
本稿では,スパースグラフ上でのCTQWの実装について検討する。
論文 参考訳（メタデータ） (2024-08-20T05:20:55Z) - Graph Unfolding and Sampling for Transitory Video Summarization via Gershgorin Disc Alignment [48.137527345353625]
携帯電話からYouTubeやTikTokなどのソーシャルメディアサイトにアップロードされたユーザー生成ビデオ(UGV)は、短くて繰り返しではない。
我々は、ガーシュゴリンディスクアライメント(GDA)に基づく高速グラフサンプリングにより、遷移UGVを複数のディスクに線形時間で要約する。
提案アルゴリズムは,最先端の手法と比較して,映像の要約性能が向上し,複雑さが大幅に低減されていることを示す。
論文 参考訳（メタデータ） (2024-08-03T20:08:02Z) - Quantum walks on join graphs [0.0]
隣接行列あるいはラプラシア行列を関連するハミルトニアンとする重み付き結合グラフ上での連続量子ウォークの挙動を考察する。
結合グラフにおいて、強いコスペクトル性、周期性、完全状態移動(PST)を特徴付ける。
有界な$frac2|V(X)|$はグラフの無限族に対してきついことを実証する。
論文 参考訳（メタデータ） (2023-12-12T00:33:30Z) - Quantum walks on blow-up graphs [0.0]
グラフ$G$の$n$コピーは、グラフ$oversetnuplusG$である。
ブローアップグラフ $oversetnuplusG$ 上の量子状態移動の存在について検討する。
論文 参考訳（メタデータ） (2023-08-26T14:07:25Z) - Rule-based Graph Repair using Minimally Restricted Consistency-Improving
Transformations [65.268245109828]
一貫性の維持と一貫性の向上という,一貫性の新たな概念を導入します。
本稿では, 規則に基づくグラフ修復手法を提案する。
論文 参考訳（メタデータ） (2023-07-18T11:20:54Z) - Online Learning with Feedback Graphs: The True Shape of Regret [82.00098840619847]
ミニマックスの後悔は任意のグラフと時間的地平線に対して$R*$に比例することを示す。
複雑な探索戦略を導入し、最小限の最小後悔境界を達成する主アルゴリズムを定義する。
論文 参考訳（メタデータ） (2023-06-05T15:35:00Z) - AnchorGAE: General Data Clustering via $O(n)$ Bipartite Graph
Convolution [79.44066256794187]
我々は、グラフ畳み込みネットワーク(GCN)を構築するために使用される生成グラフモデルを導入することにより、グラフに非グラフデータセットを変換する方法を示す。
アンカーによって構築された二部グラフは、データの背後にある高レベル情報を利用するために動的に更新される。
理論的には、単純な更新が退化につながることを証明し、それに従って特定の戦略が設計される。
論文 参考訳（メタデータ） (2021-11-12T07:08:13Z) - Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。
実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文 参考訳（メタデータ） (2021-10-21T18:43:00Z) - Exact Matching of Random Graphs with Constant Correlation [2.578242050187029]
本稿では, ErdHos--R'enyi グラフに対するグラフマッチングやネットワークアライメントの問題を扱う。
これはグラフ同型問題のうるさい平均ケース版と見なすことができる。
論文 参考訳（メタデータ） (2021-10-11T05:07:50Z) - Local classical MAX-CUT algorithm outperforms $p=2$ QAOA on high-girth
regular graphs [0.0]
すべての次数$D ge 2$ of girth $> 5$に対して、QAOA$はQAOA$ on $G$よりも大きなカット率を持つことを示す。
任意の定数$p$に対して、すべてのグラフ上でQAOA$_p$と同様に動作する局所古典的MAX-CUTアルゴリズムが存在すると推測する。
論文 参考訳（メタデータ） (2021-01-14T09:17:20Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳（メタデータ） (2020-08-24T06:50:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。