論文の概要: Influence in Completely Bounded Block-multilinear Forms and Classical
Simulation of Quantum Algorithms
- arxiv url: http://arxiv.org/abs/2203.00212v1
- Date: Tue, 1 Mar 2022 03:42:24 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-23 12:25:08.098229
- Title: Influence in Completely Bounded Block-multilinear Forms and Classical
Simulation of Quantum Algorithms
- Title（参考訳）: 完全境界ブロック多重線形形式の影響と量子アルゴリズムの古典シミュレーション
- Authors: Nikhil Bansal and Makrand Sinha and Ronald de Wolf
- Abstract要約: Aaronson-Ambainis予想を証明する(Theory of Computing '14)
すべての完全有界次数-$d$ブロック-多重線型形式において、常に影響が少なくとも1/mathrmpoly(d)$の変数が存在する。
我々は、量子アルゴリズムの特定のクラスに対する効率的な古典的ほぼすべてのところのシミュレーションを得る。
- 参考スコア（独自算出の注目度）: 3.9156637371363874
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Aaronson-Ambainis conjecture (Theory of Computing '14) says that every
low-degree bounded polynomial on the Boolean hypercube has an influential
variable. This conjecture, if true, would imply that the acceptance probability
of every $d$-query quantum algorithm can be well-approximated almost everywhere
(i.e., on almost all inputs) by a $\mathrm{poly}(d)$-query classical algorithm.
We prove a special case of the conjecture: in every completely bounded
degree-$d$ block-multilinear form with constant variance, there always exists a
variable with influence at least $1/\mathrm{poly}(d)$. In a certain sense, such
polynomials characterize the acceptance probability of quantum query
algorithms, as shown by Arunachalam, Bri\"et and Palazuelos (SICOMP '19). As a
corollary we obtain efficient classical almost-everywhere simulation for a
particular class of quantum algorithms that includes for instance $k$-fold
Forrelation. Our main technical result relies on connections to free
probability theory.
- Abstract（参考訳）: アーロンソン・アンバイニス予想(Theory of Computing '14)は、ブールハイパーキューブ上のすべての低次有界多項式は影響変数を持つと述べている。
この予想が真であれば、すべての$d$-query量子アルゴリズムの受容確率は、$\mathrm{poly}(d)$-query 古典アルゴリズムによってほぼ至るところで(つまり、ほとんど全ての入力において)よく近似できることを意味する。
すべての完全有界次数-$d$ブロック-多重線型形式において、定数分散を持つ変数は常に、少なくとも 1/\mathrm{poly}(d)$ の影響を持つ変数が存在する。
ある意味で、そのような多項式は、Arunachalam, Bri\"et and Palazuelos (SICOMP '19) で示されているように、量子クエリアルゴリズムの受容確率を特徴づける。
系として、例えば$k$-fold forrelationを含む特定の量子アルゴリズムのクラスに対する効率的な古典的ほぼすべてのシミュレーションを得る。
我々の主な技術的結果は自由確率論への接続に依存する。
関連論文リスト
- Halving the Cost of Quantum Algorithms with Randomization [0.138120109831448]
量子信号処理(QSP)は、線形演算子の変換を実装するための体系的なフレームワークを提供する。
近年の研究では、量子チャネルへのユニタリゲートを促進する技術であるランダム化コンパイルが開発されている。
提案アルゴリズムは, 平均進化が対象関数に収束するように戦略的に選択されたランダム化の確率的混合を実装し, 誤差は等価個体よりも2次的に小さい。
論文 参考訳（メタデータ） (2024-09-05T17:56:51Z) - 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) - 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) - Generalized Hybrid Search and Applications to Blockchain and Hash
Function Security [50.16790546184646]
まず,ハイブリッド量子古典戦略を用いて,様々な探索問題を解くことの難しさについて検討する。
次に、ハイブリッド量子古典探索アルゴリズムを構築し、その成功確率を解析する。
論文 参考訳（メタデータ） (2023-11-07T04:59:02Z) - A one-query lower bound for unitary synthesis and breaking quantum
cryptography [7.705803563459633]
ユニタリ合成問題では、任意の$n$qubitのユニタリ$U$を、任意のブール関数$f$を計算するオラクルで拡張された効率的な量子$A$で実装できるかどうかを問う。
本研究は, 対向する$Af$の最大成功確率を解析することにより, 下位境界の証明を可能にする, 効率的なチャレンジャーアドゲームとしてのユニタリ合成を証明する。
論文 参考訳（メタデータ） (2023-10-13T05:39:42Z) - Influences of Fourier Completely Bounded Polynomials and Classical
Simulation of Quantum Algorithms [0.0]
量子クエリアルゴリズムは、フーリエ完全有界な新しいクラスによって特徴づけられることを示す。
我々は、すべてのそのような変数は影響のある変数を持つと推測する。
我々の証明は単純で、より良い定数を得ることができ、ランダム性を使用しない。
論文 参考訳（メタデータ） (2023-04-13T17:58:36Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - The principle of majorization: application to random quantum circuits [68.8204255655161]
i) 普遍的、ii) 古典的シミュラブル、iii) 普遍的、古典的シミュラブルの3つのクラスが考慮された。
回路のすべての族が平均的に正規化の原理を満たすことを検証した。
明らかな違いは、状態に関連したローレンツ曲線のゆらぎに現れる。
論文 参考訳（メタデータ） (2021-02-19T16:07:09Z) - Quasi-polynomial time algorithms for free quantum games in bounded
dimension [11.56707165033]
2プレイヤフリーゲームの値に対する加法$epsilon$-approximationsを計算するために、$exp(mathcalObig(T12(log2(AT)+log(Q)log(AT))/epsilon2big))という半定値プログラムを与える。
量子分離性問題と接続し、線形制約を伴う改良された多部量子デ・フィネッティ定理を用いる。
論文 参考訳（メタデータ） (2020-05-18T16:55:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。