論文の概要: 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（参考訳）: 完全境界ブロック多重線形形式の影響と量子アルゴリズムの古典シミュレーション
• 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を含む特定の量子アルゴリズムのクラスに対する効率的な古典的ほぼすべてのシミュレーションを得る。 我々の主な技術的結果は自由確率論への接続に依存する。

関連論文リスト

• Parallel Quantum Advantage with Limited Adaptivity Requires Structure [2.6546344072296084]
  我々はAaronsonとAmbainisの予想を証明し、量子クエリアルゴリズムが古典的なシミュレーションをほぼすべての場所に含んでいることを証明した。 指数量子スピードアップは十分に構造化された入力でのみ可能であることを示す。 我々の主な技術的貢献は、密分布から引き出されたオラクルにオラクル上の一様分布を関連付ける結合定理である。
  論文  参考訳（メタデータ） (2026-08-20T17:37:03Z)
• Quantum Speedups Require Structure or Depth [6.942576237126963]
  すべての$t$-query $d$-round量子アルゴリズムが、$tO(d2)$古典的なクエリでほとんどの入力でシミュレート可能であることを示す。 非構造問題に対して、超多項式スピードアップは超定常深さの量子回路を必要とし、指数的なスピードアップはさらに深さを必要とする。
  論文  参考訳（メタデータ） (2026-08-19T17:42:10Z)
• Optimal Lower Bounds for Hamiltonian Simulation [42.227880669333835]
  ハミルトニアン$H = sum_j h_j$ の場合、ゲート上の下界と量子コンピュータ上の時間発展をシミュレートするクエリの複雑さを証明できる。 任意の項ノルムのホールドは$|h_j|$, time $t$, trace-distance error $$である。
  論文  参考訳（メタデータ） (2026-07-22T07:41:32Z)
• From Hilbert's Tenth Problem to Quantum Speedup: Explicit Oracles for Bounded Diophantine Systems [0.0]
  我々は、有界整数領域上のディオファント方程式を解くために、完全に可逆的なアルゴリズムフレームワークを導入する。 抽象ブラックボックスの仮定を超えて、この明示的なアーキテクチャ合成は、必要な量子演算が有界なオーバーヘッドとして働くことを保証している。
  論文  参考訳（メタデータ） (2026-05-13T18:01:01Z)
• Average-case quantum complexity from glassiness [45.57609001239456]
  グラスネス(Glassiness)は、物理学において、不安定な自由エネルギーの風景を特徴とする現象であり、安定な古典的アルゴリズムの難しさを意味する。 レプリカ対称性の破れに基づく標準的な量子ガラス性の概念は、ギブスサンプリングのための安定な量子アルゴリズムを妨げていることを証明している。
  論文  参考訳（メタデータ） (2025-10-09T17:37:33Z)
• Halving the Cost of Quantum Algorithms with Randomization [0.138120109831448]
  量子信号処理(QSP)は、線形演算子の変換を実装するための体系的なフレームワークを提供する。 近年の研究では、量子チャネルへのユニタリゲートを促進する技術であるランダム化コンパイルが開発されている。 提案アルゴリズムは, 平均進化が対象関数に収束するように戦略的に選択されたランダム化の確率的混合を実装し, 誤差は等価個体よりも2次的に小さい。
  論文  参考訳（メタデータ） (2024-09-05T17:56:51Z)
• Classically estimating observables of noiseless quantum circuits [36.688706661620905]
  本稿では,ほとんどの量子回路上での任意の観測値の期待値を推定するための古典的アルゴリズムを提案する。 非古典的にシミュレート可能な入力状態やオブザーバブルの場合、予測値は、我々のアルゴリズムを関連する状態の古典的な影またはオブザーバブルで拡張することで推定できる。
  論文  参考訳（メタデータ） (2024-09-03T08:44:33Z)
• 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)
• Quantum Logarithmic Space and Post-selection [0.4588028371034406]
  ポストセレクション(Post-Selection)は、アーロンソンによって量子複雑性理論の分野に導入された影響力ある概念である(Royal Society A, 2005 の論文)。 我々の主な結果は、$sf PostBQL=$、すなわち、選択後(sf PostBQL$)で境界付きエラー(polynomial-time)対数空間量子アルゴリズムによって解決できる問題のクラスを示す。 また、$sf$は時間制限のない有界誤差対数空間量子アルゴリズムによって解くことができる問題のクラスと一致することを示す。
  論文  参考訳（メタデータ） (2021-05-06T14:02:01Z)
• 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)

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

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