4
$\begingroup$

It is my understanding that mostly one considers as the "classical" state, a single bit string (eg 00101), with a discrete number of deterministic gates applied to it. All computers that loosely form this architecture would be equivalent, according to the Church-Turing these, and as such define the P complexity class for problems where they are efficient.

Then, there are quantum computers, that can handle superpositions of bit strings, e.g. $(|00101\rangle+|00111\rangle)/\sqrt 2$. For these, tailored algorithms such as Shor's one, can allow more complex operations out of the P class in polynomial time.

My question is, to what extend has the power of classically mixed states been studied? They seem to be largely overlooked? Could it be that non-P problems can be solved efficiently when working with classical mixtures such as $(|00101\rangle\langle 00101|+|00111\rangle\langle 00111|)/2$, i.e. diagonal density matrices, or Markov processes represented by a classical master equation.

I have seen some work where "classical fluctuations" in the sense of interaction with the environment are seen as a resource (e.g. https://www.nature.com/articles/nphys1342 , https://journals.aps.org/pra/abstract/10.1103/PhysRevA.59.2468), but my question goes deeper than that and asks whether classical mixtures should be considered completely on the same footing as quantum superpositions, and whether comparisons with purely deterministic classical algorithms are an unfair way of claiming quantum advantage.

EDIT: I'm also wondering if calculations with classical probability distributions are equivalent to the N ("non-deterministic") from NP

$\endgroup$
3
  • 3
    $\begingroup$ Do you know about the complexity class BPP? $\endgroup$
    – DaftWullie
    Commented Feb 22 at 8:49
  • $\begingroup$ @DaftWullie I wasn't really. But happy to learn more about it. Should BPP be considered the baseline to overcome for quantum advantage/supremacy rather than P? $\endgroup$
    – Wouter
    Commented Feb 22 at 9:49
  • 3
    $\begingroup$ Yes. It basically means that you've got access to a random number source as well, which is pretty much what a diagonal density matrix is (modulo some questions about what distributions you allow to be prepared). $\endgroup$
    – DaftWullie
    Commented Feb 22 at 10:14

3 Answers 3

7
$\begingroup$

(The other answers and comments have already touched on the main points, but I have to take the opportunity to answer in my own words.)

What you're describing is known as randomized or probabilistic computation. Randomized algorithms are widely used in practice, and it is not an exaggeration to say that no other topic has been studied more in computational complexity over the past 40 years — there are entire conferences on the topic (such as RANDOM, which has now run for about 25 years). Indeed, a random complexity theorist will likely care a lot more about randomness than they will about quantum computing.

In theoretical computer science, the term nondeterministic has a different meaning — so it doesn't literally mean not deterministic. In a nondeterministic computational model there may be multiple next-steps available at a given moment, and what is of interest is whether there exists a sequence of steps that leads to a given outcome. It's not meant to be something built, but rather it's a way of formalizing notions connected with verification. For example, you can think of proofs of theorems in some formal system as being like nondeterministic computations. It may be hard to find a proof, but if someone else has found a proof then (in principle) it's simple to check it one step at a time to see that it's valid.

It is pretty common that the notions of randomized and nondeterministic computations are connected in theoretical computer science, but the N in NP is absolutely not equivalent to using randomness.

$\endgroup$
3
  • 1
    $\begingroup$ To me, "non-deterministic" has always felt like one of the worst (or let's say "most misleading", to avoid complaints) misnomers -- is there a historic explanation as to where this came from? -- I mean, at least my feeling is that anyone but a theoretical computer scientist would interpret "nondeterministic" as something involving randomness. $\endgroup$ Commented Feb 23 at 14:17
  • 2
    $\begingroup$ I agree that it's pretty bad. I believe Rabin and Scott introduced the term in their 1959 paper on finite automata (but don't quote me on that). So what's worse: the term nondeterministic or the fact that thousands and thousands of undergraduates have been forced to memorize their procedure for converting nondeterministic into deterministic finite automata? $\endgroup$ Commented Feb 23 at 14:34
  • $\begingroup$ (Don't get me wrong, it's an amazing paper.) $\endgroup$ Commented Feb 23 at 14:41
2
$\begingroup$

"Nondeterministic" as used in theoretical computer science is a legacy term popularized from at least the 70's, and imagines a special Turing machine (that's the machine with an infinite tape and a head moving the tape forward and backward, writing and erasing 0's and 1's). This nondeterministic machine can make state transitions in a nondeterministic fashion. Such a machine can take multiple parallel paths down the computation - this is why we refer to the model as "we can always randomly guess the answer to some problem in NP!".

But, it seems different than the mixed-state quantum machine envisioned in the question. A nondeterministic Turing machine is a fanciful machine that has not (yet) been built; however, many people believe no such machine exists in the real world. Depending on how broad the question is read, the mixed-state quantum machine described in the question may be more akin to a (bounded error) probabilistic machine as suggested by @DaftWullie, which is similar to the traditional Turing machine but includes a special "coin-flip" instruction to accommodate the randomness.

That's not to say that mixed-state quantum machines are not interesting objects to study - indeed, if one is granted a single (pure-state) qubit that can act to control operations of a well-defined unitary $U$ on a mixed-state ensemble, then this model may be able to do solve very interesting problems that are not likely to be in P, nor even in NP. This is the "DQC1" or "One Clean Qubit"model of computation. In this model the clean qubit stores, in its amplitudes, the trace of $U$; this trace is intractable to determine with a classical computer.

$\endgroup$
1
  • $\begingroup$ So, 'nondeterministic' is akin to evolving the whole probability density function, and 'probabilistic' means a single shot evolution, sampled from the probability density function. Physicsally, for a mixed state we tend to sat that it is "actually" in only one of the pure state so the 'probabilistic' description seems more appropriate. However, In a situation such as a thermal Gibbs state, one would usually say that the best description is really the mixed state as a whole, and then it gets closer to the "nondeterministic" one? $\endgroup$
    – Wouter
    Commented Feb 26 at 3:48
0
$\begingroup$

Mixtures like your given $(|00101\rangle\langle00101|+|00111\rangle\langle00111| )/2$ are in fact describing random distributions of classical results, so you are asking here about a non-deterministic machine. As for the question to what extent it has been studied, quite a lot, it seems: https://en.wikipedia.org/wiki/Nondeterministic_Turing_machine#Computational_equivalence_with_DTMs.

And what might be the extra power of classically mixed states? As the link explains this is related to the "P=NP problem", so at least that has also been studied intensively! Finally, the question whether the extra power (if there is any) of the classically mixed states would actually be equal to that of pure quantum states: this has answer no, unless all the extensive research into quantum error corrections has overlooked that noisy quantum computing is actually perfectly fine. Because the problem to be solved there is precisely that mixed states are what results from this noise.

$\endgroup$
2
  • 1
    $\begingroup$ Thanks for your answer! I find in the last section of the Wikipedia page, very interestingly, that the relation with quantum computers has not really been sorted out, but it has been believed that both can perform some tasks that the other efficiently that the other cannot? Although the link is old, it would mean that there is no known problem where it has actually been proven that it is more efficient on a quantum computer than on a NTM? And it is actually believed that NTM can solve NP-complete problems efficiently? That would be very powerful. $\endgroup$
    – Wouter
    Commented Feb 23 at 1:59
  • 1
    $\begingroup$ @Wouter: It depends on relation between complexity classes P, NP, BQP and BPP. If for example BPP = BQP, then non-deterministic classical computers would be as powerful as quantum ones. If P = NP, we again would need only classical ones. However, it seems that this is hardly the case. Although research is still far from final conclusion... $\endgroup$ Commented Feb 23 at 7:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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