4 papers
Approximating the Trace Distance Between Product Quantum States
Kun He, Dimitrios Myrisiotis, Junhong Nie +1
We study the trace distance \[D_{\mathrm{tr}}(Ï,Ï) =\frac12\|Ï-Ï\|_1, Ï=\bigotimes_{i=1}^nÏ_i,\quad Ï=\bigotimes_{i=1}^nÏ_i, \] when the two exponentially large states are…
Algorithms and Hardness for Estimating Statistical Similarity
Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel +3
We introduce and study the computational problem of determining statistical similarity between probability distributions. For distributions and over a finite sample space,…
Computational Explorations of Total Variation Distance
Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel +3
We investigate some previously unexplored (or underexplored) computational aspects of total variation (TV) distance. First, we give a simple deterministic polynomial-time algorithm…
Efficient, Low-Regret, Online Reinforcement Learning for Linear MDPs
Philips George John, Arnab Bhattacharyya, Silviu Maniu +2
Reinforcement learning algorithms are usually stated without theoretical guarantees regarding their performance. Recently, Jin, Yang, Wang, and Jordan (COLT 2020) showed a polynomi…