Local Indistinguishability of Probability Distributions
Program: Institute for Theoretical Computer Science and Communications (ITCSC) Summer Research Program, The Chinese University of Hong Kong
Supervisor: Prof. Andrej Bogdanov, Department of Computer Science and Engineering, The Chinese University of Hong Kong
Co-author: Xin Lyu, Yao Class, Tsinghua University
Introduction
Suppose we have two probability distributions p and q, both defined on fixed-length bit strings (say length-3), and with disjoint supports. Here is an example, where the probability mass is denoted below a string:
You can check that p and q have disjoint supports.
The preliminary question is: given a random sample from either p or q (with probability 1/2 each), how good could an algorithm be at guessing which distribution it is from? Of course, the problem would be trivial if the sample is fully known. What if the algorithm is allowed to query only two bits of the sample in any order?
Before we dive into the problem, let's cover some backgrounds first. The algorithm is called a distinguisher, and there are different types of distinguishers:
- Non-adaptive distinguishers. These always look at fixed bit positions of the sample, say the first and the second bits.
- Adaptive distinguishers. These could have some strategies of determining which bit positions to look at. An example is below.
- Quantum distinguishers. These are quantum circuits behind the scene, and the querying process is implemented with quantum oracles.
In order to evaluate the performance of a distinguisher, let's define a distinguishing advantage for it:
Some simple calculations yield the advantage of this distinguisher, which is one third:
It is obvious to see that there are three different non-adaptive distinguishers, and they all perform worse than the adaptive one:
Research Question
Please refer to the slides below.
In this project, we have constructed several examples with various gaps and ratios of the advantages. In the last example, we came up with a construction inspired by the Deutsch-Jozsa algorithm, and proved that a quantum distinguisher could perfectly distinguish between the two distributions after querying half of the bits, while classical distinguishers all fail to achieve non-zero advantage without revealing all the bits.
Please refer to the slides for more information.