<p>P and BQP are <strong>decision-problem classes</strong>, i.e. the correct output is always a <em>deterministic</em> 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.</p>

<p>So for instance the statement</p>

<blockquote>
  <p>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).</p>
</blockquote>

<p>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.</p>

<hr>

<p>More comments on your question:</p>

<ul>
<li><p>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.</p></li>
<li><p>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.</p></li>
<li><p>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.</p></li>
<li><p>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).</p></li>
<li><p>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.</p></li>
<li><p>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.</p></li>
</ul>

CC BY-SA 3.0
2015-05-17T14:37:11.733Z
If randomness is not needed for machines that output a single bit, it is also not needed for machines that output a **deterministic** function, because you can deterministically compute each bit of this function. The crucial distinction is not languages versus functions, but deterministic computation versus other kinds.
Peter Shor 
CC BY-SA 3.0
2015-05-17T18:39:20.810Z
@PeterShor, thanks for your comment. I updated the wording to make this point clearer and fix the first bullet point. Please let me know if it still misses the mark somewhere!
usul
CC BY-SA 3.0
2015-05-17T09:15:58.730Z
2015-05-17T18:37:21.697Z
2015-05-17T18:37:21.697Z
usul
<p>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. </p>

<p>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. </p>

<p>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.         </p>

CC BY-SA 3.0
2015-05-17T17:53:10.997Z
2015-05-17T21:07:07.963Z
2015-05-17T21:07:07.963Z
Gil Kalai
<blockquote>
  <p><strong>DISCLAIMER</strong><br>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.</p>
</blockquote>

<hr>

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

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

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

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

<p>John Von Neumann once said: <em>"Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin"</em>. 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).</p>

<p>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 <strong>true</strong> 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.</p>

<p>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:</p>

<blockquote>
  <p>In a world where $\mathbf{P} = \mathbf{BQP}$, would randomness exist at all?</p>
</blockquote>

CC BY-SA 3.0
2015-05-17T08:38:32.143Z
side note: theoretically at least BQP=P doesn't rule out a role for randomness completely, e.g. we have unconditional separation results in communication complexity. We have cases where we know randomness helps. And conceptually, NP is a useful notion even if no one believes that nondeterministic machines are realistic.
Kaveh
CC BY-SA 3.0
2015-05-18T19:11:04.693Z
a cryptographic perspective on (psuedo) randomness is that there is a continuum of PRNGs of different complexity, ie hardness levels. this is reflected in famous complexity theoretic proofs such as Natural Proofs by Razborov/ Rudich. so P=BQP would only prove an equivalency result ("only") for a "low level" of randomness. the study of kolmogorov complexity is also related...
vzn
<cc.complexity-theory><quantum-computing><randomness><physics>
Suppose $\mathbf{P} = \mathbf{BQP}$. Then what is randomness? Would it even exist at all?
Giorgio Camerani
# Suppose $\mathbf{P} = \mathbf{BQP}$. Then what is randomness? Would it even exist at all?

(Asked by: username_0 on 2015-05-17)

> **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?

**Tags:** cc.complexity-theory, quantum-computing, randomness, physics
> **Comments:**
> **username_1**: side note: theoretically at least BQP=P doesn't rule out a role for randomness completely, e.g. we have unconditional separation results in communication complexity. We have cases where we know randomness helps. And conceptually, NP is a useful notion even if no one believes that nondeterministic machines are realistic.  
> **username_2**: a cryptographic perspective on (psuedo) randomness is that there is a continuum of PRNGs of different complexity, ie hardness levels. this is reflected in famous complexity theoretic proofs such as Natural Proofs by Razborov/ Rudich. so P=BQP would only prove an equivalency result ("only") for a "low level" of randomness. the study of kolmogorov complexity is also related...  

---

## 2 answers

### Answer by username_3 on 2015-05-17. Score: 18

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.

> **Comments:**
> **username_4**: If randomness is not needed for machines that output a single bit, it is also not needed for machines that output a **deterministic** function, because you can deterministically compute each bit of this function. The crucial distinction is not languages versus functions, but deterministic computation versus other kinds.  
> **username_3**: @PeterShor, thanks for your comment. I updated the wording to make this point clearer and fix the first bullet point. Please let me know if it still misses the mark somewhere!  

---

### Answer by username_5 on 2015-05-17. Score: 13

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.


---

