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.20225v1
Date: Thu, 30 May 2024 16:30:16 GMT
ステータス: 処理完了
システム内更新日: 2024-05-31 13:29:24.512880
Title: Novel oracle constructions for quantum random access memory
Title（参考訳）: 量子ランダムアクセスメモリのための新しいオラクル構造
Authors: Ákos Nagy, Cindy Zhang,
Abstract要約: 量子辞書エンコーダ(quantum dictionary encoder)やデータアクセスオラクル( data access oracles)としても知られる量子(ランダムアクセス)メモリを設計する新しい方法を提案する。プロパティ $mathcalW_f で、oracles を $mathcalO_f$ で構築します。我々の構成は、整数値関数と見なされる$f$のウォルシュ・アダマール変換に基づいている。
参考スコア（独自算出の注目度）: 0.6445605125467572
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We present novel ways of designing quantum (random access) memory, also known as quantum dictionary encoders or data-access oracles. More precisely, given a function, $f : \mathbb{F}_2^n \rightarrow \mathbb{F}_2^d$, we construct oracles, $\mathcal{O}_f$, with the property $\mathcal{O}_f |x\rangle_n |0\rangle_d = |x\rangle_n |f(x)\rangle_d$. Our constructions 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. Our design comes with a tuneable amount of ancillas that can trade depth for size. In the ancillas-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 design is $O \left( \log_2 \left( \mathcal{W}_f \right) + \log_2 \left( \tfrac{d}{\epsilon} \right) \right)$, using $n + d \mathcal{W}_f$ qubits.
Abstract（参考訳）: 量子辞書エンコーダ(quantum dictionary encoder)やデータアクセスオラクル( data access oracles)としても知られる量子(ランダムアクセス)メモリを設計する新しい方法を提案する。より正確には、函数 $f : \mathbb{F}_2^n \rightarrow \mathbb{F}_2^d$ が与えられたとき、プロパティ $\mathcal{O}_f |x\rangle_n |0\rangle_d = |x\rangle_n |f(x)\rangle_d$ が成立する。我々の構成は、整数値関数と見なされるウォルシュ・アダマール変換(英語版)に基づいており、一般に、我々の方法の複雑さはウォルシュ・アダマール変換の空間性と共にスケールし、その空間性は$f$ではなく、二進最適化問題や低次ウォルシュ・アダマール変換を持つ関数のような場合により好ましい構成をもたらす。私たちのデザインには、サイズに応じて深さを交換できる調整可能な量のアンシラが付属しています。アンシラのない設計では、これらのオラクルは$\epsilon$-approximatedなので、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である。最も浅い設計の深さは$O \left( \mathcal{W}_f \right) + \log_2 \left( \tfrac{d}{\epsilon} \right)$, using $n + d \mathcal{W}_f$ qubitsである。

関連論文リスト

The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文参考訳（メタデータ） (2024-10-26T06:21:42Z)
Tight Lower Bounds under Asymmetric High-Order Hölder Smoothness and Uniform Convexity [6.972653925522813]
我々は、高次H'olderの滑らかかつ一様凸関数を最小化するオラクル複雑性に対して、厳密な下界を提供する。解析は、一階および二階の滑らかさの下での関数の以前の下界を一様凸関数と同様に一般化する。
論文参考訳（メタデータ） (2024-09-16T23:17:33Z)
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)
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 Quadratic Binary Optimization Problems [0.6524460254566903]
擬似非拘束バイナリ最適化(QUBO)問題に対するGrover型手法について検討する。このような問題に対して、左[1, m right] の値 mathbbZ$ のチューナブルパラメータである $Lambda を用いてマーカーオラクルを構築する。 Lambda$のすべての値に対して、これらのオラクルの非クリフォードゲート数は厳格に低い。この結果のいくつかは新規であり、固定点探索に基づく任意の手法に有用である。
論文参考訳（メタデータ） (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)
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)
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)

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

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