We also know that there are things that a quantum computer can do that an equivalent classical machine simply cannot do in reasonable time.
I thought it was still an open question whether there are computations that a classical computer is necessarily slower at than a quantum computer. From Aaronson's Philosophy/Comp-Complexity paper, p.35 :
More generally, that quantum computers can solve certain problems superpolynomially faster than classical computers is not a theorem, but a (profound, plausible) conjecture. [49] [50]
Footnote 49: A formal version of this conjecture is BPP =/= BQP, where BPP (Bounded-Error Probabilistic Polynomial-Time) and BQP (Bounded-Error Quantum Polynomial-Time) are the classes of problems efficiently solvable by classical randomized algorithms and quantum algorithms respectively. ... any proof of the BPP =/= BQP conjecture would be considered almost as great a breakthrough as P =/= NP.
Footnote 50: Complicating matters, there are quantum algorithms that provably achieve exponential speedups over any classical algorithm: one example is Simon’s algorithm [119], an important predecessor of Shor’s algorithm. However, all such algorithms are formulated in the “black-box model” (see Beals et al. [23]), where the resource to be minimized is the number of queries that an algorithm makes to a hypothetical black box. Because it is relatively easy to analyze,the black-box model is a crucial source of insights about what might be true in the conventional Turing machine model. However, it is also known that the black-box model sometimes misleads us about the “real” situation. As a famous example, the complexity classes IP and PSPACE are equal [115], despite the existence of a black box that separates them (see Fortnow [56] for discussion).
Yeah, so this is a good point. The separation given by Grover's algorithm is essentially a blackbox model. And Shore's algorithm being better depends on the claim that factoring is not in P, which is a claim strictly stronger than P != NP (and a claim which is doubted by a lot more people. Henry Cohn for example says there's no good reason to think that factoring is not in P.) So yes, this is under the black box. system.
Let P(chr) = the probability that the statements attributed to Jesus of Nazareth and Paul of Tarsus regarding salvation and the afterlife are factually mostly correct; and let U(C) be the utility of action C, where C is in {Christianity, Islam, Judaism, atheism}.
Two of the key criticisms of Pascal's wager are that
If, however, P(chr) is not infinitessimal, and U(Christianity) is merely very large, these counter-arguments fail.
Many poor arguments have been made that P(chr) > .1. But as far as I know, no one has ever made the best argument in favor of Christianity:
If you accept the simulation argument, then P(sim) > .99.
If you look at the fraction of computing power used for entertainment, I don't know what it is, but the top 100 supercomputer list for June 2011 lists a total of 4,531,940 cores in the top 100 supercomputers in the world; versus (rough guess) a billion personal computers and video game consoles, and a similar number of ordinary computers used at work. It would be reasonable to set p(ent|sim) = .5.
If you set P(ego|ent, sim) according to the fraction of entertainment simulations in which the person playing the game has an avatar in the game, then P(ego|ent, sim) is large. I originally set this at p > .99, but am now setting it to p = .5 in response to Jack's comment below.
We notice there are no obviously immortal world leaders on Earth (but see vi21maobk9vp's comment below). If we therefore limit the possible avatars that our simulator God is using on Earth to the major monotheistic religions of Christianity, Islam, and Judaism, and consider them all equiprobable; plus a 25% chance that this God is jumping from one avatar to another, or chose to reveal Himself via Jesus but then Paul screwed everything up, or some other minority position; then p(chr0|ego, ent, sim, Earth) = .25.
P(follow-thru) is difficult to estimate; I will set it somewhat arbitrarily as .1. Given our observations of game-players here on Earth, it is not independent of p(ego), as players of self-glorifying games are likely to be young adolescent males, and so are people who enjoy burning insects with magnifying glasses.
We now have p(chr) > .99 x .5 x .5 x .25 x .1 = .0061875. As stipulated, your afterlife accounts for at least 99% of your utility if follow-thru (and hence chr) is true. If we suppose that the length of time for which God rewards us in Heaven or torments us in Hell has an exponential distribution, and we are considering only the part of that distribution where >= 99% of your utility is in the afterlife, then almost certainly p(chr) * U(Christianity | chr) > (1-p(chr)) * U(atheism | not(chr)). It now appears we should accept Pascal's wager.
(The expected utilities for Christianity and Islam are similar, and this argument gives no reason for favoring one over the other. That is of only minor interest to me unless I accept the wager. The important point is that they both will have expected utilities similar to, and possibly exceeding, that of atheism.)
You can argue with any of the individual numbers above. But you would have to make pretty big changes to make p(chr)(U(Christianity|chr)) negligible in your utility calculation.
(IMHO, voting this article up should indicate it passed the threshold, "That's an interesting observation that contributes to the discussion", not, "Omigod you're right, I am going out to get baptized RIGHT NOW!".)