論文の概要: An algebraic interpretation of Pauli flow, leading to faster flow-finding algorithms
- arxiv url: http://arxiv.org/abs/2410.23439v1
- Date: Wed, 30 Oct 2024 20:30:01 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-01 17:00:32.829169
- Title: An algebraic interpretation of Pauli flow, leading to faster flow-finding algorithms
- Title（参考訳）: パウリ流の代数的解釈によりより高速なフローフィニングアルゴリズムが実現される
- Authors: Piotr Mitosek, Miriam Backens,
- Abstract要約: パウリフローの存在は、積 $NC が有向非巡回グラフの隣接行列を形成するような正逆の$C$ of$M$が存在するときのみである。
我々は、パウリフローを見つけるために$mathcalO(n3)$アルゴリズムを取得し、一般化フローを見つけるために以前の$mathcalO(n4)$バウンドを改良した。
- 参考スコア（独自算出の注目度）: 1.4732811715354455
- License:
- Abstract: The one-way model of quantum computation is an alternative to the circuit model. A one-way computation is driven entirely by successive adaptive measurements of a pre-prepared entangled resource state. For each measurement, only one outcome is desired; hence a fundamental question is whether some intended measurement scheme can be performed in a robustly deterministic way. So-called flow structures witness robust determinism by providing instructions for correcting undesired outcomes. Pauli flow is one of the broadest of these structures and has been studied extensively. It is known how to find flow structures in polynomial time when they exist; nevertheless, their lengthy and complex definitions often hinder working with them. We simplify these definitions by providing a new algebraic interpretation of Pauli flow. This involves defining two matrices arising from the adjacency matrix of the underlying graph: the flow-demand matrix $M$ and the order-demand matrix $N$. We show that Pauli flow exists if and only if there is a right inverse $C$ of $M$ such that the product $NC$ forms the adjacency matrix of a directed acyclic graph. From the newly defined algebraic interpretation, we obtain $\mathcal{O}(n^3)$ algorithms for finding Pauli flow, improving on the previous $\mathcal{O}(n^4)$ bound for finding generalised flow, a weaker variant of flow, and $\mathcal{O}(n^5)$ bound for finding Pauli flow. We also introduce a first lower bound for the Pauli flow-finding problem, by linking it to the matrix invertibility and multiplication problems over $\mathbb{F}_2$.
- Abstract（参考訳）: 量子計算の一方通行モデルは、回路モデルに代わるものである。
ワンウェイ計算は、準備済みの絡み合ったリソース状態の連続的な適応的な測定によって完全に駆動される。
それぞれの測定について、1つの結果のみが望まれるので、基本的な疑問は、意図された測定スキームが堅牢に決定的な方法で実行できるかどうかである。
いわゆるフロー構造は、望ましくない結果を修正するための指示を提供することで、堅牢な決定論を実証する。
パウリ流はこれらの構造の中で最も広く、広く研究されている。
多項式時間でフロー構造を見つける方法が知られているが、しかしながら、それらの長い複雑な定義は、しばしばそれらを扱うのを妨げている。
パウリフローの新しい代数的解釈を提供することにより、これらの定義を単純化する。
これは、基礎となるグラフの隣接行列から生じる2つの行列(フロー要求行列$M$とオーダー要求行列$N$)を定義することである。
パウリフローが存在することは、その積$NC$が有向非巡回グラフの随伴行列を形成するような正逆$C$ of$M$が存在するときのみである。
新たに定義された代数的解釈から、パウリフローを見つけるための$\mathcal{O}(n^3)$アルゴリズム、一般化されたフローを見つけるための以前の$\mathcal{O}(n^4)$バウンド、より弱いフローを見つけるための$\mathcal{O}(n^5)$バウンドを改善する。
また、マトリクスの可逆性と乗算問題に$\mathbb{F}_2$ をリンクすることで、パウリのフローフィニング問題に対する第1の下位境界を導入する。
関連論文リスト
- Pauli Transfer Matrices [0.0]
パウリ転移行列は、$n$-qubit のパウリ基底における線型写像の作用を示す。
パウリ基底のテンソル積構造を明示的に利用する新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-11-01T11:52:51Z) - Quantum computational complexity of matrix functions [2.7488316163114823]
2つの原始問題の計算複雑性について検討する。
単項関数、チェビシェフ関数、時間発展関数、逆関数の4つの関数を考える。
論文 参考訳（メタデータ） (2024-10-17T18:00:03Z) - A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - Pauli Decomposition via the Fast Walsh-Hadamard Transform [0.0]
パウリの弦係数に対する新しい正確かつ明示的な公式を示す。
行列要素の置換まで、分解係数は一般化されたアダマール行列の乗算によって元の行列と関係があることが示される。
方程式の数値的な実装は、現在利用可能な解よりも優れている。
論文 参考訳（メタデータ） (2024-08-12T14:56:45Z) - Pauli Flow on Open Graphs with Unknown Measurement Labels [0.0]
ワンウェイ量子計算(英: One-way quantum computing)は、回路モデルに代わる量子計算の普遍的なモデルである。
開グラフが与えられたパウリフローの存在を測定ラベルとともに効率的に決定する方法が知られている。
X と Z の測定のみの場合、フローの存在は、隣接行列から導出される行列の右可逆性に対応する。
論文 参考訳（メタデータ） (2024-08-12T11:19:27Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - One-sided Matrix Completion from Two Observations Per Row [95.87811229292056]
行列の欠落値を$XTX$で計算する自然アルゴリズムを提案する。
合成データの一方の回収と低被覆ゲノムシークエンシングについて,本アルゴリズムの評価を行った。
論文 参考訳（メタデータ） (2023-06-06T22:35:16Z) - Relating Measurement Patterns to Circuits via Pauli Flow [0.0]
パウリ流を効率的に同定し,ゲート型量子回路に変換できることを示す。
次に、この関係を利用して、ZX-計算におけるグラフ理論の書き換えの効果をシミュレーション結果から導出する。
論文 参考訳（メタデータ） (2021-09-13T00:48:24Z) - Quantum algorithms for spectral sums [50.045011844765185]
正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。
本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
論文 参考訳（メタデータ） (2020-11-12T16:29:45Z) - Leveraged Matrix Completion with Noise [84.20092979053119]
未知の$ntimes n$ matrix of rank $r$ from just $mathcalO(nrlog2 (n))$ entry.
我々の証明は、ゴルフスキームに基づく十分な最適条件を記述する新しいアプローチによって支持されている。
論文 参考訳（メタデータ） (2020-11-11T16:25:45Z) - Linear-Sample Learning of Low-Rank Distributions [56.59844655107251]
ktimes k$, rank-r$, matrices to normalized $L_1$ distance requires $Omega(frackrepsilon2)$ sample。
我々は、$cal O(frackrepsilon2log2fracepsilon)$ sample, a number linear in the high dimension, and almost linear in the matrices, usually low, rank proofs.というアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-09-30T19:10:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。