Fugu-MT 論文翻訳(概要): Novel oracle constructions for quantum random access memory

論文の概要: Novel oracle constructions for quantum random access memory

arxiv url: http://arxiv.org/abs/2405.20225v2
Date: Thu, 13 Jun 2024 09:34:47 GMT
ステータス: 処理完了
システム内更新日: 2024-06-14 22:56:33.182136
Title: Novel oracle constructions for quantum random access memory
Title（参考訳）: 量子ランダムアクセスメモリのための新しいオラクル構造
Authors: Ákos Nagy, Cindy Zhang,
Abstract要約: 量子ランダムアクセスメモリのための新しい設計を提案する。我々は、プロパティの始式であるMathcalO_f left| x rightrangle_n left| 0 rightrangle_d = left| x rightrangle_n left| f(x) rightrangle_d で、オラクルを$mathcalO_f$で構築する。
参考スコア（独自算出の注目度）: 0.6445605125467572
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We present new designs for quantum random access memory. More precisely, for each function, $f : \mathbb{F}_2^n \rightarrow \mathbb{F}_2^d$, we construct oracles, $\mathcal{O}_f$, with the property \begin{equation} \mathcal{O}_f \left| x \right\rangle_n \left| 0 \right\rangle_d = \left| x \right\rangle_n \left| f(x) \right\rangle_d. \end{equation} Our methods are based on the Walsh-Hadamard Transform of $f$, viewed as an integer valued function. In general, the complexity of our method scales with the sparsity of the Walsh-Hadamard Transform and not the sparsity of $f$, yielding more favorable constructions in cases such as binary optimization problems and function with low-degree Walsh-Hadamard Transforms. Furthermore, our design comes with a tuneable amount of ancillas that can trade depth for size. In the ancilla-free design, these oracles can be $\epsilon$-approximated so that the Clifford + $T$ depth is $O \left( \left( n + \log_2 \left( \tfrac{d}{\epsilon} \right) \right) \mathcal{W}_f \right)$, where $\mathcal{W}_f$ is the number of nonzero components in the Walsh-Hadamard Transform. The depth of the shallowest version is $O \left( n + \log_2 \left( \tfrac{d}{\epsilon} \right) \right)$, using $n + d \mathcal{W}_f$ qubit. The connectivity of these circuits is also only logarithmic in $\mathcal{W}_f$. As an application, we show that for boolean functions with low approximate degrees (as in the case of read-once formulas) the complexities of the corresponding QRAM oracles scale only as $2^{\widetilde{O} \left( \sqrt{n} \log_2 \left( n \right) \right)}$.
Abstract（参考訳）: 量子ランダムアクセスメモリのための新しい設計を提案する。より正確には、各函数に対して、$f : \mathbb{F}_2^n \rightarrow \mathbb{F}_2^d$ は、oracles, $\mathcal{O}_f$ を、プロパティ \begin{equation} \mathcal{O}_f \left| x \right\rangle_n \left| 0 \right\rangle_d = \left| x \right\rangle_n \left| f(x) \right\rangle_d で構成する。 end{equation} 我々のメソッドは、整数値関数と見なされる$f$のWalsh-Hadamard変換に基づいている。一般に、我々の手法の複雑さはウォルシュ・アダマール変換のスパーシリティとともにスケールし、$f$のスパーシリティではなく、二進最適化問題やウォルシュ・アダマール変換の低次関数のような場合により有利な構成をもたらす。さらに、私たちのデザインには、サイズに応じて深さを交換できる調整可能な量のアンシラが付属しています。アンシラのない設計では、これらのオラクルは$\epsilon$-approximatedなので、Clifford + $T$ depthは$O \left( \left( n + \log_2 \left( \tfrac{d}{\epsilon} \right) \right) \mathcal{W}_f \right)$である。最も浅いバージョンの深さは$O \left(n + \log_2 \left( \tfrac{d}{\epsilon} \right)$、$n + d \mathcal{W}_f$ qubitである。これらの回路の接続性も$\mathcal{W}_f$で対数的である。応用として、近似度が低いブール関数に対して、対応するQRAMオーラクレスの複素数は2.75widetilde{O} \left( \sqrt{n} \log_2 \left(n \right) \right)}$としてしかスケールしないことを示す。

関連論文リスト

Efficient Continual Finite-Sum Minimization [52.5238287567572]
連続有限サム最小化(continuous finite-sum minimization)と呼ばれる有限サム最小化の鍵となるツイストを提案する。我々のアプローチは$mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$で大幅に改善されます。また、$mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$という自然な一階法は存在しないことを証明し、この方法の第一階法がほぼ密であることを示す。
論文参考訳（メタデータ） (2024-06-07T08:26:31Z)
On Partially Unitary Learning [0.0]
ヒルベルト空間の最適写像 $IN$ of $left|psirightrangle$ と $OUT$ of $left|phirightrangle$ が提示される。この最適化問題の大域的な最大化を求めるアルゴリズムを開発し,多くの問題に適用した。
論文参考訳（メタデータ） (2024-05-16T17:13:55Z)
Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文参考訳（メタデータ） (2024-02-06T15:39:09Z)
Fixed-point Grover Adaptive Search for Binary Optimization Problems [0.6524460254566903]
二次二項最適化問題に対するGrover-type法について検討する。このような問題に対して、左[1, m right] の値 mathbbZ$ のチューナブルパラメータである $Lambda を用いてマーカーオラクルを構築する。次に,新しいemphFixed-point Grover Adaptive Search for QUBO Problemsを紹介した。
論文参考訳（メタデータ） (2023-11-09T18:49:01Z)
Extending Matchgate Simulation Methods to Universal Quantum Circuits [4.342241136871849]
マッチゲートはパリティ保存された2ビットゲートのファミリーであり、その隣の回路は古典的にシミュレート可能であることが知られている。本稿では,$boldsymboln$-qubit 回路に $boldsymbolN$ gates と $boldsymbolN-m$ を共役するシミュレーション手法を提案する。
論文参考訳（メタデータ） (2023-02-06T09:50:16Z)
On the Sample Complexity of Two-Layer Networks: Lipschitz vs. Element-Wise Lipschitz Activation [20.70453775428433]
本研究では,異なるアクティベーション関数を用いた有界二層ニューラルネットワークのサンプル複雑性について検討する。我々は、$sigma$ が要素ワイドであれば、$mathcalH$ のサンプルの複雑さは、幅の対数依存しか持たないことを証明する。
論文参考訳（メタデータ） (2022-11-17T16:27:15Z)
Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文参考訳（メタデータ） (2022-06-17T17:55:43Z)
Low-degree learning and the metric entropy of polynomials [49.1574468325115]
少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
論文参考訳（メタデータ） (2022-03-17T23:52:08Z)
Matrix concentration inequalities and efficiency of random universal sets of quantum gates [0.0]
ランダム集合 $mathcalS の部分集合 U(d)$ に対して、$mathcalS$ が $delta$-approximate $t$-design となる確率の有界性を与える。正確な$t$-designから引き出された$mathcalS$に対して、$delta$-approximate $t$-designが不等式$mathbbPleft(delta geq x right)leq 2D_tを満たす確率を示す。
論文参考訳（メタデータ） (2022-02-10T23:44:09Z)
Thresholded Lasso Bandit [70.17389393497125]
Thresholded Lasso banditは、報酬関数を定義するベクトルとスパースサポートを推定するアルゴリズムである。一般には $mathcalO( log d + sqrtT )$ や $mathcalO( log d + sqrtT )$ としてスケールする非漸近的後悔の上界を確立する。
論文参考訳（メタデータ） (2020-10-22T19:14:37Z)
On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
論文参考訳（メタデータ） (2020-02-09T03:39:46Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。