論文の概要: Influences of Fourier Completely Bounded Polynomials and Classical
Simulation of Quantum Algorithms
- arxiv url: http://arxiv.org/abs/2304.06713v1
- Date: Thu, 13 Apr 2023 17:58:36 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-14 13:19:07.209200
- Title: Influences of Fourier Completely Bounded Polynomials and Classical
Simulation of Quantum Algorithms
- Title（参考訳）: フーリエ完全有界多項式の影響と量子アルゴリズムの古典シミュレーション
- Authors: Francisco Escudero Guti\'errez
- Abstract要約: 量子クエリアルゴリズムは、フーリエ完全有界な新しいクラスによって特徴づけられることを示す。
我々は、すべてのそのような変数は影響のある変数を持つと推測する。
我々の証明は単純で、より良い定数を得ることができ、ランダム性を使用しない。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We give a new presentation of the main result of Arunachalam, Bri\"et and
Palazuelos (SICOMP'19) and show that quantum query algorithms are characterized
by a new class of polynomials which we call Fourier completely bounded
polynomials. We conjecture that all such polynomials have an influential
variable. This conjecture is weaker than the famous Aaronson-Ambainis (AA)
conjecture (Theory of Computing'14), but has the same implications for
classical simulation of quantum query algorithms.
We prove a new case of the AA conjecture by showing that it holds for
homogeneous Fourier completely bounded polynomials. This implies that if the
output of $d$-query quantum algorithm is a homogeneous polynomial $p$ of degree
$2d$, then it has a variable with influence at least $Var[p]^2$.
In addition, we give an alternative proof of the results of Bansal, Sinha and
de Wolf (CCC'22 and QIP'23) showing that block-multilinear completely bounded
polynomials have influential variables. Our proof is simpler, obtains better
constants and does not use randomness.
- Abstract（参考訳）: 我々は、Arunachalam, Bri\"et and Palazuelos (SICOMP'19) の主な結果の新しいプレゼンテーションを行い、量子クエリアルゴリズムがフーリエ完全有界多項式と呼ばれる新しい多項式のクラスによって特徴づけられることを示す。
そのような多項式はすべて影響変数を持つと推測する。
この予想は有名なaaronson-ambainis (aa) 予想 (theory of computing '14) よりも弱いが、量子クエリアルゴリズムの古典的なシミュレーションにも同じ意味を持つ。
我々は、同次フーリエ完全有界多項式に対して成り立つことを示すことにより、AA予想の新しいケースを証明した。
これは、$d$-query量子アルゴリズムの出力が次数2d$の等質多項式$p$であるなら、少なくとも$Var[p]^2$の影響を持つ変数を持つことを意味する。
さらに、Bansal, Sinha and de Wolf (CCC'22 and QIP'23) の結果の代替証明として、ブロック-多重線型完全有界多項式が影響変数を持つことを示す。
我々の証明はより単純で、より良い定数を得、ランダム性を使用しない。
関連論文リスト
- Quantum Advantage via Solving Multivariate Quadratics [12.62849227946452]
p_i(x_n)=y_i_iin [m]$ over $mathbbF$。
解は高い確率で存在するが、古典的暗号解析に基づく解を見つけることは困難である。
論文 参考訳（メタデータ） (2024-11-22T03:10:10Z) - Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - Complementary polynomials in quantum signal processing [0.0]
与えられた$P$を実装するには、まず対応する補完的な$Q$を構築しなければならない。
この問題に対する既存のアプローチでは、明示的な誤り解析には適さない数値的手法が採用されている。
複素解析を用いた補体系に対する新しいアプローチを提案する。
論文 参考訳（メタデータ） (2024-06-06T16:47:11Z) - The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。
特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。
QMA(2) が $textQMA+(2)$ に等しいことを示す。
論文 参考訳（メタデータ） (2024-02-29T01:35:46Z) - The Power of Adaptivity in Quantum Query Algorithms [0.5702169790677977]
問合せモデルにおける深度計算のトレードオフについて検討し、その深さは適応的な問合せラウンドの数と1ラウンド当たりの並列クエリ数に対応する。
我々は、量子アルゴリズム間の最も強力な分離を$r$対$r-1$の適応性を持つラウンドで達成する。
論文 参考訳（メタデータ） (2023-11-27T18:21:32Z) - An Exponential Separation Between Quantum Query Complexity and the
Polynomial Degree [79.43134049617873]
本稿では,部分関数に対する完全次数と近似量子クエリの指数関数的分離を実証する。
アルファベットのサイズについては、定値対分離の複雑さがある。
論文 参考訳（メタデータ） (2023-01-22T22:08:28Z) - Quantum and classical low-degree learning via a dimension-free Remez
inequality [52.12931955662553]
ハイパーグリッド上の関数をポリトーラス上の高調波拡張に関連付ける新しい方法を示す。
巡回群 $exp(2pi i k/K)_k=1K$ の積に対して函数の上限が$f$であることを示す。
我々は最近、超キューブやキュービット上の観測可能な観測値の低次学習を、同様に効率的に行う方法として、EI22, CHP, VZ22を引用して、新しい空間に拡張した。
論文 参考訳（メタデータ） (2023-01-04T04:15:40Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳（メタデータ） (2022-10-12T17:54:02Z) - On converses to the polynomial method [0.0]
アーロンソンらによる驚くべき「方法への逆」は、任意の有界二次函数は、グロエンディーク定数に関連する普遍的乗法因子まで正確に計算できることを示している。
小さい加法誤差を許容した場合、結果が依然として成り立つことを示す。
論文 参考訳（メタデータ） (2022-04-26T13:32:02Z) - Influence in Completely Bounded Block-multilinear Forms and Classical
Simulation of Quantum Algorithms [3.9156637371363874]
Aaronson-Ambainis予想を証明する(Theory of Computing '14)
すべての完全有界次数-$d$ブロック-多重線型形式において、常に影響が少なくとも1/mathrmpoly(d)$の変数が存在する。
我々は、量子アルゴリズムの特定のクラスに対する効率的な古典的ほぼすべてのところのシミュレーションを得る。
論文 参考訳（メタデータ） (2022-03-01T03:42:24Z) - A refinement of Reznick's Positivstellensatz with applications to
quantum information theory [72.8349503901712]
ヒルベルトの17番目の問題において、アルティンはいくつかの変数の任意の正定値が2つの平方和の商として書けることを示した。
レズニックはアルティンの結果の分母は常に変数の平方ノルムの$N$-次パワーとして選択できることを示した。
論文 参考訳（メタデータ） (2019-09-04T11:46:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。