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

The comments by Aaron Sterling, Sasho Nikolov, 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:

  1. We can rule out a polynomial-time classical algorithm to generate random numbers. [1]
  2. “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]
  3. "We can't simulate [a quantum mechanical trajectory] $\psi(t)$ in the usual way … there're too many variables." [3]
  4. 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?


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:


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

If not, what grounds should we give?

  • 1
    $\begingroup$ 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? $\endgroup$ Jun 1, 2011 at 17:00
  • 3
    $\begingroup$ I think this is a great question. But, in your example, how does Alice know her string of digits is not algorithmically compressible? $\endgroup$ Jun 1, 2011 at 17:35
  • 1
    $\begingroup$ On the equivalence sampling/searching: scottaaronson.com/papers/samprel.ps $\endgroup$ Jun 1, 2011 at 20:08
  • 1
    $\begingroup$ @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. $\endgroup$ Jun 2, 2011 at 22:58
  • 2
    $\begingroup$ @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 $\endgroup$ Jun 3, 2011 at 20:00

1 Answer 1


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.


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.