<p>The gist of the question is, given that quantum probability is a source of true randomness, how does that effect the extended (or efficient, or polynomial-time) Church-Turing thesis?</p>

<p>The answer is that, per conjecture, it doesn't affect it.   People conjecture that BPP = P, i.e., that randomized algorithms can be derandomized with pseudo-random-number generators with polynomial overhead.   Faith in PRNGs as a replacement for true randomness is one reason that people would believe the extended Church-Turing thesis if not for quantum computation.</p>

CC BY-SA 3.0
2015-05-17T15:45:21.837Z
2015-05-17T15:45:21.837Z
Greg Kuperberg
<p><i>Since no answer was given, a flag has been set requesting that this question be  converted to a community wiki.</i></p>

<hr>

<p>The comments by Aaron Sterling, Sasho Nikolov, and Vor have been synthesized into the following resolution, which is open for community wiki discussion:</p>

<blockquote>
  <p><strong>Resolved:</strong>&nbsp;&nbsp; With respect to classical algorithms that output numbers, samples, or simulation trajectories, strict mathematical logic requires that either all four of the following propositions be accepted, or none of them:</p>
  
  <ol>
  <li><em>We can rule out a polynomial-time classical algorithm to generate random numbers.</em>&nbsp;<a href="http://ieeexplore.ieee.org/iel5/18/22641/01054210.pdf?arnumber=1054210" rel="nofollow noreferrer">[1]</a></li>
  <li><em>“We can rule out a polynomial-time classical algorithm to sample the output distribution of a quantum computer, under the sole assumption that the polynomial hierarchy is infinite.”</em>&nbsp;<a href="http://arxiv.org/abs/1009.5104" rel="nofollow noreferrer">[2]</a></li>
  <li><em>"We can't simulate [a quantum mechanical trajectory] $\psi(t)$ in the usual way&nbsp;&hellip; there're too many variables."</em>&nbsp;<a href="http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.45.9310" rel="nofollow noreferrer">[3]</a></li>
  <li><em>The extended Church-Turing-Thesis (E-C-T) is ruled out, for the rigorous reason  that classical algorithms cannot generate random numbers.</em>&nbsp;<a href="http://rjlipton.wordpress.com/2011/06/06/types-of-papers/#comment-12070" rel="nofollow noreferrer">[4]</a></li>
  </ol>
</blockquote>

<p>To initiate discussion, here are affirmative and negative responses that, although each defensible, are deliberately over-stated.  A strongly affirmative argument might be:</p>

<blockquote>
  <p><b>Affirmative:</b>&nbsp;&nbsp;These four statements reflect theorems that, to respect rigor, require us never to speak of classical algorithms that generate random numbers, random samples, or quantum simulations, but rather to speak only of classical algorithms that generate pseudo-random numbers and (by extension) pseudo-random samples, and pseudo-quantum simulations.</p>
  
  <p>This being understood, all four statements are true.  Moreover, to avoid ambiguity and prevent confusion, mathematicians should encourage scientists and engineers to affix the prefix "pseudo-" to almost all usages of "random", "sample", and "quantum simulation".</p>
</blockquote>

<p>A strongly negative argument might be:</p>

<blockquote>
  <p><b>Negative:</b>&nbsp;&nbsp;These statements (and their associated formal theorems) are sign-posts that direct us to a <a href="http://rjlipton.wordpress.com/2011/06/06/types-of-papers/" rel="nofollow noreferrer">Lakatos-style</a> “red-light” district of mathematics where we are beckoned to enthusiastically embrace (what might be called) the disciplines of pseudo-randomness, pseudo-sampling, and pseudo-simulation&nbsp;&hellip; mathematical practices that are fun for a deliciously sinful reason: they achieve mathematical effects that formal logic says are impossible.  Therefore, what could be more magical, and more fun, than this conclusion: the resolution's four statements each are formally true, but practically false?  </p>
  
  <p>This being understood, all four statements are false.  Moreover, since most practical embraces of "randomness", "sampling", and "quantum simulation" occur in this magical environment&mdash;in which issues associated to Kolmogorov complexity and oracular assessments are willfully overlooked&mdash;it is mathematicians who should alter their usage.</p>
</blockquote>

<p>Realistically, though, how <em>should</em> complexity theorists phrase their findings relating to randomness, sample, and simulation&nbsp;&hellip;  on the one hand, with a view toward sustaining a reasonable balance of clarity, concision, and rigor&nbsp;&hellip; and on the other hand, with a view toward sustaining low-noise communication with other STEM disciplines?  The latter goal is especially important, as practical capabilities steadily increase in fields like cryptography, statistical testing, machine learning, and quantum simulation.</p>

<p>It would very helpful (and enjoyable too) to read well-reasoned answers, either affirmative or negative.</p>

<hr>

<p>The question asked is</p>

<blockquote>
  <p>What is/are the generally accepted role(s) of verification in the complexity-theoretic definitions associated to sampling, simulation, and testing the extended-Church-Turing (E-C-T) thesis?</p>
</blockquote>

<p>The preferred answer is references to articles, monographs, or textbooks that discuss these issues in-depth.  </p>

<p>Should this literature prove to be sparse or otherwise unsatisfactory, then (after two days) I will convert this question to a community wiki asking:</p>

<blockquote>
  <p>What is/are <i>reasonable and proper</i> role(s) of verification in the complexity-theoretic definitions associated to sampling, simulation, and testing the extended-Church-Turing (E-C-T) thesis?</p>
</blockquote>

<p><b>Background</b></p>

<p>The question asked is motivated by the recent thread <a href="https://cstheory.stackexchange.com/q/88/1519">"What would it mean to disprove Church-Turing thesis?"</a>, specifically the (excellent IMHO) answers given by <a href="https://cstheory.stackexchange.com/questions/88/what-would-it-mean-to-disprove-church-turing-thesis/886#886">Gil Kalai</a> and by <a href="https://cstheory.stackexchange.com/questions/88/what-would-it-mean-to-disprove-church-turing-thesis/4838#4838">Timothy Chow</a></p>

<p>In the question asked, the phrase <em>"proper and/or accepted complexity-theoretic definitions"</em> is to be construed as restraining Alice from implausible claims like the following:</p>

<blockquote>
  <p><b>Alice:</b>&nbsp;&nbsp;Here is my experimental sample of truly random binary digits computed by my (one-photon) linear optical network.<br><br><b>Bob:</b>&nbsp;&nbsp;Here is my simulated sample of pseudo-random digits computed by a classical Turing machine.<br><br><b>Alice:</b>&nbsp;&nbsp;Sorry Bob ... your sample is algorithmically compressible, and mine isn't. Therefore my experimental data demonstrate that the E-C-T is false!" </p>
</blockquote>

<p>In the absence of any association of verification to sampling, Alice's reasoning is impeccable. In&nbsp;other&nbsp;words, should complexity theorists regard the E-C-T as having <i>already</i> been formally disproved&nbsp;&hellip; decades ago?  </p>

<p>From a practical point of view, simulation methods associated to <a href="http://faculty.washington.edu/sidles/ENC_2011/#forGilKalai" rel="nofollow noreferrer">quantum trajectory sampling on varietal state-spaces</a> are coming into widespread use in many disciplines of science and engineering.  That is why complexity-theoretic definitions of sampling that respect the central role of verification (which is inseparable from replicability) in science and engineering would be very welcome to practicing scientists and engineers&nbsp;&hellip; especially if these definitions were accompanied by theorems describing the computational complexity of verified sampling. </p>

<hr>

<p><strong>Added Edit:</strong>  Thanks to a collaboration between the University of Geneva and the company <em>id Quantique</em>, it is perfectly feasible to complete this exercise in reality.   </p>

<p>Here are 1024 random bits that are <a href="http://www.randomnumbers.info/content/Download.htm" rel="nofollow noreferrer">certified by <em>id Quantique</em></a> as being algorithmically incompressible:</p>

<pre><code>0110001000010111111100010111001000101110110001001100000010010110
0101000110100011101001110110000001010110011101111110101010110100
1001001110001110101000001110000101000110000001010001101001000000
0110101010110000110101001110011010010101000000110000010000010111
0100110110001011011101110000010110000100110001001110011000000011
1111010100010110110010011000110110110010101101010000010010001111
1101111000111101111010000110100110011000101101010110110110000101
1110111100000111000111101111110011101101110111101001001111111110
1000001011001000011101001000001110101110101010000111100000111010
1010011001110111101001100010110000101101100100101100000110111111
1000001101111001111011100011110101011010010100000010100101100010
0011101000111100000001101100111110100100010100100010011000001000
0000001001110101010111110001010010000111010011000100001101101000
1011111010001000110101110101111101010111111011011111110010010111
0111000010000111000100110110010101110100000110101001111010101001
0100011110011101000011000100110110010000100001111100101001010011 
</code></pre>

<p>Should we now accept the claim: "The E-C-T thesis is disproved"?</p>

<p>If not, what grounds should we give?</p>

CC BY-SA 3.0
2011-06-01T17:00:03.080Z
by verification do you mean that the statement "algorithm A has property P in a computational model M" can be tested in finite time, for any particular input length? E.g., the property "probabilistic algorithm A halts witnin $1000n$ steps on any input of size $n$, using at most $\log_2 n$ random bits and accetpt language $L$ with probability $2/3$" can be verified in finite time for any $n$. Verified in finite time would mean by a deterministic Turing machine as a failsafe model of computation?
Sasho Nikolov
CC BY-SA 3.0
2011-06-01T17:35:53.247Z
I think this is a great question.  But, in your example, how does Alice know her string of digits is not algorithmically compressible?
Aaron Sterling
CC BY-SA 3.0
2011-06-01T17:46:02.160Z
Yes, that's the point, Aaron -- Alice doesn't know that her digits are random in any objectively verifiable sense ... she has merely been told (by standard textbooks) that the digits are random.  Although the hypothesis that Alice's digits are random *is* testable (by many standard statistical tests) it is true too that Bob's simulated data (if he uses a good generator) can pass all the same tests (unless we guess Bob's generator seed).  For reasons that include the considerations in Sasho Nikolov's comment (see above), it's not so obvious (to me) what the "right" verification criteria are.
John Sidles
CC BY-SA 3.0
2011-06-01T20:08:47.867Z
On the equivalence sampling/searching: http://www.scottaaronson.com/papers/samprel.ps
Marzio De Biasi
CC BY-SA 3.0
2011-06-01T21:35:49.053Z
The above manuscript "The Equivalence of Sampling and Searching" is a good example of a "big-endian" sampling definition, which imposes no requirement of verification or replication.  Big-endian definitions of sampling are terrific for proving theorems, but if we embrace that big-endianism, then isn't the E-C-T thesis already disproven?  And when the article speaks of experiments, we have to wonder: Are  experiments that cannot feasibly be verified and replicated really experiments in the established sense of the word?  Thus, sampling definitions need to be chosen with care and stated plainly.
John Sidles
CC BY-SA 3.0
2011-06-02T12:42:47.000Z
For example (and to prepare to this question to become a community wiki), the article "Equivalence of Sampling and Searching" asserts that "We can rule out a polynomial-time classical algorithm to sample the output distribution of a quantum computer, under the sole assumption that the polynomial hierarchy is inﬁnite." This is tricky to parse, since the phrase "rule out" has ambiguous meanings.  Given a simulated dataset, are there replicable criteria for "rule out"? Or can solely oracles "rule out"? The question asked seeks to reconcile and clarify experimental versus CT usages of "rule out."
John Sidles
CC BY-SA 3.0
2011-06-02T22:58:07.607Z
@John: just a clarification (I underline that I'm not an expert): "*... are certified by id Quantique as being algorithmically incompressible*", but how can they certify it? Obviously Kolmogorov complexity of a string is not computable so the sentence seems false. Even if they simply say "*we certify that the sequence is (quantum) random*" I have some doubts: the physical process (the hardware) is difficult to balance so they use Von Neumann unbiasing which is good, but doesn't guarantee that the result is *truly random*.
Marzio De Biasi
CC BY-SA 3.0
2011-06-02T23:29:17.460Z
@Vor, I agree entirely with what you say.  When engineers assert "These numbers are random", they mean something very different by "random"  from what mathematians expect.   And the converse is true too.   E.g., when mathematicians assert "We can rule out a polynomial-time classical algorithm," they mean something very different by "rule out" from what  engineers expect.  Reducing imprecision and misunderstanding in this two-way communication channel is the main objective of my post.  As sampling experiments and simulations become more sophisticated, these clarifications become more important.
John Sidles
CC BY-SA 3.0
2011-06-03T20:00:21.497Z
@John Sidles: while you make sound and interesting observations, I do not understand what you're looking for. It's clear what Aaronson and coauthors mean by "rule out": if PH is infinite, there doesn't exist a particular algorithm in a particular model. i suppose you're asking if the modeling assumptions are verifiable. note that the purpose of the model is to verify only the modeling assumption, instead of test any possible algorithm/theorem
Sasho Nikolov
CC BY-SA 3.0
2011-06-04T13:51:55.687Z
@Vor, you are right that it's clear what mathematicians mean when they say "rule out" ... and it's clear too what experimentalists mean whey *they* say "rule out" ... which is something entirely different!  Confusions thus arise when  mathematicians and experimentalists read one-another's articles.  The passage quoted was written by a mathematician, specifically to be read by experimentalists, and yet the intended meaning "rule out" is not specified ... so at least *one* class of readers will misunderstand the article's conclusion.  I will amend the question to address this issue.
John Sidles
CC BY-SA 3.0
2011-06-04T21:08:48.363Z
@Sasho, my mistake, the above comment is in response to your observation (not Vor's) ... both your and Vor's comments are quite good (IMHO).
John Sidles
<quantum-computing><program-verification><sample-complexity>
What is the proper role of verification in quantum sampling, simulation, and extended-Church-Turing (E-C-T) testing?
John Sidles
# What is the proper role of verification in quantum sampling, simulation, and extended-Church-Turing (E-C-T) testing?

(Asked by: username_0 on 2011-06-01)

Since no answer was given, a flag has been set requesting that this question be  converted to a community wiki.

The comments by username_2, username_1, and Vor have been synthesized into the following resolution, which is open for community wiki discussion:

Resolved:   With respect to classical algorithms that output numbers, samples, or simulation trajectories, strict mathematical logic requires that either all four of the following propositions be accepted, or none of them:

We can rule out a polynomial-time classical algorithm to generate random numbers. [1]
“We can rule out a polynomial-time classical algorithm to sample the output distribution of a quantum computer, under the sole assumption that the polynomial hierarchy is infinite.” [2]
"We can't simulate [a quantum mechanical trajectory] $\psi(t)$ in the usual way … there're too many variables." [3]
The extended Church-Turing-Thesis (E-C-T) is ruled out, for the rigorous reason  that classical algorithms cannot generate random numbers. [4]


To initiate discussion, here are affirmative and negative responses that, although each defensible, are deliberately over-stated.  A strongly affirmative argument might be:

Affirmative:  These four statements reflect theorems that, to respect rigor, require us never to speak of classical algorithms that generate random numbers, random samples, or quantum simulations, but rather to speak only of classical algorithms that generate pseudo-random numbers and (by extension) pseudo-random samples, and pseudo-quantum simulations.
This being understood, all four statements are true.  Moreover, to avoid ambiguity and prevent confusion, mathematicians should encourage scientists and engineers to affix the prefix "pseudo-" to almost all usages of "random", "sample", and "quantum simulation".

A strongly negative argument might be:

Negative:  These statements (and their associated formal theorems) are sign-posts that direct us to a Lakatos-style “red-light” district of mathematics where we are beckoned to enthusiastically embrace (what might be called) the disciplines of pseudo-randomness, pseudo-sampling, and pseudo-simulation … mathematical practices that are fun for a deliciously sinful reason: they achieve mathematical effects that formal logic says are impossible.  Therefore, what could be more magical, and more fun, than this conclusion: the resolution's four statements each are formally true, but practically false?  
This being understood, all four statements are false.  Moreover, since most practical embraces of "randomness", "sampling", and "quantum simulation" occur in this magical environment—in which issues associated to Kolmogorov complexity and oracular assessments are willfully overlooked—it is mathematicians who should alter their usage.

Realistically, though, how should complexity theorists phrase their findings relating to randomness, sample, and simulation …  on the one hand, with a view toward sustaining a reasonable balance of clarity, concision, and rigor … and on the other hand, with a view toward sustaining low-noise communication with other STEM disciplines?  The latter goal is especially important, as practical capabilities steadily increase in fields like cryptography, statistical testing, machine learning, and quantum simulation.
It would very helpful (and enjoyable too) to read well-reasoned answers, either affirmative or negative.

The question asked is

What is/are the generally accepted role(s) of verification in the complexity-theoretic definitions associated to sampling, simulation, and testing the extended-Church-Turing (E-C-T) thesis?

The preferred answer is references to articles, monographs, or textbooks that discuss these issues in-depth.  
Should this literature prove to be sparse or otherwise unsatisfactory, then (after two days) I will convert this question to a community wiki asking:

What is/are reasonable and proper role(s) of verification in the complexity-theoretic definitions associated to sampling, simulation, and testing the extended-Church-Turing (E-C-T) thesis?

Background
The question asked is motivated by the recent thread "What would it mean to disprove Church-Turing thesis?", specifically the (excellent IMHO) answers given by Gil Kalai and by Timothy Chow
In the question asked, the phrase "proper and/or accepted complexity-theoretic definitions" is to be construed as restraining Alice from implausible claims like the following:

Alice:  Here is my experimental sample of truly random binary digits computed by my (one-photon) linear optical network.Bob:  Here is my simulated sample of pseudo-random digits computed by a classical Turing machine.Alice:  Sorry Bob ... your sample is algorithmically compressible, and mine isn't. Therefore my experimental data demonstrate that the E-C-T is false!" 

In the absence of any association of verification to sampling, Alice's reasoning is impeccable. In other words, should complexity theorists regard the E-C-T as having already been formally disproved … decades ago?  
From a practical point of view, simulation methods associated to quantum trajectory sampling on varietal state-spaces are coming into widespread use in many disciplines of science and engineering.  That is why complexity-theoretic definitions of sampling that respect the central role of verification (which is inseparable from replicability) in science and engineering would be very welcome to practicing scientists and engineers … especially if these definitions were accompanied by theorems describing the computational complexity of verified sampling. 

Added Edit:  Thanks to a collaboration between the University of Geneva and the company id Quantique, it is perfectly feasible to complete this exercise in reality.   
Here are 1024 random bits that are certified by id Quantique as being algorithmically incompressible:
0110001000010111111100010111001000101110110001001100000010010110
0101000110100011101001110110000001010110011101111110101010110100
1001001110001110101000001110000101000110000001010001101001000000
0110101010110000110101001110011010010101000000110000010000010111
0100110110001011011101110000010110000100110001001110011000000011
1111010100010110110010011000110110110010101101010000010010001111
1101111000111101111010000110100110011000101101010110110110000101
1110111100000111000111101111110011101101110111101001001111111110
1000001011001000011101001000001110101110101010000111100000111010
1010011001110111101001100010110000101101100100101100000110111111
1000001101111001111011100011110101011010010100000010100101100010
0011101000111100000001101100111110100100010100100010011000001000
0000001001110101010111110001010010000111010011000100001101101000
1011111010001000110101110101111101010111111011011111110010010111
0111000010000111000100110110010101110100000110101001111010101001
0100011110011101000011000100110110010000100001111100101001010011 

Should we now accept the claim: "The E-C-T thesis is disproved"?
If not, what grounds should we give?

**Tags:** quantum-computing, program-verification, sample-complexity

> **Comments:**
> **username_1**: by verification do you mean that the statement "algorithm A has property P in a computational model M" can be tested in finite time, for any particular input length? E.g., the property "probabilistic algorithm A halts witnin $1000n$ steps on any input of size $n$, using at most $\log_2 n$ random bits and accetpt language $L$ with probability $2/3$" can be verified in finite time for any $n$. Verified in finite time would mean by a deterministic Turing machine as a failsafe model of computation?  
> **username_2**: I think this is a great question.  But, in your example, how does Alice know her string of digits is not algorithmically compressible?  
> **username_0**: Yes, that's the point, Aaron -- Alice doesn't know that her digits are random in any objectively verifiable sense ... she has merely been told (by standard textbooks) that the digits are random.  Although the hypothesis that Alice's digits are random *is* testable (by many standard statistical tests) it is true too that Bob's simulated data (if he uses a good generator) can pass all the same tests (unless we guess Bob's generator seed).  For reasons that include the considerations in username_1's comment (see above), it's not so obvious (to me) what the "right" verification criteria are.  
> **username_3**: On the equivalence sampling/searching: http://www.scottaaronson.com/papers/samprel.ps  
> **username_0**: The above manuscript "The Equivalence of Sampling and Searching" is a good example of a "big-endian" sampling definition, which imposes no requirement of verification or replication.  Big-endian definitions of sampling are terrific for proving theorems, but if we embrace that big-endianism, then isn't the E-C-T thesis already disproven?  And when the article speaks of experiments, we have to wonder: Are  experiments that cannot feasibly be verified and replicated really experiments in the established sense of the word?  Thus, sampling definitions need to be chosen with care and stated plainly.  
> **username_0**: For example (and to prepare to this question to become a community wiki), the article "Equivalence of Sampling and Searching" asserts that "We can rule out a polynomial-time classical algorithm to sample the output distribution of a quantum computer, under the sole assumption that the polynomial hierarchy is inﬁnite." This is tricky to parse, since the phrase "rule out" has ambiguous meanings.  Given a simulated dataset, are there replicable criteria for "rule out"? Or can solely oracles "rule out"? The question asked seeks to reconcile and clarify experimental versus CT usages of "rule out."  
> **username_3**: @John: just a clarification (I underline that I'm not an expert): "*... are certified by id Quantique as being algorithmically incompressible*", but how can they certify it? Obviously Kolmogorov complexity of a string is not computable so the sentence seems false. Even if they simply say "*we certify that the sequence is (quantum) random*" I have some doubts: the physical process (the hardware) is difficult to balance so they use Von Neumann unbiasing which is good, but doesn't guarantee that the result is *truly random*.  
> **username_0**: @Vor, I agree entirely with what you say.  When engineers assert "These numbers are random", they mean something very different by "random"  from what mathematians expect.   And the converse is true too.   E.g., when mathematicians assert "We can rule out a polynomial-time classical algorithm," they mean something very different by "rule out" from what  engineers expect.  Reducing imprecision and misunderstanding in this two-way communication channel is the main objective of my post.  As sampling experiments and simulations become more sophisticated, these clarifications become more important.  
> **username_1**: @username_0: while you make sound and interesting observations, I do not understand what you're looking for. It's clear what Aaronson and coauthors mean by "rule out": if PH is infinite, there doesn't exist a particular algorithm in a particular model. i suppose you're asking if the modeling assumptions are verifiable. note that the purpose of the model is to verify only the modeling assumption, instead of test any possible algorithm/theorem  
> **username_0**: @Vor, you are right that it's clear what mathematicians mean when they say "rule out" ... and it's clear too what experimentalists mean whey *they* say "rule out" ... which is something entirely different!  Confusions thus arise when  mathematicians and experimentalists read one-another's articles.  The passage quoted was written by a mathematician, specifically to be read by experimentalists, and yet the intended meaning "rule out" is not specified ... so at least *one* class of readers will misunderstand the article's conclusion.  I will amend the question to address this issue.  
> **username_0**: @Sasho, my mistake, the above comment is in response to your observation (not Vor's) ... both your and Vor's comments are quite good (IMHO).  

---

## 1 answers

### Answer by username_4 on 2015-05-17. Score: 2

The gist of the question is, given that quantum probability is a source of true randomness, how does that effect the extended (or efficient, or polynomial-time) Church-Turing thesis?

The answer is that, per conjecture, it doesn't affect it. People conjecture that BPP = P, i.e., that randomized algorithms can be derandomized with pseudo-random-number generators with polynomial overhead. Faith in PRNGs as a replacement for true randomness is one reason that people would believe the extended Church-Turing thesis if not for quantum computation.


---

