Quasi-polynomial time algorithms for free quantum games in bounded
dimension
dimension
File(s)
Published version
Author(s)
Jee, Hyejung H
Sparaciari, Carlo
Fawzi, Omar
Berta, Mario
Type
Journal Article
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.
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.
Date Issued
2021-07-02
Date Acceptance
2021-04-23
Citation
LIPIcs : Leibniz International Proceedings in Informatics, 2021, 1, pp.1-20
ISSN
1868-8969
Publisher
Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
Start Page
1
End Page
20
Journal / Book Title
LIPIcs : Leibniz International Proceedings in Informatics
Volume
1
Copyright Statement
© Hyejung H. Jee, Carlo Sparaciari, Omar Fawzi, and Mario Berta;
licensed under Creative Commons License CC-BY 4.0
48th International Colloquium on Automata, Languages, and Programming (ICALP 2021
licensed under Creative Commons License CC-BY 4.0
48th International Colloquium on Automata, Languages, and Programming (ICALP 2021
Identifier
http://arxiv.org/abs/2005.08883v3
Subjects
quant-ph
quant-ph
Notes
v3: 20+14 pages, 1 figure, updated title, extended version
Date Publish Online
2021-07-02