論文の概要: 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$でスケールする。
この証明のために、量子分離可能性問題と接続し、線形制約を持つ改良された多元量子デファインッティ定理を用いる。
また、量子側情報に対する識別可能性の損失を最小化する情報完全測定も導出する。
関連論文リスト
- 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.3916094706589679]
マンデルスタム-タム境界は、あるパラメータ上でリー-チャウ境界を最適化することで得られることを示す。
ヒルベルト空間の次元が $lesssim 2000$ であれば、$p$ に最適化された統一境界は数分で正確に計算できる。
論文 参考訳(メタデータ) (2023-10-13T01:52:04Z) - Approximation Algorithms for Quantum Max-$d$-Cut [42.248442410060946]
量子Max-$d$-Cut問題(Quantum Max-$d$-Cut problem)は、プロジェクターに付随する期待エネルギーを、全ての局所相互作用上の2つの$d$-dimensional quditsの非対称部分空間に最大化する量子状態を見つけることである。
我々は,非自明な性能保証を実現するために,有界な純度を持つ混合状態の積状態解を求めるアルゴリズムを開発した。
論文 参考訳(メタデータ) (2023-09-19T22:53:17Z) - 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) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。
我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。
我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
論文 参考訳(メタデータ) (2020-04-14T11:05:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。