More Like this

1. On the optimal error exponents for classical and quantum antidistinguishability

   https://doi.org/10.1007/s11005-024-01821-z  

   Mishra, Hemant K; Nussbaum, Michael; Wilde, Mark M (June 2024, Letters in Mathematical Physics)

   The concept of antidistinguishability of quantum states has been studied to investigate foundational questions in quantum mechanics. It is also called quantum state elimination, because the goal of such a protocol is to guess which state, among finitely many chosen at random, the system is not prepared in (that is, it can be thought of as the first step in a process of elimination). Antidistinguishability has been used to investigate the reality of quantum states, ruling out ψ-epistemic ontological models of quantum mechanics (Pusey et al. in Nat Phys 8(6):475–478, 2012). Thus, due to the established importance of antidistinguishability in quantum mechanics, exploring it further is warranted. In this paper, we provide a comprehensive study of the optimal error exponent—the rate at which the optimal error probability vanishes to zero asymptotically—for classical and quantum antidistinguishability. We derive an exact expression for the optimal error exponent in the classical case and show that it is given by the multivariate classical Chernoff divergence. Our work thus provides this divergence with a meaningful operational interpretation as the optimal error exponent for antidistinguishing a set of probability measures. For the quantum case, we provide several bounds on the optimal error exponent: a lower bound given by the best pairwise Chernoff divergence of the states, a single-letter semi-definite programming upper bound, and lower and upper bounds in terms of minimal and maximal multivariate quantum Chernoff divergences. It remains an open problem to obtain an explicit expression for the optimal error exponent for quantum antidistinguishability. 

   more » « less
2. On the optimal error exponents for classical and quantum antidistinguishability

   Mishra, Hemant K; Nussbaum, Michael; Wilde, Mark M (June 2024, Letters in mathematical physics)

   The concept of antidistinguishability of quantum states has been studied to investigate foundational questions in quantum mechanics. It is also called quantum state elimination, because the goal of such a protocol is to guess which state, among finitely many chosen at random, the system is not prepared in (that is, it can be thought of as the first step in a process of elimination). Antidistinguishability has been used to investigate the reality of quantum states, ruling out psi-epistemic ontological models of quantum mechanics (Pusey et al. in Nat Phys 8(6):475–478, 2012). Thus, due to the established importance of antidistinguishability in quantum mechanics, exploring it further is warranted. In this paper, we provide a comprehensive study of the optimal error exponent—the rate at which the optimal error probability vanishes to zero asymptotically—for classical and quantum antidistinguishability. We derive an exact expression for the optimal error exponent in the classical case and show that it is given by the multivariate classical Chernoff divergence. Our work thus provides this divergence with a meaningful operational interpretation as the optimal error exponent for antidistinguishing a set of probability measures. For the quantum case, we provide several bounds on the optimal error exponent: a lower bound given by the best pairwise Chernoff divergence of the states, a single-letter semi-definite programming upper bound, and lower and upper bounds in terms of minimal and maximal multivariate quantum Chernoff divergences. It remains an open problem to obtain an explicit expression for the optimal error exponent for quantum antidistinguishability. 

   more » « less
3. Topological and Algebraic Properties of Chernoff Information between Gaussian Graphs

   https://doi.org/10.1109/ALLERTON.2018.8635946  

   Li, Binglin; Wei, Shuangqing; Wang, Yue; Yuan, Jian (October 2018, 2018 56th Annual Allerton Conference on Communication, Control, and Computing (Allerton))

   In this paper, we want to find out the determining factors of Chernoff information in distinguishing a set of Gaussian graphs. We find that Chernoff information of two Gaussian graphs can be determined by the generalized eigenvalues of their covariance matrices. We find that the unit generalized eigenvalues do not affect Chernoff information and their corresponding dimensions do not provide information for classification purpose. In addition, we can provide a partial ordering using Chernoff information between a series of Gaussian trees connected by independent grafting operations. By exploiting relationship between generalized eigenvalues and Chernoff information, we can do optimal classification linear dimension reduction with least loss of information for classification. 

   more » « less
4. Singletons for Simpletons: Revisiting Windowed Backoff with Chernoff Bounds

   https://doi.org/10.4230/LIPIcs.FUN.2021.24  

   Zhou, Qian; Calvert, Aiden; Young, Maxwell (September 2020, 10th International Conference on Fun with Algorithms (FUN 2021))

   Farach-Colton, Martin; Prencipe, Giuseppe; Uehara, Ryuhei (Ed.)

   Backoff algorithms are used in many distributed systems where multiple devices contend for a shared resource. For the classic balls-into-bins problem, the number of singletons - those bins with a single ball - is important to the analysis of several backoff algorithms; however, existing analyses employ advanced probabilistic tools to obtain concentration bounds. Here, we show that standard Chernoff bounds can be used instead, and the simplicity of this approach is illustrated by re-analyzing some well-known backoff algorithms. 

   more » « less
5. Parametrized topological complexity of sphere bundles

   https://doi.org/10.12775/TMNA.2022.049  

   Farber, Michael; Weinberger, Shmuel Weinberger (January 2023, Topological Methods in Nonlinear Analysis)

   Parametrized motion planning algorithms \cite{CFW} have high degree of flexibility and universality, they can work under a variety of external conditions, which are viewed as parameters and form part of the input of the algorithm. In this paper we analyse the parameterized motion planning problem in the case of sphere bundles.Our main results provide upper and lower bounds for the parametrized topological complexity; the upper bounds typically involve sectional categories of the associated fibrations and the lower bounds are given in terms of characteristic classes and their properties. We explicitly compute the parametrized topological complexity in many examples and show that it may assume arbitrarily large values. 

   more » « less