0
$\begingroup$

Imagine there is a class of system such that a measurement can be performed on an exemplar of this class, each measurement producing 1 bit of information. There are no limitation on how many times the experiment can invoke new instance of a class, and there are no limitations on how many times measurement can be performed. However there are only N types of measurements that can be done.

To clarify, here are some examples:

  1. The measured systems are fixed 4-bit strings, all equal to “0100”; N = 4 and corresponds to measurements of each one of these bits
  2. The measured system is 4 independent random bits. N = 4 and correspond to measurements of these random bits.
  3. Measured system is a pair of entangled photons. N = 4 (there are 2 ways of measuring polarization of the first photon, and 2 ways of measurement the polarization of the second photon).

It’s clear that system as a black box looks the same, and whatever its inner workings, it can be judged by results obtained from the string of 0s and 1s obtained by the measurements. For example, in 1'st case 3 of 4 types of measurements would produce 0s for every instance of the system. In 2nd case all measurements would produce independent random bits. In the 3rd case there would also be random bits, however their distribution will violate Bell's inequality.

My question is – what are the most general classes of systems that can be described by this definition and discriminated by a limited pre-set amount of kinds of measurements?

Improve this question
$\endgroup$
3
  • $\begingroup$ How do you plan to define "general", and in particular, whether one system is "more general" than another? What makes you think there exists a single "most general" system of this form? What do you mean "discriminated by..."? Discriminated from what? $\endgroup$
    – D.W.
    Jun 16, 2016 at 19:56
  • $\begingroup$ @D.W. By “discriminated” I mean that if experimenter knows that system can be either of class A (say, static string) or class B (say, random string), there exists an algorithm (a sequence) of measurements that with probability > 1-epsilon tells what is the actual class of the system. $\endgroup$
    – Oleg Stroganov
    Jun 16, 2016 at 20:29
  • $\begingroup$ By “general” classes I mostly rely on the common sense. A concrete class may belong to a more general class with parameters: any static string belongs to more general class of static strings with N parameters; any random bit belongs to more general class of random bits with probability of 1s being p%. Once I know the general class (static or random string), by performing measurements I could estimate parameters. In one sense, “generalness” is related to a sequence of algorithms that must be applied to discriminate one class from another, but maybe there is more natural way of looking at it. $\endgroup$
    – Oleg Stroganov
    Jun 16, 2016 at 20:31

1 Answer 1

Reset to default
2
$\begingroup$

I don't think there will be any result of the form you want. There's no single "most general system" that has this property.

(Instead, it'd be better to choose some specific pair of classes of systems you're interested in and ask specifically how to distinguish those two; that's more likely to yield an answerable question.)

To learn about work in the computer science literature that might be applicable to your situation, here are some subjects you should probably take a look at:

  • Total variation distance measures the "probability" with which we can distinguish two distributions, given a single sample from each, and assuming we have unlimited computational power. (There are also other metrics.)

  • Computational indistinguishability, as studied in the cryptographic literature, measures the "probability" with which we can distinguish two distributions, assuming that the distinguishing algorithm is limited to some feasible amount of computation (e.g., no more than one billion CPU-years).

Your situation amounts to the following: we have a family of distributions $D_1(\theta_1)$ parameterized by $\theta_1$ (corresponding to systems of class A, where $\theta_1$ indicates which specific system instance we are working with) and a family of distributions $D_2(\theta_2)$ parameterized by $\theta_2$ (corresponding to systems of class B, where $\theta_2$ indicates the specific instance). The observer doesn't know $\theta_1,\theta_2$ but gets to observe either a single value sampled from distribution $D_1(\theta_1)$ or a single value $D_2(\theta_2)$, and wants to try to distinguish which of those two types of values he has been given. You want to know whether, for all $\theta_1,\theta_2$, it's always possible to distinguish with good probability (say, better than guessing).

The special case of this is: given two distributions $D_1,D_2$, if the observe gets to observe either a single value sampled from $D_1$ or a single value sampled from $D_2$, can the observe distinguish which of those two types of values he has been given? That's been studied carefully. If there are no limits on the computational power of the algorithm used by the observer, the answer is characterized by the total variation distance. If the observer is limited to use a computationally-feasible algorithm, the answer is characterized by computational distinguishability.

For the case of a family of distributions, the answer will be characterized by

$$\min \{d(D_1(\theta),D_2(\theta_2) : \theta_1,\theta_2\}$$

where $d(\cdot,\cdot)$ is some appropriate distance measure (total variation distance, computational distinguishability).

There's also a corresponding theory about what happens if the observer gets to see $n$ samples drawn independently from the chosen distribution.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Is there any conceptual difference between distinguishing two classical probability distributions and distinguishing between classical distribution and a distribution generated by a quantum setup (say, with violation of Bell's inequalities)? $\endgroup$
    – Oleg Stroganov
    Jun 17, 2016 at 21:58
  • $\begingroup$ @OlegStroganov, I don't know. To me, that sounds like it should be posted as a separate, new question. This is a question-and-answer site, so we want one question and one answer. Comments shouldn't be used to ask follow-up questions or new questions; they should be asked separately (after thinking about them and researching them). I suspect the answer might depend on, e.g., what kinds of observations are permitted (can the distinguisher interact with the system or only passively measure?) and whether the distinguisher algorithm is classical or quantum. $\endgroup$
    – D.W.
    Jun 17, 2016 at 22:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.