論文の概要: Round and Communication Balanced Protocols for Oblivious Evaluation of
Finite State Machines
- arxiv url: http://arxiv.org/abs/2103.11240v1
- Date: Sat, 20 Mar 2021 20:49:41 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-23 14:15:33.521134
- Title: Round and Communication Balanced Protocols for Oblivious Evaluation of
Finite State Machines
- Title（参考訳）: 有限状態マシンの公開評価のためのラウンド・コミュニケーションバランスプロトコル
- Authors: Rafael Dowsley and Caleb Horst and Anderson C. A. Nascimento
- Abstract要約: 有限状態機械を不明瞭に評価するためのプロトコルを提案する。
評価は有限状態マシンのプロバイダと入力文字列のプロバイダとの間で共有される。
我々はこの問題に対する2つの異なる解決法、すなわち、信頼できないが解決しないヘルパーをセットとして提示する。
- 参考スコア（独自算出の注目度）: 12.427126681901482
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose protocols for obliviously evaluating finite-state machines, i.e.,
the evaluation is shared between the provider of the finite-state machine and
the provider of the input string in such a manner that neither party learns the
other's input, and the states being visited are hidden from both. For alphabet
size $|\Sigma|$, number of states $|Q|$, and input length $n$, previous
solutions have either required a number of rounds linear in $n$ or
communication $\Omega(n|\Sigma||Q|\log|Q|)$. Our solutions require 2 rounds
with communication $O(n(|\Sigma|+|Q|\log|Q|))$. We present two different
solutions to this problem, a two-party one and a setting with an untrusted but
non-colluding helper.
- Abstract（参考訳）: 本研究では,有限状態機械のプロバイダと入力文字列のプロバイダとの間で,双方が相手の入力を学習せず,訪れた状態が両方から隠蔽されるように,その評価を明示的に評価するためのプロトコルを提案する。
アルファベットサイズ $|\sigma|$, 状態数 $|q|$, 入力長 $n$ に対して、以前の解は数ラウンドを$n$ で直線化するか、$\omega(n|\sigma||q|\log|q|)$ で通信する必要があった。
我々の解は通信$O(n(|\Sigma|+|Q|\log|Q|))$の2ラウンドを必要とする。
我々はこの問題に対する2つの異なる解決法、すなわち、信頼できないが解決しないヘルパーをセットとして提示する。
関連論文リスト
- Distributed inner product estimation with limited quantum communication [3.729242965449096]
量子通信が制限された場合, 内部積の分散推定の課題を考察する。
我々は、$k=Theta(sqrt2n-q)$コピーが本質的に必要であり、このタスクに十分であることを示す。
また、任意のエルミート $M$ に対して $|langle psi|M|phirangle|2$ を推定することを考える。
論文 参考訳（メタデータ） (2024-10-16T15:46:59Z) - A quantum protocol for applying arbitrary phase transformations [0.0]
我々は、$|psirangle=sumpsi(x),|xrangle$を$|psi'rangle=sumpsi(x),eialpha|phi(x)|2,|xrangle$に変換する量子プロトコルを提案する。
論文 参考訳（メタデータ） (2024-09-17T09:32:00Z) - Asynchronous Approximate Agreement with Quadratic Communication [23.27199615640474]
非同期ネットワークは$n$のメッセージ送信パーティで、そのうちの最大$t$はビザンチンです。
本研究では,入力の凸内積にほぼ等しい出力が得られるような近似一致について検討する。
これは、信頼できるブロードキャスト毎に$Theta(n2)$メッセージ、またはイテレーション毎に$Theta(n3)$メッセージを取る。
論文 参考訳（メタデータ） (2024-08-10T09:03:06Z) - Dimension Independent Disentanglers from Unentanglement and Applications [55.86191108738564]
両部非絡み込み入力から次元独立なk-パーティイトディジアンタングル(類似)チャネルを構築する。
NEXP を捉えるためには、$| psi rangle = sqrta | sqrt1-a | psi_+ rangle という形の非負の振幅を持つのに十分であることを示す。
論文 参考訳（メタデータ） (2024-02-23T12:22:03Z) - Unitarity estimation for quantum channels [7.323367190336826]
ユニタリティ推定は、量子デバイス認証とベンチマークにおいて基礎的で重要な問題である。
我々は、アンシラ効率のアルゴリズムを誘導するユニタリティ推定のための統一的なフレームワークを提供する。
アルゴリズムの$d$-dependenceと$epsilon$-dependenceの両方が最適であることを示す。
論文 参考訳（メタデータ） (2022-12-19T09:36:33Z) - A Framework for Distributed Quantum Queries in the CONGEST Model [0.0]
量子クエリアルゴリズムを量子CONGESTで実装するための一般的なフレームワークを提供する。
分散Deutsch-Jozsa問題に対するプロトコルを一般化する。
また、サイクル検出と計算の問題を量子スピードアップする。
論文 参考訳（メタデータ） (2022-02-22T15:18:39Z) - Distributed Saddle-Point Problems Under Similarity [173.19083235638104]
与えられたサブ最適度$epsilon0$は、$Omegabigのマスター/ワーカーネットワークで達成されることを示す。
次に,ネットワークの下位の型(ログオーバまで)に適合するアルゴリズムを提案する。
頑健なロジスティック回帰問題に対して提案アルゴリズムの有効性を評価する。
論文 参考訳（メタデータ） (2021-07-22T14:25:16Z) - On Distributed Differential Privacy and Counting Distinct Elements [52.701425652208734]
我々は、$n$ユーザのそれぞれが離散集合から要素を保持する設定について研究する。
目標は、すべてのユーザーに対して異なる要素の数を数えることだ。
論文 参考訳（メタデータ） (2020-09-21T04:13:34Z) - 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) - Quantum Differentially Private Sparse Regression Learning [132.1981461292324]
我々は、スパース回帰問題を解くために、効率的な量子微分プライベート(QDP)ラッソ推定器を考案する。
最後に、QDP Lasso はプライバシー保証付きで $tildeO(N-2/3)$ に近い最適ユーティリティを実現していることを示す。
論文 参考訳（メタデータ） (2020-07-23T10:50:42Z) - Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
Aaronson, Kothari, Kretschmer, Thaler (2020) が考える数え上げ問題の次の変種に対する厳密な下界を証明する。
このタスクは、入力セット$xsubseteq [n]$が$k$か$k'=(1+varepsilon)k$であるかどうかを識別する。
論文 参考訳（メタデータ） (2020-02-17T10:53:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。