Quantum. Crypto. Things happen. I blog.
1. A bunch of people emailed me to ask about the paper “Realization of a scalable Shor algorithm”: a joint effort by the groups of my MIT colleague Ike Chuang and of Innsbruck’s Rainer Blatt. The paper has been on the arXiv since July, but last week everyone suddenly noticed it because it appeared in Science. See also the articles in MIT News and IEEE Spectrum.
Briefly, the new work uses Kitaev’s version of Shor’s factoring algorithm, running on an ion-trap quantum computer with five calcium ions, to prove that, with at least 90% confidence, 15 equals 3×5. Now, one might object that the “15=3×5 theorem” has by now been demonstrated many times using quantum computing (indeed, Chuang himself was involved in the historic first such demonstration, with Neil Gershenfeld in 1997). Furthermore, if one counts demonstrations not based on quantum computing, some people have claimed even earlier precedents for that theorem.
Nevertheless, as far as I can tell, the new work is a genuine milestone in experimental QC, because it dispenses with most of the precompilation tricks that previous demonstrations of Shor’s algorithm used. “Precompilation tricks” are a fancier term for “cheating”: i.e., optimizing a quantum circuit in ways that would only make sense if you already assumed that 15 was, indeed, 3×5. So, what’s new is that a QC has now factored 15 “scalably”: that is, with much less cheating than before.
Of course, as I’m sure the authors would acknowledge, the word “scalable” in their title admits multiple interpretations, rather like the word “possible.” (It’s possible to buy strawberry Mentos, and it’s also possible to convert the Sun into computronium, but for different senses of “possible.”) As I wrote in the comments section of my last post:
There are still all the difficulties of integrating a huge number of qubits—which, in ion-trap implementations, would almost certainly mean having many traps that can communicate with each other using gate teleportation—as well as implementing quantum fault-tolerance (meaning: doing 2-qubit gates at the fault-tolerance threshold, moving qubits around to the right places, pumping in fresh qubits, pumping out dirty ones, etc). Those all remain major engineering problems for the future.
See also this comment by Vaughan Pratt, who remarks: “the MIT press release … would appear to have translated [‘scalable’] to mean that RSA was now approaching its best-by date, although the paper itself makes no such claim.”
In any case, regardless of how long it takes until we can factor enormous numbers like 91, congratulations to the MIT and Innsbruck groups on what’s certainly progress toward scalable ion-trap QC!
2. Other people wrote to ask about a striking recent preprint of Kaplan, Leurent, Leverrier, and Naya-Plasencia, which points out how Simon’s algorithm—i.e., the forerunner of Shor’s algorithm—can be used to break all sorts of practical private-key authentication schemes in quantum polynomial time, assuming the adversary can query the scheme being attacked on a coherent superposition of inputs. In practice, this assumption is unlikely to hold, unless the adversary gets the actual obfuscated code of the scheme being attacked (in which case it holds). Also, this is not the first time Simon’s algorithm has been used to attack cryptography; previous work in the same spirit by Kuwakado and Morii showed how to use Simon’s algorithm to break the 3-round Feistel scheme and the Even-Mansour scheme, again if we assume superposition queries.
Even so, Kaplan et al. seem to pretty dramatically expand the range of “practical” cryptosystems that are known to be vulnerable to Simon attacks in the superposed-query model. I suspect this will force a revision in how we talk about Simon’s algorithm: from “useless, but theoretically important, and historically important because it led to Shor’s algorithm” to “actually maybe not that useless.” (See here for a previous attempt of mine to give an interesting “explicit” problem that Simon’s algorithm solves in polynomial time, but that’s classically hard. Alas, my candidate problem turned out to be classically easy.) This is analogous to the revision that “Einstein-certified randomness” and the RUV theorem recently forced in how we talk about Bell’s inequality: we can no longer tell students that Bell’s work was important because of the conceptual point it proved about local hidden variables, and because of all the other stuff it led to, even though it obviously has no applications in and of itself. Now it does have applications in and of itself.
To a quantum complexity theorist like me, who doesn’t know nearly as much applied crypto as he should, the real news in the Kaplan et al. paper is not that Simon’s algorithm can break the sorts of systems they study. Rather, it’s that so many systems that are vulnerable to Simon attack exist and are used in the first place! Once people understand the problem, I doubt it will be hard to design schemes of similar efficiency that remain quantum-secure even in the superposed-query model (under some plausible assumption, like that an underlying one-way function is quantum-secure). Indeed, recent work of Boneh and Zhandry, among others, has already taken significant steps in that direction. So the situation doesn’t seem “as bad” as it was with public-key crypto, where once Shor’s algorithm comes along, the plausibly quantum-secure alternatives that we currently know (like lattice-based crypto and quantum key distribution) are either much less efficient than RSA and Diffie-Hellman, or else require new hardware. Still, the new observations about Simon’s algorithm show us how the history of quantum computing could have unfolded differently: rather than Simon → Shor → everyone gets excited (because their crypto is now vulnerable), people could’ve gotten cryptographically excited immediately after Simon.
3. Speaking of Diffie-Hellman, belated congratulations to Whitfield Diffie and Martin Hellman for an extremely well-deserved Turing Award!
4. At MIT’s weekly quantum information group meeting, Aram Harrow spoke about his new paper with Ed Farhi, “Quantum Supremacy through the Quantum Approximate Optimization Algorithm.” Using the same arguments developed around 2010 by me and Alex Arkhipov, and (independently) by Bremner, Jozsa, and Shepherd, this paper shows that, even though the recently-developed QAOA/Quinoa quantum optimization algorithm turns out not to beat the best classical algorithms on the Max E3LIN2 problem (see here and here)—still, whatever that algorithm does do, at least there’s no polynomial-time classical algorithm that samples from the same distribution over outputs, unless the polynomial hierarchy collapses.
In other words: even if the algorithm fails at its original goal, it’s still hard for a classical computer to reproduce its exact pattern of failure! Hence: Quantum Supremacy.
A secondary goal of Aram and Eddie’s paper is to make the Aaronson-Arkhipov and Bremner et al. arguments more accessible to physicists, by decreasing the amount of “weird complexity theory” invoked. (I suppose I’ve asked for this—for physicists to de-complexify complexity theory—by telling everyone for years how easy quantum mechanics becomes once you take away the physics!) I’ll leave it to physicists to judge how well Aram and Eddie succeed at their pedagogical goal, but I’m thrilled by any such effort to communicate across fields. Aram’s talk would surely have served that same educational purpose, had it not gotten derailed partway through by Donald Trump jokes from the audience. (My contribution: “Aram, will you disavow support from quantum supremacists?”)
Unrelated Update: Some people might be interested in this brief interview with Michael Cerullo, who read The Ghost in the Quantum Turing Machine and wanted to ask me about “the relevance of quantum mechanics to brain preservation, uploading, and identity.”
Follow
Comment #1 March 6th, 2016 at 2:55 pm
I may be wrong, but my understanding is that a quantum computer can only show that 15=3×5 with (very) high probability.
So no real proof of that theorem.
Comment #2 March 6th, 2016 at 2:56 pm
wolfgang #1: I said “with at least 90% confidence” right there in the post… 🙂
Comment #3 March 6th, 2016 at 3:02 pm
MIT seems to think the probability is above 99%.
Comment #4 March 6th, 2016 at 3:07 pm
Avi #3: Presumably, to whatever extent “MIT thinks” anything, it thinks a 90% correctness probability can be amplified to 99% anyway by repeating the algorithm a few times, so what’s the difference? 🙂
Comment #5 March 6th, 2016 at 3:10 pm
@Scott #2
I am getting old …
but let me use this to ask a follow up question.
One would think that a classical computer can take the result and check if it is a valid factorization (which should require little extra effort), so are there any restrictions what the combination quantum computer + classical computer can prove?
Comment #6 March 6th, 2016 at 3:21 pm
wolfgang #5: Since factoring is in NP, it’s indeed trivial for a classical computer to verify any claimed factorization. So the classical/quantum combination can indeed “prove” the answer with ~99.9999999% confidence, or whatever you take the physical error rate of your classical computer to be. This is why talking about “15 = 3×5 with high probability” is purely for humor purposes: the exact error rate is irrelevant as long as it’s reasonably small. What’s relevant is just the engineering problem of scaling to larger sizes with any non-negligible probability of getting the right answer.
(Now, if you could scale to large sizes at all, you’d almost certainly do so using hierarchical fault-tolerance, which you could also use to push your QC’s probability of outputting the correct factorization up to 99.999% or whatever, if you desired. But for breaking RSA, even a 1% probability of outputting the correct factorization on any given run would suffice.)
Comment #7 March 6th, 2016 at 3:34 pm
@Scott #6
But the combination q.c. + c..c could provide for other advantages e.g. it is easy to check e.g. if a number can be divided by 2 with a deterministic algorithm (just check the last bit).
So a combination q.c. + c.c. could perhaps factor 16 = 2x2x2x2 much faster than a q.c. alone 😎
Is it known that q.c. + c.c. is necessarily in the same complexity class as “q.c. only” ? Or is q.c. always understood as qc. + c.c. ?
This leaves aside that in reality a c.c. is a very special case of a q.c. of course.
Comment #8 March 6th, 2016 at 3:52 pm
wolfgang #7: As you mentioned, a QC can simulate a classical computer, so as far as our theoretical models are concerned, QC+CC is just QC. (More formally, PBQP, BQPP, etc. are simply BQP.)
The only time it gets more interesting, is when you consider a QC that’s restricted in various ways (as one example, to logarithmic depth), in combination with a classical computer that’s unrestricted (i.e., can do all of polynomial time). For example, Cleve and Watrous showed in 2000 that factoring is in the class ZPPBQNC: that is, it can be solved in polynomial time by a hybrid quantum/classical algorithm in which the quantum component has logarithmic depth. This fact might become important in practice, if we pass through a phase when the engineering is good enough to do small-depth quantum circuits (with couplings between arbitrary pairs of qubits, not just nearest neighbors), but still not good enough to do arbitrary-depth circuits.
Comment #9 March 6th, 2016 at 5:08 pm
An obstacle to the alternative unfolding of the history of quantum computing is that the (open) cryptography community was not very interested in the topic of authentication modes for symmetric cryptography at the time of Simon’s algorithm. Interest dates from 2000, as can be seen from the proliferation of modes after that date. The only earlier mode is CBC-MAC from about 1980, which was developed by the NSA without much explanation.
Comment #10 March 6th, 2016 at 5:18 pm
@Scott
So what is actually the probability that 15=3×5 is false?
Obviously very small, but also not exactly 0.
Something like epsilon^N I would guess, where N is the number of classical computers / mathematicians in this world, which is limited by the number of atoms in the visible universe.
But how would one calculate epsilon?
Comment #11 March 6th, 2016 at 5:37 pm
wolfgang #10: You can sensibly talk about the probability that a computer programmed to check N=pq will make an error, as I was implicitly doing in comment #6. And for sufficiently enormous p and q, such a computation might be the only access we have to whether N=pq. But as far as Bayesian probability theory can say, Pr[N=pq] (for fixed N,p,q) equals 1 if N=pq, and 0 otherwise, and that’s that.
Or to put it more colloquially: if you’re willing to entertain a “small but nonzero probability that 15 is not 3×5,” then why be so selective? You should worry just as much about the axioms of probability theory being all wrong, and a “small” probability actually being a large one … or Pr[15=3×5] actually equaling 47, or whatever. You know you’ve hit rock bottom when your attempts to dig deeper just dent your shovel.
Comment #12 March 6th, 2016 at 6:17 pm
Taking it you disagree with http://lesswrong.com/lw/mp/0_and_1_are_not_probabilities/, then?
I think we should work on the slope in the other direction. Is it meaningful to say that probability of (Pi.BinaryDigit(Graham’s number)=1) is 50%?
If you agree that it is, then you’ve accepted uncertainty over logical facts. It’s only a small leap to go from there to logical facts you already “know”.
(I feel like I’ve seen you discuss some form of this argument before, but can’t quite track it down.)
Comment #13 March 6th, 2016 at 6:35 pm
Avi #12: I was careful in what I wrote! There might indeed be all sorts of situations where we need to make sense of probabilities over mathematical statements. One good example is when we bet on how open math problems will turn out, something I’ve been known to do myself! 🙂 And the question of how to build sensible theories that include statements like
Pr[the BB(1000)th binary digit of π is 1] = 1/2
is one that interests me as much as it interests the LessWrong people—I touched on some related questions in Why Philosophers Should Care About Computational Complexity, and “my brain is open” for any new ideas about this.
But crucially, any such theory will not be Bayesian probability theory: it’ll be a nontrivial extension or generalization thereof! And I don’t know how to make sense of questions like wolfgang’s in the absence of such a theory.
Let me also venture a prediction: any such theory should have the property that expressions like Pr[15=3×5] evaluate to “as close to 1 as is needed for whatever application we’re talking about.” I.e., it’s possible that the probability assigned to a mathematical statement could change with time, depending on how much computational effort people had sunk into proving or disproving the statement, and what they found when they did. This would be the case, for example, with the digits-of-π probability above.
But in the case of 15=3×5, your uncertainties about the correct application of the new probability theory itself ought to completely swamp your uncertainty about the arithmetical statement! That’s what I mean in saying that the theory should assign such a statement “a probability that’s as close to 1 as needed”: in some sense, the theory has no standing to assign a lower probability.
Comment #14 March 6th, 2016 at 6:45 pm
@Scott #11
So let’s take a “sufficiently enormous” number n and check with a QC if it is p*q .
As I understand it you cannot get Pr[n=p*q] to exactly 1 with finite resources and a finite number of runs.
So what is fundamentally different between those numbers and 5×3?
Comment #15 March 6th, 2016 at 7:12 pm
wolfgang #14: Again, you seem to be leaving out the relevant point that factoring is in NP. I.e., each run of Shor’s algorithm has some probability of failing to find p and q—but once you do find them, you can check them with a deterministic classical computer, which errs only for bizarre hardware reasons like cosmic rays. So I would say that, for enormous p and q, our generalized probability theory should say that
Pr[N=p*q]
approaches as close to 1 as we like, exactly as Pr[15=3*5] does. It’s just that the approach to 1 might be not quite as rapid as in the case of 15=3*5. 🙂
Comment #16 March 6th, 2016 at 7:29 pm
@Scott
But “a deterministic classical computer” really exists only in Copenhagen …
Comment #17 March 6th, 2016 at 7:44 pm
Scott #8,
Regarding the result of factoring being in ZPP^BQNC In general, ZPP collapses relative to a random oracle. Is there any chance of derandomizing this result to get factoring in P^BQNC ?
Related to that, is ZPP^BQNC = P^BQNC equivalent to the obvious circuit lower bound where there is a problem in 2^(O(n)) time (with a BQNC oracle) that doesn’t have 2^(o(n)) size circuits with a BQNC oracle? It seems like that sort of result should relativize.
Comment #18 March 6th, 2016 at 8:13 pm
wolfgang #16: In my comment, I already acknowledged the possibility that a “deterministic classical computer” can err! (For example, because of cosmic rays.) Even so, by doing the multiplication on many different classical computers, which are differently programmed, etc., it seems to me that we can make Pr[p*q=N] as large as is needed for any desired application—so that, in any other expression where Pr[p*q=N] occurred, we could substitute 1 without risk of serious error.
The alternative is to say that there’s some generalized probability theory that lets you meaningfully declare that 15=3*5 with (say) probability 0.99999999, but no higher. This I find intolerable, for the following reason, which I fear we’ll be talking past each other if you don’t engage: no matter what probability ε>0 the theory were to assign to 15≠3*5, that probability would be completely swamped by “the probability that the generalized probability theory is wrong,” or had been incorrectly applied, etc. The number would therefore be meaningless. The basic principle here is that, if we need to presuppose theory A (say, the basic facts of arithmetic) even to talk about theory B (say, the theory of gambling odds for mathematical statements), then B doesn’t get to pronounce on the probability that A is true, or shouldn’t be taken seriously if it does.
Comment #19 March 6th, 2016 at 8:14 pm
“Now, one might object that the “15=3×5 theorem” has by now been demonstrated many times using quantum computing (indeed, Chuang himself was involved in the historic first such demonstration, with Neil Gershenfeld in 1997). Furthermore, if one counts demonstrations not based on quantum computing, some people have claimed even earlier precedents for that theorem.”
Citation needed! 🙂
Comment #20 March 6th, 2016 at 8:35 pm
>> many different classical computers
As I wrote earlier, the probability would go like epsilon^N where N is the number of classical computers, but N is obviously limited in a universe of finite lifetime.
So I think there is a probability p>0 , which may be a function of the age of the universe etc.
>> that probability would be completely swamped
This is very much possible, but establishing a limit on p from first principles e.g. physics in a universe of finite size, would be quite interesting in itself, e.g. if one discusses cosmology etc.
Comment #21 March 6th, 2016 at 8:38 pm
Joshua #17: Here’s the paper by Cleve and Watrous. As far as I can tell from reading it (it’s not explicit about this point), the only place where the ZPP algorithm ever needs randomness is in choosing a random base x for the modular exponentiation function, f(r)=xr mod N, that’s the core of Shor’s algorithm. If so, then any number-theoretic hypothesis that would let you derandomize the choice of x—I’m guessing (I’m not certain) that GRH would do the trick—would also put factoring into PBQNC.
In other words, I don’t think you’d need anything as powerful as a circuit lower bound to achieve this particular derandomization: “merely” something like GRH! 🙂
(And just like AKS removed the need for GRH in deterministic primality testing, so it seems possible that, with enough effort, one could get an unconditional result here as well.)
Anyway, yes, if you assume that EBQNC requires circuits with BQNC oracle gates of size 2Ω(n), that will also be enough to imply the general equality PBQNC=BPPBQNC, by Impagliazzo-Wigderson. But these sorts of implications are basically never “if and only if.” There are indeed implications both ways between derandomizations and circuit lower bounds, but they don’t quite match; you lose something going from one to the other.
Comment #22 March 6th, 2016 at 8:41 pm
Philip #19: How do you cite, like, a Babylonian cuneiform?
Comment #23 March 6th, 2016 at 8:44 pm
Well if the probability of the theory being wrong is X, and the probability the theory assigns to 15≠3*5 is Y, then we have an upper bound on the probability of 15=3*5 of 1-Y*(1-X), or a lower bound on the opposite of Y*(1-X).
As long as you can place some probability on the theory being right, you can get an upper bound on other statements.
(Counter-point: choose X,Y such that p(theory is correct)=X, and p(X*Y!=XY|theory)>=Y. Then the upper bound is correct iff it isn’t. Note: XY should be replaced by the value as given by your best guess at the time of generating Y.)
Comment #24 March 6th, 2016 at 9:35 pm
Avi #23: The trouble is, you’re implicitly using ordinary probability theory to reason about the correctness of something other than ordinary probability theory! Rather than give myself a headache worrying about the epistemology of such a move, I prefer to appeal to meta-level “principles of intellectual hierarchy,” like so:
(i) If, hypothetically, the axioms of set theory were to imply 1+1=3, then that would be a problem for the axioms for set theory, not for arithmetic. 1+1=2 was there first.
(ii) If a physical theory seems to imply negative or complex or infinite probabilities for observable events (all of which have actually happened), then those are internal issues for the physical theory to sort out (as indeed they were). The axioms of probability were there first.
(iii) Finally, if someone claims to calculate a “probability” that 3×5=7—i.e., that all our intuitions and experiences and computations misled us on that question of elementary arithmetic since the beginning of civilization—then the likelihood that something is wrong with their probability calculation is so overwhelmingly larger than the likelihood is something is wrong with the multiplication tables, that the calculation can’t actually tell us anything. Personally, I wouldn’t even say that it gives a lower bound, because as mentioned earlier, I refuse to speak non-tongue-in-cheek about things like “the probability that XYZ theory of probability is true.” Rather, as a Knightian, risk-averse individual, I’ll just discard results entirely that come from a speculative theory of probability, and that contradict more fundamental facts (like those of kindergarten arithmetic) on which the speculative theory is based.
Comment #25 March 6th, 2016 at 10:27 pm
>> using ordinary probability theory to reason about the correctness of something other than ordinary probability theory
But in other context we do this all the time, e.g. we use semi-classical gravitation to reason about quantum gravity or we use perturbative string theory to understand the full M-theory which we do not know yet.
So perhaps one could use classical probability theory to argue about the probability that some mathematical statements are false in a first approximation and as long as those probabilities are small it may actually make sense as a first step …
Comment #26 March 6th, 2016 at 10:52 pm
>if someone claims to calculate a “probability” that 3×5=7—i.e., that all our intuitions and experiences and computations misled us on that question of elementary arithmetic since the beginning of civilization
I’m not sure why a probability of .000000001 that 3*5=7 would imply that our intuitions misled us etc.
Sure, if they calculated that it was *likely*, then they’re probably mistaken, and I’m willing to think that the probability they’re mistaken is extremely high. But why is a calculation that merely ends up with a non-zero probability of 3*5=7 so improbable as to be meaningless?
For a realistic (hah) lower bound on the probability of 3*5=7:
Number of atoms in the universe ~= 10^80.
Handwaved Premise 1: by shifting all atoms in a way consistent with QM uncertainty and each atom is at most shifted to a position with a probability of 1/10^10, we can manipulate any particular person’s brain to have internally consistent incorrect beliefs about 3*5. (This seems plausible. Say the probability of this is at least 1/10^6.)
Probability of an arbitrary such manipulation is 1/((10^10)^(10^80))=1/10^10^81
So probability of the arbitrary such manipulation times probability of the premise … the premise’s probability barely matters here as long as it’s not superlow.
Premise 2: you can’t tell the difference between the world in which 3*5=15 and you believe 3*5=7 with internally consistent beliefs, from the reverse. (Internally consistent just means you don’t notice a contradiction, no matter how hard you think. This can be because quantum noise “randomly” knocks you out whenever you get too close, whatever.)
Given such premises (all eminently plausible) we must conclude that 1/10^10^81 is a lower bound for the probability that 3*5=7.
(Even if my numbers are off, we can clearly do such a calculation with better attention to physics. I tried to pick bigger numbers just in case.)
So do you think the probability of 3*5=7 is at least 1/10^10^100?
If not, on what justification do you have such high confidence in *physical* observations?
Comment #27 March 6th, 2016 at 11:36 pm
Scott, I too think we need to seperate out levels of abtraction when reasoning. Reflection is a 3-level hierarchy. It bottoms out at Boolean logic (T/F truth values). That’s the ‘object level’.
Next level up reflects our uncertainty about sensory data (meta-level) and that’s optimally handled by Bayesian probability theory (0-1 truth values).
For symbolic reasoning, we’ve reached the meta-meta level, and we are looking for a way of handling the uncertainty in the underlying mathematical models themselves. A coherence measure based on ‘inference to the best explanation’ (IBE) is my favored solution.
The Bayesian level (meta-level) is really about prediction – the probabilities reflect what we anticipate is going to happen in the future (induction).
But symbolic reasoning (meta-meta level) is not about prediction. It’s about inference to the best explanation (that’s abduction). So we need to look for a new measure (not probabilities) which enables us to rank how good different explanations are.
A strong piece of the puzzle is provided by the ‘Theory-Theory Of Concepts’. According to this theory (state-of-the-art in cognitive science), concepts (or categories) are *equivalent* to models about reality. This is implicit in object-oriented programming – programming can be regarded as equivalent to *modelling*.
‘Conceptual Coherence’ was first proposed by Murphy and Medin in 1985 as a measure of how coherent a collection of concepts was. Concepts obey the principle of compositionality (Collections of concepts can be combined to form other concepts).
The key point here, is that according to the ‘theory-theory of concepts’, concepts and models are equivalent. This means that we could use that coherence measure for reasoning about mathematical models!
For a good summary of ‘The Theory-Theory of Concepts’, click here (best summary I’ve read so far):
http://www.iep.utm.edu/th-th-co/
A 2009 Conference held in Edinburgh dealt with the topic ‘Inference To The Best Explanation: A Comparison of Approaches’. Three different approaches were considered:
(1) approaches based on Bayes theorem, (2) approaches based on confirmation, (3) approaches based on coherence
Testing showed that the coherence approach to IBE was beating all others.
Link here:
http://scm.ulster.ac.uk/~e10207076/Research/IBE_truth.pdf
Comment #28 March 7th, 2016 at 1:51 am
I think I read somewhere once that “1+1=2” is the only actual math proven in Russell and Whitehead’s “Principia Mathematica”, in a footnote about 3/4 of the way through the book. I gave up about 700 pages before getting to this.
Comment #29 March 7th, 2016 at 3:42 am
Dan Bernstein proved as far back as 2003 that 83 is prime, by completely classical means:
http://cr.yp.to/talks/2003.03.23/slides.pdf
Being able to run Shor’s algorithm on 91 would beat this, but just barely.
Comment #30 March 7th, 2016 at 4:10 am
wolfgang #25:
But in other context we do this all the time, e.g. we use semi-classical gravitation to reason about quantum gravity or we use perturbative string theory to understand the full M-theory which we do not know yet.
Neither of those are the most reassuring examples imaginable! 🙂
Seriously, I agree that there are cases where we can only learn about a theory that we don’t understand by doing “perturbation expansions” around a weaker theory that we do understand. However, in every case where that works, I would say it works because the weaker theory tells us a circumscribed regime where we can expect it to be valid—and therefore, tells us where to look for the border between its regime and the regime of the full theory, where we can try to eke out progress. Thus, GR tells us to look at the singularities, QFT tells us to look at extremely high energies and short distances, black-box lower bounds in complexity theory tell us to look at non-black-box algorithms, etc.
But arithmetic and probability theory aren’t like this at all. They’re tyrannical; they demand to apply anywhere and everywhere; there’s no border beyond which they acknowledge the possibility of their own breakdown. So as long as we’re working within them, I don’t see how to talk sensibly about any possible replacement theories, or about the probability of those replacement theories being true.
(Incidentally, within physics, QM is “tyrannical” in exactly the same sense, which is one of the central ways QM differs from GR.)
Comment #31 March 7th, 2016 at 4:17 am
Avi #26:
So do you think the probability of 3*5=7 is at least 1/10^10^100?
If not, on what justification do you have such high confidence in *physical* observations?
My answer, again, is that all the details of the calculation that you did depended on your knowledge of quantum mechanics and cosmology. But if 3*5=7, then none of our knowledge about quantum mechanics or cosmology is reliable (for that matter, none of our knowledge about rocks or wooden sticks is reliable). For example, there could just as easily be 1080000 atoms in the visible universe as 1080, completely changing the calculation. For indeed, 1080000 differs from 1080 only by some multiple of 3*5 – 7 = 0. 🙂
Therefore, the whole basis for the calculation collapses.
Comment #32 March 7th, 2016 at 4:19 am
[…] divulgativa en Scott Aaronson, “Quantum. Crypto. Things happen. I blog,” Shtetl-Optimized, 06 Mar 2016; Jennifer Chu, “The beginning of the end for encryption schemes?” MIT News, 03 Mar […]
Comment #33 March 7th, 2016 at 4:34 am
Raoul #28: No, it wasn’t a footnote, it was in the main text. See here for a scan, and here for a blog discussion about why it took them so long.
The short answer, I think, is that Russell and Whitehead weren’t trying to increase their certainty about 1+1=2—or if they were, they shouldn’t have been. Rather, they were trying to build one of the first useful computers: a 1910 computer, it’s true, one that requires pencil and paper to run, but that has the extremely interesting property that if you run it for long enough it will spit out all of ordinary mathematics in some coded form, and no mathematical statements that are false.
Once you think about it that way, it’s no surprise that someone building a computer might need years of effort until they’ve gotten to the point where their machine can even prove 1+1=2, or (what amounts to the same thing in this context) print “Hello world.” Of course if you just wanted 1+1, or a screen with the words “Hello world” on it, you could get that more easily, but you don’t just want that. You want a general-purpose computer, for which 1+1=2 and “Hello, world” are just the sanity checks that it’s up and running and ready to handle Fermat’s Last Theorem and World of Warcraft.
Comment #34 March 7th, 2016 at 5:25 am
Interesting paper here Scott,”Probabilistic alternatives to Bayesianism: the case of explanationism”.
Authors suggest how Inference-to-the-best-Explanation (IBE) might need modifications to probability theory:
http://www.ncbi.nlm.nih.gov/pmc/articles/PMC4410515/
“What is surprising is the almost complete neglect by psychologists of a form of inference that is neither deductive nor inductive but that does seem to play a key role—for better or worse—in human thinking. The form of inference we mean has been labeled “abductive inference” (or “abduction”) by the great American pragmatist philosopher Charles Sanders Peirce.”
Comment #35 March 7th, 2016 at 6:15 am
Don’t Chaitin Ω-constants provide a number-theoretic venue that is grounded in probability, in which mysteries abound, and breakdown lurks?
For example, surely it is very tricky to talk about “Chaitin δ-constants”, which are defined for a finitely specified universal Turing machine TM, and for a finitely specified and consistent set of inference axioms, to be the difference between the probability Ω that TM halts, and the probability Ω’ that TM provably halts. A natural question is: as we vary the set of inference axioms, is δ = Ω – Ω’ bounded below?
Perhaps this tough-but-natural class of questions, provides a concrete case for which “the tyranny of arithmetic and probability theory” is insufficient to discipline our mathematical understanding?
Comment #36 March 7th, 2016 at 7:54 am
John #35: Greg Chaitin deserves eternal credit for discovering the fascinating mathematics of Ω, but is also notorious for overstating the philosophical implications.
There are many places in mathematics where “mysteries abound” (ironically, Ω might not be one of them: I believe most of the interesting open problems about it have been solved, leaving only things like “what’s the 10000th bit of Ω?” that we fully understand why we won’t solve). And there are many things in mathematics (arguably, all nontrivial ones!) that are “very tricky to talk about.”
But that still doesn’t mean there’s any reason to imagine a breakdown of the laws of arithmetic or of probability. Ω, in particular, is at some level “just an ordinary real number,” defined using the standard rules of arithmetic and probability. Its binary expansion happens to encode the halting problem in an extremely compact way, and for that reason, to be unknowable in a very strong sense. But just like for (say) the 1000th Busy Beaver number, or the BB(1000)th bit of π, our human inability to know something is perfectly consistent with its mathematical well-definedness.
Comment #37 March 7th, 2016 at 8:16 am
mjgeddes #34: I haven’t read that paper, but maybe I should comment that my rejection of what I’ve called “Bayesian fundamentalism” is related to David Deutsch’s, who also rejects strict Bayesianism in favor of an approach to knowledge that privileges explanations.
Inspired by this comment thread, I would say: Bayesianism is a wonderful tool in any situation where we can sensibly assign a prior, and I even agree with the LessWrong crowd that there are many parts of life where our civilization desperately needs more of it.
On the other hand, if you view Bayesianism as a completely all-encompassing master key of universe—as demanding that you assign a subjective probability even where no one understands what it could possibly mean to assign a probability—then you end up having to talk about things like “the probability that probability theory is false,” as Avi and wolfgang did above. And because you’re a good Bayesian who’d never bet an infinite amount of money for any finite return (in case Satan or quantum fluctuations were messing with your brain, etc.), you’d say that this probability must be nonzero.
But to me, as I said, this is such an absurdity that the only conclusion is that, if we want to preserve the powerful tool of Bayesianism, we can’t apply it to every interesting question. If we do, it becomes self-devouring—much like the axioms of set theory do if we imagine they can settle absolutely everything, including their own consistency.
In conclusion, let me suggest the following principle:
I will not assign a nonzero probability to something like 3×5=7, for which there’s no explanatory theory telling me how it possibly could be true. That doesn’t mean that I’ll assign a zero probability—i.e., that I’ll accept a bet with infinite odds on anything that strikes me (perhaps mistakenly) as a logical or metaphysical impossibility. It just means that I’ll refuse to bet at all.
Comment #38 March 7th, 2016 at 8:25 am
@Scott
I think Avi’s calculation makes a lot of sense and something like it is unavoidable if you believe in quantum theory.
To your point that N could be different from 10^80 – in this case you would still get a probability greater than 0.
In other words, we could find ourselves in one of the crazy branches of the wavefunction and there is a nonzero probability for that and I think Avi made a good attempt to estimate the probability in a first approximation.
Comment #39 March 7th, 2016 at 9:20 am
wolfgang #38: If that’s your objection, then it’s trivially answered. If 3*5=7, then N is also infinity, because we can add 0 = 3*5 – 7 to N infinity times without changing it. Therefore, from the assumption 3*5=7, we find that Avi’s calculation implies Pr[3*5=7]=0.
I keep trying to explain my perspective in different ways, and will probably give up soon, but to try one more time: if elementary arithmetic is wrong, then all our knowledge about quantum mechanics and cosmology is definitely wrong. Therefore, on pain of incoherence, we don’t get to use QM and cosmology to do a calculation of the probability that elementary arithmetic is wrong. Elementary arithmetic, like modus ponens and other rules of logic, is just a prerequisite to having a rational conversation at all. If there exist branches of the wavefunction where humans are systematically wrong about elementary arithmetic, then in those branches humans can’t have rational conversations either, so we can simply exclude them from our reference class.
Comment #40 March 7th, 2016 at 9:44 am
Ok, well, presumably you’d bet at 99:1 odds that 3*5=15.
And you won’t bet at 10^10^80:1 odds that 3*5=15.
A simple binary search on those, assuming your bet decisions are consistent, will yield a number X such that for all Y>X, you won’t bet at Y:1 odds, and for all Y<X, you will bet at Y:1 odds.
As long as you have an upper and lower bound, you can binary search your way into an exact number. If you don't have an upper bound, then you're committed to betting at effectively infinite odds.
Refusing to bet is still a choice from which we can derive implicit probabilities.
(By "bets are consistent" I merely mean that if bet A dominates bet B, and you'll take bet B, you'll also take bet A. I don't require you to take the inverse of a bet at the inverse of the probability or anything like that.)
I can't actually derive a Dutch book unless I can get you to bet at some probability that 3*5=7. But I can get you to turn down sure wins. Suppose we pin down such an X as above.
I offer two bets simultaneously: one that 3*5!=15 with odds of 1:4X, and the second that 3*5=15 with odds of 2X:1
If 3*5!=15, then you win 4X and lose 2X. If 3*5=15, you win 2X and lose 1. Either way is a win, so you should accept this bet.
But you are unwilling to accept either bet separately, which would imply you can't accept the whole. (If we're in an expected utility framework this is obvious: each bet must have negative EU, so the sum is also negative EU. I'm not sure how intuitive this is once we're throwing out assumptions, so this assumption might be problematic.)
Comment #41 March 7th, 2016 at 9:52 am
@Scott
You sound like somebody who rejects Albert’s theory because absolute time is a priori required (read Kant!) and if you reject absolute time and space all of Newtonian mechanics makes no sense.
>> If 3*5=7, then N is also infinity
But there is only a very small probability for that, therefore Pr[3*5=7] = 0 does not follow.
Comment #42 March 7th, 2016 at 10:01 am
One last thought,
you seem to have less problems to discuss Pr[n=p*q] if really large numbers (like n=10^80 ?) are involved, so what is fundamentally different to the 3×5 case? You did not answer that yet.
Are you a kindergarten-arithmetic-supremacist ?
Comment #43 March 7th, 2016 at 10:11 am
Avi #40: I confess that I don’t understand.
Given any bet that you offer me, I’ll simply look at the part of the bet that specifies what happens if 15=3*5, and accept if and only if I’d accept that (say, if it’s positive utility with a risk profile that I find acceptable). The part of the bet that specifies what happens if 15≠3*5 is irrelevant to me.
In particular, yes, I would accept a bet at 1010^80:1 odds that 15=3*5. That is, I agree to pay you $1000 * 1010^80 if 15≠3*5, if you’ll pay me $1000 if 15=3*5. Details, including how to decide who won, and what happens in the event one of us can’t pay, are to be decided in court if necessary. Will you agree to that bet right now? 😉
More seriously: I don’t care about any hypothetical earnings that I might pass up in the event 15≠3*5. So, given that, can you give a Dutch-book argument to show that, even if 15=3*5, you can still make money off me? I’m not seeing how.
Comment #44 March 7th, 2016 at 10:13 am
Avi,
The paper I linked to above rebuts Bayesian arguments from Dutch books quite decisively (just link on link and scroll down).
“Douven (1999) points out that, in the dynamic Dutch book argument, what makes the non-Bayesian updater vulnerable to a dynamic Dutch book is not the use of a non-Bayesian update rule per se, but rather the combination of that rule and certain decision-theoretic principles, notably ones for determining the fairness of bets. As argued in the same paper, update rules must be assessed not in isolation, but as parts of packages of rules, which include decision-theoretic rules and possibly further update rules. Making use of a decision-theoretic principle proposed in Maher (1992), Douven demonstrates the existence of packages of rules that include a non-Bayesian update rule but that nevertheless do not leave one susceptible to dynamic Dutch books.”
I agree with Scott up to a point. I also reject Bayesian fundamentalism, and like Deutsch, consider inference to the best explanation to be essential. And yes, I also think that there has to be a ground-set of procedures that we just have to accept in order to carry out reasoning at all. But I’m not sure that it extends all the way to arithmetic and probability theory. I think only basic Boolean logic needs to be taken as certain.
Comment #45 March 7th, 2016 at 10:16 am
Did you pick 91 since its the first number that looks prime
but isn’t?
There are tricks for div by 2,3,5,11.
The squares are well known (is there a trick for that?)
So the least number that looks prime but isn’t would be
91=7*13.
Of course, thats in base 10 so maybe you just picked 91
arbitrarily.
Comment #46 March 7th, 2016 at 10:23 am
>In particular, yes, I would accept a bet at 1010^80:1 odds that 15=3*5. That is, I agree to pay you $1000 * 1010^80 if 15≠3*5, if you’ll pay me $1000 if 15=3*5. Details, including how to decide who won, and what happens in the event one of us can’t pay, are to be decided in court if necessary. Will you agree to that bet right now?
I assumed you wouldn’t. If you will, and this doesn’t depend on the actual odds, then aren’t you effectively committing to bet at infinite odds? Or are you willing to bet at any finite odds but not at infinite?
What if, instead of a straight bet, we also generate a random number from 1 to 10^10, 1000 times in a row. If 3*5!=15, you owe me $1000 no matter what. If 3*5=15 and we get 1000 7s in a row, then I owe you $1000.
Will you take that bet? What if we gradually make the numbers bigger?
Comment #47 March 7th, 2016 at 10:24 am
Also, doesn’t taking any finite bet but refusing to take an infinite bet violate induction?
Comment #48 March 7th, 2016 at 10:52 am
mjgeddes #45:
In the particular book I constructed I didn’t rely on any Bayesian postulates. Merely accepting dominating bets if the dominated is accepted, and accepting combinations only if at least one member is accepted.
Comment #49 March 7th, 2016 at 11:05 am
If a quantum computer can break a private-key authentication scheme, is it possible for a quantum computer to defend an authentication scheme with a public-private keys generation using a method (also alternative to prime numbers) that another quantum computer cannot solve in a finite time?
Comment #50 March 7th, 2016 at 11:14 am
domenico #49: I’m not sure I understand the question, but yes, there are many private-key authentication schemes that are believed to be secure even against QCs (indeed, in principle you can build such schemes from any one-way function). Furthermore, you don’t need a QC to do the authentication in these schemes, just a classical computer.
Comment #51 March 7th, 2016 at 11:25 am
@Scott
Sorry, but I could not resist.
>> Details … are to be decided in court if necessary.
If the court calls on an expert witness like Alexander Grothendieck to decide on the factorization of e.g. 57 your bet would be quite foolish.
But what is the probability that A.G. was actually right and all other N mathematicians were wrong?
Obviously, the probability G that a well-designed mathematician is wrong about kindergarten arithmetic is greater than zero, so the probability that all N mathematicians are wrong has to be approximately G^N …
Comment #52 March 7th, 2016 at 11:29 am
wolfgang #41, #42:
(1) Kant’s great mistake was to imagine that a-priori knowledge extends beyond logic and mathematics, to statements about the empirical world like spacetime being Euclidean. It doesn’t: math, which is the one really a-priori discipline, is equally happy with non-Euclidean geometries, therefore non-Euclidean geometries are physically allowed also!
(2) Just for you, let me generalize my previous argument. Suppose Pr[3*5=7]=ε>0. Assume for simplicity that 3*5=15 otherwise. Then
N = N+0 = N+E[15-3*5] = N+8ε > N.
So we can keep adding to N without changing it, so N=∞, so there are infinitely many atoms in the universe, so Avi’s argument for Pr[3*5=7]>0 fails. 🙂
(3) For really large numbers n,p,q, in principle I can become just as certain that n=p*q as I am that 15=3*5. The only problem is that I might not be as certain yet: I might not have done the computation, or if I did, I might fear that the computation had an error. Thus, the only difference is that in the case of 15, my computational process has already converged as far as it’s possible to converge, so that there’s no longer any bet for which my taking it or not taking it depends on what happens if 15≠3×5.
Comment #53 March 7th, 2016 at 11:31 am
gasarch #45:
Did you pick 91 since its the first number that looks prime but isn’t?
Yes.
Comment #54 March 7th, 2016 at 11:39 am
Avi #46:
[A]ren’t you effectively committing to bet at infinite odds?
For 15 vs. 3×5, sure! I’ll agree to pay you ∞ dollars if 15≠3×5, if you’ll agree to pay me $1000 if they’re equal. So again I ask: will you agree to that bet?
(If you won’t agree, I assume it’s because you doubt my ability to come up with ∞ dollars. But hey, I will agree to pay you everything I have, and all my future earnings—even if the Singularity arrives, current theories in cosmology turn out to be wrong, and we both live for infinite time!)
What if, instead of a straight bet, we also generate a random number from 1 to 10^10, 1000 times in a row. If 3*5!=15, you owe me $1000 no matter what. If 3*5=15 and we get 1000 7s in a row, then I owe you $1000.
Will you take that bet? What if we gradually make the numbers bigger?
Yes, I’ll also agree to that bet, with any numbers you want to substitute.
Comment #55 March 7th, 2016 at 11:42 am
>> I can become just as certain …
This (implicitly) depends on the age of the visible universe.
Your computations take time, the more complex the longer, therefore in a universe of finite age you cannot be absolutely certain.
Comment #56 March 7th, 2016 at 11:44 am
@Scott #54
Again, your bet is unwise if you settle it e.g. in an unbiased court who calls on N expert witnesses who may be wrong with probability G each.
Comment #57 March 7th, 2016 at 11:56 am
To make this simpler, I’ll bet $1000, conditional on both 3*5=15, and you generating a random string with a preimage under SHA3-512 of 512 bits all equal to 0. Clearly the probability of that is non-zero. (Also, this must be done before any efficient method to preimage SHA3-512 is published.)
While I’ll take the infinity if 3*5!=15.
Some counterfactual me in an impossible universe is very happy right now 🙂
Comment #58 March 7th, 2016 at 11:57 am
mjgeddes #44:
I also think that there has to be a ground-set of procedures that we just have to accept in order to carry out reasoning at all. But I’m not sure that it extends all the way to arithmetic and probability theory. I think only basic Boolean logic needs to be taken as certain.
Let me refine my position a bit: first-order logic, arithmetic, and probability theory considered as pure math are all knowable a-priori. And all three also have the “tyrannical property”: that is, once we’ve agreed to apply any of these frameworks to any aspect of our experience, it rejects any attempt to describe the same aspect in any contradictory way.
But I’d also say that, precisely because these frameworks are so tyrannical, we need to be extremely careful not to apply them to the physical world in wrong or naïve ways. And this is especially true for probability theory, which is the easiest of the three to misapply.
As a famous example, you can’t insist that there must be some probability p∈[0,1] for the electron to go through the first slit, even though you didn’t measure which slit it went through. There’s a probability if you do measure, but if you don’t there’s only an amplitude. The axioms of probability theory remain fine; you were just trying to apply them where you shouldn’t have.
As a second example, the one we discussed upthread: to me, “the probability that probability theory shouldn’t be used here because it’s inapplicable to our world” is every bit as nonsensical as “the probability that the unmeasured electron is in the first slit.”
Now, this doesn’t mean that probability theory can’t ever be inapplicable, and must therefore be invoked always and everywhere. Quite the contrary! It means that once you do invoke probability theory in some domain, it’s tyrannical over that domain, brooking no alternatives to itself—and therefore, you’d better be careful before letting the genie out.
Comment #59 March 7th, 2016 at 12:09 pm
Avi #57: It’s a deal! But I won’t bother trying to collect on it, since it’s not worth the investment of my time.
Comment #60 March 7th, 2016 at 12:18 pm
wolfgang #56:
Again, your bet is unwise if you settle it e.g. in an unbiased court who calls on N expert witnesses who may be wrong with probability G each.
I find that an absurd objection, for the following reason: even if I don’t bet, there’s still a GN probability that you’ll take me to court and successfully win money from me—say, by convincing a jury that the conversation we’re having right now harassed you, or whatever! And I don’t see that your probability of winning goes up in any appreciable way, if you win conditioned on convincing the jury that 15≠3×5. Also, even if you won one or both insane lawsuits, I’d least I’d have the internal satisfaction of being right. 🙂
Comment #61 March 7th, 2016 at 12:31 pm
@Scott #60
So what you seem to say is that we do not have a reliable method to handle very small probabilities, therefore we set such probabilities to 0 by fiat.
Comment #62 March 7th, 2016 at 12:56 pm
wolfgang #61: Well, there exist tiny probabilities that we can handle perfectly well, like the probability that a fair coin will return 10000 heads in sequence. But yes, there are other tiny probabilities that
(a) we can’t calculate (or we can calculate them and we get 0, which some Bayesians would consider unacceptable), and
(b) we also have no practical way to elicit betting odds for, since the uncertainty in any bet will be completely dominated by “noise terms,” risk aversion, limits of finite money, and other issues unrelated to the underlying question.
In those cases, being risk-averse, I still might not “set the probability to 0 by fiat,” but I also wouldn’t accept any bet that committed me to a nonzero probability.
Comment #63 March 7th, 2016 at 1:24 pm
By saying above that “your uncertainties about the correct application of the new probability theory itself ought to completely swamp your uncertainty about the arithmetical statement”, you imply there’s some probability that our system of reasoning about probability is wrong, say X, and that the probability that we’re mistaken about the arithmetic is less than X, whatever that means.
But then any event with a probability less than X can’t be reasoned about. Suppose 1/2^Y<X. Then our uncertainty about "Y flips of this coin will come up heads in a row" should *also* be dominated by by uncertainty over whether we have the right theory.
If you think that we can talk about arbitrarily small probabilities, simply by talking about ever increasing numbers of consecutive heads, then you must be arbitrarily confident in your theory being correct. Accepting that there's a chance the theory is wrong puts an upper bound on how confident you can be in anything.
Comment #64 March 7th, 2016 at 1:27 pm
With comparable justice, might the following also be said?
Among the more plainly evident of those philosophical illuminations is, for example, that we plausibly are still far from appreciating all of the obstructions to proving PvsNP.
As Herman Melville (might have) put it in Moby Dick:
Note too that mathematicians of the caliber of Michael Harris envision that
Conclusion To borrow an aphoristic construction from Mark Twain’s Roughing It: If
a preachera number theorist can conceive of complex numbers as a ‘dead end’, then surelya lawyercomplexity theorists are authorized to conceive the same of integers. 🙂Mea culpa If my comment (#35) had referred, not to “Chaitin δ-constants”, but to “Chaitin-Hartmanis δ-constants”, and had provided a reference to Hartmanis’ reasoning, then my point would have been clearer, in that the motivation for the δ-construction (of #35) drew equally from the results of Chaitin and Hartmanis.
Comment #65 March 7th, 2016 at 1:54 pm
Avi #63: In practice, the domain where I’d be talking about probabilities like 1/210000 is pure mathematics—and in that domain, I am arbitrarily confident that probability theory is correct.
I’m not arbitrarily confident that if, while flipping a physical coin, you were going to encounter a run of 10,000 heads, by the 5,000th flip a space iguana would appear instead to devour your coin.
Comment #66 March 7th, 2016 at 1:59 pm
gasarch #45: re number 91.
I forget where I read the something like the following:
“There are complex rules for divisibility by other primes. But the only rule that is worthwhile (other than for 2,3,5,11) is that 1001 = 7*11*13. Using this fact allows you to subtract off multiples of 1001 until you get a three digit number, which is easy to check for divisibility by 7, 11 or 13.”
In this case, 91 = 1001 / 11 = 7 * 13, so it is trivial in the (2,3,5,1001)+Division rule set.
I might have read that in Lanczos’s “Applied Analysis”, which is chock full of useful math techniques, such as how to approximately solve cubic and quintic equations. (Who hasn’t wondered about this?)
Comment #67 March 7th, 2016 at 3:34 pm
All —
Factorials are products, and thus have a much higher precedence than evaluating = or !=, so 3*5!= 360, and thus 3*5!=15 is false.
Comment #68 March 7th, 2016 at 4:10 pm
#68 I got excited there for a second thinking I could retire, but then I realized this doesn’t change anything, it only makes me wrong in a different way.
Comment #69 March 7th, 2016 at 7:51 pm
Hi Scott,
Do you think an implementation of DQC1 could be a good way to reach quantum supremacy? (I know this isn’t very well connected to the original post but it’s something I have been meaning to ask for quite a while.)
Comment #70 March 7th, 2016 at 8:12 pm
Chris #69: In principle, sure, there’s pretty good evidence that DQC1 can get speedups over classical, and one could at least imagine a hardware architecture that let you do DQC1 but not all of BQP (namely, one where a few clean qubits are possible but super-duper-expensive, and can be coupled to thousands of dirty qubits). In practice, though, the hardware architectures that are major contenders right now, such as superconducting qubits and ion traps, all seem to have the property that once you could keep one or two qubits alive for a suitably long time (say, using error-correction), there’s not much that would stop you from integrating lots of clean qubits, thereby leapfrogging over DQC1 and going straight to universal QC.
Comment #71 March 7th, 2016 at 9:10 pm
I think it would be true that the central thing is to explain where consciousness is located in space only if consciousness were a noun, but I think it’s a adjective, I think Scott Aaronson is the way matter behaves when it’s organized in a Scottaaronsonian way. And if personal identity was so delicate that the change in the quantum state of one atom in your brain made you a different individual you’d become a different person trillions of times a second, and that doesn’t sound right. I can’t say which of 2 identical collection of atoms is “you” until the meaning of that personal pronoun is pinned down much more precisely, but if they both remember being Scott Aaronson yesterday then they both have a equal right to call themselves Scott Aaronson today.
John K Clark
Comment #72 March 7th, 2016 at 9:13 pm
I’m not excited by Simon’s algorithm: my computer is not going to work on superpositions. So I think cryptographers will mostly ignore this issue until we want to encrypt with quantum computers, which will be a long time.
Comment #73 March 7th, 2016 at 9:22 pm
I’ve been hoping for commentary here on Shtetl Optimized (or any other quantum computing weblog; how many are still seriously active?) of Barbara Terhal’s recent thorough-going review “Quantum error correction for quantum memories” (Rev. Mod. Phys., 2015).
Terhal’s 40-page review (which to me seems really excellent), concludes with a summary remark on the difficulty of “integrating lots of clean qubits”
As a very rough comparison, the relatively straightforward scaling (in theory anyway) of Ronald Drever’s and Stan Whitcomb’s 40-meter prototype gravitational wave interferometer at CalTech (in 1981) to Advanced LIGO (in 2016) — entailing an optical power gain of order 10^4 and an increase in mode-length of order 10^2, but otherwise no very radical theoretical or technological breakthroughs — has taken thirty-five years and cost over a billion dollars. The net reduction in demonstrated strain noise for 1981-2016 was about a factor of 10^-4 (in Hz^{-1/2}). For details consult the original LIGO proposal to the NSF. Fun! 🙂
So broadly speaking, the technological scaling that Barbara Terhal’s article contemplates is, at least superficially, considerably more radical than LIGO’s.
Conclusion Realistically estimating the difficulty and cost of quantum technology-scaling has historically not been easy; and yet the scalable demonstration of quantum supremacy (by any means whatsoever) would be an absolutely epochal scientific achievement.
That’s why (for me and many folks) the new ideas of the Ed Farhi / Aram Harrow paper are both utterly fascinating and immensely important. More please! 🙂
Comment #74 March 7th, 2016 at 11:20 pm
John Clark #71: It’s obvious that the exact quantum state of my brain changes dramatically not only from day to day but nanosecond to nanosecond! Even so, all the states are causally tied together in a chain of quantum-mechanical evolution, in a way that a digital copy plausibly wouldn’t be tied to any element in the chain. In other words, while the state S(t) at time t might be totally different in detail from S(t+1), if you knew S(t) and the relevant environmental inputs at times between t and t+1, you could evolve forward to S(t+1)—which you couldn’t necessarily do if you only knew an approximation S'(t) capturing the “classical digital abstraction layer” of S(t).
Now, I have no idea whether the above observations are actually relevant to philosophical questions about personal identity—as I admit many times in the GIQTM essay! But whatever the faults of the viewpoint I explore in GIQTM, I’d claim that it’s 100% consistent with your dictum that “consciousness is an adjective rather than a noun.” This is precisely a view that tries to locate personal identity in the way matter behaves when it’s organized in a certain way, and that’s impressed by the apparent difficulty (ultimately related to the no-cloning theorem) of constructing a second hunk of matter that behaves identically, even given arbitrarily advanced future technology. If all that mattered was the static, macroscopic information content (the synaptic strengths, etc.), rather than the detailed behavior of one specific physical system with that information content, then clearly the former would be copyable in principle, so a GIQTM-style view wouldn’t work.
Comment #75 March 8th, 2016 at 4:22 am
Hi Scott, it’s great that you blogged about Kaplan et al.’s paper, I was aware of their results since a few months ago and I think it’s a very interesting work, of practical importance for modern post-quantum crypto. I was also aware of Kuwakado and Morii’s results on Feistel and Even-Mansour schemes, and I’ve been trying for a while (with little success, apparently) to advertise this issues in my community. To be fair, there was a little misunderstanding in Kuwakado and Morii’s original paper on Feistel networks, which might have prevented it to be fully appreciated in the crypto community, but it was a slight mistake easy to fix. I think that these two smart Japanese guys have been overlooked for too long.
Regarding your observation:
> In practice, this assumption is unlikely to hold
I’m not sure I agree 100%. It is true that, for the case of symmetric-key encryption schemes and PRPs, since these are supposed to be run on a classical device, it is not immediately clear how to have superposition access to the encryption/permutation oracles – this is in sharp contrast to the case of hash functions (where the Quantum Random Oracle Model *must* be used) or public-key cryptography (where the minimum assumptions should be superposition access in the CPA phase, as in Boneh and Zhandry’s IND-qCPA).
However, there are two important issues here.
The first is purely theoretical: it might happen that an encryption/permutation oracle is used in some cryptographical reduction of some scheme or primitive resistant against quantum adversaries. This does not necessarily mean that quantum access to the oracle should be granted in reality, but still there might be tricky instances (think of meta-reductions, if you’re familiar with them) where it could be much easier to achieve results by giving quantum access to the oracles. From this perspective, quantum superposition access might be a useful generalization.
The second issue is of much more practical concern. Sure you have heard about so-called “side-channel attacks”. Think of an encryption device as a chip on a smart card, and think of those crazy nerdy people having immense pleasure in putting your chip under a microscope, shining it with lasers, freezing it with liquid nitrogen, recording thermal/EM/audio noise from the behaviour of the chip, and, in so doing, magically extracting information. This is not sci-fiction, there are people actually doing this, and there exist whole branches of cryptography dealing with the design of schemes which should “behave well” under such conditions for a broad range of hardware devices.
Now, it is not unthinkable of some future technology which, after exposing your encryption device to different physical parameters from those it is supposed to run with, makes your device show some sort of partial quantum behaviour. This claim might sound weird given how hard it is to even build a proper quantum computer now, but consider that future devices (and current ones too) might incorporate optoelectronic components, optical interfaces, extreme miniaturization, and so on. Even if it has not been done so far, in security one has to assume the worst possible reasonable scenario, therefore it might make sense to also consider cases where a quantum adversary has this sort of powerful interaction with the encryption device.
I hope the above is clear and raises some valid point, even if anybody is welcome to disagree 🙂
Comment #76 March 8th, 2016 at 5:10 am
Scott #70: I think you’re right – the leading hardware contenders are pulling away from the rest of the pack. That’s great for the field of QC but I guess it makes doing non-universal forms of QC seem a bit less exciting. It makes me wonder about what will happen to the funding for the hardware platforms that have been left behind. Perhaps comment #73 about the difficulties of predicting the scaling of technology will keep the research councils funding a broad range of hardware platforms for a little bit longer.
P.S. I once thought about a platform that I hoped could do for DQC1 what photons do for BosonSampling:
http://iopscience.iop.org/article/10.1088/1367-2630/16/5/053045?fromSearchPage=true
Comment #77 March 8th, 2016 at 6:34 am
Tommaso #75: Thanks for the interesting and helpful comment! I completely agree that there are all sorts of weird ways that insecurity against quantum query attacks might make cryptosystems insecure (or less secure than one wants) even in the “real world”—indeed, that’s part of why I decided to blog this.
Comment #78 March 8th, 2016 at 6:43 am
Chris #76: Well, there’s also lots of experimental work that continues in cold atoms, photonics, NV centers in diamond, (the quest for) nonabelian anyons, and other approaches. One of the things I’ve learned from experimentalists in recent years has been how the best experimental designs often require a hybrid of approaches. To take a few examples:
– The Delft loophole-free Bell test involved using entangled photons to control NV centers in diamond
– The leading proposals for how you would scale ion-trap QC also involve coupling photonic qubits to the ions
– I’ve seen a serious proposal for using superconducting qubits to control microwave photons in resonators, which could give you single-photon sources of the quality needed for KLM QC or BosonSampling
– Even if topological QC turns out not to be the best engineering route, the topological ideas have profoundly influenced the “ordinary” QC approaches (most obviously through Kitaev’s surface code)
I’d think this, if nothing else, would be an argument for continuing research into multiple QC platforms at this (still extremely early) stage of the field.
Comment #79 March 8th, 2016 at 8:55 am
Amen! And isn’t similarly true that “The best algorithm designs often require a hybrid of approaches”?
This parallelism has created an ongoing ingenuity-race between the (experimental) “quantum supremacists” and the (computational) “algorithm supremacists”.
A great virtue (as I see it) of Google’s Quantum AI Lab is that their research strategy vigorously pursues both hybridizations — e.g., TensorFlow algorithm advances and DWave quantum advances — within a single research effort.
This dual-hybridization strategy acts to neutralize premature (and usually sterile) wrangling over “who’s right”. Instead it constructively focuses Google’s research efforts upon the indisputably fertile reality that both ongoing hybridizations (algorithm and quantum) are already yielding new computational capacities of immense value.
Google’s broad-band research strategy contrasts pretty strikingly with at least some Shtetl Optimized rhetoric; e.g. April 2014’s essay “Waiting for BQP Fever”“
Such rhetoric is catnip to science reporters, but over the long haul, does it serve STEAM students well? Perhaps as a research community, we shouldn’t prematurely identify any one “main reason” to pursue research in quantum computing?
Conclusion The longer the horse-race goes on between algorithm supremacists and quantum supremacists and the faster their variegated / various-gaited horses run, the more everyone benefits, and the more fun everyone has. 🙂
That’s why (as it seems to me) we shouldn’t hope for any early end to this algorithm-versus-quantum supremacy race. Fortunately the available evidence strongly indicates that the race isn’t likely to end very soon!
Comment #80 March 8th, 2016 at 11:41 am
Scott: I looked over your paper you linked above, and think your criteria of “We know an algorithm that takes as
input a positive integer k, and that outputs the decimal digits of p = 2k − 1 using a number of
steps that is polynomial—indeed, linear—in the number of digits of p. But we do not know any
similarly-efficient algorithm that provably outputs the first prime larger than 2k − 1.18”
Is insufficient. First of all, there’s no variable to vary over when talking about a specific prime, so “polynomial” is meaningless. Secondly, suppose we define f(X) over integers as taking the 1st digit from the left, then the 2nd, then the 4th, then the 8th, etc, so f(12345)=124 and f(12345678)=1248
Set y=f(f(f(f(f(…f(Graham’s number))))) such that there are the fewest number of fs such that y has less than a million digits.
Suppose I were to prove that y is prime. I think we’d consider y a “known” prime, even though it probably can’t be computed in any reasonable amount of time and the number of digits is low.
Do you think that such a number would not be “known”?
Comment #81 March 8th, 2016 at 2:27 pm
@Scott #74
>> the exact quantum state of my brain
I am not sure such a thing exists , because a macroscopic clump of matter is entangled with the environment in a way that may not be possible to disentangle even in principle.
Already on a classical level the question would be where your brain begins and ends (do we need to include the electromagnetic field it produces?) …
And if you succeed in isolating a brain from the environment it probably dies quickly …
Comment #82 March 8th, 2016 at 2:49 pm
Avi #80: You raise an interesting issue. How can I deny that
f(…f( Graham’s number )…)
would be a “known prime,” supposing hypothetically that it were proved to be prime?
OK then, but if we admit y as a “known prime,” then how can we not admit
z = the next prime larger than 274,207,281-1 ?
After all, z is far more algorithmically accessible than y is, and it’s just as mathematically determined.
Pondering this, people might have a gut feeling that y is “known” while z is “unknown” just because of what the respective algorithms look like: an algorithm to compute y “knows exactly what it’s aiming for,” and goes directly there without any false starts or missteps, even if the computation actually takes astronomically longer than the computation of z.
Meanwhile, the algorithm to compute z works by testing numbers one after another until it finds one that’s prime. So we get an intuitive sense that the algorithm is searching for something that it doesn’t actually “have” yet, and that it could halt at a different number than the one it does halt at (even though, on reflection, it couldn’t).
Does anyone have any suggestions for a formal criterion that captures the above distinction? I’m coming up empty right now. More concretely, I have no idea how to rule out the possibility of (say) an algorithm to find z, which would have roughly the same efficiency as the “try numbers one by one” method but would look qualitatively different, would look like it was just shooting straight for its target in the same sense that the algorithm for y is.
Comment #83 March 8th, 2016 at 4:04 pm
Scott – love your blog – nice work. I would love to see a post that specifically addresses whether or not quantum computers can do infinite computations in finite time and what that really means – in terms that people who are not quantum mechanics mathematicians can understand. Also I would love to see a post explaining your tagline in layman’s terms — “If you take just one piece of information from this blog:
Quantum computers would not solve hard search problems
instantaneously by simply trying all the possible solutions at once.” When you write it up – email me so I can read it.
Comment #84 March 8th, 2016 at 4:10 pm
Scott #74 says if you knew the exact quantum state at S(t) and the relevant environmental inputs at times between t and t+1 you could evolve forward to S(t+1), but I’m not sure that would necessarily be correct if true randomness exists; and I know of no law of logic that demands every event have a cause.
The primary philosophical difficulty in thinking about the connection between free will and predictability is nobody can seem to agree what “free will” means. And as for predictability, even in a pure Newtonian world sometimes the only way to know what something will do is to watch it and see.
It would only take a few minutes to write a program to find the smallest even integer greater than 2 that can not be expressed as the sum of two primes and then stop, but will that simple program ever stop? If Goldbach Conjecture is false then it will stop but if it’s true it never will, but nobody knows if it’s true. And a program is looking for a proof of Goldbach will eventually stop if Goldbach is true and has a proof, but if Goldberg is true but has no finite proof (and if it isn’t Turing tells us there are a infinite number of similar conjectures that are) then neither program will ever stop. So if you want to know what programs like that will do you just have to watch them and see.
If “free will” means the inability to always know what you’re going to do before you do it (and that’s as good a definition as any) then those programs have free will.
John K Clark
Comment #85 March 8th, 2016 at 4:59 pm
John Clark #84: The fundamental problem with pointing to the difficulty of predicting computer programs is that you don’t just need to wait and see! Rather, if you know the code of the program, you can always just run the program on a different, faster computer to predict it.
In quantum mechanics, states (specifically, mixed states) are the things you use to calculate the probabilities of observations. According to standard QM, there is true randomness, measurement outcomes have no deterministic “causes” (in the sense that, given full knowledge of the state, you can still only calculate the probabilities), and the formalism of mixed states handles all of this automatically.
Incidentally, I hit all these points in the beginning sections of GIQTM—totally fine if you disagree, but probably faster for both of us if we don’t have to rehash what’s there.
Comment #86 March 8th, 2016 at 5:43 pm
Meanwhile in unrelated news, the Alphago team of Google seems confident enough in the quality of their go playing computer. They have arranged a match of the computer against Li Se-dol, one of the best living go players of the world. The match is starting very soon, and consists of five games without handicap. This time, unlike with the matches in 2015-10, the game data will be published live.
Comment #87 March 8th, 2016 at 6:01 pm
Nova Spivack #83: The answer to your question is NO, there is no sense whatsoever in which quantum computers would “do infinite computations in finite time.”
Quantum computers could do certain things quickly that we think would take an exponential amount of time to simulate using classical computers. But that doesn’t mean that everything that a classical computer could do in exponential time, could quickly be done by a quantum computer! As far as we know today, QCs would give exponential speedups only for certain special kinds of problems.
As a second point, one thing we know for certain is that whatever a quantum computer can do, a classical computer can do also, if you “merely” give the classical computer exponentially more time. And that immediately rules out the possibility of QC giving you “infinite” speedups: it could “merely” give you astronomically large ones.
As for explaining this blog’s tagline: a good starting point might be my Scientific American article, The Limits of Quantum Computers. You could also try my Shor, I’ll Do It post. Let me know if you read those and want more.
Comment #88 March 8th, 2016 at 8:01 pm
Thanks Scott #78 and John Sidles #79. I guess quantum technology is broad – encompassing computing, communication, simulation and metrology – and because of this, we may get to quantum supremacy multiple times in multiple ways. Ashley Montanaro says it’s arguable we may have already reached this point for quantum simulation http://www.nature.com/articles/npjqi201523 .
Comment #89 March 8th, 2016 at 10:20 pm
Scott asks in his “The Ghost in the Quantum Turing Machine” essay:
“Suppose an experimenter flips a fair coin while you lie anesthetized in a white, windowless hospital room. If the coin lands heads, then she’ll create a thousand copies of you, place them in a thousand identical rooms, and wake each one up. If the coin lands tails, then she’ll wake you up without creating any copies. You wake up in a white, windowless room just like the one you remember. Knowing the setup of the experiment, at what odds should you be willing to bet that the coin landed heads? ”
I would give 50/50 odds. It makes no subjective difference to me if there are 999 chunks of matter in 999 identical rooms organized in a Johnkclarkian way or only one. A billion identical programs running on a billion identical computers at the same time is equivalent one program running on one computer.
John K Clark
Comment #90 March 8th, 2016 at 10:21 pm
More from Scott’s s “The Ghost in the Quantum Turing Machine” essay:
“However, those who consider 50/50 the obvious answer should consider a slight variant of the puzzle. Suppose that, if the coin lands tails, then as before the experimenter leaves a single copy of you in a white room. If the coin lands heads, then the experimenter creates a thousand copies of you and places them in a thousand windowless rooms. Now, though, 999 of the rooms are painted blue; only one of the rooms is white like you remember. You wake up from the anesthesia and find yourself in a white room. You wake up from the anesthesia and find yourself in a white room. Now what posterior probability should you assign to the coin having landed heads?”
I would still give 50/50 odds because 999 of the cases are indistinguishable, so there are not a thousand possibilities but only 2, John Clark waking up in a white room and John Clark waking up in a blue room. If however I wake up in a blue room I would say there was 100% chance the coin landed heads, and I would also say there is a 100% chance that I am a copy and a 100% chance that somewhere in that hospital the original John Clark is waking up in a white room.
John K Clark
Comment #91 March 9th, 2016 at 6:52 am
Sorry if I’m late to the party, but I wanted to point out something relevant to the discussion of probability. Scott, you write that a problem with any dogmatic application of Bayes is that
and discuss e.g. the probability that 3 x 7 = 15. This is indeed silly; the genius of Bayes’ theorem is that it allows inductive reasoning (i.e. reasoning in which a conclusion cannot deductively follow from a premise) as well as deductive reasoning.
Things like p(3 x 7 = 15 | axioms) = 0 and even p(Bayes’ formula | axioms) = 1 are in fact trivial, as they can be found deductively without any induction. Of course, things like
p(3 x 7=15 | axioms and that I’m bad at deductive logic)
p(Bayes’ theorem | axioms and that I’m bad at deductive logic)
are problematic. They become slighlty easier to think about if phrased as e.g.
p(Jim derives Bayes’ theorem | Jim assumes some axioms and that Jim is bad at deductive logic)
but in any case, no paradox is reached.
Comment #92 March 9th, 2016 at 11:29 am
There is at least one class of algorithms that is an exception to this rule (and it is a commonly encountered class): algorithms that have no explicit termination criterion.
For example, Chaitin’s Ω-constant is formally uncomputable, yet Chaitin is happy to supply (in his book Exploring Randomness) finitely-specified software that is warranted to compute Ω to any desired accuracy. The ‘catch’ is, Chaitin’s software doesn’t notify you when it is finished! Rather, the longer the software runs, the more confident the user can be, that the output value of Ω is accurate within some specified error-bound.
This example illustrates a general point: races between algorithm-supremacists and quantum-supremacists very commonly hinge upon subtleties involving the rules of the race.
As a second example, quantum-supremacists can produce random (algorithmically incompressable) binary sequences, a capability that in no algorithm-supremacist can claim. Yet in practice, few algorithms are more widely deployed than (quasi-)random number generators.
And as a third example, comparably subtle issues of elucidation arise when we contemplate the class of natural answers to the question: What verifiable computational capacities suffice to collapse the Polynomial Hierarchy?
Here the stipulation “verifiable” makes an enormous practical difference (as Juris Hartmanis was among the first complexity theorists to point out).
Prediction Each fresh proposal by the quantum-supremacists to confound the algorithm-supremacists will perversely help to catalyze fresh algorithm advances, and vice versa; moreover this lively back-and-forth benefits everyone.
Conclusion There’s plenty of scope for transformational advances to be compatibly achieved by both algorithm-supremacists and quantum-supremacists. More soberingly, there’s plenty of scope for (mostly sterile) squabbling regarding the “official” rules of the supremacy-competitions.
Sterile squabbling, no one needs. So perhaps it is well for every variety of supremacist to contemplate Dick Lipton’s and Ken Regan’s favorite Far Side cartoon. 🙂
Comment #93 March 9th, 2016 at 12:05 pm
Andrew #91: I should clarify that, when I talk about “Bayesian fundamentalism,” I’m thinking of an ideology centered around LessWrong (but also defended by wolfgang and others upthread), which basically says that you should cash your beliefs about every factual question whatsoever into which betting odds you would currently accept (and then hopefully make money…) We can distinguish this ideology from Bayesianism considered as a strict mathematical formalism.
And yes, perhaps the most obvious place where the ideology parts ways with the formalism is on this question of Pr[2+2=5]. In the formalism, obviously that’s 0, as you point out. But the adherents of the ideology say that you should never bet infinite odds on anything—for what if you’re confused about arithmetic, or a demon messed with your brain, etc. etc.? I believe Eliezer Yudkowsky expressed this in slogan form as “0 and 1 are not probabilities.”
So on reflection, maybe my only real peeve here is the conflation of the Bayesian formalism with the Bayesian ideology: it’s always questionable to use the former as a stalking-horse for the latter, but never more so than when the two actually contradict each other!
Comment #94 March 9th, 2016 at 12:15 pm
Scott #83:
What about relative to a halting oracle? “the next prime larger than 2^74,207,281-1 ?” intuitively feels “known” if we have an oracle/hypercomputer.
Even if we had an ordinary computer, but it was 10^10^100 times faster (so it could print out any particular digit of the prime in a second), I think we’d still consider it known. So the actual running time does matter, even on the same algorithm. A formalization would need to take that into account.
Suppose (this is probably already proven impossible, though) that there’s some unknown algorithm that would find the next prime after any given prime “fast”, and that furthermore that we can test any algorithm to see if it does this (with a guaranteed to halt test). Would a program that loops over all programs until it happens on the “prime-finding” one, then runs it to generate the next prime after 2^74,207,281-1, count as knowing that prime?
Weirdly, my intuition says yes, which means there’s a difference between object level blind guessing and meta-level blind guessing.
For a formal criterion, I’d first include all cases where we can generate individual digits quickly, regardless of method.
Then to deal with my Graham example, maybe we should separate “platonic” computations that are costless in calculating how complicated the operation is (like shuffling around digits), and other computations that are costly (like iterating over possible numbers). You want to make sure the platonic group isn’t Turing complete, but still captures a good chunk of what we consider “simple” about function f. I’m not confident this is doable at all, because Turing completeness is difficult to prevent and we’re trying to include all “natural” functions. (e.g. we want to include exponentiation to allow 2^74,207,281-1 to be “known”, but we don’t want to allow recursion). A proof that this is *not* doable would also help, if we could isolate the assumptions that make it impossible.
But separating permissible operations seems the right thing to do when you’re worried about different versions of the same algorithm producing different outcomes.
What about the Graham derived number above, except we replace the last half of Graham’s number with the first prime exceeding it first? Some part of me insists this is still simpler than “first prime above 2^74,207,281-1”, but for this one I expect others’ intuition to differ.
Comment #95 March 9th, 2016 at 12:18 pm
(To clarify, different outcomes means whether we’d consider it known or not, not that the algorithm produces different results)
Comment #96 March 9th, 2016 at 12:53 pm
Scott Says #85:
” The fundamental problem with pointing to the difficulty of predicting computer programs is that you DON’T just need to wait and see! Rather, if you know the code of the program, you can always just run the program on a different, faster computer to predict it.”
But if you run your superfast computer to find a numerical counterexample to prove that a mathematical proposition is untrue you will never find it if it is in fact true. And if you run the superfast computer to find a proof of it your will never find it if the proposition is true but has no finite proof. Turing tells us there is no way in general to put statements into the categories provable, false, or true but not provable; so maybe working on the Goldbach problem is a waste of time and maybe it isn’t. And even if Goldbach isn’t there are a infinite number of similar problems that are. So even if your superfast computer has been working on Goldbach for a trillion years it might stop in the next 10 seconds or it might never stop. All you can do is watch it and see.
John K Clark
Comment #97 March 9th, 2016 at 1:27 pm
Avi Says: in Comment #94
“What about relative to a halting oracle? “the next prime larger than 2^74,207,281-1 ?” intuitively feels “known” if we have an oracle/hypercomputer.”
If it exceeds the computational power of the entire physical universe to calculate (as seems likely) does the 423rd prime number greater than 10^100^100 really exist or only sorta exist?
John K Clark
Comment #98 March 9th, 2016 at 1:35 pm
John Clark #96: The point you’re both trying to make makes absolutely no sense to me. I’m … familiar with the unsolvability of the halting problem, and with the fact that a program to (say) search for counterexamples to Fermat’s Last Theorem still won’t find any counterexamples if you run it twice as fast.
But human actions are always chosen after only a finite amount of deliberation. This means that, if
(a) you possessed an exact description of the physical state of someone’s brain, as well as of their environment, and
(b) the laws of physics are computable,
then in principle, you could calculate the probabilities for everything the person might do at a given future time—if you liked, until the end of the person’s natural life. (And that’s what we’re trying to talk about, the predictability of the sorts of people who have already lived, not of hypothetical future immortals.)
Moreover, you could generate this information (say) 100 times as quickly as the person him- or herself generated it, by the simple expedient of running the program on massively-parallel computers that simulated the brain at 100x the natural speed. (Since neurons are incredibly slow by electronics standards, this would surely be possible, assuming we had such a simulation in the first place.) The unsolvability of the halting problem is completely irrelevant to this.
It’s totally fine if you want to dismiss all this as irrelevant to the aspects of free will that you care about. But that you’d have the prediction capability I said, under the assumptions I said, is not debatable.
Comment #99 March 9th, 2016 at 2:26 pm
Clark #98: given the assumption of an oracle, we would be able to compute any given digit quickly. We couldn’t *store* it all, and you could advocate something like https://en.wikipedia.org/wiki/Ultrafinitism and say it doesn’t *really* exist, but the existence of an oracle would seem to imply that ultrafinitism is false, because the outcome of the calculation depends on larger numbers. If you want to prove something actually is an oracle, you’d need to assume P!=NP, though, or it could be tricking you.
Comment #100 March 9th, 2016 at 6:57 pm
Scott says in #98:
” But human actions are always chosen after only a finite amount of deliberation. This means that, if (a) you possessed an exact description of the physical state of someone’s brain, as well as of their environment, and (b) the laws of physics are computable, then in principle, you could calculate the probabilities for everything the person might do”
I would certainly agree with that, if you can calculate when a person will die then you’d know if they haven’t had thought X or performed action Y by then they never will; but I think that fact just tells us something about the fragile nature of human biology rather than anything profound about the universe as a whole. I was also a little confused when you said in your The Ghost in the Quantum Turing Machine essay:
“free will” seems to combine two distinct ideas: first, that your choices are “free” from any kind of external constraint”
I don’t see why anybody would even want that sort of freedom, I want to be influenced by outside factors like light bouncing off a wall so I don’t walk into one.
“and second, that your choices are not arbitrary or capricious, but are “willed by you.””
But if I am rational then there is a reason, a cause, for why I behaved as I did, that’s why when somebody behaves in a way we don’t understand we say “why did you do that?” and if they can not answer we conclude they are irrational.
It seems to me that absolutely everything happens because of cause and effect and thus is deterministic (but not necessarily predictable) OR it does not happen because of cause and effect and thus is random. So like it or not we’re either roulette wheels or we’re cuckoo clocks.
John K Clark
Comment #101 March 9th, 2016 at 7:27 pm
I think the “0 and 1 are not probabilities” is similar to a frequentist sentiment I saw one written time in response to a typo of significance of detection of some effect: “I’m not even 900 sigma confident that I’m awake right now.” Very small numbers are hard to interpret…
Comment #102 March 10th, 2016 at 12:30 am
0 and 1 are not probabilities – they’re Boolean values that can only be applied at a different level of abstraction than probability theory. So Yudkowsky is correct there.
The Less Wrong/Yudkowskian mistake is to think that all of intelligence can be captured by pattern recognition. What Yudkowsky fails to grasp is that probability theory can really only establish correlations (patterns). It cannot definitely establish causation. Causation is not reducible to mere correlations.
To properly handle causation, we need categorization, which the process of combining some particular set of data into single coherent concepts.
To see that this cannot be reduced to probability calculations, we just need to consider happens when we attempt to compare different categories: this depends on how data is *presented* or *communicated*.
It’s important to understand that concepts (categories) are *identical* to explanations. This is because concepts are *models* about theory.
This is where IBE (Inference to the Best Explanation) comes in. By using explanations for inference, we are actually comparing hypotheses according to how they are symbolically represented or presented (specifically, according how ‘coherent’ a given set of data making up a category is). But this is partially a matter of ‘style’ or ‘presentation’.
But in Bayesian probabiliy theory, the probabilities of a given hypothesis don’t depend on how the evidence is presented. Ergo, categorization cannot be captured by probability theory.
The conclusion is that probabilities are not the correct measure for handling uncertainty about models. As mentioned, we need a ‘coherence’ measure of some kind.
Comment #103 March 10th, 2016 at 8:58 am
@Scott #93
I hadn’t heard the 0 and 1 are not probabilities position before. My first thought is that it’s nonsense. E.g. P(\Omega)=1 and tautologies like P(A|A) = 1 are obvious counterexamples. You can literally construct endless more.
It’s funny, for hundreds of years people mistrusted (Bayesian) inductive logic and insisted on only deductive reasoning in e.g. science. Now you tell me there are people with the exact opposite position!
Comment #104 March 10th, 2016 at 10:39 am
@Scott @andrew
The debate is not really about Bayesianism imho.
My point was that Pr[15 /= 5×3] > 0 just as
Pr[16579 /= 137*121] > 0
and Pr[n /= q*p] with n = 10^80
for the simple reason that every mathematician and quantum computer has a non-zero probability to fail and there is only a finite number of them in the visible universe.
Avi quantified the probability and I really think if you disagree with it then you disagree with physics as we know it.
The platonic idea that 15=3×5 is absolutely certain implies that there is a reality beyond physics and you would have to explain how you can be so certain about that.
Comment #105 March 10th, 2016 at 11:48 am
wolfgang #104: On the contrary, if you think it’s conceivable that 15≠3×5, then I’d say that you’re the one who needs to explain what possible observations of the physical world would lead you to think that—otherwise, I won’t even understand what you mean. As I tried to explain in this video, even if cavemen found that anytime they put two rocks and two rocks together they got five rocks, it would be bizarre for them to conclude that “2+2=5.” Rather, the cavemen would be deeply confused by what was happening—confused because they knew that 2+2=4—and would probably look for explanations to settle the mystery (maybe an animal spirit always comes along and inserts the fifth rock?).
So, if our certainty that 2+2=4 doesn’t come from experience, where does it come from? From the exercise of reason—the same reason that we need as a prerequisite to any empirical investigation. That we have the capacity for reason is of course a contingent fact of physics and biology. But the good news is that once we do have it, we can use it to formulate general statements like Modus Ponens or 2+2=4 that we can see would still be true even if the laws of physics had been different, and that indeed have undergone no change even as physics has been revolutionized multiple times. (Otherwise, I’d say that the very words and concepts that we’re using to have this conversation are meaningless, so we might as well stop.)
I don’t call myself a “Platonist,” since I don’t even know what it even means to say that mathematical truths “exist in a Platonic realm.” Indeed, that concrete way of putting things even strikes me as a step backwards—as if astronomers could one day send probes to Plato’s realm to find out what’s in it, or prove that it never existed. The concepts of “existence” and “reality” that we use when discussing physical objects are just flat-out irrelevant here.
I instead call myself an “anti-anti-Platonist”: someone who’s not literally committed to a “Platonic realm” of mathematical truth, but who given the choice, would much rather that people believe in such a realm than that they spout the self-evident garbage that goes with denying math’s intellectual autonomy.
Comment #106 March 10th, 2016 at 12:01 pm
>> spout the self-evident garbage
alright, I get it
Comment #107 March 10th, 2016 at 1:57 pm
Scott Says in Comment #105
“ if you think it’s conceivablethat 15≠3×5, then I’d say that you’re the one who needs to explain what possible observations of the physical world would lead you to think that”
I agree, and for that reason I think that physics is (probably) more fundamental than mathematics. Mathematicians are always saying that mathematics is a language, a language that is especially good at describing how physical things behave but a language nevertheless. If that’s true then like any other language you can write both fiction and nonfiction. So maybe inner consistency isn’t enough for reality, after all some novels have no plot holes, so maybe some very abstract mathematics like Kenneth Kunen’s Huge Cardinal Numbers or even the 423rd prime number greater than 10^100^100 are fictional stories written in the language of mathematics that are equivalent to fictional Harry Potter stories written in English.
John K Clark
Comment #108 March 10th, 2016 at 2:02 pm
What about simple miscomputation? Like thinking 12+20=22 because you just added incorrectly. In this case, I guess, the observation is that whenever you carry out the process you are aware of for adding numbers, with the inputs “12” and “20”, you get “22”. Except you’re not actually carrying it out correctly.
Comment #109 March 10th, 2016 at 2:47 pm
John Clark #107: By exactly the same logic, someone else might claim that geology and biology are “more fundamental than physics,” because physics is equally happy to describe fictional icy methane worlds orbiting two suns and populated by three-eyed tentacle creatures made of silicon; only geology and biology describe our actual earth with its carbon-based life.
This would actually be perfectly fine, as an explanation for why someone preferred geology or biology over physics. To each her own! But the use of the word “fundamental” here is just silly. Physics and math are intertwined but about different subjects: physics, the laws of our universe; math, the necessary truths that would hold even if our universe were different. Math supplies the menu of possibilities from which physics chooses. Both subjects have their own fundamental discoveries and concepts.
Incidentally, the study of large cardinal axioms, CH, AC, etc. is an example very different in character from the rest of mathematics. While it’s still rigorous and important mathematics, that study really might be compared to writing fanfiction, in the sense that one creates whole detailed universes in which all of math can be done, but which differ from each other, and no one of which could clearly be said to be the “real” universe.
But what about Wiles’s proof of Fermat’s Last Theorem—was that also fanfiction? There’s no alternative universe where xn+yn=zn has nontrivial integer solutions for n≥3. The same goes for virtually everything in number theory, analysis, topology, algebraic geometry, combinatorics, theoretical computer science, etc., almost none of which has any nontrivial dependence on the axioms of set theory.
Finally, I don’t agree that math is a language. Languages, definitions, and notations are certainly part of it, but another part is discoveries: things that couldn’t possibly have been otherwise, that follow from the definitions, that humans didn’t know and then suddenly did know. Once finite simple groups were defined in the 1800s, the existence of the Monster group then followed as an unavoidable consequence—though no one knew it until the late 1970s / early 1980s. In that sense, the Monster is not a convention about how to use language, like “a bachelor is an unmarried man.” Nor is it fanfiction. Even though it has no physical location or extent, humans discovered it in much the same sense that they discovered Antarctica and Pluto.
Comment #110 March 10th, 2016 at 2:56 pm
To say that something is ‘platonic’, is just to say that it’s ‘universal and timeless’. It applies at all times and places. Yes, at least some mathematics has this character. I think it’s OK to say that something ‘exists in the platonic realm’, so long as we realize that this is a different type of ‘existence’ than the physical world. (Again, we just neeed to be careful to separate out levels of abstractions).
If there is uncertainty in the statement ‘2+2=4’, it’s not the sort of uncertainty that you’d attach a probability to. But you could ask; ‘How coherent are the axioms that imply the statement?’.
In so far as something has only deductive content, it has to be a priori certain. First-order logic has this character. (Fully consistent and complete).
But any inductive or abductive content introduces uncertainty. Deciding which axioms are ‘true’ in the first place is not deductive. However, this type of uncertainty is not the type of uncertainty that you’d use ‘probabilities’ to discuss: instead, you’d talk about the ‘coherence’ of your proposed axioms.
Comment #111 March 10th, 2016 at 7:55 pm
Sniffnoy #108:
What about simple miscomputation?
Of course that happens often, and is a good reason not to bet infinite odds even about arithmetical questions that you feel very confident about (like, say, a 3-digit addition that you verified many times on paper). But in that case, it’s clear that “the problem is yours”; there’s no indication that there’s not an absolute truth about the sum, or that the sum would be different under different laws of physics, or anything like that.
Comment #112 March 10th, 2016 at 8:57 pm
Scott Says in Comment #109
“ John Clark #107: By exactly the same logic, someone else might claim that geology and biology are “more fundamental than physics,” because physics is equally happy to describe fictional icy methane worlds orbiting two suns and populated by three-eyed tentacle creatures made of silicon […] the use of the word “fundamental” here is just silly.”
Maybe it’s due to my lack of imagination but I can conceive of matter that obeys the laws of physics existing without three-eyed tentacle creatures made of silicon existing, but I can’t visualize three-eyed tentacle creatures made of silicon existing without matter that obeys the laws of physics existing. Also I wonder if the physical universe did not exist, if there were not even one thing in it, would mathematics exist? If the answer is no then physics is more fundamental than mathematics. If the answer is yes then mathematics is more fundamental than physics; but I think physics would still be more fundamental than intelligence or consciousness because I don’t see how intelligence could work without matter that obeys the laws of physics. And although consciousness is very important to us Evolution can’t see it at all just as we can not directly see it in anything except ourselves, so if consciousness were not a unavoidable byproduct of intelligence I don’t see why Evolution would bother making something that was conscious at all, and yet I know for a fact that it did at least once and probably many billions of times. But as I say maybe that’s just due to my lack of imagination.
John K Clark
Comment #113 March 10th, 2016 at 9:20 pm
John Clark #112:
Also I wonder if the physical universe did not exist, if there were not even one thing in it, would mathematics exist?
One reason I don’t like the framing of the “Platonism debate” is that I think people get way too hung up on “existence,” forgetting that that concept has very different meanings in different contexts. Jupiter exists, quantum entanglement exists, and infinitely many primes exist, but not all in the same sense!
But in any case, setting aside the question of what it could mean for “mathematics to exist,” I feel completely comfortable in saying that if the physical universe didn’t exist, Fermat’s Last Theorem would still be true.
Comment #114 March 10th, 2016 at 10:59 pm
Perhaps the term “fanfiction” carries unfortunate connotations? For example, is quantum computing “fanfiction” in which hamiltonian flows do not decoherently couple qubits to a universal QED vacuum? Are complexity classes “fanfiction” in which (nonexistent) oracles classify Turing Machines? Ouch.
Let’s look around for a logical middle ground (and less-freighted language to describe that middle ground).
In regard to the foundations for mathematics, Colin McLarty’s “What does it take to prove Fermat’s Last Theorem? Grothendieck and the logic of number theory” (2010) reminds us that the clarity and simplicity that are (sometimes) associated to mathematical “fanfictions” can so greatly foster creative insights, as to amply justify their existence.
More generally, the white paper “Homotopy type theory: unified foundations of mathematics and computation” (2014), which is authored by a august team of mathematical luminaries explicitly proposes to construct a (homotopic!) fan-fiction:
Needless to say, not everyone agrees that these ambitious “fan-fictional” objectives are feasible and/or desirable; still it is well worthwhile (isn’t it?) for students to at least be aware of these works.
Question and answers Is it true that HoTT, quantum computing, and complexity theory alike are founded upon “fanfictions”? Obviously “yes”.
Shall we therefore restrict our investigations to non-fanfictional ZFC axioms, strict QED hamiltonians, and Hartmanis-type no-oracle complexity theory? Obviously “no”.
Conclusion It is desirable that some investigators embrace fanfictions (and even invent new ones), and it is comparably desirable that other investigators reject fanfictions (which after all are formally unnecessary, or even counter-factual). Most of all, it is vitally important that the research community as a whole acknowledges and respects — and even celebrates — this creative diversity of opinion.
After all, in research as in the game of “go”, optimal strategies commonly are mixed strategies! 🙂
Comment #115 March 11th, 2016 at 12:33 am
Comment on “Realization of a scalable Shor algorithm” (Zhengjun Cao and Lihua Liu):
“We remark that the demonstration of quantum factorization proposed by Monz et al. does not conform to the Shor algorithm. The necessary step of Continued Fraction Expansion in Shor algorithm can not be accomplished. The original Shor complexity argument does not apply to the demonstration. It does not specify a universal quantum modular exponentiation method. In view of these flaws, we do not think that the demonstration is believable. Naturally speaking, it has no relation to the Shor algorithm.”
Comment #116 March 11th, 2016 at 12:42 am
Scott Says in #113
“I feel completely comfortable in saying that if the physical universe didn’t exist, Fermat’s Last Theorem would still be true.”
Maybe, but then again Fermat’s Last Theorem involves numbers and if not even one physical thing existed…..well…. I’m not sure. After all everything we know about numbers comes from physics, humans started their study of numbers by observing how physical objects like their fingers behaved, and even today mathematicians use the physical neurons in their brains to deduce more facts about numbers.
I think we could agree that without the physical universe nothing would know if Fermat was true, or even what the theorem said, or what a number was, or what “truth” meant. Maybe that wouldn’t cause the complete oblivion of mathematics, but it must at least reduce its level of existence.
John K Clark
Comment #117 March 11th, 2016 at 12:58 am
John Sidles Says in #114
“Perhaps the term “fanfiction” carries unfortunate connotations?”
A negative connotations certainly but I don’t think it’s an unfair connotation.
” For example, is quantum computing “fanfiction” ”
My strong hunch is that it is not but I won’t be completely convinced until somebody makes a physical quantum computer that can solve a problem that a conventional computer could not solve before the sun turns into a red giant. Then I’ll know without a doubt that quantum computing is the real deal and no fanfiction.
John K Clark
Comment #118 March 11th, 2016 at 8:58 am
John Sidles #114 and John Clark #117: I should clarify that I wasn’t using “fanfiction” in the pejorative sense of “research that’s useless and has no connection to reality,” but in the purely descriptive sense of “research whose purpose is to build up and explore detailed hypothetical worlds, no one of which is obviously ‘truer’ than the others.”
There’s nothing wrong with actual fanfiction, and “fanfiction” by the above definition also has an important role in science; it helps us clarify the space of possibilities and the consequences of our starting assumptions (even if it doesn’t force everyone’s acceptance in the way discoveries about our world do, but remains restricted to a “fan base”—which is fine!). Personally, I try to follow set-theoretic fanfiction with interest! And as for the fanfiction of building oracle worlds that cause certain pairs of complexity classes to collapse and others not to collapse, I’ve even been known to participate myself. 🙂
Comment #119 March 11th, 2016 at 9:20 am
Scott #105, So I’m curious what your explanations to settle the mystery would be if you happened to put two and two rocks together but the yield was five rocks?
[If I’m honest my reaction order would probably look like: 1) demons! 2) I’ve had a stroke? 3) This has got to be a trick 4) I wonder how many rocks I can generate this way ]
I’m also really digging the digressions into different types of existence that have come up recently in the comments here.
[I spent a lot of time (amateur) trying to figure out how mathematics works, but in much the same way that I would try to figure out how a toaster works. At some point it occurred to me that maths don’t quite work the same way as toasters.
Also I’ve got a spiritual belief in God, but I don’t see how God could work in any sense that everything we know about works and still be God (if there are spiritual gears then wouldn’t there have to be a system that is more powerful then God … kind of defeats the point of God).
However, for either type of existence that I’m talking about here, I do not have a meaningful way to talk about why things in these modes of existence should be expected to work even though I believe they both do.]
Comment #120 March 11th, 2016 at 11:01 am
DLI #119:
So I’m curious what your explanations to settle the mystery would be if you happened to put two and two rocks together but the yield was five rocks?
[If I’m honest my reaction order would probably look like: 1) demons! 2) I’ve had a stroke? 3) This has got to be a trick 4) I wonder how many rocks I can generate this way ]
I suppose it would depend on how exactly it happened that five rocks came to be there. Like, does a fifth rock just materialize out of nothing before my eyes? At what spatial location, relative to the other four rocks? What’s its shape and size, and how does that vary with the shapes and sizes of the original rocks? Also, how close to each other do the two and two rocks need to be before the universe “knows” that this is an agglomeration of four rocks and it should therefore create a fifth one?
Notice that these are all empirical questions—immediately suggesting the experiments that might get me to the bottom of mystery—but they’re questions that I couldn’t even ask without knowledge (in this case, that 2+2=4) that’s non-empirical. It seems to me that most good empirical investigation has the same character: that is, we come with some prior theoretical expectation about how the world “has to be,” based on a mathematical model that we rigorously understand—but then we let the world tell us if there are subtle or not-so-subtle ways in which our model fails to reflect reality.
Comment #121 March 11th, 2016 at 11:06 am
Fanfiction may indeed have value but my point was that the acid test to determine if something is fanfiction or something more always involves physics. Although beautiful and logically consistent a few still thought that General Relativity might be fanfiction, but the recent experimental detection of Gravitational Waves pretty much eliminated the last remaining doubt. But what about the Real Numbers, are they a fanfiction? Are there really a INFINITE number of points between zero and one on a tape measure, an infinity infinitely larger than the infinite number of integers? I’m just asking.
John K Clark
Comment #122 March 11th, 2016 at 11:47 am
John K. Clark says in #116
>Maybe, but then again Fermat’s Last Theorem involves >numbers and if not even one physical thing existed…..well…. >I’m not sure.
Uh you realize that the natural numbers can be constructed purely from the empty set?
Comment #123 March 11th, 2016 at 12:04 pm
John Clark #121:
Are there really a INFINITE number of points between zero and one on a tape measure, an infinity infinitely larger than the infinite number of integers? I’m just asking.
Since you like physics so much, you should know that physics has a lot to say about that exact question.
In Galilean and Newtonian physics, the answer is yes.
In special and general relativity, the answer is again yes.
In nonrelativistic QM, the answer is again yes.
In quantum field theory, the answer is once again yes.
In quantum gravity, the answer is “it’s complicated.” The number of different locations along a tape measure that can be resolved by measurement should be at most 1033 per centimeter (one per Planck length), but that might or might not correspond to “space being discrete” in any straightforward way.
In any case, notice that it’s a complete scientific nonstarter to ask how many points are “really there.” Either you have to ask how many points are postulated by our best physical theories, or else you have to ask an operational question, like how many points could be resolved by making a measurement.
Comment #124 March 11th, 2016 at 12:18 pm
The fanfictional worlds that John K Clark, Scott, and Gautham Kamath are discussing, were amusingly envisioned in a much-honored story by an acknowledged Grandmaster of fictional-universe construction:
Needless to say, we’ve learned a lot about causality since 1957, in every domain from quantum to neurological to psychological to cultural. Yet even today, natural questions like “What is ‘causing’ AlphaGo’s go-moves to be so much better (so far) than Lee Sedol’s go-moves?” are not easy to answer. So perhaps Jack Vance’s narrative theme is worth revisiting! 🙂
Comment #125 March 11th, 2016 at 12:25 pm
Scott #120:
I think I was mostly looking for a “what’s your personality” type of response, which I think your followup questions answer pretty well. So unless anyone is really itching to go down that particular rabbit trail I’m going to drop it (thanks for playing btw).
Avi #80:
While I don’t think your point was to talk about *that* prime number, I actually had some fun thinking about the number you described. Do you mind if I call it Avi’s prime number (or perhaps Avi’s “prime” number until we can get some better resolution as to what it’s primality is)?
Comment #126 March 11th, 2016 at 3:40 pm
Here is an fanfictional universe that MathOverflow attributes to Tim Gowers, with details altered to adapt the fanfiction to the present discussion:
Gowers’ narrative amusingly shows us why reasoning about infinite classes of Turing Machines can be treacherous! 🙂
Comment #127 March 11th, 2016 at 3:47 pm
Gautham Kamath Says: in #122
“Uh you realize that the natural numbers can be constructed purely from the empty set?”
But if nothing exists, not even one thing, who is going to be doing the constructing?
John K Clark
Comment #128 March 11th, 2016 at 3:56 pm
Scott says in #123
“The number of different locations along a tape measure that can be resolved by measurement should be at most 10^33 per centimeter (one per Planck length), but that might or might not correspond to “space being discrete” in any straightforward way.”
Granted, maybe space is continuous and maybe time is too, but if we ever get experimental confirmation that is not the case then my faith that the Real Numbers have a good name would be shaken.
John K Clark
Comment #129 March 11th, 2016 at 4:15 pm
John Clark #128: If you’re willing to accept the “good name” of the integers, then rational numbers are just given by ordered pairs of integers, and real numbers are just given by limits of infinite sequences of rational numbers. Furthermore, the computable reals—that is, the countable subset of reals specifiable by finite computer programs—suffice for essentially any application to physics, even if we don’t talk about the possible “spacetime discreteness” imposed by quantum gravity. The only reason why physicists don’t typically make that restriction is that it’s irrelevant to their purposes. (Physicists famously care less about the metamathematical meaning of an integral than in whether they can evaluate it, and get out a scattering cross-section.)
Comment #130 March 11th, 2016 at 4:58 pm
John K. Clark #128: The “real numbers” is not a very good name. I think the following is about correct:
The names “rational” and “irrational” were used by the old-timers of the day to intentionally insult those who considered numbers that were not fractions. Much later, another generation of old-timers coined the words “real” and “imaginary” to insult those who understood complex arithmetic.
The above reconstruction is purely from memory, and is furthermore possibly compromised by reading “Men of Mathematics” as a kid. But I think it is about right.
Comment #131 March 11th, 2016 at 5:19 pm
DLI #126:
It’s probably not prime. To be more precise, the probability of a random number n being prime is 1/log(n)
See http://mathworld.wolfram.com/PrimeNumberTheorem.html and http://www.johndcook.com/blog/2010/10/06/probability-a-number-is-prime/
So as our number has close to a million digits (you can probably get a better estimate by figuring out the expected number of digits, which should be less than 1m because it can be less but not more), the probability of it being prime is ~1/1,000,000 log 10
or around 1/2302585. (Still more likely than 3*5=7 🙂
But sure, feel free to name it after me.
Comment #132 March 12th, 2016 at 12:04 am
Avi #131:
Actually, I was hoping that it can eventually be proven to be composite, but then people decide to keep calling it Avi’s prime for historical reasons. I guess I have a strange sense of humor though.
Unfortunately your function ‘f’ always takes the first digit of it’s input, so we’ll probably never know the first digit of Avi’s prime. However, if it happened that Graham’s number had a power of two digits AND your ‘f’ had the property that f ^ (n-1) ( has-power-of-two-digits( X ) ) = f ^ n ( has-power-of-two-digits( X ) ), then we would know the last digit of Avi’s number (it would be the same as Graham’s number which is unfortunately 7 and not 2 as I was hoping). Anyway, I don’t see why any of those “facts” have to be true, but they suggest to me that we can look for certain characteristics of repeated application of your ‘f’ function that might yield that Avi’s prime is composite without having to know way too many digits of Grahams number.
Or if there aren’t any good ways to attack the problem with your chosen function maybe there is some function such that the problem still seems interesting and there’s a way to get the solution without running an algorithm on a computer that can’t fit in our universe.
Comment #133 March 12th, 2016 at 12:56 am
Scott Says in #129
” the computable reals—that is, the countable subset of reals specifiable by finite computer programs—suffice for essentially any application to physics”
That is a very good point, and in fact even that might be overkill, all the computable reals may not be necessary for physics. If there is a limit on how many computations the physical universe can perform then a finite subset of the computable reals would be sufficient to do physics. If even the universe doesn’t know how to solve NP-complete problems in polynomial time then physicists will never observe such a phenomena and so don’t need to worry about it or explain it.
John K Clark
Comment #134 March 12th, 2016 at 10:51 am
Denote number systems as follows:
N: Natural numbers,
Z: Integers,
Q: Rational numbers,
R: Real numbers, and
K: Computable reals.
(Is there a standard letter used for the computable reals? I am using K because C is already taken.)
If you are teaching, say, math to CS majors, everyone finds N, Z, and Q to be trivial, but R is pretty slippery. I have always thought that N, Z, and Q are “natural” in the sense that they are likely to occur in one and only one way to any form of intelligence that considers numbers and equations:
1. N follows from counting.
2. Z is the obvious way to deal with equations such as 2 + x = 1.
3. Q is the obvious way to deal with equations such as 2x = 3.
The next stop on this tour is that the equation x * x = 2 shows that Q is “not enough”.
It is not nearly as obvious that the reals R are the “correct” or only reasonable generalization of Q. Certainly Dedikind cuts and Cauchy sequences are reasonable approaches. The fact they they both result in R gives R some status as the way to go. R also results from various concepts of completion in topology.
R provides a nice set of numbers for proving theorems, but it is not clear that it has any use in the “real” world that could not be provided by some other set, such as K. Any opinions on this?
Furthermore, is the usual definition of K natural, or obvious, or correct? Or the only one?
To summarize: you need something beyond N, Z, and Q to do physics; R and K are possibilities. Are they the only ones? In what sense are they “natural” or “correct”?
Comment #135 March 12th, 2016 at 5:15 pm
Raoul Ohio Says in #134:
“To summarize: you need something beyond N, Z, and Q to do physics; R and K are possibilities. Are they the only ones? In what sense are they “natural” or “correct”?”
If a number is not computable, that is to say if even the universe can’t produce it, then a physicist would have no use for it either. And if it’s true that the universe can only make a finite number of computations then the set of numbers that are truly computable is infinitely smaller than the set that Turing called computable.
John K Clark
Comment #136 March 12th, 2016 at 5:32 pm
Raoul, what about complex numbers, C? Very important for quantum physics!
To my way of thinking, I can again see a 3-level hierarchy in the number system.
I think there’s a basic ground-set of mathematical truth that is in some sense, a-priori true (absolute truth), as Scott insists on.
But move up the hierarchy, and inductive content is getting slipped in, which introduces some uncertainty (note: by ‘induction’, I’m not talking about mathematical induction – I’m talking about generalization from evidence in the computer science sense). Deciding which axioms to add is not deductive.
Level 1: Combinatorics (finite math)
Level 2: N,Z,Q
Level 3: R,C
Only level 1 insights are a-priori true in my view. Even facts about N,Z,Q have already slipped in some non-deductive content.
Comment #137 March 12th, 2016 at 7:47 pm
Scott #111: I’m not sure you got the point of my miscomputation example. (On the other hand, it’s possible I’ve misunderstood and am replying to a point you weren’t making.) My point was that, if you do accept the idea of subjective “logical probability”, the probabilities don’t become zero or one just because the numbers involved are small. Of course, if you were talking about probability purely in the ordinary sense, then of course the probability is zero or one.
Comment #138 March 12th, 2016 at 7:53 pm
mjgeddes #136: How are you distinguishing between level 0 and level 1? I mean, there’s an obvious distinction that could be drawn here, where level 1 allows arbitrary statements about N while level 0 only allows Δ_0 statements (in the arithmetic hierarchy), or an appropriate analogue — statements which require only a finite effort to check by brute force. But that’s not what you said; you labeled level 0 as “combinatorics”. Most combinatorics deals with infinite statements, because that is what is interesting! For an example of the most basic sort — for any finite set of size k, the number of subsets is 2^k. Each instance of that is a finite-brute-force-effort statement, but the statement as a whole is not. But as sloon as you allow these sorts of statements, well, now you’re back to talking about N — and Z, and Q. I mean, N itself is quite combinatorial, really. Just thinking additively, it’s the free monoid on one generator, for instance…
Comment #139 March 12th, 2016 at 8:33 pm
Reading the interview with Cerullo, I see a problem. Essentially, it’s the same problem John Clark identified (that “free will” is worthless without the “will” part), but I can be a bit more concrete about it; you said:
“But by hypothesis, the copy wouldn’t behave like you in all situations, and the differences could serve as a sort of empirical certificate that your consciousness hadn’t been cleaved into two, or transferred from one physical substrate to another, or anything like that.”
I don’t think this works, unless the copy is doing something that you wouldn’t (or vice versa, I suppose). So we have to attend to the “will” part of free will after all.
Comment #140 March 12th, 2016 at 8:36 pm
A recent, short, physics-compatible, mathematically modern discussion of the role of complex numbers in modern quantum physics is “Geometry of matrix product states” (JMP 2014, available also as arXiv:1210.7710), by the well-respected researchers Jutho Haegeman, Michaël Mariën, Tobias Osborne, and Frank Verstraete.
Specifically, in this survey’s “Section II.A. Crash course in complex geometry”, the naturality of complex numbers is associated to the threefold compatibility of metric structures $G$, almost complex structures $J$, and symplectic structures $JG$.
In a nutshell, the naturality of real numbers is geometrically associated to the primitive notion of infinitely divisible curves and surfaces; matrix product states then appear as real manifolds that support almost complex structures; real numbers are in this geometric sense more fundamental than complex numbers.
To paraphrase Leopold Kronecker, “God charted the universe with real numbers; complex numbers are the work of man!” Perhaps this explains why mathematicians like Michael Harris can creatively contemplate complex numbers (in comment #64) as a potential “dead end.” 🙂
Comment #141 March 12th, 2016 at 10:27 pm
Others, and Raoul # 134 in particular:
Good comment (#134); it’s of a kind that brings a structure to a discussion.
“R provides a nice set of numbers for proving theorems, but it is not clear that it has any use in the “real” world that could not be provided by some other set, such as K.”
The real purpose of R is that it provides a logical closure. It is for this reason that it finds uses in proving theorems. It becomes “nice,” exactly for the same reason.
It is comforting to know that no matter what mathematical operation you undertake on what (measures of what (actually existing) physical) quantities, if these operand quantities are not restricted to any set less powerful than R, even then, the end result would close either in R or in a higher level synthetic construct like C whose “inputs” have the same cardinality as R anyway.
Find an exception set E to the continuum hypothesis (possibly containing a single member), and most of the crowning glory of R would immediately be stolen by E.
But whether E is found or not, in any case, R would be required for closure (unless E can be shown to supply the closure). And if you replace the R (or E presuming it’s powerful enough) by the K, you would inevitably also lose the logical closure. Just try the $\pi$, to begin with. [[Perfect] Circles may not exist in physical reality, but everyone here would agree that second-degree algebraic equations do [at least in some sense]…]
Logic is indispensable for gaining knowledge to any consciousness—human or alien; it’s an expression of the law of identity. If the world is not in a metaphysical flux, logic must remain the very means of gaining knowledge about it.
Our method of gaining knowledge and therefore the concrete forms of logic that we follow may not be shared by an alien. (For us, it is, primarily, induction, and then, on its basis and as a great device to reduce cognitive load, deduction). But logic in the general, in some form or the other, i.e., as informing a method of identification used by a kind of consciousness, must always remain indispensable to any consciousness, including that of an alien.
Incidentally, I hesitated applying the “the” to the R. R is not defined via any concretely specified operation (the way, say, N or Q are), but via the indefinitely specified requirement that it fulfill the required closure.
No one has “truly” defined R, ever (i.e. defined it as an end result of a specific operation). All that they have ever done is to silently take a piece of paper (or a stretch of sand), draw a (preferably) horizontal line, then looked up and probingly looked into the fellow human’s eyes with a “you know what I mean” implicit in that glance. Communication, it is called; not definition. Communication of a self-evident truth. The definition itself is only ostensive.
Approaches like the Dedekind cut and the Cauchy sequences seem reasonable not because they go towards defining any specific operation that might define R, but because they help explicitize the nature of, and thereby help refine our explicit grasp of, what we already know and mean even otherwise (and what we communicate via those richly meaningful glances at each other).
CS folks perhaps simply want to insert a computer in between the two parties, say with a CCD camera installed on one of the computers capturing that (continuous) horizontal line, and with the Internet transmitting it to another computer. The existence and the intermediacy of computers and the K seems to provide, to them, a form of an assurance which they perhaps cannot find with the notion of the R itself. Physicists (and their desires) are then thrown in merely in the hope to steelman the argument. It seems to work.
But physics, as in contrast to what physicists do, does require logical closures, including to the end-results of every possible quantitative operation.
—
mjgeddes #136, you can always “do” QM without taking the $\Psi$ to be a complex-valued function. The calculations would carry exactly the same power. It’s just that you would have to be careful to introduce the necessary coupling at every stage. … Sort of like how clerk Maxwell wrote very long set of scalar equations which now “reduce” to a set of 4 vector equations (or is it 5?) [Yes, someone could also reduce each lengthy comment on each blog to 140 or fewer number of characters, later on.]
More than enough, already… Goodbye.
Best,
–Ajit
PS: Physics also requires units, or physical dimensions, BTW.
[E&OE]
Comment #142 March 13th, 2016 at 12:20 am
Ben Standeven #129: I can’t reply to the objection because I don’t even understand it. Where I wrote:
But by hypothesis, the copy wouldn’t behave like you in all situations…
you could equivalently rephrase it:
But by hypothesis, the copy wouldn’t behave as you would in all situations…
I.e., if we think of “you” as a function mapping possible past histories onto a probability distribution over what you do next, you and the approximate copy would be associated with appreciably different functions. You wouldn’t behave differently merely because you received different stimuli; there would be some stimulus S such that you behaved differently even if you both received S.
Comment #143 March 13th, 2016 at 5:04 pm
Scott wrote in 142:
“if we think of “you” as a function mapping possible past histories onto a probability distribution over what you do next, you and the approximate copy would be associated with appreciably different functions.”
It’s true that small changes can have huge consequences but trying to define ”you” by invoking the future is like pushing on a string because we’re talking about subjectivity here and nobody knows what the future will be, we only know about the past. So I think the only definition of “you” is a iterative one, today “you” is the person who remembers being “you” yesterday.
As for free will, the only definition of it that is not gibberish is “the inability to always know what you’re going next until you do it even in a stable environment”. And yes that means a pocket calculator has free will because it doesn’t know how much 2+2 is until it preformed the calculation. And it also means that if philosophers never use the term “free will” again their subject will not in any way be harmed.
John K Clark
Comment #144 March 13th, 2016 at 6:47 pm
When I discussed N, Z, Q, R, and K above, I did not include C, the complex numbers, because I figured they were just a trivial two dimensional linear space over R.
But is that the whole story? Let K and L denote the computable numbers in R and in C, respectively.
What is the relation between L and K^2 (ordered pairs in K)? My first guess is that they are isomorphic. But are they?
More generally, is there any uncountable system whose computable elements are not isomorphic to a tuple in K?
Comment #145 March 13th, 2016 at 7:52 pm
Raoul: Yes, they are the same thing. (As in, not merely isomorphic in some abstract sense, but rather, a complex number is computable iff its real and imaginary components are computable.) I mean, OK, I think that’s more by definition rather than by substantive reasoning… but what sensible definition could you possibly make such that that doesn’t hold?
Comment #146 March 13th, 2016 at 10:38 pm
This trivial linear relation becomes very much less trivial, and very much less linear, first when complex numbers are extended to complex functions, then when complex functions are extended to complex geometric structures.
Fields Medalist Shing-Tung Yau’s “Perspectives on geometric analysis” (Surveys in Differential Geometry, Volume X, 2006, available as arXiv:math/0602363v2) is a panoramic survey of these complex extensions.
Searching Yau’s survey for the word “complex” is a wonder-inducing exercise — and a humility-inducing exercise too — for mathematicians, scientists, and engineers alike! 🙂
Conclusion Nowadays, quantum simulation software algorithms are grounded in an expanding mathematical universe of complex structures whose geometric properties are very far from fully understood; hence it is natural to presume that these properties are very far from fully exploited.
Outlook The rich ground of open complex mysteries helps us to appreciate how it has happened, that during recent decades, the capabilities of quantum simulations have advanced with a transformative rapidity that was unforeseen by even the most ardent “algorithm supremacists” (see #79) of the 20th century.
That is why, even today, there is no very obvious end in sight to further advances in algorithmic quantum simulations. Good!
Comment #147 March 13th, 2016 at 11:05 pm
Sniffnoy: I think that you are probably correct, but it might be worthwhile to nail down the details. I propose three things that are might be worth thinking about.
1. This is a long shot. Think up some aspect of complex analysis that has nothing to do with real analysis (oxymoron?) and use this to define a number z = x + yi in L. Maybe some kind of “feigenbaum constant”, but defined in terms of maximum modulus, or Swartz reflection, or classification of holomorphic functions.
PROBABLY you can compute x and y by trading each calculation involving a complex number in for about four calculations with real numbers, and thus x and y are in K. Here I use the interpretation that complex math with z is just real math with the ordered pair (x,y), but with funny rules. This suggests that a number z in L is an ordered pair of numbers in K, and it seems pretty hard to get around this approach for embedding L into K \times K. Is this argument ironclad? Can anyone come up with a clever complex concept that cannot be traded in for reals in a constructable fashion?
2. What about the other direction? If x and y are unrelated numbers in K, can you turn that fact into a construction (using only complex math) that produces the number z = x + yi in L? It is not obvious that you can always do this.
3. Maybe “using only complex math” is not a reasonable criteria for membership in L. For example, one could define a set of numbers computable using only a certain set of operations (say, complex arithmetic), and another set computable using any algebra. Thus there might be different classes of computable numbers.
Comment #148 March 14th, 2016 at 11:57 am
In regard to the chain of inclusions of (#146)
• N: Natural numbers are included in …
• Z: Integers, which are included in …
• Q: Rational numbers, which are included in …
• K: Computable reals, which are included in …
• R: Real numbers …
Startlingly, this chain breaks at the complex numbers, in the crucial sense that real functions are not fully included in the set of (holomorphic) complex functions, and real geometric structures are not fully included in the set of (holomorphic) complex structures.
The geometric reasons are summarized in Wikipedia’s article “Almost complex manifolds”, see in particular the section “Integrable almost complex structures“.
Further reading Earlier this week, Jacob Bridgeman and Christopher Chubb posted to the arxiv a student-friendly set of notes amusingly titled “Hand-waving and Interpretive Dance: An Introductory Course on Tensor Networks” (2016, arXiv:1603.03039); these notes illuminate a literature that has grown so vast that no single course can encompass it.
Implication For reasons that in theory are not well understood, but in practice are eagerly exploited by algorithm supremacists, holomorphic structures are proving to be terrifically effective at compactly encoding information about high-dimension datasets and dynamical processes.
These burgeoning algorithmic capabilities are giving quantum supremacists plenty to race against! 🙂
Comment #149 March 14th, 2016 at 6:22 pm
John Sidles: In regard to the “chain breaking” when going from R to C, that is only because in complex analysis 100% of the attention is given to analytic functions. This direction is astoundingly fruitful, leading to a vast store of knowledge, much of it compiled in the 1800’s.
But if you wanted to, you could work with complex functions every bit as ugly as those studied in real analysis — it just does not buy you much.
Traditionally; “real analysis is about ugly functions” and “complex analysis is about beautiful functions” (is that an old saying, or did I invent that?). On the one hand, the beauty of analytic functions does NOT live in the real functions. On the other hand, real analysis is largely devoted to integration and measure theory, and these topics must be robust in the face of the worst examples anyone can dream up. Thus nowhere differentiable functions are a valid concern in real analysis, but complex analysis is all about everywhere infinitely differentiable functions — because that is where the powerful theorems lie.
Comment #150 March 14th, 2016 at 11:49 pm
Raoul Ohio (#149), please let me respectfully submit that your comment might reasonably be amended as follows:
This picture builds on Carlton Caves’ on-line notes “Completely positive maps, positive maps, and the Lindblad form” (2000), which describe a world in which the nowhere-differentiable unraveling of complex dynamical trajectories is crucial to efficient quantum dynamical simulations.
A particularly attractive virtue (as it seems to me) of Caves’ stochastic recipes — which formalize and generalize the foundational notion of unraveling that was introduced by Howard Carmichael — is that Caves’ recipes explicitly satisfy Rudolf Peierls’ criterion for thermodynamic sensibility (“Some simple remarks on the basis of transport theory”, 1974):
Conclusion The complex racehorses being bred by algorithm supremacists don’t run smoothly, but they sure run fast! 🙂
Comment #151 March 14th, 2016 at 11:56 pm
Raoul #144: As far as I know, L is just defined as K^2 (where R^2 is identified with C in the usual way). I’m not quite sure how else you would define it, actually.
Comment #152 March 15th, 2016 at 7:06 pm
@Scott, 142:
The trouble with looking at probability distributions over a person’s behavior is that to observe them, we need to put the person in the same scenario multiple times. And to do this, we either need to make multiple copies of the person, or do something essentially equivalent, such as wiping their memory between trials; otherwise the person’s history won’t be the same from one trial to the next.
Comment #153 March 15th, 2016 at 7:32 pm
If we take the complete algebraic closure of the p-adic numbers, we get the complex p-adic numbers. (https://en.wikipedia.org/wiki/P-adic_number#Metric_completions_and_algebraic_closures)
These are an algebraic closed field with the same cardinal as the reals, so they are field-isomorphic to the ordinary complex numbers (of course the isomorphism does not preserve the norm). Since the isomorphism depends on the axiom of choice, it presumably isn’t computable. So a computable p-adic complex number might not correspond to a computable complex number. But I guess that, since the correspondence depends on the choice of isomorphism, this doesn’t really pick a specific complex number at all.
Comment #154 March 15th, 2016 at 7:57 pm
Come to think of it, if the mapping is based on a choice function, it probably will send each computable p-adic number to a computable complex number; one simply can’t compute which complex number.
Comment #155 March 16th, 2016 at 3:59 am
On this topic of 1+1 = 2, I’m never sure whether the question is the shortest proof or the longest.
Whenever you have more than one binary operation, you get to choose which one is meant by its omission. These days it’s multiplication. But one could imagine that in the early days of Roman numerals it was addition.
In those days the following one-line proof would suffice:
II = II
Since it’s hard to see how modern algebra could shorten this proof, one imagines the goal must be the longest proof.
But with what probability can we be sure of 1 + 1 = 2?
Well, what are the alternatives? What are the odds that 1 + 1 = 1, or 1 + 1 = 3? Surely the same as the odds that 0 = 1.
Ah, but perhaps there is a small but finite chance that 1 + 1 = 2.0000001 or 1.999999999.
But in that case we’d have two integers that didn’t sum to an integer.
The odds of that unlikely event are surely greater than the odds that 1 + 1 is either 2.0000001 or 1.999999999.
Is Austin’s Philosophy Department warming to this material yet?
Comment #156 March 16th, 2016 at 9:33 am
Vaughan #155: For the record, I was the one defending the position above that no known sensible theory assigns Pr[1+1=3] a nonzero value! (And more concretely, I offered to bet everything I have on 1+1=2, though I wouldn’t bet everything on harder arithmetical questions even if I felt confident about the answer—I’ve made too many mistakes!)
What makes this tricky is that I do think there are interesting research questions around how to formalize the intuition that, say, the BB(1000)th bit of π is equally likely to be 0 or 1 as far as any human can now say. But clearly, the “only” difference between that question and the 1+1=2 question is one of computational complexity—so, this points to the need for a workable generalization of probability theory, which reduces to ordinary probability theory in the limit of infinite computing resources.
I haven’t yet talked to anyone in Austin’s philosophy department, but am very open to that! I enjoyed interacting with some of the philosophers at MIT, like Alex Byrne and Agustin Rayo.
Comment #157 March 16th, 2016 at 11:18 am
Scott #156: News related to probability of bits or digits (not of pi, but of prime numbers) appeared yesterday:
http://phys.org/news/2016-03-mathematician-pair-prime-random-thought.html
The gist is that the last digits {1,3,7,9} of the sequence of prime numbers is measured to be far from random. No mention is made of how this goes with bases other than 10.
We often hear of the largest known prime. In the other direction, what is the smallest number not known to be prime or not? That is presumably a moving target, so a better question is: how far out have the numbers been sorted into prime or not prime, as of today? The time history of this would also be interesting. Exponential growth? Possibly the NSA knows more than anyone, and are likely to not be talking!
Comment #158 March 16th, 2016 at 3:13 pm
Raoul: Yes, it works (or supposedly works — it’s not proved) for any modulus; the actual paper is here. Note that the various possibilities are equidistributed in the long run, it’s just that the error term is larger than expected!
Comment #159 March 17th, 2016 at 8:37 am
Sniffnoy #158,
It seems like it is more accurate to say that the second order terms are different and larger than one would expect, since they aren’t just big-O terms but terms we can write down explicitly.
Comment #160 March 17th, 2016 at 10:54 pm
I see, so when terms have lower bounds or can be written down explicitly, it’s no longer appropriate to call them “error terms”? Or what?
Comment #161 March 18th, 2016 at 5:37 pm
Further hybridizing the racehorses of algorithm supremacists and quantum supremacists (2015, arXiv:1512.05709v1):
These findings are plausibly compatible with an increasingly hybridized STEM-world, in which QED-mediated systems are (seemingly) efficiently simulable; yet general quantum dynamical systems are (seemingly) not efficiently simulable; moreover some (seemingly) natural condensed-matter questions are not even mathematically decidable.
So hurrah! for pragmatic algorithm supremacy! And hurrah too! for principled quantum supremacy! And a third hurrah! For … uh … Kurt Gödel and a measure of cognitive humility? 🙂
Comment #162 March 19th, 2016 at 3:53 pm
Sniffnoy #160,
Yeah, I think most people would call those lower order terms. Although that’s not always standard. At least to me, “error term” in analytic number theory gives mind to terms which are big-O of something, whereas lower order terms have actual constants out front.
Comment #163 March 20th, 2016 at 12:37 am
OK, that makes sense.
Comment #164 March 20th, 2016 at 3:16 am
Hi Scott,
in his recent talks, Boaz has been making the case for the desirability of a theory able to deal with questions of the form “what is the probability that the 2^100-th digit of pi is 1?”
He views his recent work on integrality gaps for sum-of-squares relaxations as something that would eventually fit into such a theory.
The slogan is that this theory would be to Bayesian probability as the “classical” theory of pseudorandomness is to frequentist probability. More here: http://windowsontheory.org/2015/10/01/a-different-type-of-pseudo/
Comment #165 April 7th, 2016 at 5:57 am
Just a fantasy about measurement. Suppose that we are measuring spin of a particle. It passes by a large body of spins and due to spin-spin interaction affect large body of spins that having much larger coupling constant between particles in the body than to the measured particle. The affected spins on the surface of body are weakly entangled now (or they have weakly correlated state). In the next moment, this entanglement due to coupling in the body propagates to the volume. But now few weakly entangled particles are affecting single unentangled particle in the second layer of the body. So the second layer is more entangled (correlated) than the first one. This entanglement propagates to the depth of the body, until the whole body is entangled. This is caricature, since thermal fluctuations counteract this process, and I just want illustrate what would satisfy me in terms of theory. But it shows that each material has susceptibility to entanglement and classical measurement device is probably close to phase transition in terms of entanglement, otherwise weak measurements will not propagate and will be either suppressed by the bulk state in the ordered phase, or dissipate in disordered phase. That what one would call mesoscopic effects, at least in solid state.
Comment #166 May 1st, 2016 at 1:47 pm
I just realized that my whole f(f(f …(Graham’s number) construction is unneeded. You can just talk about the first million digits of Graham’s number, if it were proven to be prime.