Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

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?

share|improve this question
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? –  Sasho Nikolov Jun 1 '11 at 17:00
3  
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 Jun 1 '11 at 17:35
1  
On the equivalence sampling/searching: scottaaronson.com/papers/samprel.ps –  Marzio De Biasi Jun 1 '11 at 20:08
1  
@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 Jun 2 '11 at 22:58
2  
@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 Jun 3 '11 at 20:00

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.