2^n is exponential, but 2^50 is finite
Unrelated Update (Oct. 23) I still feel bad that there was no time for public questions at my “Theoretically Speaking” talk in Berkeley, and also that the lecture hall was too small to accomodate a large fraction of the people who showed up. So, if you’re someone who came there wanting to ask me something, go ahead and ask in the comments of this post.
During my whirlwind tour of the Bay Area, questions started pouring in about a preprint from a group mostly at IBM Yorktown Heights, entitled Breaking the 49-Qubit Barrier in the Simulation of Quantum Circuits. In particular, does this paper make a mockery of everything the upcoming quantum supremacy experiments will try to achieve, and all the theorems about them that we’ve proved?
Following my usual practice, let me paste the abstract here, so that we have the authors’ words in front of us, rather than what a friend of a friend said a popular article reported might have been in the paper.
With the current rate of progress in quantum computing technologies, 50-qubit systems will soon become a reality. To assess, refine and advance the design and control of these devices, one needs a means to test and evaluate their fidelity. This in turn requires the capability of computing ideal quantum state amplitudes for devices of such sizes and larger. In this study, we present a new approach for this task that significantly extends the boundaries of what can be classically computed. We demonstrate our method by presenting results obtained from a calculation of the complete set of output amplitudes of a universal random circuit with depth 27 in a 2D lattice of 7 × 7 qubits. We further present results obtained by calculating an arbitrarily selected slice of 237 amplitudes of a universal random circuit with depth 23 in a 2D lattice of 8×7 qubits. Such calculations were previously thought to be impossible due to impracticable memory requirements. Using the methods presented in this paper, the above simulations required 4.5 and 3.0 TB of memory, respectively, to store calculations, which is well within the limits of existing classical computers.
This is an excellent paper, which sets a new record for the classical simulation of generic quantum circuits; I congratulate the authors for it. Now, though, I want you to take a deep breath and repeat after me:
This paper does not undercut the rationale for quantum supremacy experiments. The truth, ironically, is almost the opposite: it being possible to simulate 49-qubit circuits using a classical computer is a precondition for Google’s planned quantum supremacy experiment, because it’s the only way we know to check such an experiment’s results! The goal, with sampling-based quantum supremacy, was always to target the “sweet spot,” which we estimated at around 50 qubits, where classical simulation is still possible, but it’s clearly orders of magnitude more expensive than doing the experiment itself. If you like, the goal is to get as far as you can up the mountain of exponentiality, conditioned on people still being able to see you from the base. Why? Because you can. Because it’s there. Because it challenges those who think quantum computing will never scale: explain this, punks! But there’s no point unless you can verify the result.
Related to that, the paper does not refute any prediction I made, by doing anything I claimed was impossible. On the contrary (if you must know), the paper confirms something that I predicted would be possible. People said: “40 qubits is the practical limit of what you can simulate, so there’s no point in Google or anyone else doing a supremacy experiment with 49 qubits, since they can never verify the results.” I would shrug and say something like: “eh, if you can do 40 qubits, then I’m sure you can do 50. It’s only a thousand times harder!”
So, how does the paper get up to 50 qubits? A lot of computing power and a lot of clever tricks, one of which (the irony thickens…) came from a paper that I recently coauthored with Lijie Chen: Complexity-Theoretic Foundations of Quantum Supremacy Experiments. Lijie and I were interested in the question: what’s the best way to simulate a quantum circuit with n qubits and m gates? We noticed that there’s a time/space tradeoff here: you could just store the entire amplitude vector in memory and update, which would take exp(n) memory but also “only” about exp(n) time. Or you could compute the amplitudes you cared about via Feynman sums (as in the proof of BQP⊆PSPACE), which takes only linear memory, but exp(m) time. If you imagine, let’s say, n=50 and m=1000, then exp(n) might be practical if you’re IBM or Google, but exp(m) is certainly not.
So then we raised the question: could one get the best of both worlds? That is, could one simulate such a quantum circuit using both linear memory and exp(n) time? And we showed that this is almost possible: we gave an algorithm that uses linear memory and dO(n) time, where d is the circuit depth. Furthermore, the more memory it has available, the faster our algorithm will run—until, in the limit of exponential memory, it just becomes the “store the whole amplitude vector” algorithm mentioned above. I’m not sure why this algorithm wasn’t discovered earlier, especially since it basically just amounts to Savitch’s Theorem from complexity theory. In any case, though, the IBM group used this idea among others to take full advantage of the RAM it had available.
Let me make one final remark: this little episode perfectly illustrates why theoretical computer scientists like to talk about polynomial vs. exponential rather than specific numbers. If you keep your eyes on the asymptotic fundamentals, rather than every factor of 10 or 1000, then you’re not constantly shocked by events, like a dog turning its head for every passing squirrel. Before you could simulate 40 qubits, now you can simulate 50. Maybe with more cleverness you could get to 60 or even 70. But … dude. The problem is still exponential time.
We saw the same “SQUIRREL! SQUIRREL!” reaction with the people who claimed that the wonderful paper by Clifford and Clifford had undercut the rationale for BosonSampling experiments, by showing how to solve the problem in “merely” ~2n time rather than ~mn, where n is the number of photons and m is the number of modes. Of course, Arkhipov and I had never claimed more than ~2n hardness for the problem, and Clifford and Clifford’s important result had justified our conservatism on that point, but, y’know … SQUIRREL!
More broadly, it seems to me that this dynamic constantly occurs in the applied cryptography world. OMIGOD a 128-bit hash function has been broken! Big news! OMIGOD a new, harder hash function has been designed! Bigger news! OMIGOD OMIGOD OMIGOD the new one was broken too!! All of it fully predictable once you realize that we’re on the shores of an exponentially hard problem, and for some reason, refusing to go far enough out into the sea (i.e., pick large enough security parameters) that none of this back-and-forth would happen.
I apologize, sincerely, if I come off as too testy in this post. No doubt it’s entirely the fault of a cognitive defect on my end, wherein ten separate people asking me about something get treated by my brain like a single person who still doesn’t get it even after I’ve explained it ten times.
Follow
Comment #1 October 22nd, 2017 at 7:56 pm
Another crucial aspect which should have been mentioned in the popular science papers is that the IBM method has scaling that is exponential in the circuit depth. Precisely to avoid simulation strategies like this, in our (i.e. Google) supremacy proposal paper we set the circuit depth target at 40 cycles. The IBM paper discusses simulating a circuit with 23 cycles. I do not think they will be able to get to 40 cycles. Thus, the new IBM paper does not seem to pose a threat to our supremacy experiment. In fact, we never thought that the simulation was classically intractable at 49 qubits and depth 23.
Comment #2 October 22nd, 2017 at 8:00 pm
By depth 23 I really meant depth 27 (in the IBM paper). But my point stands nonetheless.
Comment #3 October 22nd, 2017 at 8:50 pm
Ryan: Thanks! But from the standpoint of my and Lijie’s algorithm, the scaling of the running time with circuit depth depends entirely on how many layers of recursion you use (which in turn determines how much running time you need).
With no recursion, memory usage is ~2n, but dependence on depth is only linear. Then, a rule of thumb is that each time you want to use half again as much memory, you can multiply the running time by a factor of d—all the way to the opposite extreme, where you’re using linear memory and ~dn time.
Comment #4 October 22nd, 2017 at 8:59 pm
> All of it fully predictable once you realize that we’re on the shores of an exponentially hard problem, and for some reason, refusing to go far enough out into the sea (i.e., pick large enough key sizes) that none of this back-and-forth would happen.
To defend cryptographers for a minute: the overheads of ciphers with large key sizes are pretty noticeable! For an extreme instance, passively-powered chips of the types used in contactless credit cards often only come with a few kb of memory, and would cost a lot more with bigger memory.
Even with beefier hardware, if you have a server with a saturated modern Internet uplink (say 10 gigabits), encrypting everything with AES will peg one of its cores: https://calomel.org/aesni_ssl_performance.html Granted, most people will run out of disk well before hitting 10 gbps, but throw in a couple more constant factors and people might start having real problems with the overhead.
(And the last thing you want is a bunch of engineers wondering whether the performance hit for encryption is really worth it…)
Comment #5 October 22nd, 2017 at 9:42 pm
I don’t think your statements about cryptography are correct. The only time crypto changed because of brute force attacks was the transition from 64 bits to 128. EFF had to do a publicity stunt to convince people that brute force had caught up.
If you expect Moore’s law to keep going with a doubling time of 1 year, then it should take 64 years from breaking 64 bit crypto to breaking 128, and we’re nowhere near that.
I believe that the NSA believes 128 bit crypto to be safe from classical attacks for decades (a classified number thereof), even taking into account future discoveries of flaws in existing cryptosystems. The only reason it advocates 256 bit crypto is fear of quantum computers.
Most crypto news is attacks that improve on brute force. Usually they improve only by a few bits and they get a lot more coverage than they should, but “Attacks only get better.” Of course, you should also expect some such attacks, which is why NSA budgets a (classified) margin for them. Sometimes they exceed that budget and really break the system, far beyond brute force, but usually that happens after a series of minor attacks.
Comment #6 October 22nd, 2017 at 11:40 pm
Douglas #5: I attended a talk by Adi Shamir where he presented “breaks” of one seriously-proposed cryptosystem after another. Yes, a large part of the issue was exactly what you’re talking about: “breaks” that weren’t actually breaks, but just tiny improvements over brute-force search that are then arbitrarily defined to be “breaks.” But often enough, the issue indeed seemed to be that the key sizes were too small. When questioned about this, Adi joked (or was it a joke?) that crypto researchers have to propose systems with dangerously small key sizes, since otherwise virtually everything would be unbreakable, and the researchers would have nothing further to write papers about and would lose their jobs. He also insisted, repeatedly, on the ground rule that once a system is “broken” by his lights, we don’t discuss trivial changes to the system that would’ve defeated the break: the system is broken, end of story, and any modification to it is a new system! The whole attitude seemed almost gleefully atheoretical, and made happy that most of the time I only need to worry about asymptotics and general families of problems.
Comment #7 October 23rd, 2017 at 12:00 am
Hi Scott,
I’m not an expert on practical cryptography, but I strongly disagree with your characterization of the breaking of cryptographic hash functions as totally predictable. Cryptographic standards typically come with claimed security of at least 2^{100} (with the exception of DES, whose key size was intentionally and more-or-less transparently kept small enough to allow brute-force attacks). For the gold standard, AES, it’s big news when people find a way to use 2^{40} memory to break AES-256 in time 2^{254.27}, compared to the expected brute-force running time of 2^{255} (https://link.springer.com/chapter/10.1007/978-3-319-19962-7_3). If AES is actually as strong as this, then we’re in the neighborhood of actual physical barriers to computation.
So, if current crypto standards are broken, it will be because of a design flaw, not because of Moore’s law, and not because we chose key sizes that were already just on the edge of breakable.
Comment #8 October 23rd, 2017 at 12:24 am
Noah #7: To clarify, I don’t claim that it’s predictable which cryptosystems will get broken when. Indeed, this is exactly the sort of event that I described in the post as being in the “SQUIRREL! SQUIRREL!” category.
The claim is just that, if the key sizes are anywhere within the range of human civilization—which there’s no very principled reason for them to be, only more-or-less contingent reasons (“we wanted more efficiency for smart card applications” / “we needed to be standards-compliant” / “the NSA demanded a backdoor”)—then it’s predictable that at least some of the cryptosystems will be broken, and that when that happens, many people will wrongly imagine that there was some deep conceptual flaw with the cryptosystem, rather than merely that n was too small.
Comment #9 October 23rd, 2017 at 5:50 am
Actually, none of the modern crypto systems (AES-128, AES-256, RSA2048, Ed25519) are “broken” in the sense that they can be decrypted using any reasonable hardware in any reasonable time.
Heck, even 3DES is unbroken and it’s around 30 years old. Though we are getting close to a feasible brute-force for it.
Please note, that in crypto research “break” means _any_ improvement over brute-force search. So an improvement that brings down complexity from 2^256 to 2^200 would be considered a major break but it won’t realistically matter for anything.
Comment #10 October 23rd, 2017 at 7:45 am
Ryan your comment about circuit depth reminds me of the constantly challenging level of non-standard terminology that confuses a great many “general” journalists and more importantly the ‘general” reader and potential user of quantum computing applications, and at whom the IBM research paper was aimed when it was picked up in the press last week. I still have dozens of questions around “why bother with quantum computing if we can classically simulate this level of advance”. One thing I hope will coming to happen is the slow but steady march towards broader understanding, and your point about circuit depth will help add a degree of perspective.
Scott – really nice piece. Thank you for posting. It now means I dont have to write up my own responses but just point to yours (again). I suspect that your blog will receive more ‘feedback’ from cryptographers though, which I think misses the point sadly. “Squirrel Squirrel” indeed 🙂
Comment #11 October 23rd, 2017 at 10:08 am
The new developments regarding 2^n algorithms for BosonSampling and better simulations for quantum circuits all the way to 50 qubits are quite impressive. I agree with Scott that that these developments do not undermine the “quantum supremacy” program.
In my view, the major line to cross would be of creating high quality encoded qubits. (For all we know, this would require controlling 100 qubits or so or some anyonic methods.) However, a convincing evidence for quantum supremacy would be great as well and a major step.
However, I don’t share the sentiment against finite numbers 🙂 . If without quantum error correcting you will not be able to control quantum circuits with X qubits and quantum error correcting (of the needed quality) requires good-quality control of Y qubits, then if X=20 and Y=100, the fact that 20 is smaller than 100 means that you are in big trouble. If X=500 and Y=100 then you are in good shape.
Of course, the reason for why X is considerably smaller than Y may come from asymptotic analysis of computational complexity nature.
Comment #12 October 23rd, 2017 at 10:39 am
Hi Scott,
I feel like the situation with boson sampling is a bit different in that, as far as I know, there’s currently no clear path to scalability of boson sampling experiments to n photons (other than implementing the BS algorithm on a fault-tolerant quantum computer, or other significant changes in experimental design). Without fault tolerance, the runtime of a realistic quantum experiment is also exponential in n, just because the probability that all (or almost all) photons survive is exponentially small in n. So you can’t just increase n to outperform a classical competitor; you also need to improve some other parameters, like loss rates, correspondingly.
So then the question is whether there exists any experimentally accessible range of parameters which is still hard to simulate classically, and the recent classical BS simulation algorithms substantially increase the level of experimental challenge.
For supremacy proposals based within the standard quantum circuit picture, on the other hand, we already have good arguments (like the whole theory of quantum fault-tolerance!) that we should be able to take n -> infinity. So even if someone comes up with a simulation algorithm that can cope with depth-50 circuits on 49 qubits (say) using a supercomputer, at some point they aren’t going to be able to keep up (or else BPP=BQP…).
Comment #13 October 23rd, 2017 at 12:08 pm
I wonder if this can be circumvented. If we had a quantum computer that could factor, say, 2048-bit integers, then we could test this without needing a classical computer that can do the same. Are there problems (other than factoring) that could yield verifiable quantum supremacy experiments without needing powerful classical computers?
Comment #14 October 23rd, 2017 at 12:17 pm
Neither increasing beyond 50 either the qubit count which one may classically simulate, nor the qubit count in a hopefully-BQP-efficient machine, would provide much better evidence of quantum supremacy than just 50.
At 50, it is easy enough to sample the speeds of each device while it runs the same algorithm with the same input, across many runs of each device, and detect a result of significance using everyday statistical hypothesis testing.
Comment #15 October 23rd, 2017 at 1:50 pm
I disagree with your characterization of applied cryptography. Firstly, using symmetric algorithms with sufficient key sizes to withstand quantum attack is hardly a novel concept: that’s why 256 bit keys exist. AES/Rijndael had them almost two decades ago. That doesn’t mean cryptanalysis is a pointless exercise, because you don’t know how catastrophic your break is going to be when you start. Also, cryptanalysis builds on top of previous results and insights: attacks never get worse, they only get better. A 256 bit symmetric key may save you from a direct quantum search, but it won’t save you from a bad key schedule or linear cryptanalysis or differential cryptanalysis or $INSERT_FAVORITE_ANALYTIC_TECHNIQUE_HERE. It certainly doesn’t save you from things that don’t attack the mathematical primitive, like side-channel attacks, fault attacks, et cetera.
For asymmetric algorithms, achieving PQ security with algorithms designed for classical attackers simply by increasing key size is far more wildly impractical than you seem to suggest in the commentary. For more details, I suggest the 2017 paper “Post-quantum RSA” by djb et al. PQ cryptanalysis is still incredibly useful because problems turn out to be less hard than we thought they would be (which I think speaks to your general point about not worrying about finite improvements): for example, going from IDH to SIDH.
As presented, if I read your comments charitably, it looks like you’re chiding people for publishing negative results and pretending key size is some kind of magic wand.
(Finally, I’d suggest a different example, because hash functions don’t take keys.)
Comment #16 October 23rd, 2017 at 2:44 pm
Everyone: I’m actually delighted to learn that my impression of applied crypto seems to have been off-base. But does this really mean that I’ll never be reading again about a ‘break’ of a cryptosystem for which the underlying problem retains its exponential hardness? I.e., that from now on, everyone will be choosing sufficiently large n’s (by which I mean: key size, input size, or whatever other name you give to the log of the size of the space someone searches if they’re trying to break your system)? Awesome!! 🙂
Comment #17 October 23rd, 2017 at 2:59 pm
tas #13: Yes, there are other interesting problems that QCs can solve that belong to NP, such as discrete log, membership in matrix groups, elliptic curve problems, other things from number theory and group theory.
And then there’s the fact that, if you use a quantum computer to simulate a quantum system (say, a large molecule), then even if the problem isn’t in NP, you can verify the computer’s predictions by testing them against the system itself.
Finally, there are the breakthroughs over the last decade on verifiable quantum computation—breakthroughs in whose birth this blog played a small part. Basically, the upshot of this work is that any quantum computer, runing any algorithm whatsoever, can prove its results to a classical skeptic, provided that either
(1) the skeptic is willing to send single, unentangled qubits to the QC (prepared in states known only to the skeptic), and measure qubits that are sent back, or
(2) the skeptic can send classical challenges from two quantum computers, and get back classical answers—and those two QCs share entanglement but are known to be unable to send each other signals.
For more about this, see e.g. the seminal papers by:
Broadbent, Fitzsimons, and Kashefi
Aharonov, Ben-Or, and Eban
Reichardt, Unger, and Vazirani
The “only” real drawback of the things I mentioned above, is that proving quantum supremacy with them is likely to require technologies that won’t exist for a while. (Well, and also, unlike with the sampling problems, we don’t know how to relate the number-theory problems or e.g. estimating the rate of your favorite chemical reaction to general questions in complexity theory, like the infinitude of the polynomial hierarchy.)
Comment #18 October 23rd, 2017 at 3:31 pm
Ashley #12: I confess that I don’t see any deep issue of principle that separates BosonSampling from, say, non-fault-tolerant random quantum circuit sampling, of the sort that Google and others might do soon. At most, the two are separated by contingent engineering issues (and, of course, by mathematical issues, e.g. one involves the permanent while the other involves much messier functions; one gives rise to a natural complexity class “below” BQP while the other doesn’t seem to).
Just a few weeks ago, I attended a quantum optics conference in Rome, where I talked to optics experts who expressed optimism that BosonSampling really can be scaled to ~50 photons, via a combination of scattershot, variable times of arrival, and other tricks. Now, is it possible that the experimentalists are overoptimistic about this? Certainly! It would hardly be the first time.
But by the same token, from where we stand right now, maybe the superconducting people are overoptimistic. Maybe, when they test their 49-qubit chip, the couplings will give rise to all sorts of unexpected noise, and you won’t be able to fix it without full fault-tolerance.
In other words: in both cases we’re talking about non-fault-tolerant architectures: ones that might someday be improved to become fault-tolerant (in the case of BosonSampling, using KLM or something similar) but are not now. In both cases, seeing a clear quantum speedup without fault-tolerance might or might not be possible; it’s all a question of numbers, and if it’s possible at all then most likely it’s “just barely” possible.
I agree that on this planet, it’s looking probable that random circuit sampling with superconducting qubits is going to come first. And random circuit sampling is great; Lijie and I even wrote a whole 60-page paper about it! I submit only that, for all we can say, BosonSampling comes first on other planets, ones in which technology has advanced in slightly and unimportantly different ways… 😉
Comment #19 October 23rd, 2017 at 4:18 pm
Is 50 qbits enough to do anything interesting?
Comment #20 October 23rd, 2017 at 4:22 pm
would you have any reason to believe whether Kalai’s thesis that QC is impossible is true (in some mathematical sense)? Can that thesis be put on a mathematical foot?
Comment #21 October 23rd, 2017 at 4:30 pm
Re: “will I never hear about a break again”:
You appear to treat keyless (you mentioned hash functions), symmetric algorithms and various asymmetric algorithms of unspecified nature (you mentioned groups). We need to be more precise in this context if we’re going to get anywhere, because these are drastically different from a cryptanalysis and complexity analysis perspective. The kinds of minor improvements you’re suggesting tend to be more in the symmetric analysis camp, but “just pick a big enough group already” is clearly about asymmetric algorithms. Asymmetric cryptography is precisely where you’d expect to see the very significant algorithmic speedups; e.g. Joux’ attacks on pairings, or quantum attacks on isogeny Diffie-Hellman.
Comment #22 October 23rd, 2017 at 6:04 pm
fred #19: Depends what you mean by “interesting.” 50 qubits should be enough to do something classically pretty hard, thereby clearly demonstrating the reality of a quantum advantage, and forcing Gil Kalai to admit he was wrong, which for me was always the #1 application of QC anyhow. 🙂
But something useful, like simulations of commercially important molecules? The most optimistic estimates I’ve seen suggest you might be able to start doing that with 100-200 logical qubits, but with a circuit depth high enough to require error-correction. So, I think it’s coming, but I’d be surprised if within the next couple years.
Comment #23 October 23rd, 2017 at 6:17 pm
Laurens #21: Of course I’m familiar with breaks, classical or quantum, that dramatically reduce the computational complexity of the underlying problem, by exploiting its structure! Such breaks are likelier the more structure there is to exploit, and hence more common for public-key than private-key systems. These breaks are basically the opposite of the kind of breaks we were talking about here, the kind based on brute force plus clever tricks plus small values of n, the kind for which I was fantasizing that security practices would improve to the point where I’d never have to read about them again. 🙂
Comment #24 October 23rd, 2017 at 6:25 pm
AJ #20: We’ve discussed Gil’s ideas countless times on this blog, often with Gil himself here—search the archives! For now, suffice it to say that one of my central reasons to be skeptical, is that I’ve never seen any clear mathematical statement (at least, not one that I understood) of what Gil believes the world would be like, such that QC would be impossible—whereas I know a very clear mathematical statement of what the world would be like such that QC would be possible. At the same time, I’m glad that skeptics like Gil exist, since they’re the reason why we can say that the QC experiments of the next few years will be breaking new ground in fundamental science, why they’re “not just engineering”!
Comment #25 October 23rd, 2017 at 8:00 pm
What kind of circuits are we planning to use in the quantum supremacy experiments?
For example, suppose we perform the experiment by running a QC with randomly generated circuits, and validate the results against a classical simulation.
How would we establish that a sufficient number of hard circuits were used, even probabilistically? How do we make sure that enough hard instances are tested, such that any respective failures are not attributable to gate fidelity?
Basically, how much debate can we expect post supremacy?
Also, you mentioned your paper with Lijie. As a result of that, and previous work, do you have an understanding of how the difficulty of simulating a QC (using a standard gate set) varies with the number and disposition of each gate type.
For example, is there an understanding of whether a specific gate is the bottleneck, or whether certain gate configurations are more problematic.
Would you be able to generate a random quantum circuit that’s difficult to simulate, in the same way that you’d be able to generate an NP-Complete problem instance that’s difficult to solve?
Comment #26 October 23rd, 2017 at 8:21 pm
June #25: Yes, if you generate a quantum circuit uniformly at random, from an ensemble that avoids certain obvious easy cases (no entanglement, no interference, stabilizer gates only…), I think it’s a reasonable conjecture that with overwhelming probability over the choice of circuit, the circuit’s output distribution will be intractable to sample classically, even to constant error in variation distance. And all the more so if you want a single, uniform classical algorithm that takes as input a description of the quantum circuit and then generates a sample.
In the present state of complexity theory, this sort of conjecture is not amenable to proof, but one can give reduction arguments. E.g., in my paper with Lijie, we point out that, if you agree that guessing whether a given output amplitude is large or small can’t be done significantly better than chance by a polynomial-time classical algorithm, then it follows that such a classical algorithm can’t generate outputs with large probabilities either, in a way that would pass the statistical tests that we imagine applying in these quantum supremacy experiments.
No, it’s not a specific gate or “certain gate configurations” that are the bottleneck. It’s just all the gates together generating a “generic-looking state” involving 2n amplitudes, and not knowing a classical algorithm to answer questions about those amplitudes that’s significantly better than brute force.
(As I’m constantly telling people, “quantum speedup” is a negative condition, not a positive one. That is, all it means is that, of all the special reasons why a quantum system might be easy to simulate classically, none of those reasons apply in the case at hand.)
Comment #27 October 23rd, 2017 at 10:10 pm
Scott #23 You appear to be restating my comment. The point I previously raised is that the only kinds where the inching you’re lamenting happens are in keyless and symmetric algorithms, but you also suggested we should just pick bigger groups, which doesn’t really apply to those algorithms. Do you have examples of a lengthy sequence where cryptographers just always pick the smallest group, and then cryptanalysis gets a little better, and then we pick a slightly larger group, et cetera et cetera?
However, production cryptography absolutely _does_ install wide security margins where it can. 128 bits is a huge margin against a classical attacker, 256 bits is a huge margin against a quantum one. Salsa20 is fine, but as far as we can tell so far, Salsa20/12, Salsa20/8 are also fine. And yet, we standardize on the safe option. What is a “safe” margin in your opinion?
It honestly sounds like you’re just unhappy about the term “break” 🙂
Comment #28 October 24th, 2017 at 12:59 am
Scott #18: Thanks! That sounds like an exciting experimental possibility. Though I’m far from an expert on this front, it looks like the ideas you’ve outlined are designed to deal with the problem of producing n input photons at once, rather than the problem of loss within the circuit. This could also become a big problem once n is large, as each photon will have to go through something like either n^2 optical components (using a standard Reck scheme) or at best n (using your+Alex’s optimised low-depth circuits).
So it seems possible that for large n a loss-tolerance scheme, as yet undemonstrated, would be needed. It’s true that the proposed 49-qubit chip isn’t yet doing fault tolerance either, but to me the gap between that architecture and full fault-tolerant operation seems smaller: the qubits are already around the fault-tolerant threshold, and it seems that all you need to do for fault-tolerance is implement intermediate measurements. This looks easier to do in a superconducting-type architecture than in optics, as all the physical ingredients are already there, and one just needs to implement classical control of subsequent gates / measurements based on measurement outcomes. Also, “partial-fault-tolerance” has already been demonstrated on small systems.
I agree that, in both cases, we just don’t know yet whether we’ll be able to see a quantum speedup of some kind without fault-tolerance, and this will all come down to some delicate numbers. The good news is that we’ll probably know quite soon 🙂
Comment #29 October 24th, 2017 at 1:25 am
Unrelated Question for Unrelated Update,
Has deepmind’s last realisation (alphagozero) significantly changed your prior for a strong AI within a few decades?
Comment #30 October 24th, 2017 at 3:21 am
Jay #29: Were you actually at my talk and meaning to ask me that? (Just so I know whether I can avoid answering 😉 )
Comment #31 October 24th, 2017 at 3:31 am
Laurens #27: Yeah, I’m unhappy about the term “break” when it doesn’t actually mean that, but I also think I framed things badly. “Some of my best friends are applied cryptographers.” If I make fun of them, it’s only because I love them, the same reason I make fun of physicists. Indeed, all I want is for the rest of the world to adopt the good security practices (like choosing large enough n) that they too would all endorse. Well, all except for Adi Shamir, who said that he wants people to continue choosing small n’s so that he can write break papers.
Incidentally, you’ve said twice that you were thrown off by my talking about “choosing a larger group,” but I didn’t remember saying anything of the kind—and I just searched the post and comments and indeed can’t find it.
Comment #32 October 24th, 2017 at 3:38 am
Establishing quantum supremacy by having a QC running random circuits is such a cop out.
It’s totally disappointing. If adequate.
That’s like, the least we could possibly do… all other options would also involve running a circuit.
Maybe we could have it compute, and then immediately uncompute, the solution to an actual problem prior to running garbage?
It’s like, TCS is taking such a backseat here. It’s a big occasion and we’re not invited.
I’m only half serious here, but it’s a strong half.
Comment #33 October 24th, 2017 at 4:20 am
Job #32: TCS is taking a backseat? What the hell are you talking about—do you understand the first thing about this??
Among all things that a quantum computer can do, sampling hard distributions (as in BosonSampling, IQP, or random circuit sampling) is the one where complexity theory is most obviously in the driver’s seat—since we actually know how to relate the hardness of these tasks, at least in the error-free case, to things like the infinitude of the polynomial hierarchy. (And also, because we have enormous freedom to design whatever problem we want, just so long as it’s classically hard.)
Obviously quantum supremacy is just the beginning of the story, not the end. Indeed, it’s not even the end of what you do with a 50-qubit device (you also demonstrate error-correction and anything else you can). My view has always been simple: after the debate about the reality of quantum speedups has been definitively settled, then you start work toward speedups that are useful for something.
Comment #34 October 24th, 2017 at 8:16 am
The fact that I couldn’t explain to Scott (over more than a decade, see #24) my analysis for why the impressive current quantum-computer race is going to fail is a major source of disappointment for me 🙂 . Let me make another try via the following analogy:
Consider a superman style superhero who, in order to use his superpowers needs to wear his robe, which he often does, to the benefit of his fellow citizens. And now suppose that he can have even much greater superpowers if he wears his quantum robe. Alas, wearing the quantum robe is very difficult and already requires quantum superpowers. In this situation he can go on with his ordinary superhero activities, but to be a quantum superhero is an unreachable goal!
Comment #35 October 24th, 2017 at 8:25 am
Scott #24
“I’ve never seen any clear mathematical statement (at least, not one that I understood) of what Gil believes the world would be like, such that QC would be impossible”
The one thing I wonder about – the wave function in QM behaves like any wave in the sense that a lot of sub-waves can add up constructively and destructively.
Wave behavior is well understood mathematically, but, in practice, actual wave-like systems do exhibits limits on how many waves you can actually “stack up”, no?
E.g. if you look at the surface of a lake, the movement of the water surface may be the result of the sum of hundreds of individual harmonic sources, but how far can you scale this up? To a thousand sources? A million? A billion? Somewhere in the movement of the water molecules, the amplitude and phase information of all those sub-waves have to be ‘stored’, but there’s gotta be some limit because water is made up of individual molecules. Also, only so much energy can be carried by the water before the wave-like nature of the water surface breaks down (and the more sources you have, the less energy is available to them).
Similarly, isn’t there a limit on how many light waves can “stack up” at a given point in space?
Isn’t it then reasonable to expect that QM would also exhibit some limit on the summing nature of the wave function (because of the finite nature of space, etc)?
Comment #36 October 24th, 2017 at 8:33 am
Gil #34:
Consider a superman style superhero who, in order to use his superpowers needs to wear his robe, which he often does, to the benefit of his fellow citizens. And now suppose that he can have even much greater superpowers if he wears his quantum robe. Alas, wearing the quantum robe is very difficult and already requires quantum superpowers. In this situation he can go on with his ordinary superhero activities, but to be a quantum superhero is an unreachable goal!
That’s your argument? No wonder you’ve been unable to explain it to me for a decade! 🙂
Comment #37 October 24th, 2017 at 8:36 am
Pearl of wisdow #101: anytime you don’t want to answer someone on your blog, don’t. 🙂
(if that helps: no, I won’t go to a talk and ask about something unrelated to that talk)
Comment #38 October 24th, 2017 at 8:39 am
fred #35: The difference is that the waves in QM aren’t waves of photons, or any other ordinary physical “thing”: they’re waves of probability amplitude. And it’s the nature of probabilities, or of amplitudes, that in order to describe an arbitrary system with n particles, you need exp(n) of them. Just like no one has come up with a sensible modification of probability theory that avoids this, so no one has come up with a sensible modification of QM that avoids it either. Which is not to say that no possible such modification could exist, but that’s the scale of what we’re talking about.
But why even argue about it? The whole point of the upcoming quantum supremacy experiments, for me, is so we don’t have to keep arguing about it in this comments section, so that your and Gil’s and everyone else’s noses get rubbed in the full reality of the situation! 😀
Comment #39 October 24th, 2017 at 9:00 am
Scott #38
Okay, I guess the question is then whether it’s possible to make sure that the quantum computer and you always agree on what set of physical events those probabilities are referring to.
Comment #40 October 24th, 2017 at 9:01 am
Jay #37: It’s an enormous question, and I’d like to take more time to think about it before writing a “serious” reply.
Briefly, though: AlphaGo Zero is clearly a major accomplishment. The original AlphaGo sort of threw me off: I’d assumed that, if they initialized it by training on hundreds of thousands of human games, then they must’ve had a good reason, like that they already tried it without such training and found that it didn’t get off the ground. But then, no, it turns out that the training set isn’t needed after all.
I still think superhuman AI is very likely a long ways off—and more to the point, even if it weren’t, it’s not something that I’d have any idea how to think about productively, and therefore I’m almost forced to restrict my attention to the possible futures where it doesn’t happen anytime soon.
AlphaGo Zero isn’t obviously strong evidence for the feasibility of superhuman general AI. After all, machines have been able to destroy humans at integer addition for quite a long time, and without any prior training whatsoever on the mental math heuristics that the greatest human adders over the centuries have learned or found useful. But we don’t normally take that as strong evidence that machines will soon destroy humans in all other domains as well. So the question, whose answer isn’t obvious, boils down to: on the scale of generality, is Go more like integer addition, or like general human thought?
Having said all that, if I wanted to make the case that Yudkowsky-style AI “foom” scenarios were plausible in our lifetimes, then I’d certainly be harping nonstop about AlphaGo Zero right about now.
Comment #41 October 24th, 2017 at 9:03 am
Scott #36, Hmm, my superman analogy is a special tribute to you, the creator of the immortal “Zork Bloogorithm” and the slogan about ordinary words 🙂 . Anybody interested in the mathematics can read, e.g., this paper. Sure, We can certainly wait a couple of years, to see how things go.
Comment #42 October 24th, 2017 at 9:23 am
Scott #40
An AI defeating humans at Go is one thing, but the real breakthrough imo is that an AI was able to do the same with poker, a game with partial information (against the best players teaming together).
https://spectrum.ieee.org/automaton/robotics/artificial-intelligence/ai-learns-from-mistakes-to-defeat-human-poker-players
Comment #43 October 24th, 2017 at 9:52 am
” But we don’t normally take that as strong evidence that machines will soon destroy humans in all other domains as well.”
The operative word here is “soon”. I think the better, non-parochial, view is that they have. 😉
Comment #44 October 24th, 2017 at 10:23 am
Scott: Perhaps you edited the parenthetical after “far enough out into the sea” and don’t recall what it originally said first? That’s where I recall that phrase being from. But OK, let’s say that you never said “group”, only meant symmetric or keyless cryptanalysis.
Let us pick a bigger key size. Well, RC4 had relatively massive keys (so big they could be confused for RSA key sizes): 2048 bits. And yet, no matter how many of those 2048 bits you use, RC4 has disastrous biases, which we found through two decades of cryptanalysis. I don’t have to pick a pathological example: what does that huge key schedule look like? (Key schedules are already very costly, especially for tiny embedded devices.)
Uh, OK. What other knobs can we twiddle? Perhaps block size? No, that’s broken too. We’ve even tried both at the same time with Hasty Pudding, and that was shortly thrown out. Do you suggest we just use XTS everywhere?
Maybe rounds are the ticket. Oops, nope. That’s (slide attacks) how cryptographers broke KeeLoq, the remote control protocol for a bunch of fancy cars. Not “cryptographically” broken, but drive-off-with-the-car broken.
Of course even if all of these features were effective, you’ve now almost certainly generated a cipher that’s far easier to attack via side channels. Side channel attacks are actually a hard problem, even for the sizes we have now. And for what? To go from a cipher that no extant attacker can put a dent in to…. exactly that, except now with more vulnerabilities extant attackers _can_ make use of?
I’ve read your blog for years and love your QC material, but let’s just say that this isn’t your finest hour. Perhaps the entire field was in fact trying to do the best job it could in the circumstances provided, and didn’t just create the perfect storm of environmental factors for an oroborous of boring papers. Or, you know, maybe they did the latter. I’m sure some other fields look that way from the outside too 😉
(Feel free not to reply: I’m very done.)
Comment #45 October 24th, 2017 at 10:32 am
Scott #40,
There does seem to be a few other potential aspects of the AlphaGo Zero that do make this different:
First, Go is either EXPTIME or EXPSPACE complete (depending on the version of the ko rule used). Granted the constructions to get that involve very large size boards, but still the sheer complexity of the problem is striking, and if one thinks that one of the barriers to foom/recursive self-improvement are computational complexity then this should be a cause for concern.
Second, the AlphaGo Zero surpassed human thought on this and surpassed by a lot what already the best computers were doing, which suggests that this an example where purely algorithmic improvements with very little hardware improvements can have very big results, something which does make foom situations more likely.
Third, some arguments against AGI more generally seem to be variations of Penrose’s sort of arguments. In that context, if human intuition was somehow solving incredibly difficult problems, that would be an argument in favor of his sort of claim. If we’re not doing so, then those sorts of claims (and certainly his claims that humans somehow can solve the Halting Problem or the Halting Problem given a Halting Problem oracle) look substantially more suspect.
Comment #46 October 24th, 2017 at 11:02 am
#43,
brains are built with software (sperm + egg DNA) and a couple pounds of raw material 😛
Comment #47 October 24th, 2017 at 3:56 pm
Ashley #12, Scott #18
Scattershot and time-bin encoding and etc help with the issue of generation of a 50-photon state, which is what I would have expected the experimentalists to be refering to. But I think Ashley’s point is that, in our current inplementations of bosonsampling, each time a photon goes through a beamsplitter it has some constant probability of being lost. If the circuit depth is linear in the number of photons (which is the best known necessary depth for the hardness of bosonsampling results), each photon will have an exponentially small probability of making it to the other end of the circuit – let alone all 50. This is even assuming you have a perfect 50-photon state at the input. And if you look at the per-beamsplitter loss rate of these state-of-the-art experiments, the success probability of a 50-photon run is just abysmal.
I think that a way around this, which I thought about for a long time but haven’t made progress on, is to figure out whether bosonsampling on a circuit of logarithmic depth is hard (maybe showing that the circuit looks sufficiently Haar-random already in this regime). This would bring the per-photon loss probability down to a scalable regime.
I do agree with Scott’s broader point in #18, though. I just wanted to point out this distinction which I think is important (and raises a nice interesting theoretical question).
Comment #48 October 24th, 2017 at 10:12 pm
Scott #40,
Thanks for the answer. I understand the feeling. On some forum I was writing some rant on how alphago zero is impressive, both for machine learning and lovers of go, but before I could get happy with my treatment of resnets, someone jumped in and said “that means strong AI soon”. My first reaction was “ok let’s just add some rebuttal” but then I froze and realized that I’m just not so sure he’s wrong. Nor right. Then, a couple of hours later, my little toe said: why thinking so hard when you can just ask Scott? 🙂
Fred #42
We keep reading that from time to time, but I just don’t get the point. From the perspective of, say, a go player, the policy of the opponent looks random (even in self-play, because the policy of your opponent includes information computed from one more move). Don’t you think this kind of randomness is fundamentally harder than picking cards from some known or easy to learn distribution?
Joshua #43
Could you expand on your first point? One concern is that, although Go is (part of) an EXPTIME problem, it may actually be much simpler (the same way some problem might looks 3-SAT, but then you realise you have a special set of instances which reduce to 2-SAT). Is there anything one could do to make your idea robust against this kind of attacks?
I also like your second point very much (sorry, not the third: at some point rebutting Penrose-like arguments is just boring two-neuron business 🙂 ). If I may reexpress: starting from scratch, alphago zero was able to best a community of thousands of humans working for maybe a thousand years. It did that using one or two months of GPU equivalent and maybe 10^-6 the synapses of the human brain. The magnitude of the difference of means is so huge that, if this turns generalizable, it might well be possible developing strong AIs on most gaming PC.
In other words: strong AI might be close not because we’re about to make some huge progresses, but because we’re about to discover that the human brain actually sucks at producing intelligence. Which sounds kind of right…
Comment #49 October 25th, 2017 at 12:04 am
I don’t think current machine learning techniques are yet close to general AGI.
As I mentioned in the other thread, concepts and ontology are what need to be mastered here, not statistics and probability.
If we imagine that machine learning is an extension of statistics&probability, thusly;
Statistics&Probability >>>>> Machine Learning
My view is that what’s needed to penetrate to true AGI is an extension of concepts and ontology that gets us to machine psychology (goals, language, ability to adapt).
Analogously to the above then,
Ontology&Concepts >>>>>> Machine Psychology
Just as machine learning was an extension of statistics and probability, machine psychology will in my view turn out to be handled by an extension of ontology and concepts.
Which specific computer science techniques do I think we need to handle ontology and concepts?
I think the answer is a kind of modal logic, one that can deal with planning. What we’re looking for is a *temporal* logic that can generate a symbolic model of time – or , to be precise, can deal with processes evolving in time.
As it happens, there is just such a modal logic that’s already close to fitting the bill! Linear Temporal Logic (LTL)!
https://en.wikipedia.org/wiki/Linear_temporal_logic
The approach to super-intelligence is to formulate a method of knowledge representation that symbolically handles all explanatory knowledge. There are 3 levels to this:
Models of concrete objects (models of the external world)
Models of temporal objects (models of dynamic systems)
Models of abstract objects (models of modeling)
The capacity to formulate symbolic models at all levels solves super-intelligence. Model formulation is about integrating many concepts into a coherent whole (concept clouds). You want to find a way to integrate (or unify) all explanatory knowledge.
I call the capacity to integrate many lower-level concepts into higher-level ones ‘super-clicking’. And this actually what the scientific method really consists of.
Comment #50 October 25th, 2017 at 3:20 am
Sure, especially in Boson sampling, i think that’s a good counter example. But there’s something awfully circular about this setup.
In the sense that the inherent difficulty in simulating a quantum system has been sort of an assumption from the beginning, and it’s still on the table.
A demonstration of quantum supremacy by letting a QC simply be the type of system we’ve long assumed is difficult to simulate, is kind of cheap.
A more compelling demonstration would exploit the assumed hardness of simulating a quantum system to tackle the assumed hardness of an entirely different problem, like integer factorization.
But i’m pretty excited about it either way.
Comment #51 October 25th, 2017 at 4:10 am
First, on a personal note, yesterday I attended a lecture of Scott at TAU theory seminar, and it was very nice to meet in person. Our first meeting (that I remember) was when I invited Scott to Yale in 2006, we met a few times since and I find our personal meetings friendlier and friendlier over time in spite of our disagreement on the feasibility of quantum computers. (Probably we also met in Jerusalem in 2003.) Incidentally both Scott’s lectures in Yale and in Jerusalem were about learnability of quantum states. So I am looking forward to chatting with Scott this year about matters where we are not in conflict: combinatorics, and more.
A) BosonSampling
Regarding the comments on BosonSampling. My 2014 paper with Guy Kindler gives a rather clear picture of what we can expect from noisy BosonSampling experiments. (We studied a different model for noise but this insights are likely to extend to photon losts as well) When the noise level is fixed the noise will kill all high-terms Hermite polynomials. The only pure states that we can expect approaching are those with small support on high order Hermite terms to start with. Even for lower level of noise we can expect strong sensitivity of the outcomes on the noise. This means e.g. that if a photon is lost with probability t (which can be sub-constant) and there are very weak dependency pattern on which photons are lost, then the outcome will depend in a major way on these characteristics of the noise. In short, even for sub-constant level of noise, you cannot expect robust outcomes. The low Hermite expansion prediction may already be checked by the 5-photons 5-modes experiment.
B) Small quantum computers
Much current effort is toward small quantum computers (or quantum circuits) and we can expect that the same phenomena that Guy and I identified for BosonSampling applies for small quantum circuits as well. The clear predictions from our work is a) only noise-stable pure states are approachable. b) Circuits leading to another pure state will reach a far-away mixed state, and the outcomes will be chaotic. (When you run the same experiment twice you get very different results.)
These predictions can be checked in Google’s and IBM’s small quantum computers. (Perhaps already now!.)
Comment #52 October 25th, 2017 at 4:10 am
Anyway, i had a thought on refuting the extended Church-Turing thesis.
How do we ensure that nature is really solving a hard problem and not simply creating a hard problem from a solution?
If we can feed it the problem instance to be solved, reliably, and if the allowed instances are not super constrained, then it’s clear.
However, if that’s not true, then how do we know that nature did not start with a solution (say, a clique), create a problem (say, by adding random nodes), then later on transition between the two in an attempt to make someone’s life miserable?
Comment #53 October 25th, 2017 at 4:16 am
(cont.)
C) distance 3-Surface codes
As I said many times, creating distance-5 surface code where the encoded qubit has much better quality than the physical qubits will smash my conjectures to pieces. This requires 100 or so qubits and as far as I know this is something that the Google group tries to achieve already in 2018. There is an interesting easier challenge to create distance-3 surface code where you need only 20 or so qubits. This represents a state that one can try to achieve both in the Google and IBM systems. I would find it very interesting even if the quality of the encoded qubits is worse than that of the physical qubits. I dont know why this intermediate task is not pursued (and not recently mentioned) and maybe some experts can explain more about it.
D) Scott’s remarks about me.
a) “… forcing Gil Kalai to admit he was wrong, which for me was always the #1 application of QC anyhow.”
This is very flattering. (Especially when my name is explicitly mentioned.)
Sure, all you need, Scott, is a good quality distance-5 surface codes, or a robust demonstrations of random quantum circuits on 50 qubits which agrees with the classical simulation. (And a special deal before 2025 – 40 qubits as well!)
b) “I’ve never seen any clear mathematical statement (at least, not one that I understood) of what Gil believes the world would be like, such that QC would be impossible.”
Again, it is flattering that I am expected to come up with a clear mathematical statement (that Scott understands) for the entire world. I mentioned above some mathematical statements about the concrete objects we study (quantum circuits, bosonsamplng). Here is a statement related to Scott’s yesterday lecture:
“Pure quantum states that can be approached by noisy quantum local systems are efficiently learnable.”
(This applies to bosonsampling, quantum circuits, and other things in our world, if not to the world in its entirety.)
c) “I’m glad that skeptics like Gil exist, since they’re the reason why we can say that the QC experiments of the next few years will be breaking new ground in fundamental science, why they’re “not just engineering”!”
I agree 🙂
Both Scott and I think (and often say and write) that we are dealing with a clear-cut scientific question of great importance. Also, of course, failure in reaching the desired goals may reflect interesting science (regarding the interface between computation and physics and the nature of noisy quantum systems) and not merely not-good-enough engineering.
d) “The whole point of the upcoming quantum supremacy experiments, for me, is so we don’t have to keep arguing about it in this comments section”
I also agree that heated debates are not needed at this stage, and precisely for this reason, in the last years, I hardly commented on this matter here. It is useful for me (and Scott and other theoreticians) to clearly (and mathematically) explain what we expect from the coming experiments, raise some suggestions to experimentalists for specific things to try, describe our vision for what to do after the experiments, and also to patiently wait for the outcomes.
Comment #54 October 25th, 2017 at 4:28 am
As far as I know, the current status of hardness proofs for approximate boson sampling is that the number of modes m must be at least ~n^5 (assuming various conjectures) I think but Scott further conjectures that ~n^2 should do, where n is the number of photons.
Is there actually any good reason to believe one can sample approximately in polynomial time from the boson sampling distribution for m = 10n, say? Does anyone have an algorithm to do that?
Comment #55 October 25th, 2017 at 5:02 am
Similarly, do we have any reason to believe that exact boson sampling is poly time for m = 1.1 n ? (m = 2n is the proven threshold given for hardness I believe).
Comment #56 October 25th, 2017 at 7:02 am
Gil #51: you may find the paper arXiv:1610.01808 interesting (with apologies for the self-promotion). There we show that, in a different setting (“IQP circuits”), something similar holds, i.e. that with a small amount of noise the quantum circuit becomes classically simulable. The proof idea is exactly analogous to what you wrote above.
But, crucially, we also found that this noise can easily be handled using simple classical error-correcting codes. So it’s not implausible that this might hold in other settings too (e.g. that someone could invent a “fault-tolerant boson sampling” proposal that is designed to be robust against loss, without having to use full quantum fault-tolerance).
Comment #57 October 25th, 2017 at 7:04 am
[…] at the University of Texas at Austin and the head of its Quantum Information Center, said in a recent blog post that IBM’s paper on quantum supremacy did not diminish the importance of Google’s quantum […]
Comment #58 October 25th, 2017 at 8:15 am
Jay #48,
Could you expand on your first point? One concern is that, although Go is (part of) an EXPTIME problem, it may actually be much simpler (the same way some problem might looks 3-SAT, but then you realise you have a special set of instances which reduce to 2-SAT). Is there anything one could do to make your idea robust against this kind of attacks?
In these cases (again depending on your version of the ko rule), Go is not just in EXPTIME or EXPSPACE but is EXPTIME-complete or EXPSPACE-complete. So it can’t be living down below. In the same way that 3-SAT or graph coloring or whatever your favorite NP complete problem *cannot* reduce to a polynomial time problem assuming that P != NP. In fact, in this case, the situation is actually even stronger since by the hierarchy theorems we know that EXPTIME is strictly bigger than P and that EXPSPACE is strictly bigger than PSPACE.
Comment #59 October 25th, 2017 at 12:17 pm
Job #52:
How do we ensure that nature is really solving a hard problem and not simply creating a hard problem from a solution?
Err, that’s why we’re trying to build aprogrammable quantum computer, able to solve a huge range of instances of a problem, with no need to hardwire the instance into the machine! Just like a universal QC could be fed any positive integer of your choice and it would spit out the factors, so Google’s upcoming device will be able to do quantum circuit sampling with any (reasonably small-depth) circuit that you feed it; reprogramming it is just a matter of telling your classical computer to send the superconducting chip a different sequence of signals encoding the coupling strengths.
So then, what will you need to accept?
(1) That the device really is solving the problem. (For this we have verification procedures.)
(2) That the problem really is exponentially hard classically. (As usual, we can’t prove such statements, but we can relate them to relatively standard beliefs about complexity theory.)
(3) That there was no ‘t Hooft style “superdeterministic conspiracy,” which so arranged the initial conditions of the universe that “everything is a lie,” and even though you thought you were using your brain or your random number to choose a hard instance of the problem to feed to the QC, really you weren’t.
All of these assumptions, but certainly (3), seem pretty reasonable to me.
Comment #60 October 25th, 2017 at 12:46 pm
bozo #54, #55: As Alex and I mentioned in the paper, there are proofs that m~n2 modes are enough to get close to i.i.d. Gaussian, provided your m×m BosonSampling matrix is a Haar-random real orthogonal matrix rather than a unitary matrix. It’s even a standard result in the random matrix literature. No one seems to have bothered to redo the proof for the complex (unitary) case, but there’s no serious doubt that the result is true, and it would make a good course project for a student. In the meantime, experimentalists can treat m~n2 as more than enough: note that, as far as anyone can say, approximate BosonSampling remains just as hard with m=O(n) modes; it’s just that there we no longer get a clean reduction from a problem involving i.i.d. Gaussian matrices.
Your question about what happens to exact BosonSampling when m=1.1n is extremely interesting, and caused me to put together something new! When Alex and I wrote our paper in 2010, we would not have known the answer to that question, but an answer follows from the recent paper by my students Daniel Grier and Luke Schaeffer. In particular, they show that computing the permanent of a unitary matrix is #P-hard. From this we can deduce that exact BosonSampling is hard in general, unless the polynomial hierarchy collapses, even in the case m=n.
Comment #61 October 25th, 2017 at 12:59 pm
Thank you Scott #60.
I take it from your answer that we should assume that even approximate boson sampling is hard even for m = n (although clearly not for the collision free case!).
In terms of this hardness for approximate boson sampling, is there a hard threshold in terms of the total variation distance epsilon? In other words, do we expect boson sampling to be exponential time for total variation distance epsilon < x? If so, do you have a way to calculate what x is explicitly, presumably in terms of n and m?
Comment #62 October 25th, 2017 at 2:42 pm
Those particularly interested in practical aspects of cryptography and security will be rewarded by reading Bruce Schneier at https://www.schneier.com/ and/or signing up for his newsletter. Bruce analyzes everything from many angles. He is actually the guy who wrote the book(s).
Comment #63 October 25th, 2017 at 2:49 pm
Who would have guessed we would wind up quoting George W. Bush: http://phdcomics.com/comics.php?f=1980
Comment #64 October 25th, 2017 at 2:54 pm
Dear Ashley Many thanks. The paper and especially the ability to use classical error correction to handle noise is indeed fascinating! What about doing it for general quantum circuits? Certainly an analogous result for BosonSampling or other form of Bosonic fault tolerance would be great!
Comment #65 October 25th, 2017 at 3:30 pm
Gil: thanks! Though I should stress that the noise model we considered is somehow very classical itself (it can be seen as random bit flips in the classical samples obtained at the end of the circuit). Extending this idea to more general noise or for more general quantum circuits could be quite challenging… but maybe fun 🙂
Comment #66 October 25th, 2017 at 3:43 pm
Joshua #58,
Here’s an exemple for which we can demonstrate the “living down below”: any set of instances of generalized Go for which the board is n*n and the komi is above n^2 (yes… black pass and win). This set of instances belongs to generalized Go, but it can be solved in constant time.
Here’s another exemple, for which I’m not sure of the complexity: any set of instances of generalized Go for which the number of move is below n^2 and the komi above 7 (yes, as most human games). I’ll be glad to learn if anyone knows a good lower bound, but I doubt the complexity is “generalized Go-complete”.
So, if I can rephrase my question: do you see any garantee that the set of instance that corresponds to Go-as-played-by-humans doesn’t belong to a special set?
Comment #67 October 25th, 2017 at 4:32 pm
Job #50
Right, since quantum systems can behave “classically”, QM is a super-set of classical systems in that sense.
There’s clearly some extra “power” in QM, otherwise, why would nature have bothered with it? (it can’t even create stable atoms without it!)
It then looks cheap to notice that there’s gotta be some quantum system that classical systems can’t simulate efficiently, repackage them as a “computation”, and then declare quantum supremacy.
The real question is whether “qbits” are possible, as some uber version of classical bits, which truly are “perfect” (stable, independent of implementation, and infinitely scalable) digital logic abstractions.
Comment #68 October 25th, 2017 at 4:57 pm
bozo #61: Yes, as far as we know approximate BosonSampling remains hard for m=n, and even beyond that: one could try m<n, all the way down until the nm-time or whatever classical simulation becomes efficient enough.
Of course, just like in applied crypto, the more liberties you take with parameters, the greater the probability of entering the “danger zone” where the problem might succumb to some algorithm that we don’t yet know about. Especially if you choose parameters that no one had much occasion to think about before.
Your question about whether there’s some “hard threshold” in the variation distance error ε is an excellent one, and we don’t yet know the answer to it. In our paper, we just dealt with the assumption that approximate BosonSampling has no poly(n,m,1/ε) algorithm—which means, we implicitly imagined an experimenter who could get the error down to some arbitrary ε>0 using “poly(1/ε) experimental effort.” Of course that isn’t quite realistic.
If you fix ε to (say) 1/10, then—this story should sound familiar by now—our reductions don’t go through quite as nicely, but as far as anyone knows the problem is still hard.
I’m aware of some work in progress that touches a bit on this question—showing that, in the presence of sufficiently severe errors of other kinds, BosonSampling can become classically easy below a certain threshold in the variation distance error. But I don’t want to write more about it without the authors’ permission.
Comment #69 October 25th, 2017 at 5:07 pm
Ashley #28:
it looks like the ideas you’ve outlined are designed to deal with the problem of producing n input photons at once, rather than the problem of loss within the circuit. This could also become a big problem once n is large, as each photon will have to go through something like either n^2 optical components (using a standard Reck scheme) or at best n (using your+Alex’s optimised low-depth circuits).
Two replies:
First, if we do want to discuss near-term experiments rather than asymptotics, I’m told that loss at the beamsplitters is almost completely negligible compared to the problems of building efficient single-photon sources and detectors. It’s very unlikely to be a limiting factor in practice.
But secondly, as far as anyone knows, approximate BosonSampling might be classically hard even with a constant-depth beamsplitter network! Certainly exact BosonSampling remains hard for constant depth; Daniel Brod has a paper where he shows that.
In the approximate case, of course we no longer get submatrices that are i.i.d. Gaussian, so our hardness assumption for the permanent will have to involve a matrix ensemble that’s messier to describe. But I know of no result saying that the permanents that arise from constant-depth beamsplitter networks are actually easy—do you?
Comment #70 October 25th, 2017 at 8:22 pm
Jay 66,
Ah, I see your point. Yes, there’s no real guarantee like that at all, and the nature of a lot constructions to prove these sorts of things suggest that such a result would be probably false. For that matter, thinking about this more, the board sizes needed to argue even that Go is NP-hard are already very large. For example the construction used in Moore and Merten’s includes gadgets which are as large as 8 by 8, so even a 19 by 19 board can only model a very tiny circuit. I don’t know if anyone has tried to make these gadgets more efficient.
Comment #71 October 25th, 2017 at 9:48 pm
[…] at the University of Texas at Austin and the head of its Quantum Information Center, said in a recent blog post that IBM’s paper on quantum supremacy did not diminish the importance of Google’s quantum […]
Comment #72 October 26th, 2017 at 4:07 am
For AlphaGo the obvious question is if they can repeat the trick. That is train version 2 using version 1 so that version 2 always beats version 1 (as they have already shown). Then train version 3 using version 2 so that version 3 always beats version 2 and repeat.
Have they already tried this? I assume they must have done.
Comment #73 October 26th, 2017 at 4:17 am
Scott #68
Interestingly, if m = n then I believe you can simulate boson sampling exactly in something like 1.55^n time (using a variant of our exact sampling algorithm) which I think pushes the threshold for quantum supremacy to around n = 80.
Experimentally you would also have to have 80 reliable photon counters which might be difficult in the short term on its own (I am told).
Comment #74 October 26th, 2017 at 5:19 am
Scott #69: no, I don’t know of any result that says that constant-depth BS could be easier than general BS… but on the other hand, constant-depth (or even log-depth) BS using standard integrated photonic circuits could indeed be easier to simulate, as these correspond to nearest-neighbour interactions. It seems likely (though I didn’t work out the details) that you’d need long-range interactions to get computational hardness here, which would in turn involve waveguides crossing each other, hence inducing loss etc.
About the point on beamsplitter loss in “near-term” experiments, I guess it depends how near-term you mean, but although at present this doesn’t seem so significant (with experiments with under 10 photons), it could become more important when we need to have photons propagating through more than, say, 50 reconfigurable beamsplitters. Even loss induced by the underlying medium could start becoming an issue here.
As a counterpoint, there are the recent impressive achievements by experimental groups working in this area. So I guess we’ll see once such experiments start being built 🙂
Comment #75 October 26th, 2017 at 7:09 am
Not actually related to your post, but I figured I’d ask somewhere: I’m given to understand that you’re giving a talk on quantum complexity at the Hebrew University in Jerusalem, but I haven’t been able to find much information about it (time, place, verification of the existence of such an event). Any info on that would be appreciated
Comment #76 October 26th, 2017 at 8:14 am
Scott #59
Is ‘t Hooft calling you a baboon?! 😛
https://arxiv.org/pdf/1709.02874.pdf
“I am aware of the large numbers of baboons around me whose brains have arrived at different conclusions: they proved that hidden variables do not exist. But the theorems applied in these proofs contain small print. It is not taken into account that the particles and all other objects in our aquarium will tend to be strongly correlated. They howl at me that this is ‘super-determinism’, and would lead to‘conspiracy’. Yet I see no objections against superdeterminism, while ‘conspiracy’ is an ill-defined concept, which only exists in the eyes of the beholder.”
Comment #77 October 26th, 2017 at 8:40 am
Joshua #70, there is a proof here https://senseis.xmp.net/?RobsonsProofThatGOIsEXPTimeHard
tha tseems to give sligthy lower size of gadgets.
Comment #78 October 26th, 2017 at 9:20 am
Raphael #73: Wow! So, you’re not claiming that you can compute the permanent of an n×n unitary U in 1.55n time, but you are claiming that you can accept with probability |Per(U)|2 in 1.55n time? Is that written down anywhere? And where does the 1.55 come from? Sounds like a great result!
Comment #79 October 26th, 2017 at 9:36 am
Ashley #74: For constant-depth BS with spatially local beamsplitters, I guess the question is: do we have an efficient classical algorithm for the permanents of band-diagonal matrices, of constant width w? Like nw or 2w or something? I seem to remember that the answer is yes, but I don’t remember the algorithm… (and of course, even knowing the algorithm, we’d then have to turn it into a sampling procedure)
Comment #80 October 26th, 2017 at 9:42 am
Scott,
Boson sampling texts refer to some simultaneity:
“We only count the runs in which n detectors register a photon simultaneously, even if such runs are exponentially unlikely”
or in the wiki
“Then, the probability of generating simultaneously M single photons is ε^M”
What does “simultaneous” mean in this context?
Is this about defining an actual practical “time window” of +/- some fraction of nanosec (or pico seconds) where the events need to happen, or is this a quantum property of the entire system where we know that the events are either simultaneous or they’re not?
Comment #81 October 26th, 2017 at 9:45 am
fred #76: Yeah, I guess he is calling me a baboon! Rather than reply in kind, I’ll simply say it’s sad for me to witness his evolution on this subject. His first papers on a classical cellular automaton underlying physics strongly suggest that, hard as others find it to believe, he simply didn’t understand Bell’s Theorem or its importance. Then, after dozens of people must have explained to him that Bell’s Theorem really, actually does rule out what he wants, rather than admitting that his initial idea didn’t work, he started advocating a “cure” that’s clearly, obviously a trillion times worse than the disease—something that would make science impossible (as ordinary QM does not) and that has no new explanatory power (as ordinary QM does)—all, one suspects, so that he wouldn’t have to admit he was wrong.
Comment #82 October 26th, 2017 at 9:47 am
Eliana #75: Yes, I’m speaking at HUJI on Wednesday November 8, about my new result on “shadow tomography” of quantum states! But I don’t yet know the time or room either. I just emailed Dorit Aharonov and Guy Kindler to ask.
Comment #83 October 26th, 2017 at 9:50 am
Carl #72,
Since AlphaGo Zero plays against itself to learn already, having a separate program play against itself shouldn’t really make a substantial difference.
Comment #84 October 26th, 2017 at 9:55 am
Scott,
Some major cryptosystems will still be broken, but every time it will be because a serious flaw is discovered in the cryptosystem. Often, this serious flaw will reduce the running time of the fastest known algorithm to break the system from, say, 2^n to, say, 2^{n/100}. In such cases, we could have just taken our key sizes to be 100x as long, but that’s not really the main issue. The main issue is that the designers of the cryptosystem missed something huge.
To be clear, I’m talking about symmetric-key crypto. (For public-key crypto, the problems are so structured that I think it’s much more reasonable to expect major algorithmic progress. For lattices, the only area in which I’m an expert, I’m aggressively trying to tell people that there probably will be major algorithmic progress.) For symmetric-key crypto, it’s sort of kind of maybe reasonable to say that, since “almost every” function is basically a perfect PRF/CRHF. (Obviously, the flaw in this argument is that (1) most functions are not efficiently computable; and (2) existential proofs via the probabilistic method are often extremely hard to derandomize in practice.) And, cryptographers have devised various ways of making this argument slightly less absurd in the case of specific systems like AES.
Comment #85 October 26th, 2017 at 9:55 am
fred #80: “Simultaneous” in this context means, close enough in time (compared to the wavelength of the photons) that there’s which-path ambiguity, so one needs to calculate the amplitudes by summing over exponentially many different permutations of the photons, so one gets a hard computational problem (in the simplest case, the permanent).
Comment #86 October 26th, 2017 at 9:56 am
Jr #77,
Thanks for the link. It looks like some of their gadgets are smaller, but I’m not sure that lists every gadget you need. I’ll have to look at that in detail.
Comment #87 October 26th, 2017 at 9:56 am
* should read “since ‘almost every’ function is basically a perfect PRF/CRHF, we should be able to find nearly perfect PRFs/CRHFs.”
Comment #88 October 26th, 2017 at 11:07 am
Carl #72
Adding a little to what Joshua Zelinsky said:
Moreover, it is not the case, as you seem to think, that AlphaGo Zero (the latest version) was trained to beat AlphaGo Fan / AlphaGo Lee. The first version of AlphaGo Zero was random and each version was trained to beat the previous version of AlphaGo Zero. So no information from AlphaGo Fan, Lee, etc. was used in AlphaGo Zero. This is part of what makes AlphaGo Zero’s 3-day training time so impressive – it was really starting from a blank slate.
I lied a little: “each version was trained to beat the previous version of AlphaGo Zero” is actually an oversimplification – each version is trained to predict a Monte Carlo Tree Search built from the previous version of AlphaGo, which is more sophisticated.
Comment #89 October 26th, 2017 at 11:47 am
Scott #78. I didn’t mean to make a concrete claim at this point (and so may have overstated it). It is just a thought. But we shouldn’t be too surprised by the complexity as the expected rank of a matrix sampled from the boson sampling distribution is a constant fraction of n in this case. We also know there are faster algorithms for computing the permanent of matrices with less than full rank. So we would not be sampling any faster than it takes to compute permanents, in a sense.
I will see if the idea still make sense after the STOC deadline if people are interested.
Comment #90 October 26th, 2017 at 1:29 pm
Ashley #74, Scott #79
I don’t remember all details now, but you can use the result in a paper by Jozsa (https://arxiv.org/pdf/quant-ph/0603163.pdf) to prove that if you have constant-depth BS with nearest-neighbor beam splitters, then you can use some tensor network argument to simulate it (I think it doesn’t hold for logdepth though). And you can compute both probabilities at each output mode and conditional probabilities, so you can also sample from the distribution.
Indeed, in my constant-depth result we need beam splitters O(sqrt(n)) modes apart. But I think I don’t completely share Ashley’s “pessimism” about this issue. First, because some of these new integrated devices are starting to exploit nice 3D architectures which might break this nearest-neighbor restriction. But also because there might be other ways around this, for instance if you could connect two integrated devices by fibers to apply a permutation of the modes between them. Currently this is very hard, but would be such a useful thing for photonic QC (and communication) in general that I would expect experimentalists to push for it in time. In particular, for my constant-depth result to hold you would only need to apply such a permutation once.
Comment #91 October 26th, 2017 at 2:08 pm
Scott #81: Scott, please note that fred’s comment #76 is a prank. (Alternatively, fred didn’t read t’Hooft’s paper too carefully.) The context of t’Hooft’s baboon sentence is that earlier in the text he writes that “We are just baboons who have only barely arrived at the scene of science.” I’m sure calling his detractors baboons amused him a bit, but he had the reasonable pretext that he called himself a baboon as well.
Comment #92 October 26th, 2017 at 3:17 pm
Dániel #91: OK, thanks for the added context! Glad the babooning is universal.
Comment #93 October 26th, 2017 at 4:03 pm
If Google’s plan to manufacture a quantum computer with 50 qubits fails, then wouldn’t IBM’s paper on simulation of a 56 qubit machine establish classical supremacy?
Comment #94 October 26th, 2017 at 5:16 pm
Craig #93: Current classical computers outperform current quantum computers for just about every problem imaginable. You didn’t need the IBM paper to tell you that.
The question at hand is whether quantum computers can eventually outperform classical computers for some problems. If so, then in a certain theoretical sense QCs will be strictly better, since it’s a theorem that a quantum computer can always simulate a classical computer with constant slowdown.
And no, the failure of any one particular effort to build QCs wouldn’t settle these questions, unless the failure helped us uncover some new principle of nature that made QCs fundamentally impossible, rather than merely very hard to build.
Comment #95 October 26th, 2017 at 6:04 pm
But what if the new principle is that quantum computing simply does not work, that whenever you try to build these computers with enough qubits and do calculations with them, you get random output?
For instance, what if Google’s 17 qubit machine works perfectly and passes every test, but when they test their 50 qubit machine, it only works for algorithms that require 30 qubits (and they test it out many times on 30 randomly selected qubits), but when an algorithm that requires 50 qubits on their machine is run, the machine always outputs random garbage output?
Wouldn’t this give strong evidence that quantum computing simply does not work?
Comment #96 October 26th, 2017 at 9:31 pm
Carl #72,
To repeat what #’s 83 and 88 said in my words, AlphaGo Zero was not trained by results of previous versions; it trained itself.
This should be a head-scratching result for those (not just Dr. Penrose) who want to believe human intelligence has some sort of non-materialistic magic about it. Granted, the algorithm was programmed by humans, but it works completely materialistically, and is of a finite length that random trial and error could have produced in finite time (and I suspect some combination of trial and error and building on previous work was used to produce it, similar to biological evolution).
It is a ho-hum result to most readers (and the writer) of this blog because we accepted materialism long ago, but it would come as a huge shock to most of the world’s population (including most of my relatives and friends), if they understood and accepted it.
Comment #97 October 26th, 2017 at 9:45 pm
Craig #95: The situation that you describe would be a revolution in physics, as large as the discovery of quantum mechanics itself if not larger. It’s hard to convey adequately just how many times more exciting it would be to participate in such a revolution, than “merely” to succeed in building a scalable QC, which is the “boring, expected, conservative” outcome by comparison.
If Nature obeys one set of laws for 30 qubits (namely, the laws that have governed every single microscopic phenomenon observed for the last century), but a completely different set of laws for 50 qubits, then the obvious question is: why? In science, you don’t just accept such a thing as a brute fact, you ask: why? Especially because this would be a law unlike any we’d previously seen in physics—a field where, for centuries, our experience has been that each particle (or infinitesimal patch of space) does its own thing, evolves under its local Hamiltonian, interacts with nearest neighbors, etc. without knowing or caring how many other particles or patches of space it might be cohabiting a computation with.
Comment #98 October 27th, 2017 at 11:33 am
Scott, as you wrote in your PhD thesis, there are two empirical laws of physics which contradict one another, the Extended Church-Turing Thesis and Quantum Mechanics, when the number of qubits is large (if we are to assume that factoring is impossible in classical polynomial-time, which is a perfectly reasonable assumption). (There is no contradiction when the number of qubits is small.)
QM is counter-intuitive. The Extended Church-Turing Thesis is very intuitive. Why would you bet on the counter-intuitive law over the intuitive law? Not just you, but big companies like Google and IBM? To me, the Extended Church-Turing Thesis is “boring, expected, conservative outcome”.
Comment #99 October 27th, 2017 at 12:34 pm
Is it really that revolutionary for a theory to lose precision or predictive power for increasingly complex systems?
Isn’t that what normally happens?
And if it does happen it will be a long, drawn out, back-and-forth process.
How do you show that you can’t build a QC? That sounds about as hard as showing P != BQP.
If you can only try and fail, that’s not much of a revolution.
Comment #100 October 27th, 2017 at 2:12 pm
Job #99: At the risk of repeating myself hoarse, because if quantum mechanics fails, there will have to be some other theory to which it’s only an approximation. It’s the discovery of that other theory, and the need for it, that would be the revolution.
Quantum mechanics is not some random approximate theory that someone made up one day. It’s the deepest thing human beings ever learned about reality. As far as the past century of physics can say, it appears to hold perfectly and without exception in every situation that there’s ever been or will be, from a transistor to the cells of your body to a neutron star to the beginning of the universe.
So if QM seems clearly to predict that something should be possible, but that thing turns out again and again not to be possible, even after (as far as anyone can tell) the technology has gotten good enough—you don’t just throw up your hands and say “well, I guess the theory didn’t work then.” You look for a coherent picture of reality that explains the new situation.
Do you really believe I wouldn’t be thrilled to participate in the discovery of a new coherent picture of reality—one that replaces the picture we’ve had since 1926, the picture based on unitary evolution in an exponentially large Hilbert space and (as we’d describe it today) the complexity class BQP?
But the real question is this: if, as that picture suggests, the upcoming quantum supremacy experiments do work as planned, will you, Craig, and the other commenters here finally concede that I (along with most of the physics community) was right about this—that love it or hate it, the final answer or no, QM is not a thing that we have the right to just toss aside, like someone’s opinion about a movie?
Comment #101 October 27th, 2017 at 2:29 pm
Scott #103
To me this isn’t about the validity of the underlying theory, but about its practical implementation.
QC relies on perfect interference of vast amounts of probability waves.
Once you have thousands and thousands of qbits, it all starts to look like trying to balance perfectly a billion pencils on top of each other – feasible in theory but requiring amazing engineering.
This is strikingly different from regular bits, which only require any sort of stable switch (whether hydraulic, mechanical, electronic, etc).
Comment #102 October 27th, 2017 at 2:53 pm
Craig #98:
QM is counter-intuitive. The Extended Church-Turing Thesis is very intuitive. Why would you bet on the counter-intuitive law over the intuitive law? Not just you, but big companies like Google and IBM? To me, the Extended Church-Turing Thesis is “boring, expected, conservative outcome”.
For one thing, the Extended Church-Turing Thesis—or for that matter, even the original Church-Turing Thesis—was never accepted by physicists as having the status of a physical law. However, I happen to be in the camp that thinks that physicists should take these principles much more seriously than they do. So let me give your question a serious reply, because I think it deserves one.
When QM goes mano-a-mano against the Extended Church-Turing Thesis—which it does—how do you decide who’s likelier to win? For me, everything comes down to the overriding need for a coherent picture of reality.
We have a coherent picture of reality according to which quantum mechanics is true and the Extended Church-Turing Thesis is false. That picture is the one that I subscribe to, and that most scientists subscribe to, and that Google and IBM and Microsoft implicitly subscribe to. It’s a picture that does promise more computational power than the Extended Church-Turing Thesis would have, but only slighty and subtly more—as I like to say, more in a pattern that’s so weird that no science-fiction writer, no sophist just stringing words together in a way that sounded good, would ever have had the imagination to invent it.
By contrast, we do not, at present, have a coherent picture of reality according to which the Extended Church-Turing Thesis is true and quantum mechanics is false. Or, not one that’s compatible with all the empirical successes of QM for the past century. We have words you can say that might sound good—e.g., “QC works for 10 qubits, but will fail for 30 qubits”—but then no actual math to back the words up. Why does it suddenly fail for 30 qubits? You can’t just say, “because of the Extended Church-Turing Thesis”: you have to explain, how does the thesis reach down into particle physics and prevent the qubits from doing what they otherwise would have done?
Among all QC skeptics, I have the most respect for Gil Kalai, because at least he recognizes the need for such math. But as far as I can see, his attempt to find coherent math that would explain the impossibility of QC has completely, utterly failed to find anything even the slightest bit convincing.
Crucially, the need for mathematical clarity, consistency, and coherence overrides the desire for an answer that humans find “intuitive.” That’s pretty much been physics’ wildly-successful central operating principle since Galileo.
To borrow an example from David Deutsch: the theory that the seasons change because of the changing moods of the gods is extremely intuitive. Anyone can understand it. The problem is “only” that the theory doesn’t give rise to a coherent picture of reality: for example, how does it account for the fact that it’s summer in Australia when it’s winter in the US? Are there different gods in charge of the different hemispheres, with moods that always perfectly oppose each other? Unlike the theory of axial tilt, but like the theory that “QC will just fail for some reason at 30 qubits,” the divine emotional theory of the seasons keeps forcing you to invent one ad hoc explanation after another for observed phenomena—because, in an honest reckoning, it isn’t really an explanatory theory at all.
Comment #103 October 27th, 2017 at 3:01 pm
Scott,
If anyone can produce a 50 qubit quantum computer, I will be amazed, but won’t concede defeat in my position. But if anyone can produce a 100 qubit quantum computer, then I would concede defeat in my position. And my world view, that there is no such thing as magic, would be completely shattered.
Comment #104 October 27th, 2017 at 3:19 pm
Craig #102: Good! If 100 qubits is all it takes, then I predict your concession of defeat is something that I’ll live to see with plenty of time to spare.
Quantum mechanics is an unusual kind of magic: a kind that perfectly obeys precise, impersonal mathematical laws that not only are knowable, but have been known since 1926.
Comment #105 October 27th, 2017 at 3:29 pm
fred #101: Yes, there’s no dispute whatsoever that a scalable QC would be a feat of, as you put it, “amazing engineering.” But as far as we can tell today, that’s “all” it would be! And it would hardly be engineers’ first amazing feat: I fly every two weeks or so for talks and workshops, and am still sort of amazed every time the plane lifts off the runway…
Unfortunately, I’m going to sleep now, and don’t have enough energy to re-explain (for the 300th time in the history of the Shtetl-Optimized comment section? 🙂 ) the theory of quantum fault-tolerance that underlies the above view.
Comment #106 October 27th, 2017 at 3:36 pm
Craig #98: I take issue with the argument that we should accept the Extended Church-Turing Thesis because it’s intuitive. If it’s so intuitive, why didn’t we see it much earlier? Why didn’t Socrates, Euclid, or Newton state it, or something equivalent? (If they did, please link me a source, I’d be interested to learn more!) It seems like it took until around the time we had actual, physical Turing machines we could use before it was stated. And now that everyone’s carrying superfast Turing machines in their pocket, sure, it feels “intuitive”, but that’s just because we can relate it to common technology.
In other words, 200 years ago, the extended Church-Turing thesis wasn’t intuitive because the notion of Turing machines wasn’t intuitive. And in 200 years, if everyone is carrying around quantum computers in their pockets, it will be just as intuitively obvious that the Church-Turing thesis is false. So even if there’s a period of a couple centuries where it feels intuitive, that doesn’t feel like good evidence to me that it’s the be-all, end-all of what we will ever be able to compute – just that it’s the best we can do today.
Comment #107 October 27th, 2017 at 5:02 pm
Yes. I’m wrong on a regular basis.
And why would i love it or hate it? Do you really think i favor one outcome over the other?
Don’t you think i’m aware of how close we are to building a QC? That doesn’t mean i don’t have questions about it. Should i stop asking them because otherwise i’ll have to admit you were right?
Like that’s my big problem?
Comment #108 October 27th, 2017 at 8:36 pm
By the way, Scott (or Ashley, or other experts), one minor question for you: You often talk about simulating a quantum circuit’s acceptance distribution to total variation distance epsilon (say, .1). But is there any reason to believe that’s a ‘good’ notion of error?
For example, if I understand the Martinis group’s plans, they don’t believe that even their physically-implemented *quantum* circuit will have small total variation distance to the theoretical distribution. Rather, they merely hope/believe it will have nontrivial KL-divergence. (Whereas they conjecture any efficient classical algorithm will have basically maximal KL-divergence.)
Any theoretical work that considers the classical difficulty of sampling with nontrivial KL-divergence?
Comment #109 October 27th, 2017 at 10:26 pm
Job #107: LOL! I’m sorry that I was too testy last night; was just stressed and exhausted.
Comment #110 October 27th, 2017 at 10:36 pm
Ryan O #108: It’s a good question. The most relevant thing I can say about it is that, in the most recent work we’ve done—e.g., my paper with Lijie Chen—we set aside the small variation distance criterion anyway, in favor of just directly talking about the probability that your samples pass whatever verification test you’re going to apply to them. Of course one can still ask whether that probability will be noticeably large in the presence of a realistic number of bit-flip and phase-flip errors.
The basic heuristic I’ve been using is that, if you have k such errors, the “signal” that you’re trying to detect (say, the variation distance from the uniform distribution) goes down by a factor of roughly 1/exp(k). This means that you can tolerate one or two such errors in a given run, but probably no more. The Google group says they crunched the numbers and are optimistic about their ability to get a low enough error to see a signal (i.e., pass the verification test with non-negligible probability), but of course it remains to be seen.
I’m not aware of any rigorous work that looks at the complexity of approximate quantum sampling problems directly in terms of KL-divergence. (I believe the Google group looked at it but only in a heuristic way.) That seems like a good project for someone.
Comment #111 October 28th, 2017 at 1:58 am
Hey Scott, this is not really that relevant, but something in this thread reminded me so I’m going to say it here anyway. 😛 It’s kind of odd that I never see a unified notion of “problem” in computer science. Like OK, decision problems are a special case of promise problems, which are a special case of search problems; but also decision problems are a special case of sampling problems — but then also you’ve got approximate sampling…
It just occurred to me today I think the right notion of “approximate sampling” might unify all these. Specifically, your notion of Knightian uncertainty as a convex set of probability distributions. “Sample from some probability distribution in this convex set” satisfies all of the above; for exact sampling problems the set is a point, for the more usual sort of approximate sampling it’s a ball in an appropriate metric, for search problems it’s the convex hull of a set of point masses.
(Using such a general framework for everything would resolve a certain other niggling thing — I’ve noticed a certain tendency for computer scientists to ignore the distinction between “always” and “probability 1”. ZPP is usually defined for instance to require that the algorithms that define it always halt, but I’m pretty sure in fact you want that they halt with probability 1, or else the proof that ZPP is the intersection of RP and co-RP doesn’t work! But if we are doing everything in this framework then it is obvious we would only ever mean “with probability 1” and never “always”. 😛 )
Actually I’m wondering if we should say say closed convex set rather than just convex set. That does raise the question of what the topology is, given that in general we’d be considering probability distributions over the countably infinite set of strings (or natural numbers or whatever you like) rather than just over a finite set. I assume someone else, who knows measure theory stuff better, would have a better idea of what the appropriate topology would be. But ignoring such details and getting to the point — I’m a bit wary of considering the following a valid problem: Given access to a source of random bits, write an algorithm that always returns 0 or 1, and returns 1 with some nonzero probability. Because, like, how would you ever verify that a purported solution to this problem was working without inspecting its source code? “Oh, no, keep running it, it’ll return 1 eventually, I swear.”
…or maybe that’s not actually the problem I think it is at all. I mean we allow all sorts of other things as problems whose solutions can’t really be readily verified; lots of stuff is outside PSPACE, after all. I mean the halting problem is a problem, definitely, and there is truly no way to verify a purported solution of that one! (I mean also we know there is no solution, but that’s not the point.) But the probability case… man, that bugs me. I’m wary of including it.
Still, “convex” vs “closed convex” isn’t the point; that’s a nitpicky detail. (If we really are trying to be as inclusive as possible, I guess maybe the right thing to do is just say “convex” on those grounds.) The point is this notion of Knightian uncertainty you talked about looks to me like the correct general way of defining “problem”. (Well — at least for the whole bits-and-strings style of computation. If you’re working in an algebraic model of computation or something, I guess that’s potentially a whole nother story.) I don’t know, maybe this is all well-known, but I haven’t seen it before, so I thought I’d say it.
Comment #112 October 28th, 2017 at 2:11 am
Oh wait now I think I see why I didn’t say this before — it doesn’t work for problems that want you to output a quantum state, which is absolutely something we want to do sometimes (and this is all sticking to bits-and-strings, not algebraic stuff).
Uhhhh replace “probability distribution” in the above by “mixed state” maybe?? (I have never actually taken the time to learn how mixed states actually work but I’m hoping one can take convex combinations of them in a sensible way that is compatible with how one would do so with probability distributions.) Sure seems substantially less motivated when you put it that way; no longer has the simple connection to a notion of Knightian uncertainty. Blargh. That’s quantum mechanics for you. Oh well. Still worth saying I think.
Comment #113 October 28th, 2017 at 9:38 am
Sniffnoy #111,
I’ve noticed a certain tendency for computer scientists to ignore the distinction between “always” and “probability 1”. ZPP is usually defined for instance to require that the algorithms that define it always halt, but I’m pretty sure in fact you want that they halt with probability 1, or else the proof that ZPP is the intersection of RP and co-RP doesn’t work! But if we are doing everything in this framework then it is obvious we would only ever mean “with probability 1” and never “always”.
My impression is that generally when one says that a ZPP algorithm defined to always halt, it is defined that it really does always halt but it has a small probability of returning “I don’t know.”
Comment #114 October 28th, 2017 at 10:24 am
Joshua #113: Yes, that’s exactly right. And it’s standard homework exercise to prove the “don’t know” definition equivalent to the “halt with probability 1” definition.
Comment #115 October 28th, 2017 at 11:13 am
This remark is something we discussed many times, and I hope that what I say is agreed by all here, but let me repeat it anyway as both people who dislike QM and fantasize of replacing it, and devoted believer of QC, like to say or suggest or hint that a failure of QC means a failure of QM. This is false! There are many physicists who are skeptical about QC and fully believe in QM. Even serious believers of QC realize that failure of QC might be perfectly compatible with QM. (Here QM=quantum mechanics; QC= quantum computers.)
As John Preskill wrote in a 2011 paper:
“For scalability to fail as a matter of principle then, either the accepted principles of quantum physics must fail for complex highly entangled systems (as ’t Hooft [tH99] has suggested), or else either the Hamiltonian or the quantum state of the world must impose noise correlations that overwhelm fault-tolerant quantum protocols (as Kalai [K11] has suggested).”
Oded Goldreich (who is skeptical about QC) wrote in 2004: (and believed it since the early 90s):
“Firstly, the Laws of QM are merely a refutable model…
Secondly, as far as I know (and here I may be wrong), QM says that certain things are not impossible, but it does not say that every thing that is not impossible is indeed possible.”
Oded wrote in plain English essentially the same thing that John wrote in more technical terms: The failure of QC does not contradict QM.
(OK, now I move to my opinion:) The second alternatives on John Preskill’s list as well as on Oded’s are (in my opinion) much more mundane, while still of great interest.
When people say things like “Unless QM is wrong there couldn’t be any fundamental obstacle to quantum computers” they seem to ignore (or underestimate or overestimate) this second possibility, or to automatically regard it as non-fundamental, or to somehow mistakenly think that the second possibility would be as surprising or more surprising than the first.
Comment #116 October 28th, 2017 at 11:19 am
Another remark to the discussion above: The idea that QC will work perfectly up to 17 (or 30, or 50) qubits and then crash instantly for more qubits seems absurd and does not fit the experiments. The quality of QC will deteriorate as the number of qubits grows, to a large extend depending on the quality of individual qubits and gates, in a way which is overall rather understood.
Now there are two possibilities: My prediction is that the quality of QC will deteriorate to make it of no use well before we reach the number of qubits needed for quantum supremacy and quantum error correcting. In my view, there are good theoretical support for this expectation. (With nothing to do with the extended Church-Turing thesis).
Believers like Scott have different expectations than me, and are encouraged by recent achievements and plans based on these achievements by experimentalists. Success or failure in experiments in the near future will either refute my stance or support it. Even experiments that can be carried out today on existing systems on the behavior of universal QC that Google, IBM, Ray Laflamme and many others already have with 4,5,6,7,8,… qubits can be quite telling.
Comment #117 October 28th, 2017 at 11:28 am
Gil #115: No, my position is not that the possibility of scalable QC logically follows from the principles of QM. My position is more nuanced: it’s that if scalable QC is fundamentally impossible, then there must be some principle explaining why that would be revolutionary for physics. That new principle could be a replacement of QM itself by a deeper theory, but it could also be a new “principle of noise” or “principle of limitation of effective Hilbert space dimension” or whatever that was layered on top of QM. Even in the latter case, though, one would want a better picture of what the universe was like that made it manifest why QC was impossible. E.g., if all realistic quantum systems can be simulated in classical polynomial time, then how do we do the simulation?
Comment #118 October 28th, 2017 at 12:22 pm
Dear Scott, we are essentially in agreement on #117 (except for priors). It would be exciting to see how do matters fold in the next 3 years.
Comment #119 October 28th, 2017 at 1:06 pm
Huh, OK, yeah I see that, I guess you can in fact get “literally always” in such a case. It feels wrong to me to insist on that though, like that’s a little bit extra you get in this case that you’ll never use. Everything else seems to make more sense if you everywhere interpret “always” as “with probability 1”, so that little bit extra you get here won’t be relevant to those.
Comment #120 October 28th, 2017 at 6:58 pm
Dan Staley,
If one were to explain the Extended Church Turing thesis to any smart scientist living in previous generations, he or she would find it intuitive, even if they did not believe it. However, this is not the case with QM, even with scientists living today.
Comment #121 October 28th, 2017 at 7:53 pm
Scott 103,
The extended CT thesis means that the universe is in essence a giant digital computer. How is it not a coherent picture of reality to say that the program which controls our universe simulates quantum mechanics whenever it can, but gets an overflow error and outputs random garbage whenever it does not have enough processing power?
Comment #122 October 28th, 2017 at 8:00 pm
Craig #120: Actually, it’s totally non-obvious to me whether smart scientists of previous generations would or wouldn’t have found the Extended Church-Turing Thesis intuitive.
FWIW: my own intuition, as an 11-year-old who was just starting to learn BASIC programming, was that there might well be infinitely many different kinds of programming, more or less powerful or even incomparable to each other, corresponding to all the different kinds of computers and robots that you could imagine building. And that therefore, I could aspire to do something even cooler than programming: I could someday invent a fundamentally more powerful form of programming. (Of course, I wouldn’t have had the conceptual vocabulary to express this well, but I clearly remember thinking it.)
So it came as a tremendous surprise to me—forcing me to change and upgrade my original intuition—that no, there’s this thing called the Church-Turing Thesis, which says that all powerful enough programming languages are fundamentally equivalent; they can all simulate each other. (As usual: in the sense that I understand, not the Theory B / programming language semantics sense.)
Furthermore, this upgrading of my original mistaken intuition, in response to arguments and observable reality—i.e., the humbling realization that science does more than just fill in some technical details of how you already decided the world has to work, that it actually tells you big, important things that are not just elaborations of what you guessed sitting in your armchair—was pretty similar to what I later went through when I learned about quantum mechanics.
Comment #123 October 28th, 2017 at 8:27 pm
Craig #121:
How is it not a coherent picture of reality to say that the program which controls our universe simulates quantum mechanics whenever it can, but gets an overflow error and outputs random garbage whenever it does not have enough processing power?
For one thing, because any proposal along those lines that we tried to write down would more likely than not violate Lorentz invariance, the no-signalling principle, the conservation of energy, and like three dozen other basic principles of physics. And also, because the question would arise of why the universe hasn’t already generated overflow errors (or has it?) for the many complex molecules and materials that no one knows how to simulate feasibly on classical computers.
Physics has a high standard. You don’t just get to say “oh, the universe can generate random garbage instead of solving the hard computational problem”: you have to give a quantitative model that predicts that that’s what would happen, and also show that your model is consistent with relativity and energy conservation and all the other things we know.
While there’s something about your questions that I find endearing, I regret that I don’t have time to continue this exchange. Thanks for participating.
Comment #124 October 28th, 2017 at 8:46 pm
Scott 124,
Your experience with computers as an 11 year old was much different than mine, which was in 1980. My father had then bought an Apple 2 plus. Before learning BASIC programming and then Apple machine language on that computer, our computer had worked by magic to me. I had before then, very little experience with computers just like most people living then. However, it was still a mystery to me how the transistors, chips, and wires had anything to do with machine language, even after I had learned it. It wasn’t until much later when I studied Turing machines and electricity, when I realized that it did not work by magic and it was very intuitive. The Extended CT thesis is very intuitive to me now that I know how computers work.
However, the QM behind how transistors and other electrical components work is still very counterintuitive. The notion that QM is fundamentally wrong and only an approximation is appealing to me, since it makes modern computers completely unmagical and intuitive.
Comment #125 October 29th, 2017 at 12:13 am
Anton Zeilinger’s group showed that the double-slit experiment works with C60 molecules some 20 years ago. (see e.g. https://www.univie.ac.at/qfp/research/matterwave/c60/). Doesn’t it prove that QM is valid at least for 60 carbon atoms, and there is no magical barrier at under 50 qubits?
Comment #126 October 29th, 2017 at 12:22 am
Shmi #125: If that sort of example is allowed, then we might as well talk about superconducting Josephson junction qubits, which involve many trillions of electrons in a superposition of flowing clockwise around a coil and flowing counterclockwise.
But Schrödinger-cat-like examples don’t really work against Craig’s alternative ‘theory,’ which is that the universe simulates QM as long as it’s not too computationally expensive, and gives an overflow error and starts spewing random garbage otherwise.
Comment #127 October 29th, 2017 at 8:50 am
There appear to be three other problems with the too-much-computation-gets-replaced-with-garbage idea.
First, it isn’t clear in general how one would tell how much computational power was being used; if the computational bounds are determined by the amount of memory used then anything using large-scale quantum mechanics (like the Josephson junction example) would presumably fail. If the computation is bounded by the amount of time needed for a classical simulation, then it isn’t clear how much of an advantage this would give from a trying-to-make-the-universe computable standpoint.
Second, it isn’t clear how the universe or a classical computer simulator would decide that different computations are separate enough to regard something as the entire computation. For example, do Bell experiments using the stars count the stars themselves which are hundreds of light years away as part of the same aspect for purposes of what gets turned into garbage? If we took some photons from a star and ran them through a sophisticated Boson sampling system would we expect for the star itself to turn into whatever garbage we’d get from that?
Third, turning things into garbage data seems to have its own problems. If we are in a simulated universe or at least a universe that acts like a simulation for most purposes, then the turning things into garbage data could easily then corrupt nearby data or give results which are not just random, but genuinely meaningless. Sure, one could maybe imagine a kludge where it keeps them number of electrons and the like the same, but if those aren’t primitive objects, that seems very weird. For example, if one does a difficult computation with superconducting qubits why should one then expect that the resulting garbage does things like preserve the rough amount of energy in the system or even preserve the number of atoms? Ok, if one really wanted to bite the bullet one could suggest that quantum computing experiments end up being the Great Filter because once you do a few with a decent number of particles, some of what you end up with is particles whose behavior is so wrong or are so high energy that you end up destroying your planet. I’m sure Greg Egan could write a wonderful short-story with that premise, but this doesn’t seem very plausible.
Comment #128 October 29th, 2017 at 11:15 am
To respond to Scott 125 (although I do not expect a response), according to my view, all of the physical principles like conservation of energy, Lorentz invariance etc. are just approximations, just like QM. The real essence of reality is the digital physics of Zuse and Fredkin. This is all perfectly consistent with all physical observations, except quantum computing.
Comment #129 October 29th, 2017 at 11:49 am
Joshua 129,
I do not know the answers to your questions, but the good news is that if Google is indeed on track to build a 50 qubit machine, we should be able to get answers soon from their failures.
Comment #130 October 29th, 2017 at 12:08 pm
Joshua, seems you are pointing out how much less likely this “lazy universe” model is, compared to the “faithful universe” QM, if one considers Occam’s razor in terms of Kolmogorov Complexity. A lazy universe seems to require a Grand Simulator of sorts, and not just any grand simulator, but one preoccupied with keeping the classical reality of humans intact, like in The Metamorphosis of Prime Intellect. Anthropic principle on steroids.
Comment #131 October 29th, 2017 at 9:14 pm
Shmi #130,
That’s a much better way of essentially encapsulating all my concerns into a single heuristic. And also I got to learn about a scifi novel I have not read from your comment!
Comment #132 October 30th, 2017 at 3:53 pm
@Craig #128, #129, etc.
If the universe is a classical simulation, and everything that happens in the universe is polynomial time computable, why do you expect the constant is small enough that 50- or 100-qubit quantum computers will cause it to fail? Why can’t the universe simply have enough processing power to perform 2^50 or 2^100 classical bit operations for each apparent cubit in the world? Why can’t it have 2^(10^122) times as much power, just to be safe?
Whatever low-level structure prevents us from noticing the non-Lorentz-invariance could also prevent us from accessing this computing power, except by quantum computing.
———-
Two of your statements of your position seem to be in conflict, or need further clarification. When you say
“How is it not a coherent picture of reality to say that the program which controls our universe simulates quantum mechanics whenever it can, but gets an overflow error and outputs random garbage whenever it does not have enough processing power?”
it seems like the local structure of the computer program you are imagining does not correspond directly to the local structure of our universe. When two distance qubits are entangled, for instance, there is a little subroutine to keep track of them and make sure they behave according to the laws of quantum mechanics. When too many qubits get too entangled, the subroutine runs out of computing power and spits out garbage.
On the other hand, when you bring up digital physics, it sounds like the basic structure of the computer program is the physical structure of our universe – quickly looking up Zuse, it seems he believed the universe was a cellular automaton where the space matches up with our apparent space. In this picture it is hard to see why quantum computing would fail, and not other experiments involving many entangled qubits and distant entangled qubits that have already been performed.
—————————-
I disagree strongly with your opinions, but I have tried not to take a critical tone in the previous remarks as I believe it will not be very productive. But let me say one thing which is somewhat critical anyways.
Your theory is highly counterintuitive in one particular way, which is the sandwich-like structure of reality you predict. Let me give some examples:
* It appears, when measuring objects of size 1 m or so, that everything follows classical laws of probability.
* When we start measuring objects of size 10^-12 m or so, we see that they follow quantum laws of probability.
* When we start measuring objects of size 10^35 m or so, you predict that they will follow classical laws of probability again.
* It appears, when observing objects in our everyday life, that space and time are totally separate.
* When we perform very sensitive experiments involving bouncing light waves, we see that in fact physics inside moving objects is governed by Lorentz transformations.
* When we perform even more sensitive experiments, you predict Lorentz invariance will be broken.
This last one is not as good but:
* It appears in everyday life that energy can appear out of nowhere, or dissipate and disappear.
* When we measure things very carefully, we find that energy is always perfectly conserved.
* When we measure things even more carefully, you predict, energy will not be conserved.
In each case you predict that when we refine the same experiments that have up to this point been producing a picture of the universe further and further from our everyday experience, this trend will eventually reverse and many key features of our everyday experience will return.
In other words, you predict that there is a cellular automaton or underlying physical model, where scaled out by a factor of 10^23 the dominant phenomena are described by a totally different set of physical laws, even totally different laws of probability, but when scaled by a further factor of 10^12, the original laws mysteriously recapitulate themselves.
This seems about as likely to me as finding out that lightning bolts are made of trillions of trillions of tiny electrons and then, years later, finding that electrons are made of trillions and trillions of tiny copies of Zeus.
Comment #133 October 31st, 2017 at 8:28 am
Scott #129
“But Schrödinger-cat-like examples don’t really work against Craig’s alternative ‘theory,’ which is that the universe simulates QM as long as it’s not too computationally expensive, and gives an overflow error and starts spewing random garbage otherwise.”
Maybe what happens is that since most people have no good intuition about QM, they tend to regard QC as a type of “analog” machine. And we all have a feel about how analog computers do kinda work, but can’t scale like digital computers can.
Many people probably also equate QM first with the uncertainty principle, which seems to make building “precise” and large clockwork atomic mechanisms an impossibility (where in fact quantization is what makes matter “stable” in the first place).
Comment #134 October 31st, 2017 at 10:23 am
Will,
Here is my response to your points:
You said, “Why can’t the universe simply have enough processing power to perform 2^50 or 2^100 classical bit operations for each apparent cubit in the world? Why can’t it have 2^(10^122) times as much power, just to be safe?”
I think it is safe to conclude that if one could build a 100 qubit machine, since such a machine would have to keep track of 2^100 (a number with 30 decimal places) numbers at the same time, our universe would have exponential storage capacity and there would be no reason why one could not in principle build a billion qubit machine.
But also my gut tells me that a 50 qubit machine is too large for the computer simulating the universe to handle. Hopefully, we will soon get answers from Google as to whether I am right, since they say they are close to building a 50 qubit machine. I wonder how they will spin it when it fails.
——
You said, “quickly looking up Zuse, it seems he believed the universe was a cellular automaton where the space matches up with our apparent space. In this picture it is hard to see why quantum computing would fail, and not other experiments involving many entangled qubits and distant entangled qubits that have already been performed.”
I do not believe the universe has to be a cellular automaton. When I mentioned Zuse and Fredkin, I meant that I agree with them that the universe is a digital computer, but I never meant that there must be any restrictions on such a computer.
All of my views on this subject are contained here: http://vixra.org/abs/1607.0388
Comment #135 October 31st, 2017 at 2:45 pm
Scott
“my own intuition, as an 11-year-old who was just starting to learn BASIC programming, was that there might well be infinitely many different kinds of programming, more or less powerful or even incomparable to each other, corresponding to all the different kinds of computers and robots that you could imagine building.”
When I was 11, computer memory was so limited that there were indeed different “kinds” of programming 😛
You can do with 13GB of RAM and 1 TB of HDD things that you simply couldn’t do with 48K of RAM (facial/voice recognition, VR, crushing humans at Go,…).
Also, 48K was small enough that you could manually peek (and poke) at every byte of memory! A very unusual kind of programming indeed.
Comment #136 October 31st, 2017 at 3:24 pm
@Craig 134
That’s the best-written paper I’ve ever seen on vixra.
Anyways, your thesis in this paper is not that quantum mechanics is a classical simulation, like in the extended Church-Turing thesis, but rather that quantum mechanics arises from the simulation error in a simulation of classical mechanics. This view is potentially falsifiable by much more than quantum computers.
While waiting for Google, you can spend your time reconciling your theory with all the quantum mechanics experiments of the 20th century.
How would this theory explain the interference pattern in the double-slit experiment? The spectrum of the hydrogen atom? Spin? Bell’s inequality violations? The strong nuclear force? etc.
However, let’s discuss some problems that are a little more fun. Presumably in a simulation of classical mechanics, we would store the particle’s velocity, not their position, so we can update the position over time. If you work out what this means in your theory, it ends up as a number of additional bits to store the velocity equal to the log of the mass. But shouldn’t the number of bits available to store information about a particle be proportional to the mass? In particular, if we have twice as many particles, we should have twice as many bits available.
Furthermore, why isn’t the number of bits needed to store other information about the particle, like charge and color, subtracted? Or is the same number of additional bits subtracted for every kind of particle?
For any property that can take finitely many values, approximations of this form are not needed, and so we shouldn’t expect to see quantum effects. So why do we see so many properties of fundamental particles that involve quantum-mechanics on a finite-dimensional vector space, like spin and color, and so few that involve finitely many classical options (other than conserved quantities like charge)?
I have to bring Bell’s inequality violations into the fun list, too. Why are there Bell’s inequality violations? Why do they fit exactly the pattern predicted by quantum mechanics, and not a higher or a lower number?
Comment #137 November 1st, 2017 at 10:09 am
Fred 135,
When I was 11 and learned BASIC, computer memory (64K bytes) was so limited that I ran out of memory just writing my programs.
Perhaps the reason why my intuition that QC cannot work is different than Scott’s intuition that they can work is because I first learned about computers in a time when memory was a luxury, while Scott first learned about computers in a time when memory was plenty.
Comment #138 November 1st, 2017 at 10:45 am
Will 136,
You said, “That’s the best-written paper I’ve ever seen on vixra.”
Thank you.
You said, “Anyways, your thesis in this paper is not that quantum mechanics is a classical simulation, like in the extended Church-Turing thesis, but rather that quantum mechanics arises from the simulation error in a simulation of classical mechanics. This view is potentially falsifiable by much more than quantum computers.”
My thesis is that the extended Church-Turing thesis is true and that the quantum effects that are observable in nature are the result of limited memory of a computer that tries to simulate classical mechanics. I disagree that my view is potentially falsifiable by much more than quantum computers. My view explains everything that has been observed until today, but if large-scale quantum computers are ever built, my theory would be false.
You said, “How would this theory explain the interference pattern in the double-slit experiment? The spectrum of the hydrogen atom? Spin? Bell’s inequality violations? The strong nuclear force? etc.”
Simple: All of the effects that you mention can be easily simulated by a digital computer. My theory says that all of these effects are caused by the limited memory of a computer that tries to simulate classical mechanics.
You said, “However, let’s discuss some problems that are a little more fun. Presumably in a simulation of classical mechanics, we would store the particle’s velocity, not their position, so we can update the position over time. If you work out what this means in your theory, it ends up as a number of additional bits to store the velocity equal to the log of the mass. But shouldn’t the number of bits available to store information about a particle be proportional to the mass? In particular, if we have twice as many particles, we should have twice as many bits available.”
No, according my theory, the computer generating our universe would store the position and momentum in the computer memory, since these are the quantities which determine how a particle behaves in classical physics. Read my paper again, and you will see this.
You said, “Furthermore, why isn’t the number of bits needed to store other information about the particle, like charge and color, subtracted? Or is the same number of additional bits subtracted for every kind of particle?
For any property that can take finitely many values, approximations of this form are not needed, and so we shouldn’t expect to see quantum effects. So why do we see so many properties of fundamental particles that involve quantum-mechanics on a finite-dimensional vector space, like spin and color, and so few that involve finitely many classical options (other than conserved quantities like charge)?”
Charge, color, and spin are not addressed in my paper, but I can’t see any reason how these would give my theory any problems.
Comment #139 November 2nd, 2017 at 9:10 am
Craig #138
“My thesis is that the extended Church-Turing thesis is true and that the quantum effects that are observable in nature are the result of limited memory of a computer that tries to simulate classical mechanics”
I thought about that too.
Like QM is nature’s lazy way to do some kinda of classical physics approximation as efficiently as possible:
Quantization (plank constants, energy quanta), because you just can’t store infinite precision floats (for positions, velocities, space, etc) 😛
Entanglement – simulate as few things as possible, until you need to explicitly observe them.
Uncertainty principle – multithread your code as much as you can, but by leaving the shared memory un-synchronized (again, for performance), you get weird racing conditions – based on which thread touched it last, the value almost seems random.
Quantum interference (double slit experiment) – some sort of lazy evaluation. The simulation depends only on the geometry of the problem, from which you derive a probability distribution, used no matter how many electrons you send through the double slit (since you don’t observe any particular path, you don’t need to simulate them all).
…
But then it would be bizarre that taking all those shortcuts somehow leads to a system that has more computational power.
Comment #140 November 2nd, 2017 at 9:42 am
As conscious beings implemented on the “hardware” of the universe, we can only observe computation efficiency in terms of “fundamental” operations that impact our own conscious experience (whether those are classical or quantum).
The way the universe is actually doing those elementary operations (in terms of even more elementary operations) could be totally inefficient, but that’s outside of our perceptions.
But there’s still the possibility that the hardware implementing those elementary operations has itself limited resources that it needs to balance out…
Maybe the day Scott finally runs Shor on his 1,000,000,000 qbits QC, we’ll notice that distant galaxies blink in and out of existence.
There’s no free lunch after all!
Comment #141 November 2nd, 2017 at 11:17 am
Craig, not to get into any discussion about your theory, just an observation that it pattern-matches almost perfectly what I have seen from wannabe amateur physicists pushing their own pet theory. Some of the signs are, in no particular order:
– lack of familiarity with the field and its past and current problems
– inadequate (generally very elementary) if any mathematical tools used
– no thorough literature analysis related to the topic
– grandiose claims based on basic insights that somehow the whole community of physicists have supposedly overlooked
– no clear testable predictions that distinguish the new theory from the current state of the art
– is about fundamental theoretical ideas, not incremental improvements
Think of it from the economic point of view: the physics research market is efficient as far as a lay person is concerned. That is, if there was an obvious low-hanging fruit just hanging there (an equivalent of a $20 bill on a busy street), then 100,000 Physics PhDs with IQ 140+, determination of a hungry wolf, research skills honed by years of fierce competition for grants, positions and publications would pluck that fruit and uproot the whole tree with it, too.
The fields like math, physics, comp sci are no longer a lush rain forest it used to be. They are barren deserts where only the select few can do better than to barely survive. Sure, there is still vegetation high up on the trees where even the tallest giraffes have trouble reaching, and there is water deep down out of reach, but a casual visitor has no chance to get there and compete with those who are specialized, well adapted and fight for their very survival.
You claim you have found an oasis everyone else has overlooked, what are the odds of that?
Comment #142 November 2nd, 2017 at 2:21 pm
Shmi #141: Fault Craig for the other stuff all you want, but I don’t think we can accuse him of “no clear testable predictions.” He says that 100-qubit QC will never work—though he punts on the question of 50-qubit QC, which means that his prediction will probably take more than a year to refute.
On the other hand, I’ve been aware of Craig making contrarian claims on the Internet continually for the past 15 years (P≠NP proofs, soap bubbles solving NP-complete problems in polynomial time, I forget what else…). As far as I can tell, every single such claim that was able to be tested turned out to be false, and not a single failure did anything to dent his confidence in the next claim.
Comment #143 November 2nd, 2017 at 5:28 pm
Scott,
I never claimed that soap bubbles could solve NP-complete problems in poly-time. You in fact cited my quote on Usenet here in your paper:
https://www.scottaaronson.com/papers/npcomplete.pdf
Read it and you will see that I never claimed anything there. And you really should be thankful to me that my quote gave you the idea to do the soap bubble experiments, instead of mocking me.
As for P not equal to NP proofs, yes I’m guilty.
I have no idea what you are referring to when you said, “As far as I can tell, every single such claim that was able to be tested turned out to be false, and not a single failure did anything to dent his confidence in the next claim.”
I have made testable predictions on the internet that have been true and testable predictions that have been false. No big deal.
Comment #144 November 2nd, 2017 at 5:54 pm
Shmi: Eh, I’ve totally written a math paper that was low-hanging fruit; and while it’s true that I have a PhD in math and am not some total outsider amateur, in this particular case, most of the relevant background was stuff I learned from browsing Wikipedia in high school (or could have; there was less on Wikipedia back then). But (while it’s a bit worrying that this particular gap in the literature went unfilled for so long) it’s certainly not going to go upending our very conception of the universe or anything! I think at the very least you have to add some measure of results out to your efficiency claim and not just consider effort in.
But that’s assuming that sort of thing is even true… Eliezer Yudkowsky is writing a pretty interesting series on this sort of thing right now… I’m kind of inclined to give physicists more credit than doctors and medical researchers, though!
Comment #145 November 2nd, 2017 at 7:32 pm
Scott #142: Good point about predictions, I just don’t see how this one follows from what he published online. Where is the calculation that gives the 50-100 qubits limit?
And yes, the string of falsified contrarian claims you have mentioned does not quite add extra confidence to this particular claim.
Comment #146 November 2nd, 2017 at 8:55 pm
Shmi,
My pet theory is simply a combination of a well known pet theory (Zuse and Fredkin’s digital universe hypothesis) and a recent theorem by Hall and Reginatto in 2002, that Schrodinger’s equation can be derived from an exact version of Heisenberg’s uncertainty principle. I just combined them together to come up with a theory that predicts that large scale quantum computing is impossible.
Comment #147 November 3rd, 2017 at 10:41 am
Okay, soap bubbles may not solve NP problems in poly-time…
But has there been any serious research on whether Almond Soap is more efficient than, say, Olive Oil Soap?
Comment #148 November 3rd, 2017 at 10:17 pm
Like Sniffnoy, I am writing some papers on what I consider low hanging fruit in the math/physics/CS area. These involve translating certain standard methods of applied math to new areas, and thus greatly simplify what is being done there.
Low hanging is a somewhat slippery concept. Everything is obvious once you know it.
Comment #149 November 5th, 2017 at 7:29 am
@Craig #138
I just want to state for the record that I didn’t stop arguing with you because you convinced me, and in fact quite the opposite.
> Simple: All of the effects that you mention can be easily simulated by a digital computer. My theory says that all of these effects are caused by the limited memory of a computer that tries to simulate classical mechanics.
There is a missing step in there. I agree that it is possible to simulate all quantum effects on a classical computer. But to justify your theory that they are caused by limited memory, you have to explain why, not just these can be simulated, but they can be simulated more efficiently than the “analogous” classical mechanics situation.
This seems like a tall order because even medium-sized quantum molecules are difficult to simulate classically, and the difficulty comes precisely from the quantum effects. So in fact quantum molecules are harder to simulate classically than “analogous” small systems of classical particles.
There are many examples of quantum systems experimentally measured in the 20th century, where the predictions of QC are verified, that are either 1) hard to simulate classically or 2) equally hard as a classical system, with no clear relationship to memory savings.
Comment #150 November 5th, 2017 at 9:03 am
Scott
Re: soap bubbles:
“Even with 4 or 5 pegs, this process could
take around ten seconds, and it is natural to predict that with more pegs it would take longer.”
It is a shame you didn’t carry on your physical soap bubble experiment from this point to test your hypothesis. Also, it’s interesting that the soapy water doesn’t get hot when it does all this computation. In general, nature manages to carry out the most extraordinary computations and physico-chemical operations silently and at room or blood temperature. A feat we have yet to reproduce in the labs and which would be an interesting experimental goal.
Comment #151 November 5th, 2017 at 12:28 pm
Will,
I think the Hall and Reginatto paper that I cited in my paper should answer your questions. Their paper is a wonderful paper.
Comment #152 November 6th, 2017 at 1:15 pm
@Craig
I really shouldn’t respond to this, but it’s just so simple:
The uncertainty described in that paper is totally unlike the uncertainty induced in a computer system by storage limitations. In their paper, the momentum uncertainty is dependent on the position uncertainty, which is determined by looking at the probability density function. This means that to calculate the momentum uncertainty you have to calculate all possible trajectories of the particle and see how many of them end up in the same state. This requires tremendous amounts of memory, far more than just simulating the particle normally, with fixed memory to store the position and momentum.
Comment #153 November 7th, 2017 at 9:00 am
Will,
You said, “The uncertainty described in that paper is totally unlike the uncertainty induced in a computer system by storage limitations.”
No, they are fundamentally the same thing, except that on a computer everything is discrete, while in their paper, everything is continuous.
As long as one assumes as they do in the paper that:
“The strength of the momentum fluctuation at any
given time is determined by, and scales inversely with, the uncertainty in position at that time”
and that everything else is classical, one can derive Schrodinger’s equation. On a computer, this means that we can derive an approximation of Schrodinger’s equation as long as the computer tries to simulate classical mechanics, since everything on a computer is discrete and their above statement translates into there being only a finite number of bits available to specify both the position and momentum of a particle, which is true on a computer.
Comment #154 November 7th, 2017 at 9:14 am
Will,
Also, check out Zuse’s paper, which I cite in my paper. He talks about Heisenberg’s uncertainty principle there and what it means on a digital computer.
Comment #155 November 8th, 2017 at 11:36 am
[…] In fact, it’s been pointed out that simulating larger quantum computers could actually be invaluable for the technology’s continued development. “It being possible to simulate 49-qubit circuits using a classical computer is a precondition for Google’s planned quantum supremacy experiment, because it’s the only way we know to check such an experiment’s results,” the head of the University of Texas at Austin’s Quantum Information Center Scott Aaronson recently pointed out in a blog post. […]
Comment #156 November 9th, 2017 at 5:23 am
Scott #126: We might “talk about superconducting Josephson junction qubits,” but the experiment of Anton Zeilinger’s group with C60 molecules might be more impressive with respect to predictions of QM nevertheless. That experiment directly addresses Roger Penrose’s proposal that QM might become inaccurate if high masses are involved. (I know that the relevant masses are so ridiculously high that one will never be able to refute that proposal with direct experiments like this, but it is still impressive how far one can go.) The Josephson junction experiment is not suited for refuting Penrose’s proposal. It isn’t even a proper prediction of QM, but historically rather a postdiction or at best an explanation of previously observed experimental phenomena (quoted from wikipedia):
But since I am not a physicist, this is my rather layman perspective. I do understand the QM prediction for the C60 molecules and the transistors more or less, but I never managed (or even cared) to work through the Cooper pairs explanation of superconductivity in my solid state physics textbooks. This comment was initially a reply to Craig #124 and Shml #125 (see below) which I decided not post. But soon after I was reminded of Roger Penrose’s proposal, at which point I tried to include a reply to Scott #126, but still decided against posting. However, then I learned that it is not just me who has trouble to see effects of superconductivity as “obvious” QM predictions. From the recent post “The first Delft qubit” by Hans Mooij:
Shml #125: Regarding C60, I initially found it counterintuitive how the individual C atoms can have a 60 times bigger de Broglie wavelength than the entire C60 molecule. But some introductory QM books explain this: There is a canonical transformation to the center of mass frame, and the Hamiltonian (both classical and QM) stays the same under canonical transformations.
Craig #124: What exactly is counterintuitive about how transistors and other electrical components work? The band-structure, which can only be explained with QM? Or the actual working of the components, which can be quite diverse, and also includes thermodynamical aspects. (Notice that most components only work within a certain temperature range.)
Comment #157 November 9th, 2017 at 7:43 am
Gentzen,
Stuff like the band structure which can only be explained by qm is what makes transistors and other electronic components counterintuitive to me, only because qm is counterintuitive.
Comment #158 November 9th, 2017 at 10:38 am
I missed this bit of news, quite impressive:
“Today DeepMind, a London-based subsidiary of Google, announced that it has developed a machine that plays the ancient Chinese game of Go much better than its predecessor, AlphaGo, which last year beat Lee Sedol, a world-class player, in Seoul.
The earlier program was trained for months on a massive database of master games and got plenty of pointers—training wheels, as it were—from its human creators. Then it improved further by playing countless games against itself. But the new one, called AlphaGo Zero, received no training wheels; it trained itself all the way from tyro to grandmaster.
In three days.”
Comment #159 November 9th, 2017 at 5:55 pm
Craig #157: Fair enough, calling QM intuitive would be strange. My biggest trouble with the part of QM which I do understand is that exponential scaling behaviour which gives hope for quantum computing in the first place. As for the part which I don’t understand yet: “How do even the simplest interactions happen, like the Compton effect, i.e. the interaction between a single photon and a single electron?” … Well, you need quantum field theory to really compute that effect. But if you do it by handwaving, then you can even claim that it would be a prime example for the precise predictions of QM confirmed by experiment…
What if you just measure the band structure, then you don’t need to explain it by QM. Especially in cases where the QM computation of the band structure is significantly different from the experimentally determined band structure, only the later one is important anyway.
Comment #160 November 10th, 2017 at 8:29 am
Gentzen,
Thinking about it more, even batteries are counterintuitive to me. They always have been. Why should simply connecting a wire to both the anode and cathode cause electrons to rapidly move within in the wire? If the electrons really want to go from one side to the other, why can’t they just go through the battery itself? Why do they need a wire to move? I know that the answers to these questions are Chemistry and Physics 101, but these answers never have satisfied me intuitively.
Comment #161 November 25th, 2017 at 8:48 am
[…] Scott Aaronson on checking quantum supremacy without being able to simulate. […]
Comment #162 November 28th, 2017 at 10:37 am
Building a 50 qubit machine is like putting a man on Mars and sending him back to earth alive.
Building a 100 qubit machine is like putting a man on Jupiter and sending him back to earth alive.
The media doesn’t seem to get the significance of IBM’s claim of a 50 qubit machine.
Comment #163 November 28th, 2017 at 1:23 pm
Craig #162: It got a decent amount of coverage, but the problem with IBM’s announcement is that it was unaccompanied by any research paper giving technical specs or the results of experiments. It’s not the sheer number of qubits that matters: just as important is how long the qubits maintain their coherence and what you can do with them. So I’m waiting for an actual paper before doing a post about this (and the same for Google’s effort).
Comment #164 November 29th, 2017 at 11:38 am
Scott #163
The fact that IBM got away with announcing a 50 qubit machine without presenting any technical info is what disappointed me. I wish the media had pressed them for more info.
It’s like a big company like Boeing announcing that they sent a man to Mars and back to earth without any other information and the media reporting it like it’s no big deal, without asking any substantive questions.
I bet that IBM’s machine doesn’t work for all input and when they said they tested it, it only passed for some input. And I’m guessing that this is why IBM hasn’t released any more info other than that they built it and tested it.
Comment #165 December 14th, 2017 at 9:35 am
Just as I predicted:
https://www.bloomberg.com/news/articles/2017-12-14/ibm-taps-samsung-jpmorgan-daimler-in-quantum-computing-push
“IBM has also recently tested a prototype of a 50-qubit quantum computer – which is approaching a threshold known as “quantum supremacy,” where it may be able to perform calculations that are beyond the reach of a classical supercomputer. But it still produces errors.”
Comment #166 December 14th, 2017 at 10:34 am
Craig #165: Every superconducting QC chip, including the previous 9- and 22-qubit ones, “produces errors” before you spend a lot of time calibrating it. So this gives you no information one way or the other. But also, popular articles like these are such a garbled channel that I just disregard them and wait for the actual papers to come out. In this case, we’re still awaiting the paper, and I’m not a fan of IBM management’s decision to rush an announcement out before the research is ready.
In the meantime, though, the papers from IonQ and from Misha Lukin’s optical lattices group have come out, and they report very good results with up to 53 qubits, which I have no idea how you reconcile with your worldview.
Comment #167 December 14th, 2017 at 11:17 am
Scott #166
I think it is safe to conclude from the context of the article that “it still produces errors” means “it doesn’t work, even though they were expecting it to work by now”. But I agree with you that popular articles are not the best way of getting information, so I will wait for their actual scientific papers to come out.
As for IonQ and Misha Lukin’s group, are they trying to build universal quantum computers with 53 qubits or just do stunts with 53 qubits? My worldview says there is nothing preventing them from being successful performing stunts with 53 qubits; after all quantum mechanics is a pretty good theory, just not completely correct.
Comment #168 January 2nd, 2018 at 11:00 pm
[…] on the controversy are expressed in this November 14 column in Nature, which links this October 22 post by Scott Aaronson (see also his paper with Lijie Chen, “Complexity-Theoretic Foundations of […]