Suppose $\mathbf{P} = \mathbf{BQP}$. Then what is randomness? Would it even exist at all?

Question

DISCLAIMER
I do apologize in advance if this question turns out to be silly, for some trivial reason that I may be overlooking in this moment.

---

Suppose for a moment that $\mathbf{P} = \mathbf{BQP}$ is true: it is possible to efficiently simulate quantum computation by classical deterministic computation.

Now, from that very little I know about quantum computing (I'm much less than an amateur when speaking about it), if I'm not wrong a Quantum Turing Machine is able, by its very definition, to generate true randomness.

Henceforth, if $\mathbf{P} = \mathbf{BQP}$, then there exists a classical deterministic algorithm which is able to quickly output true randomness (by just quickly simulating some Quantum Turing Machine).

But... what would randomness be then? Would it even exist at all? Would you be willing to continue to call it randomness?

John Von Neumann once said: "Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin". But the above classical deterministic algorithm would indeed be an arithmetical method of producing random digits, no? When thinking a bit about it, I was also considering Max Tegmark's view (expressed in his last book) according to which randomness does not exist at all: he believes it is only an illusion, more precisely the subjective feeling you perceive each time you get cloned (i.e. each time the Universe you live in gets branched in 2 or more Universes).

From my amateur point of view, if I were told that we live in a $\mathbf{P} = \mathbf{BQP}$ world, then I would believe that there is no such thing as randomness. How could it even exist, if it is perfectly producible by a mechanical procedure? Where would it reside? If true randomness can be implemented into a C++ concretion of the above classical deterministic algorithm, then where would it actually be? Would it be hidden somewhere? Would it continue to be present somehow, inspite there is no trace of it in the C++ code? For me, simply it would not exist.

Now, to summarize, this question is not about how likely you consider $\mathbf{P} = \mathbf{BQP}$ to be. Rather, the question boils down to the following:

In a world where $\mathbf{P} = \mathbf{BQP}$, would randomness exist at all?

Answer 1

P and BQP are decision-problem classes, i.e. the correct output is always a deterministic functions of the inputs. The only question is whether randomness helps "along the way" to speed up computing this deterministic function (at the cost of sometimes being wrong), or does not. This is the key point: P=BQP says nothing about outputting random strings in general situations, but only for the situation of computing a deterministic function in polynomial time.

So for instance the statement

if P=BQP, then there exists a classical deterministic algorithm which is able to quickly output true randomness (by just quickly simulating some Quantum Turing Machine).

is false. P=BQP only implies that if a machine with randomness can usually output the correct bit, then there is a machine with no randomness that always ouptuts the correct bit.

---

More comments on your question:

• What is closer to true is that some form of pseudorandom generators exist (deterministic machines whose output "looks random" to other deterministic machines of bounded running time). However, again, these PRGs would be targeted to machines that always output just a single bit, not all tasks that use randomness in general.

• For an example single-machine problem that can be solved by a randomized machine and provably cannot be solved by a deterministic machine, consider the problem "output a string of Kolmogorov complexity $\geq n$". This is essentially the problem of outputting a random string, and of course we can prove that no deterministic machine can do this.

• As Kaveh points out, in areas like communication complexity between multiple machines, also distributed systems and probably others, we have provable differences between what can be achieved with and without randomness. The classic example is for two machines to decide if they hold the same $n$-bit string while communicating fewer than $n$ bits.

• It may be that even if BQP = P, the randomized algorithm is much faster and more useful in practice. (It may even be that someday complexity theory could prove this.) Example: Miller-Rabin primality test (randomized) vs AKS (deterministic).

• As I understand it, we could have P = BQP and yet cryptography is perfectly useful, one-way functions exist, etc. (Not the factoring problem, of course.) And cryptography relies completely on randomness.

• I think BPP is as much a model of "true" randomness as BQP. Just a different type of randomness. How to get "truly" random bits in the real world is a different story.

Answer 2

The questions touches on some very interesting issues regarding quantum computation (and randomness). BQP is the class of decision problems that can be solved efficiently (in polynomial time) but it is not clear that referring just to decision problems suffices to do justice to the power of quantum computing. If we let QSAMPLING describes the probability distributions that can be sampled efficiently by quantum computers then there are reasons to think that QSAMPLING represents computational power of quantum computers (having to do with randomness) that goes beyond BQP.

For example, it is plausible that a BPP computer (which under your assumption, as well as standard thinking of CC that derandomization is possible, is equivalent (polynomially) to deterministic computer) cannot perform QSAMPLING even if it is equipped by a BQP subroutine. Thus, it is not known that BQP=P implies that QSAMPLING can be performed by a classical computer.

The question about the meaning of randomness you referred to is fairly profound issue in the foundation of probability. (And quantum mechanics does not change the matters drastically.) Computation complexity says quite a bit about randomness but randomness has also various other aspects.