論文の概要: Oracle Separations in the Fourier Hierarchy
- arxiv url: http://arxiv.org/abs/2609.11830v1
- Date: Thu, 10 Sep 2026 17:23:35 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-11 23:53:35.454508
- Title: Oracle Separations in the Fourier Hierarchy
- Title（参考訳）: フーリエ階層におけるOracleの分離
- Abstract要約: すべての定数 $kge2$ に対して、$mathrmFH_ksubsetneqmathrmFH_k+1$ に対するオラクルが存在することを証明します。
これは、オラクル、位相オラクル、標準オラクルに回路アクセスを与える通常の方法の両方に当てはまる。
また、すべてのレベルの結合を、オラクルに対して$mathrmBQP$から分離します。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The Fourier hierarchy $\mathrm{FH}_0\subseteq\mathrm{FH}_1\subseteq\mathrm{FH}_2\subseteq\cdots$, introduced by Shi (TCS 2005), measures a quantum computation by the number of Hadamard layers it uses. Between two layers the circuit may permute basis states and attach phases, but it may not create superposition; the layers are its only source of interference. The first level is exactly $\mathrm{BPP}$, while the second already solves Simon's problem and, through phase estimation, factors integers. Shi conjectured that every additional layer strictly increases computational power, and asked, as a first step, for oracle separations between consecutive levels. To our knowledge, the question was open at every level $k\ge2$. We prove that for every constant $k\ge2$ there is an oracle relative to which $\mathrm{FH}_k\subsetneq\mathrm{FH}_{k+1}$. The separating problem is built from Forrelation (Aaronson and Ambainis, STOC 2015): the level above solves it with a constant number of queries, whereas at level $k$ it stays hard even for circuits making exponentially many queries. This holds for both of the usual ways of giving a circuit access to an oracle, the phase oracle and the standard oracle, which writes its answer into a register. The two are not interchangeable: relative to an oracle, the standard oracle is strictly more powerful at the same number of layers. We also separate the union of all the levels from $\mathrm{BQP}$ relative to an oracle. The lower bounds rest on a structural property of the hierarchy: the number of Hadamard layers limits how adaptively a circuit can query its oracle. With a phase oracle, a circuit with $k$ layers is reproduced exactly by an algorithm making only $k-1$ rounds of parallel queries, which brings known lower bounds for such algorithms to bear. The standard oracle lets a circuit branch on earlier answers, and that case needs a separate argument.
- Abstract（参考訳）: フーリエ階層 $\mathrm{FH}_0\subseteq\mathrm{FH}_1\subseteq\mathrm{FH}_2\subseteq\cdots$ は Shi (TCS 2005) によって導入されたもので、使用するアダマール層の数による量子計算を測定する。
2つの層の間において、回路は基底状態を透過し、位相を付加するが、重ね合わせは生じない。
第1のレベルはちょうど$\mathrm{BPP}$であり、第2のレベルはすでにサイモンの問題を解き、位相推定によって整数を分解している。
シーは、全ての付加層が計算力を厳密に増すと推測し、最初のステップとして、連続するレベル間のオラクルの分離について質問した。
私たちの知る限り、質問はすべてのレベルで開かれました。
任意の定数 $k\ge2$ に対して、あるオラクルが $\mathrm{FH}_k\subsetneq\mathrm{FH}_{k+1}$ であることを示す。
この分離問題はForrelation (Aaronson and Ambainis, STOC 2015): 上記のレベルは一定数のクエリで解決するが、レベルでは$k$は指数関数的に多くのクエリを生成する回路でも難しい。
これは、通常、神託、位相神託、およびその答えをレジスタに書き込む標準神託への回路アクセスを与える方法の両方に当てはまる。
託宣とは対照的に、同じ数の層において、標準的な託宣は厳格に強力である。
また、すべてのレベルの和は、オラクルに対して$\mathrm{BQP}$から分離する。
下位境界は階層の構造的性質に依存しており、アダマール層の数によって、回路がそのオラクルをどれだけ適応的にクエリできるかが制限される。
位相オラクルでは、$k$の層を持つ回路は、並列クエリをわずか$k-1$のラウンドで生成するアルゴリズムによって正確に再現される。
標準的なオラクルは、初期の答えに回路の分岐を与え、その場合別の引数を必要とする。
関連論文リスト
- A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
我々は、要素が時間とともに到着する際のソリューションの品質と安定性のトレードオフについて研究する。
我々のアルゴリズムは,有理オラクル$を$O(varepsilon-1)$recourseで実装し,そのアルゴリズムから普遍価格証明書の存在を分離する。
論文 参考訳（メタデータ） (2026-09-09T10:13:43Z) - Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memory [65.64123585249297]
メモリが$m$ の単位球上の$d$ 次元 1$-Lipschitz 凸関数を最小化する。
まず、そのようなアルゴリズムは、$tilde(fracd2sqrtm)$ Oracle queryを作らなければならないことを示す。
決定論的最適化アルゴリズムでは$tilde(mind1.6,fracd8/3m2/3)$クエリが必要である。
論文 参考訳（メタデータ） (2026-07-21T00:40:59Z) - A Relativizing MIP for BQP [2.060642030400714]
例えば、$mathsfBQP subseteq mathsfMIP$ は任意の古典的オラクルに対して成り立つことを示す。
我々は、証明効率のプロキシとして相対化を提案し、オラクルの世界における$mathsfBQP$の$mathsfIP$への進展が、非暗号化対話プロトコルに繋がることを期待している。
論文 参考訳（メタデータ） (2026-04-13T18:45:12Z) - Learning Multinomial Logits in $O(n \log n)$ time [56.23331174813387]
MNLモデル(Multinomial Logit、MNL)は、アイテム$[n]=1, ..., n$の有限宇宙から成り、それぞれ正の重みを割り当てる。
クエリはslateと呼ばれる許容可能なサブセットを指定し、モデルはそのslateからその重みに比例した確率で1つのアイテムを選択する。
このクエリモデルは、文学におけるPockett-Luceモデルまたは条件付きサンプリングオラクルとしても知られている。
論文 参考訳（メタデータ） (2026-01-07T22:07:44Z) - Computational Lower Bounds for Regret Minimization in Normal-Form Games [68.66209476382213]
乗算重み更新などの既存の学習アルゴリズムが最適に近いことを示す。
結果はKothari と Mehta が提案したアルゴリズムの枠組みで得られた。
論文 参考訳（メタデータ） (2024-11-04T00:39:52Z) - Efficient Quantum State Synthesis with One Query [0.0]
本稿では,古典的オラクルへの単一クエリ(重ね合わせ)を実現する時間類似量子アルゴリズムを提案する。
我々は、すべての$n$-qubit状態が、適切な有限ゲート集合上の$On/n)$-size回路によって0.01エラー内に構築可能であることを証明した。
論文 参考訳（メタデータ） (2023-06-02T17:49:35Z) - Quantum Algorithms for Identifying Hidden Strings with Applications to
Matroid Problems [8.347058637480506]
我々は、ペアの$s, s'$を特定するために、最大内部積のオラクルに$O(1)$クエリを消費する量子アルゴリズムを提案する。
また、サブセットのオラクルに$fracn2+O(sqrtn)$クエリを消費する量子アルゴリズムを提案し、任意の古典的アルゴリズムが少なくとも$n+Omega(1)$クエリを必要とすることを証明した。
論文 参考訳（メタデータ） (2022-11-19T11:14:19Z) - The First Optimal Acceleration of High-Order Methods in Smooth Convex
Optimization [88.91190483500932]
本研究では,滑らかな凸最小化問題の解法として最適高次アルゴリズムを求めるための基本的オープンな問題について検討する。
この理由は、これらのアルゴリズムが複雑なバイナリプロシージャを実行する必要があるため、最適でも実用でもないからである。
我々は、最初のアルゴリズムに$mathcalOleft(epsilon-2/(p+1)right)$pthのオーダーオーラクル複雑性を与えることで、この根本的な問題を解決する。
論文 参考訳（メタデータ） (2022-05-19T16:04:40Z) - An optimal oracle separation of classical and quantum hybrid schemes [0.0]
任意の深さパラメータ$d$に対して、計算時間古典が許されるとき、量子深さ$d$と2d+1$を分離するオラクルが存在することを示す。
これは古典的および量子的ハイブリッドスキームの最適オラクル分離を与える。
論文 参考訳（メタデータ） (2022-05-10T02:31:19Z) - Exponential Separation between Quantum and Classical Ordered Binary
Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
量子順序付き二項決定図($OBDD$)モデルについて検討する。
入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。
read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
論文 参考訳（メタデータ） (2022-04-22T12:37:56Z) - Simplified Quantum Algorithm for the Oracle Identification Problem [0.0]
oracleは未知の文字列のビットに$x$ of length$n$をアクセスし、既知のセットである$Csubseteq0,1n$に属することを約束する。
目標は、できるだけ少数のオラクルへのクエリを使って$x$を識別することだ。
この問題に対して,クエリ複雑性を$Oleft(sqrtfracnlog M log(n/log M)+1right)$,$M$は$C$である。
論文 参考訳（メタデータ） (2021-09-08T19:48:27Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。