論文の概要: Quasi-polynomial time algorithms for free quantum games in bounded
dimension
- arxiv url: http://arxiv.org/abs/2005.08883v3
- Date: Mon, 7 Jun 2021 09:50:35 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-19 11:14:45.453148
- Title: Quasi-polynomial time algorithms for free quantum games in bounded
dimension
- Title（参考訳）: 有界次元自由量子ゲームに対する準多項式時間アルゴリズム
- Authors: Hyejung H. Jee, Carlo Sparaciari, Omar Fawzi, and Mario Berta
- Abstract要約: 2プレイヤフリーゲームの値に対する加法$epsilon$-approximationsを計算するために、$exp(mathcalObig(T12(log2(AT)+log(Q)log(AT))/epsilon2big))という半定値プログラムを与える。
量子分離性問題と接続し、線形制約を伴う改良された多部量子デ・フィネッティ定理を用いる。
- 参考スコア（独自算出の注目度）: 11.56707165033
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We give a converging semidefinite programming hierarchy of outer
approximations for the set of quantum correlations of fixed dimension and
derive analytical bounds on the convergence speed of the hierarchy. In
particular, we give a semidefinite program of size
$\exp(\mathcal{O}\big(T^{12}(\log^2(AT)+\log(Q)\log(AT))/\epsilon^2\big))$ to
compute additive $\epsilon$-approximations on the values of two-player free
games with $T\times T$-dimensional quantum assistance, where $A$ and $Q$ denote
the numbers of answers and questions of the game, respectively. For fixed
dimension $T$, this scales polynomially in $Q$ and quasi-polynomially in $A$,
thereby improving on previously known approximation algorithms for which
worst-case run-time guarantees are at best exponential in $Q$ and $A$. For the
proof, we make a connection to the quantum separability problem and employ
improved multipartite quantum de Finetti theorems with linear constraints. We
also derive an informationally complete measurement which minimises the loss in
distinguishability relative to the quantum side information - which may be of
independent interest.
- Abstract（参考訳）: 固定次元の量子相関の集合に対する外部近似の収束半定値プログラミング階層を与え、階層の収束速度に関する解析的境界を導出する。
特に、サイズ$\exp(\mathcal{O}\big(T^{12}(\log^2(AT))+\log(Q)\log(AT))/\epsilon^2\big))$を加法$\epsilon$-approximations on the value of two-player free game with $T\times T$-dimensional quantum assistance, ここで、$A$と$Q$はそれぞれゲームの答えと質問の数を表す。
固定次元$T$の場合、これは多項式的に$Q$で、準多項式的に$A$でスケールする。
この証明のために、量子分離可能性問題と接続し、線形制約を持つ改良された多元量子デファインッティ定理を用いる。
また、量子側情報に対する識別可能性の損失を最小化する情報完全測定も導出する。
関連論文リスト
- Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
量子コンピュータを用いた結合型古典的高調波発振器系の周波数応答関数の推定問題について検討する。
提案する量子アルゴリズムは,標準的な$sスパース,オーラクルベースのクエリアクセスモデルで動作する。
そこで,本アルゴリズムの簡単な適応により,時間内に無作為な結束木問題を解くことを示す。
論文 参考訳（メタデータ） (2024-05-14T15:28:37Z) - The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。
特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。
QMA(2) が $textQMA+(2)$ に等しいことを示す。
論文 参考訳（メタデータ） (2024-02-29T01:35:46Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - A Unifying Quantum Speed Limit For Time-Independent Hamiltonian Evolution [0.3314882635954752]
マンデルスタム-タム境界は、あるパラメータ上でリー-チャウ境界を最適化することで得られることを示す。
ヒルベルト空間の次元が $lesssim 2000$ であれば、$p$ に最適化された統一境界は数分で正確に計算できる。
論文 参考訳（メタデータ） (2023-10-13T01:52:04Z) - Quantum Speedups for Zero-Sum Games via Improved Dynamic Gibbs Sampling [30.53587208999909]
我々は、ゼロサムゲームにおける$epsilon$-approximate Nash平衡を、有界なエントリを持つ$m倍n$ペイオフ行列で計算するための量子アルゴリズムを与える。
ペイオフ行列にアクセスするための標準的な量子オラクルが与えられたとき、我々のアルゴリズムは$widetildeO(sqrtm + ncdot epsilon-2.5 + epsilon-3)$で実行され、$epsilon$-approximate Nash平衡の古典的な表現を出力する。
論文 参考訳（メタデータ） (2023-01-10T02:56:49Z) - 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) - Quantum simulation of real-space dynamics [7.143485463760098]
実空間力学のための量子アルゴリズムの体系的研究を行う。
我々は、量子化学のより高速な実空間シミュレーションを含む、いくつかの計算問題に応用する。
論文 参考訳（メタデータ） (2022-03-31T13:01:51Z) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。
振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
論文 参考訳（メタデータ） (2022-01-31T22:19:49Z) - Matrix Discrepancy from Quantum Communication [13.782852293291494]
我々は,不一致の最小化と(量子)通信複雑性の新たな関連性を開発する。
対称$n times n$$A_1,ldots,A_n$ with $|A_i| leq 1$ and $|A_i|_F leq n1/4$ に対し、pm 1n において $sum_i leq n x_i A_i$ の最大固有値が最大となる符号 $x が存在することを示す。
論文 参考訳（メタデータ） (2021-10-19T16:51:11Z) - Estimating Gibbs partition function with quantumClifford sampling [6.656454497798153]
分割関数を推定するハイブリッド量子古典アルゴリズムを開発した。
我々のアルゴリズムは浅い$mathcalO(1)$-depth量子回路を必要とする。
浅層量子回路は、現在利用可能なNISQ(ノイズ中間スケール量子)デバイスにとって極めて重要であると考えられている。
論文 参考訳（メタデータ） (2021-09-22T02:03:35Z) - Quantum Algorithm for Fidelity Estimation [8.270684567157987]
2つの未知の混合量子状態 $rho$ と $sigma$ に対して、それらの忠実度 $F(rho,sigma)$ は基本的な問題である。
我々は、この問題を$namepoly(log (N), r, 1/varepsilon)$ timeで解く量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-03-16T13:57:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。