Three updates

  1. I was extremely sorry to learn about the loss of Joe Polchinski, a few days ago, to brain cancer.  Joe was a leading string theorist, one of the four co-discoverers of the AMPS firewall paradox, and one of the major figures in the Simons It from Qubit collaboration that I’ve been happy to be part of since its inception.  I regret that I didn’t get to know Joe as well as I should have, but he was kind to me in all of our interactions.  He’ll be missed by all who knew him.
  2. Edge has posted what will apparently be its final Annual Edge Question: “What is the last question?”  They asked people to submit just a single, one sentence question “for which they’ll be remembered,” with no further explanation or elaboration.  You can read mine, which not surprisingly is alphabetically the first.  I tried to devise a single question that gestured toward the P vs. NP problem, and the ultimate physical limits of computation, and the prospects for superintelligent AI, and the enormity of what could be Platonically lying in wait for us within finite but exponentially search spaces, and the eternal nerd’s conundrum, of the ability to get the right answers to clearly-stated questions being so ineffectual in the actual world.  I’m not thrilled with the result, but reading through the other questions makes it clear just how challenging it is to ask something that doesn’t boil down to: “When will the rest of the world recognize the importance of my research topic?”
  3. I’m now reaping the fruits of my decision to take a year-long sabbatical from talking to journalists.  Ariel Bleicher, a writer for Quanta magazine, asked to interview me for an article she was writing about the difficulty of establishing quantum supremacy.  I demurred, mentioning my sabbatical, and pointed her to others she could ask instead.  Well, last week the article came out, and while much of it is quite good, it opens with an extended presentation of a forehead-bangingly wrong claim by Cristian Calude: namely, that the Deutsch-Jozsa problem (i.e. computing the parity of two bits) can be solved with one query even by a classical algorithm, so that (in effect) one of the central examples used in introductory quantum computing courses is a lie.  This claim is based on a 2006 paper wherein, with all the benefits of theft over honest toil, Calude changes the query model so that you can evaluate not just the original oracle function f, but an extension of f to the complex numbers (!).  Apparently Calude justifies this by saying that Deutsch also changed the problem, by allowing it to be solved with a quantum computer, so he gets to change the problem as well.  The difference, of course, is that the quantum query complexity model is justified by its relevance for quantum algorithms, and (ultimately) by quantum mechanics being true of our world.  Calude’s model, by contrast, is (as far as I can tell) pulled out of thin air and justified by nothing.  Anyway, I regard this incident as entirely, 100% my fault, and 0% Ariel’s.  How was she to know that, while there are hundreds of knowledgeable quantum computing experts to interview, almost all of them are nice and polite?  Anyway, this has led me to a revised policy: while I’ll still decline interviews, news organizations should feel free to run completed quantum computing pieces by me for quick fact checks.

95 Responses to “Three updates”

  1. Nikhil Shagithaya Says:

    Regarding your question in the “Last Question” section on Edge, wouldn’t you say it is a bit vague? How would one even begin to objectively define ‘actionable wisdom’?

  2. Scott Says:

    Nikhil #1: Yes, of course it’s vague—but how could any question precise enough to be answered possibly be put forward as “The Last Question”? 🙂

    In retrospect, here’s something better that I could have asked: within the space of all, say, million-bit strings, how much better math can be found than Gauss’s, how much better music than Mozart’s, how much better dialogue than Shakespeare’s? I.e., how close have the actual limits of human creativity gotten to whatever is out there Platonically?

  3. Alex V Says:

    Cf.3., have you seen that paper?:

    “Efficient classical simulation of the Deutsch–Jozsa and Simon’s algorithms”
    https://link.springer.com/article/10.1007%2Fs11128-017-1679-7

  4. Peter Morgan Says:

    “Calude’s model, by contrast, is (as far as I can tell) pulled out of thin air and justified by nothing.” There, Scott, in the “as far as I can tell”, is your famous allusion to Kelvin’s “Clouds” speech. I have commented on the Quanta article.

  5. Scott Says:

    Alex #3: Yes, of course I’ve seen it. It’s also wrong—or rather, the result is egregiously and wilfully misstated. What’s actually shown there (assuming this part is correct) is that the Deutsch-Jozsa and Simon problems are efficiently solvable in a query model based on Spekkens’ toy model, which reproduces some features of quantum mechanics but not all of them. Crucially, though, this model can in no sense be called “classical.”

    Again, what justifies the usual classical query complexity model is that, if you had an efficient subroutine to compute f, then the model captures what you could actually compute using a classical algorithm that made a polynomial number of calls to the subroutine. Johansson and Larsson’s model has no similar justification of that kind. If a problem is efficiently solvable in their model, what does that mean for anything else?

    (And incidentally, it’s unclear that Simon’s problem is solvable in their model if we change the problem in quite trivial ways, like making the underlying group Z3n rather than Z2n. Not that that’s relevant to my main point above.)

    Now, based on past experience, I know many people reading this will come away with the impression that this is some sort of complicated disagreement between experts, and Scott obviously feels strongly about one side of it, but who else can say anything besides “teach the controversy”? Just to drive home the extent to which there are not two genuine sides here, let me offer a parable:

    Someone comes along and says that all the world’s mathematicians have been wrong for thousands of years, because there’s a new undiscovered integer between 4 and 5, called “Zeta,” equal to what had previously been called 4.5. And how we know that Zeta is an integer? Good question: because we’ve now defined it to be an integer! And why did we define it as such? Oh, just to refute the claim that all the integers from 1 to 10 had already been accounted for! Is any other reason needed?

    Yes, this does involve a bold new definition. But when you think about it, the hidebound reactionary mathematicians only claim that Zeta is not an integer because of some other definition of the word “integer” that they prefer. And who’s to say that one definition is “better” than another one?

    Then this gets respectful attention all over the popular science press, and people start emailing mathematicians to say that it must be right because there’s a published paper about it. Meanwhile, most mathematicians consider it beneath them even to respond to the Zeta claim, thereby feeding the perception in some quarters that it must be legit because no one has publicly refuted it. The people both able to see Zeta for what it is, and willing to do so in public under their own names and deal with any blowback that results, can be counted on the fingers of one hand, with the thumb and index finger to spare. And they are overworked, and they are tired.

  6. Craig Gidney Says:

    Your reaction to the Quanta piece exactly matched mine.

    “Okay, great, you defined a model where you can get multiple results from one query. But to implement that model on a physically realizable computer you would have compute the function twice so… how is this relevant?”

    I also happen to think that, because querying a black box on a quantum computer often involves computing *and uncomputing* the blackbox function, that quantum computers should have a factor of 2 starting penalty on the query count. So having a quantum computer for the Deutsch problem isn’t *really* guaranteed to save a function evaluation. You only do one query but in general a query may require two evaluations: one to compute, one to uncompute.

    Of course that objection is handily demolished by algorithms which have asymptotic improvements to the query count, such as Deutsch-Jozsa and Grover.

  7. jonas Says:

    That’s a nice list of questions, thank you for pointing to them. Some of them are often asked, and even asked multiple times in that list. I particularly like the questions by Dorsa Amir (how our brain is implemented), Albert Wenger (a specific question about human future that I haven’t heard asked in this precise form), and Kate Darling (about society).

  8. Richard Gaylord Says:

    “When will the rest of the world recognize the importance of my research topic?” Dammit! that was my question. ROFL

  9. Isaac Says:

    One nice thing that I would love to see is a Scott Aaronson’s answer for each of the “Last Question” questions. Instead of the “ask me anything”, you could give it a try.

  10. AJ Says:

    There is also a 1998 paper which Calude refers to ‘Probably the simplest and most frequently used way to illustrate the power of quantum computing is to solve the so-called Deutsch’s problem. Consider a Boolean function f: {0,1} → {0,1} and suppose that we have a (classical) black box to compute it. The problem asks whether f is constant [that is, f(0) = f(1)] or balanced [f(0) ≠ f(1)]. Classically, to solve the problem seems to require the computation of f(0) and f(1), and then the comparison of results. Is it possible to solve the problem with only one query on f? In a famous paper published in 1985, Deutsch posed the problem and obtained a “quantum” partial affirmative answer. In 1998, a complete, probability-one solution was presented by Cleve, Ekert, Macchiavello and Mosca. Here we will show that the quantum solution can be de-quantized to a deterministic simpler solution which is as efficient as the quantum one. The use of “superposition,” a key ingredient of quantum algorithm, is — in this specific case — classically available.

    Read More: http://www.worldscientific.com/doi/abs/10.1142/S021974990700292X‘ which gives a probability 1 solution to Deutsch’s problem.

  11. Jay Says:

    So you think Calude’s work may be right but in any case it’s grossely misspresented. Or you think it’s also wrong?

    If that’s the former, do you see any distinction between this sort of proof and proving that property X does not hold relative to special oracle Y?

  12. Nikos Pitsianis Says:

    A flying saucer lands on top of the UN building. The UN sends three theoretical computer science professors to communicate with the aliens.

    The professors enter in the flying saucer and they are greeted by a robot that tells them:

    — People of Earth, ask me a single question and I shall answer it.

    The professors consult with each other on what will be that single question and at the end they agree and ask the following:

    — What is the best one question we can ask you and what is the answer to it?

    The robot blinks its lights and after some time responds:

    .
    .
    .

    — The best question to ask me is the one you have just asked, and the answer to it is this one.

  13. Scott Says:

    Craig Gidney #6: Yes, a factor-of-2 starting penalty for quantum algorithms is fair, as long as the quantum algorithms are being used as subroutines for other quantum algorithms. At the “topmost” level—the level where you actually measure to observe the output—you don’t need to pay that factor-of-2 penalty. (This is the reason why Deutsch-Jozsa doesn’t give you more and more factors of 2 for computing the parity of n bits, if you divide the bits into blocks and recursively compute a parity of parities of parities etc.—why you only get a single factor of 2 for the whole thing.)

    Deutsch-Jozsa to decide whether a function is constant or balanced is actually again not a very convincing example of speedup, but in that case, the reason is that there’s a classical probabilistic algorithm that does essentially as well.

    But then there’s Grover, Simon, Shor (period-finding), Forrelation, Recursive Fourier Sampling, quantum walk algorithms … we have no shortage of quantum algorithms that get asymptotic speedups in query complexity compared to the best classical randomized algorithm. (These speedups can be exponential or even larger, in contrast to speedups in computational complexity, which are always at most exponential.)

  14. Scott Says:

    AJ #10: I can’t access the article, but from the abstract, that doesn’t sound like an additional claim—it’s the same claim that I just demolished, published in an additional place.

  15. Scott Says:

    Jay #11:

      So you think Calude’s work may be right but in any case it’s grossely misspresented. Or you think it’s also wrong?

    There’s an extremely popular realm where wrongness and triviality meet. In that realm, you make an astounding and wrong claim in the abstract of your paper. The abstract is of course the only thing that 99% of people will ever read, what will get discussed in the popular science press, etc. etc. Then, in the body of your paper, you modify the wrong claim to something that’s true but trivial, by changing the definitions of words. For example: you broaden the definitions of “classical” or “local,” to encompass things that anyone else would call “non-classical” or “non-local.” If anyone ever challenges you about the astounding and false claim, you can simply retreat to the true but trivial claim, then return to the false claim after they go away. And for extra bonus points, you criticize the criticizer for having failed to grasp the paradigm-smashing enormity of your redefinition.

    Note that this is exactly what Scott Alexander popularized a few years ago as the motte and bailey fallacy, except for technical subjects rather than political/ideological ones.

      If that’s the former, do you see any distinction between this sort of proof and proving that property X does not hold relative to special oracle Y?

    You have to be kidding me. The difference is clarity. The difference is that no one writes an abstract claiming to separate complexity classes in the unrelativized world, if they really just prove an oracle separation. Or if they did, then I’d criticize them as harshly as I’m criticizing these papers.

    Also, most oracle separations have actual technical content. In some cases, like Bouland et al.’s recent oracle separating SZK from PP, or the collision lower bound, or for that matter the original BBBV Theorem, people spent some real effort trying to prove the opposite and failed—so having the oracle separation gives you nontrivial information about what kinds of algorithms can or can’t exist. That’s not the case, for example, with the claim that you can compute the parity of 2 bits with 1 classical query by changing the meaning of “classical query” in a way tailor-made for that purpose—something that anyone could shruggingly assent to, once they understand that that’s the claim.

  16. Scott Says:

    Nikos #12: That’s an extremely old joke, which you seem to have changed only by subbing in “theoretical computer scientists” for whichever other experts were supposed to receive their comeuppance. And to whatever extent we laugh at the experts for having egg on their faces—well, to that extent, we’re simply conceding that the robot failed to uphold its end of the bargain!

  17. GMH Says:

    Given your previous post on “Interpretative cards” and the exchange with Maudlin, it looks like another “last question” might be: “To solve a problem in quantum mechanics, when do you apply linear evolution, and when the Born rule?” Would that question be more or less tractable than the one you asked? If one of them is a matter that really should be left to God and the angels, which one?

  18. James Cross Says:

    I always liked Asimov’s answer:

    How the threat to human existence posed by the heat death of the universe can be averted?

    The end of the story described by Wikipedia.

    “In the last scene, the god-like descendant of humanity (the unified mental process of over a trillion, trillion, trillion humans that have spread throughout the universe) watches the stars flicker out, one by one, as matter and energy ends, and with it, space and time. Humanity asks AC, Multivac’s ultimate descendant, which exists in hyperspace beyond the bounds of gravity or time, the entropy question one last time, before the last of humanity merges with AC and disappears. AC is still unable to answer, but continues to ponder the question even after space and time cease to exist. Eventually AC discovers the answer, but has nobody to report it to; the universe is already dead. It therefore decides to answer by demonstration, since that will also create someone to give the answer to. The story ends with AC’s pronouncement,

    And AC said: “LET THERE BE LIGHT!” And there was light.

  19. Scott Says:

    GMH #17: I would say that, in 90 years of people using QM, it’s never once been unclear in practice when to apply linear evolution and when the Born rule to solve a problem. And the reason is simply that, if a “problem” is clear and unambiguous enough to put on a homework set, then the problem is almost certainly ultimately about what “you” would see if you measured something! I.e., the very phrasing of a problem as a problem gives you the split that’s needed. “What would it feel like to be manipulated in coherent superposition?” is not a “problem” for which I’d want to be the professor who has to give the TAs the grading rubric.

  20. Craig Gidney Says:

    Alex #3: After reading the paper you linked, I don’t think they simulated what their proposed QSL system actually does. I think their claims about it are simply wrong.

    For example, they say that a QSL bit is made up of two bits. One for the Z-axis value of a qubit and one for the X-axis value of a qubit. But this isn’t going to behave at all like a proper qubit, because it would imply that qubits have well-defined X and Z axis values simultaneously.

    In the paper, they prepare |0> by setting the Z bit to 0 and the X bit to a random value. This is not correct. Both possible random values are wrong. What they need is an abstract variable x_1 representing “What would I get if I measured along the X axis”, as is done when simulating stabilizer circuits. They need to keep track of this variable and where it ends up in order for measurements of one qubit to affect entangled qubits correctly.

    More seriously, the paper’s construction of a QSL toffoli completely ignores phase kickback. They even *say* they’re ignoring what happens to the phase bits, and just using an identity operation instead. That’s a bit like saying you’re going to make a unicycle but without the wheel. Without the phasing effects, the algorithm won’t work correctly.

    Here is what I think their algorithm *actually* does:

    a) prepare a bunch of 0 bits [the Z values], and a bunch of random bits [the X values]
    b) swap the 0 bits with the random bits [first column of Hadamards]
    c) evaluate a function on the random bits, and toggle some unrelated bit if the function outputs true [this is the oracle evaluation]
    b) swap the random bits for the zero bits [second column of Hadamards]
    e) return the zero bits

    That’s right, their algorithm always returns 0. Which is why I don’t think they actually tried to run it.

    I feel like I must be reading this paper wrong, or missing some fundamental concept, because if not I have no idea how it made it past peer review.

  21. Jay Says:

    Scott #15,

    LOL! You made an excellent job at making me feel how wrong the misrepresentation is. Very funny 🙂

    However I’d also be interested in understanding why their result is trivial. Absence of clarity does not count. Not having actual content definitly counts, but explaining why some famous results have content does not clarify why this one hasn’t.

    More to the point, here are two interpretations my layman mind could come up with:

    First, it could be that their model is actually the same as working with the real while not taking the noise into account. Of course this would be a model for hypercomputation. Of course proving DJP easy when your model allows hypercomputation is kind of unsurprising.

    Second, it could be that no, their model does not allow hypercomputation, it’s more subtle: basically it’s QM minus entanglement. Then the proof may still be trivial to experts, but it could actually help me understand that QM is an overkill for DJP.

    Of course it’s probably a third explanation that I can’t reach yet, if then I would be glad to learn. 🙂

  22. Mitchell Porter Says:

    Re Edge question: Scott once again lives up to the responsibilities that come from being alphabetically first.

  23. Sniffnoy Says:

    So, Scott, since this appears to be something of a multi-topic thread, can Josh and I pester you with questions about this NQP not contained in ACC result? 🙂

  24. Scott Says:

    Sniffnoy #23: No, because I haven’t studied it. I have no doubt that it’s great.

  25. Sniffnoy Says:

    Scott #24: Hah, that’s what I figured was probably the case, but I thought I’d ask again anyway. 😛 (Also uh would you mind deleting my other stuck comment so it doesn’t screw up my numbering? Thanks!)

  26. Scott Says:

    Jay #21:

      However I’d also be interested in understanding why their result is trivial.

    I mean, just look at the paper (specifically, like a half-page of … [controlling myself] [deep breath] … rather easy manipulations in Section 3, which is the only part that’s relevant). Then compare to anything that’s done in real quantum computing theory—for example, any talk that’s ever been given at the annual QIP conference, which I doubt would even have allowed this in the poster session. Can you not just see the difference?

  27. Peter Morgan Says:

    It took forever for Quanta to post my comment there, but finally it’s up.
    Clouds, Scott, clouds. There’s a principled story that underlies the very specific models of Calude, Eberly, and others; each in isolation may look like almost nothing, but quantum computing hardware is just one of the possible physical and mathematical models for “Hilbert computing”. Clouds can be ignored, of course.
    Consider that for classical physics, the standard story is that classical physics has a commutative algebra of observables, generated by position and momentum, so therefore (because, say, Landau (1987, https://doi.org/10.1016/0375-9601(87)90075-2), and Baez (1987, https://link.springer.com/article/10.1007/BF00955201), but there are some others) Bell inequalities cannot be violated and there’s no entanglement.
    Alternative story, starting with Koopman-von Neumann presentations of classical physics, so almost 90 years ago, classical physics has a 𝑛𝑜𝑛commutative algebra of observables, generated by position, momentum, 𝑎𝑛𝑑 the Poisson bracket (for which see Appendix A in the paper I linked to above). If the algebra of classical observables is noncommutative, then, when we construct a representation, Bell inequalities can be violated and there is entanglement.
    More specifically, in QFT, what led me to the story just above is that the vacuum state representation of the algebra generated by the quantized EM field, a bivector-valued operator-valued distribution F(x) —for which [F(x),F(y)]=0, in general, only when x and y are space-like separated—, contains a “hidden” classical random field subalgebra generated by a bivector-valued operator-valued distribution 𝔽(x) —for which [𝔽(x),𝔽(y)]=0 for all x and y, even at time-like separation—, with the “alternative story” above leading to a noncommutative algebra of classical observables. This is easy when you see how, but it’s not at all obvious, and no-one has looked for it, so it took 90 years for me to stumble over it (not that I do it 𝑤𝑒𝑙𝑙, you’ll still have to do some work to understand how it works, but some good mathematician will do it well soon enough).

  28. Richard Gaylord Says:

    Comment #12 – i don’t understand. the alien offers to answer ONE question, the professors ask the alien TWO questions (expressed in a single sentence), and the alien answers BOTH questions. are the alien and the professors all innumerate?

  29. Scott Says:

    Richard #28: The problem is that “asking ONE question” is not a well-defined constraint. E.g., they could’ve asked, “if we had asked you (question1,question2), then what ordered pair (answer1,answer2) would you give us back?”

    (Source: discussion of genies with other nerdy kids, circa age 8 😀 )

  30. Alex V Says:

    Craig Gidney #20, Thank you for comment. I am not ready to talk about formal correctness. My initial trouble was rather about a way of formulation of the result. For me the way used by Calude was less troubling, but I may be biased, because I knew him a bit.

  31. Alex V Says:

    Craig Gidney #20: PS. I may not find that on the journal cite, but there is a python program in arXiv version of the paper: https://arxiv.org/abs/1508.05027 May be it could help, but right now I need finish my own paper and simulations.

  32. Jan-Åke Larsson Says:

    Perhaps Scott is thinking of the unpublished first draft of the paper, that did contain statements of the kind he is describing. In the published version, we have taken Scott’s earlier comments to heart and describe the QSL simulation of a quantum algorithm as an intermediate step, then noting that “these QSL algorithms are in turn efficiently simulatable in classical Turing machines.” This is the claim.

    As for being trivial, well, we aimed to make the model as simple as possible. The end result is indeed very very simple. The long description was needed to make the input-output map very very clear. Referees have a tendency to not believe that the behavior is possible at all, unless the description leaves no escape.

  33. Peter Morgan Says:

    Thanks for the stimulus, Scott, and for allowing my posts in moderation. It’s become clearer to me how specifically quantum field theoretic my concerns are, and therefore perhaps rightly no concern of yours, particularly because, in loosely category theoretic terms, the tensor product is arguably not available in QFT (composition of operators is sufficient; there’s no tensor product in the Wightman axioms, for example), whereas the tensor product is critical for many approaches to quantum computation.
    Taking the tensor product as an organizing principle, the apparent lack of a tensor product or some other systematic means of generalizing to higher dimensional linear spaces seems to me a significant limitation of Calude’s linear algebraic models, indeed to make it inequivalent to quantum computation, but not to rule out considering it seriously as a bellwether.
    In QFT the problem is rather the other way round: how do we systematically construct physical systems that are FAPP usefully modeled by algebras of operators that have finite dimensional Hilbert space representations. That’s especially a problem because we too little understand interactions in QFT, whereas we have to engineer interactions to give us FAPP isolated and confined systems. But hey, something to do out in the wild world.

  34. Richard Gaylord Says:

    scott comment #29 – if the Mueller team can phrase their questions as cleverly as you, they’ll be sure to catch Trump in a lie. actually, just asking their questions in english, or even saying nothing at all and just letting Trump go on and on, should be sufficient to accomplish that.

  35. Jay Says:

    Scott #26 #15, Ok thanks for the discussion.

  36. Jim Graber Says:

    arXiv:cs/0610153
    Most Programs Stop Quickly or Never Halt
    Cristian S. Calude, Michael A. Stay

    So is this paper also misleading, or does it mean what it says?
    And is it interesting or trivial?

    Coincidentally recently referenced in John Baez — Pyrofex
    TIA
    Jim Graber

  37. Arnab Says:

    It would be amiss not to mention Polchinski’s gut-wrenchingly honest autobiography, written after his cancer diagnosis: https://arxiv.org/abs/1708.09093

  38. Craig Gidney Says:

    Alex #31: After looking over the python code and getting it to run on my machine, here’s my conclusion.

    All the example code really does is simulate Hadamards and Paulis and CNOTs. It does fine on that. But restricting yourself to that gate set makes it trivial to solve the problem classically. To actually test it out, we need Toffolis. Which the code does not include.

    So I took the Toffoli described in the paper, and added it to the code. According to the paper, we implement a Toffoli by completely ignoring the phase bits and flipping the target X bit if the two control X bits are on. Like so:

    def toffoli(state, c1, c2, target):
    “””Flip the X bit of the target if both control Xs are on.”””
    if state[0] & (1 << c1):
    if state[0] & (1 << c2):
    state[0] ^= 1 << target

    With that in hand, I implemented a balanced function:

    def balanced_with_toffoli(state, c1, c2, c3, target):
    """Flips the target if exactly 1 or 3 of the controls are on."""
    toffoli(state, c1, c2, target)
    toffoli(state, c1, c3, target)
    toffoli(state, c2, c3, target)

    Then overwrote the contents of 'Ufbalanced' to use my function:

    def Ufbalanced(state, perm):
    balanced_with_toffoli(state, 1, 2, 3, 0)

    And ran the simulation with some additional print lines. I set n to 3 and made sure it was using Ufbalanced:

    Deutsch-Jozsa:
    [0001, 1110] initial
    [1110, 0001] after hadamards
    [1111, 0001] after oracle
    [0001, 1111] after hadamards
    000 measured
    Constant

    I ran it several more times, and the code continued to claim that my balanced function was constant. I can tell it's using my function because I can see the X bits being updated according to it.

    Not working for toffolis means the code doesn't work period. Oracles often require Toffoli gates. For example, the oracle "flip the target when the input k satisfies 11 <= k < 2^(n-1) + 11" can't be implemented with just CNOTs. If you can't simulate Toffolis, you can't simulate Deutsch-Josza.

    In conclusion:

    – The code does work when you limit the oracle to CNOTs.

    – The Toffoli construction from the paper is wrong.

    – The algorithm fails on most oracles, and therefore the claims about efficient classical simulation are wrong.

  39. Scott Says:

    Jim #36: That paper actually looks really cute, and like something I’d enjoy reading (I will read it if I have time). The results all seem extremely simple, but I didn’t see off the top of my head how to prove them. Certainly this paper doesn’t do anything like what the other paper does, claiming that a whole field is wrong about one of its basic examples because of an idiosyncratic redefinition of words.

    Even strong researchers can sometimes write papers that are stinkers (and vice versa…), so you really do need to judge things by their merits rather than their authors. This is also a good illustration of why we have a peer review system (though keep in mind that in CS, conferences are more important than journals, and also, pretty much anything can get in to some conference or journal).

  40. Scott Says:

    Craig #38: Thanks so much for your investigation of this!

  41. Job Says:

    Craig’s result makes sense to me.

    I’ve tested something like QSL in the context of Simon’s problem by scanning over all possible Simon’s circuits of fixed width/depth (with no ancilla bits).

    QSL does surprisingly well even in Simon’s problem because it essentially allows you to run the input function backwards.

    I’ve found that, if you run a Simon function in reverse, on a random value, you can reliably get an output that’s orthogonal to the secret value, depending on gate set.

    In my tests, it always works if the gate set is restricted to CNOT. However, and more importantly, it still works most of the time even when Toffoli gates are added.

    The exceptions were circuits in which Toffoli gates were arranged to compute the majority function of n bits – which is what Craig’s circuit does.

    And that’s using a more adequate Toffoli implementation, which doesn’t ignore the phase bits (i.e. on the phase side, it does two CNOTs from the target bit to each of the control bits).

    I have some understanding of why it fails, and i don’t expect something like QSL to be able to solve what is essentially a modified version of Simon’s problem, where the solver can peek into the black box one gate a time.

    However, if you could solve that version of Simon’s problem, it would still be a significant result IMO.

    This classical vs quantum boundary, that’s so apparent in Simon’s problem is what interests me the most.

  42. Scott Says:

    Jim #36, addendum to #39: Actually, now that I read that paper more carefully, unless I’ve misunderstood something there’s a serious issue that makes it far less interesting than I thought. Namely, the authors advertise their result as “most programs either halt quickly or else run forever.” But they don’t prove such a statement for any natural probability distribution over programs, such as the uniform distribution. Instead, they prove it only for a distribution that they specificially construct to make the statement true!

    Having said that, a paper about halting programs being coauthored by a guy named Mike Stay is a charming instance of nominative determinism.

  43. COLIN BENJAMIN Says:

    Dear Scott,
    Regarding the article in Quanta by Ariel Bleicher, we in the following work have dealt directly with this aspect.
    Kindly have a look at the following paper: “Do quantum strategies always win?” by N. Anand and Colin Benjamin, Quantum Information Processing, Volume 14, issue 11, pp 4027-4038 (November 2015),https://doi.org/10.1007/s11128-015-1105-y, also available at arXiv:1412.7399.

    In the aforesaid work we challenge the notion that quantum strategies are always better than classical strategies. Ariel’s commentary did not take our work into consideration but we hope that you find our work useful.

  44. Scott Says:

    Colin #43: First of all, quantum game theory is a very different subject from quantum computation (the subject of Ariel’s article). In quantum game theory, everything comes down to the definitions, to such an enormous extent that I can barely understand it. But secondly, I’m having trouble thinking of a single field in which quantum strategies, algorithms, or protocols are always better than their classical parts—or of a quantum information proponent, even the most irresponsible and hype-prone, who’s ever made such an extravagant claim. Typically, the hope with quantum information is sometimes to do better than the best classical strategy, and for the “sometimes” to include cases that someone might actually care about.

  45. Jan-Åke Larsson Says:

    Craig #38 The simulation does work for the construction used in the paper, where the Toffolis are used to build the permutation of fig. 4. It is correct that the construction does not work for every gate array that corresponds to a certain function. But there are even quantum unitaries that give the correct function map in the computational basis, but give the wrong phase relation, and subsequently the wrong output for these algorithms. We give an example in Section 5 of our paper in which the quantum unitary has the correct function output, but for which the quantum D-J algorithm gives no information about the function, just as your example for QSL above. One phase rotation is enough. When taking this possibility into account, most quantum unitaries that give the correct function map give the wrong phase relation, similar to QSL. It is extremely important that the phase relation is preserved in the quantum unitary, which is part of the difficulty of building a quantum computer.

    Mapping this into our model, we find that “The QSL framework presented above is deliberately chosen as simple as possible, …. A direct consequence of this simplicity is that the phase relation requirement of quantum computation, that enables phase kick-back, is translated into a simple requirement on the QSL oracles, presence or absence of a CNOT between query- and answer-register.” This is the reason the simulation only works for the construction used in our paper.

    We do have another more advanced version of the QSL Toffoli in the works, that eases the rather harsh requirement on oracle structure, and enables small instances of Shor and Grover to be run in QSL. Only small instances, mind, we do not expect to be able to factor efficiently. Our intent is to learn more on the resources used in a quantum computer, learn more about what is the real difficulty in building a quantum computer. As far as is possible.

    And we agree wholeheartedly with Scott #44: Typically, the hope with quantum information is sometimes to do better than the best classical strategy, and for the “sometimes” to include cases that someone might actually care about.

  46. Jim Graber Says:

    Hi Scott,
    Thank you very much for checking out the Calude Stay paper, which I just learned about and am just starting to try to understand. But clearly the secret, good or bad , is in the measure. And of course you can devise measures where the odd numbers are much more common than the even numbers or vice versa.
    A similar paper which I have been aware of longer is Hamkins and Miasnikov, The halting problem is decidable on a set of asymptotic probability one, arXiv:math/0504351. The weakness here, which H&M point out is that it only applies to Turing machines with semi-infinite tapes.
    ((A very old joke: All of mathematics is trivial or untrue.))
    Nevertheless I wonder if Calude-Stay and Hamkins-Miasnikov are still true (although unproved) for more reasonable measures.
    That is, the average proof is short, and long proofs (as well as Goedel-Rosser statements and busy beavers) are rare.
    Semi-evidence for this speculation comes from Wolfram’s search for the minimal universal Turing machine as well as the busy beavers work.
    I don’t even know what is known or widely believed on the question of typical proof lengths (or typical halting times) despite having googled around and being aware of (but not claiming to understand) references such as Plaisted and Zhu and also Kroening and Strichman.
    Any other good references or further thoughts?
    Thanks again and TIA
    Jim Graber

  47. eot Says:

    Dear Scott, did you see this paper?

    ‘Simulating boson sampling in lossy architectures’ ( arXiv:1712.10037 )

    “Losses are probably the most damaging imperfections challenging boson sampling. Despite its importance, little is know about the resilience of boson sampling to losses, except that it remains hard in the regime of a constant number of lost photons. In this work we show that all current architectures that suffer from an exponential decay of the transmission with the depth of the circuit, such as integrated photonic circuits or optical fibers, can be nearly efficiently simulated classically. Either because the depth of the circuit is large enough that it can be simulated by thermal noise with an algorithm running in polynomial time, or the depth of the circuit is short enough that a tensor network simulation runs in quasi-polynomial time.”

    I know that you replied to comment that was long similar lines (exponential loss in photon numbers gives exponential running time of a boson sampler), and your reply was something like that boson sampling might become fault tolerant in the future. To me though, it seems like the only way to introduce fault tolerance is some kind of feed forward and then you’re not in linear optics anymore. Or to have loss that doesn’t scale exponentially (how?).

    Of course this paper doesn’t say you can’t make a specific instance of a boson sampler that cannot be simulated by any available classical computer (that might happen), but it seems to question the asymptotic scaling.

  48. Scott Says:

    Jim #46: If we consider (say) theorems of ZF set theory that are n bits long, then the average length of their proofs will be mind-bogglingly enormous. But that’s like Christos Papadimitriou’s quip that the average net worth of his coauthors is more than $1 billion. (One of them was Bill Gates, then a freshman at Harvard.) In the ZF case, the average will be dominated by the few theorems—which we know to exist by an argument of Gödel—whose shortest proofs have Busy Beaver length.

    So presumably we really want to be asking about the median proof length of an n-bit theorem—or analogously, and for exactly the same reasons, the median time taken by an n-bit halting program to halt. In this case, the answer could depend a lot on messy details of how you do the enumeration, but I could easily believe it’s extremely small: O(n) or maybe even O(1). I don’t know what that tells you about anything else, but it would be fun to work it out if no one’s done so already. Anyone have ideas?

  49. Scott Says:

    eot #47: Sure, I saw that paper. Look, I don’t think any QC architecture has acceptable asymptotic scaling in the absence of fault-tolerance. With BosonSampling, the idea has always been

    (1) if you could do it near-perfectly (say, using fault-tolerance), then there are very interesting arguments that you’d doing something classically hard, and

    (2) even in the world of the near future, where you’re not going to do it near-perfectly, you might be able to do it with 50 or 60 photons well enough to get a clear speedup over the best classical simulations known or believed to exist.

    We’ve never claimed more. (Note also that, even if you could scale BosonSampling to arbitrary photon numbers, as far as we know it wouldn’t be good for anything, among other reasons because we’d no longer know how to verify the answers classically!)

    If you care about more detailed numbers, as long as the beamsplitters don’t need to be nearest-neighbor, I see no reason why BosonSampling shouldn’t be classically hard with a beamsplitter network of depth ~log(n). If BosonSampling remains hard with a constant fraction of lost photons—something we don’t yet know, but which is consistent with current knowledge—that would mean that to solve a classically hard problem, it would be enough to get the loss rate down to ~1/log(n) per beamsplitter, which looks like it could be achieved with plenty of margin to spare for the range of n’s we’re talking about. Or is there something in the Garcia-Patron et al. paper that suggests otherwise?

  50. COLIN BENJAMIN Says:

    Scott, on your reply to my comment #43, I have to disagree that quantum game theory and quantum computation have nothing in common. After all quantum game theory or game theory in general has two or more players competing against each other via quantum or classical strategies. These strategies are nothing but quantum algorithms with a finite number of steps to perform a desired action in lieu of some payoffs at the end. In fact quantum game theory can be seen as a test bed for quantum vs classical algorithms or quantum vs quantum algorithms, in order to find out which one is better at a certain task.

  51. Scott Says:

    Colin #50: I didn’t say they had nothing in common.

  52. asdf Says:

    There’s another paper by Calude and Jürgensen claiming that almost all arithmetically true statements are unprovable, over a reasonably natural distribution based on the lengths of the statements.

    http://www.cs.auckland.ac.nz/~cristian/aam.pdf

  53. clayton Says:

    Scott, how do you feel about 1802.02175, appearing on the arXiv tonight, which claims to be based mainly on work you did but did not publish?

  54. Scott Says:

    clayton #53: Lenny asked me, and I happily gave him my blessing to post that. It feels like a huge weight off my shoulders.

    After I’d dragged my feet for two years with writing our paper, and Lenny (who at more than twice my age has more than 50 times my energy) got more and more impatient with me, I had no right whatsoever to tell him not to post whatever the hell he wanted!

    I haven’t read Lenny’s current manuscript carefully to see if there’s stuff in it that I disagree with. That’s completely intentional—if I did read it, I’m sure I would find some stuff to quibble with, but then I’d drag my feet on providing the necessary revisions for another two years!

    Instead, I’m simply hoping that once the pile of stuff that I’ve been suffocating under clears up enough that I can breathe, I’ll write up the results more formally and then we’ll put both of our names on the resulting paper.

    In the meantime, if you’d like to read my version of these results, then please see Chapter 7 of my Barbados lecture notes—it’s pretty much all there.

  55. clayton Says:

    Scott #53: very cool! I wondered about the connection to the Barbados lecture, but I’m glad to hear that nothing unhappy is happening behind the scenes

  56. The last questions | Alec Nevala-Lee Says:

    […] to just restate one of their research targets, albeit succinctly.” The computer scientist Scott Aaronson wrote on his […]

  57. Craig Gidney Says:

    Jan-Åke Larsson #45: I guess I don’t understand the point of the paper if QSL can only simulate such a limited gate set with so many restrictions around how they can be used.

    Stabilizer simulations could efficiently simulate larger gate sets over a decade ago, without such restrictions. What does QSL do that GraphSim couldn’t do in 2005?

  58. John Sidles Says:

    Scott deposes (circa #49) I don’t think any QC architecture has acceptable asymptotic scaling in the absence of fault-tolerance … We’ve never claimed more.

    Searching my own BibTeX database for comparable assertions, I found no such statement in the peer-reviewed literature prior to September 2017, when Aram Harrow and Ashley Montanaro’s Nature survey article “Quantum computational supremacy” opined:

    The question of how to model simulability in the presence of noise is subtle and still under debate. […] Quantum-supremacy experiments may need to make use of some form of error correction, but this might be substantially simpler than the machinery required for full quantum fault-tolerance. […] In these early days of the field, the focus on quantum supremacy is a way to ensure that quantum computers solve clearly defined problems for which the classical competition can be well understood.

    It’s lamentable that Harrow and Montanaro’s Nature survey does not stipulate which “classical competition” quantum simulation algorithms can reasonably be regarded as “well understood.”

    Instead, it’s far from obvious (to me anyway) that “classical competition” algorithms are well understood by anyone. As Cristian Calude rightly says in a recent Quanta article (hopefully in the part of the Quanta article that Scott calls “quite good”):

    Most of the time when people talk about quantum computing, classical computing is dismissed, like something that is past its prime. But that is not the case. This is an ongoing competition.

    Even today, does there exist anywhere in the peer-reviewed Quantum Supremacy literature, any explicit acknowledgement that scalable demonstrations of Quantum Supremacy plausibly may require scalably fault-tolerant general quantum dynamics? Such that, in the absence of experimental demonstrations of scalably fault-tolerant quantum dynamics, and in the presence of ongoing improvements in classical simulation efficiency, it is entirely plausible that demonstrating Quantum Supremacy, in any form whatsoever, will prove to be infeasible, now and forever?

    In summary, when it comes to the feasibility vs infeasiblity of demonstrating Quantum Supremacy, neither side’s “bailey” is secure, and the fertile “motte” of quantum knowledge extends farther than either side can reasonably see.

  59. David Speyer Says:

    Since people are talking about Calude-Jurgensen, maybe people can help me understand it. Nine years ago, the paper asdf links came up in this Mathoverflow thread and I argued that it couldn’t be true. For a grammatical sentence X in some formal theory, let f(X) be the sentence “0=0 or X”. Every sentence of the form f(X) is provable. I argued that, for any reasonable probability distribution on grammatical sentences, a positive proportion of them are of the form f(X).

    I couldn’t follow the definition of the distribution in the Calude-Jurgensen paper, so I couldn’t nail down the issue for certain, and writing Calude didn’t clarify matters. It could be that I am making some basic error. Can anyone clarify this issue for me? Or just suggest some natural probability measure for which this issue (and easy variants of it) don’t arise?

    It seems to me the same same issue also applies to Scott’s comment 48. I have no idea about the median ZF theorem, but some positive proportion of ZF theorems should be of the form f(X). Analogously, some positive proportion of Turing machines should execute the algorithm “If 0=0, halt, else (arbitrary code block).”

    Are there any good ways to avoid these issues?

  60. David Speyer Says:

    My third paragraph should have pointed out explicitly that f(X) has a proof of length O(|X|).

  61. fred Says:

    Scott,

    will a Quantum Computer give any sort of advantage for bitcoin mining?
    And if so, where can I buy two dozens of them?

  62. fred Says:

    Scott,

    regarding Boson Sampling, is it conceivable that nature made it so that quantum supremacy exists only for non Turing complete systems?

  63. Scott Says:

    fred #61: You’re about the 5000th person to have asked. I’ll give you the same answer I gave everyone else, which is to read this recent survey. Long story short:

    (1) Sure, a QC could give you a square-root (Grover) speedup for the proof-of-work involved in bitcoin mining, though almost certainly no more than that.

    (2) If you’re the only entity in the world with full fault-tolerant QCs, this could give you a significant advantage. If a bunch of entities have QCs that they use for bitcoin mining, then the hardness parameter automatically gets adjusted to compensate and we’re right back where we started.

    (3) If people cared about this, there are simple ways they could modify the proof-of-work to reduce QCs’ advantage for it, probably to where it no longer mattered at all.

    (4) With bitcoin as it now exists, the biggest threat from QCs actually involves the signature scheme (i.e., the way you prove that given bitcoins are under your control), which is currently based on elliptic-curve crypto and is therefore fully breakable by Shor’s algorithm. Again, if people cared enough, they could migrate that aspect of bitcoin to quantum-resistant signature schemes.

    (5) None of this is going to be relevant in what John Preskill calls the “NISQ era”—i.e., the coming era of noisy, non-fault-tolerant intermediate-scale QCs, with 50 to a few hundred qubits. It only really starts to matter in the era of full fault-tolerant QC, whose date of arrival is left to the reader to determine.

  64. Scott Says:

    fred #62: Sure, a priori it’s conceivable that the class of feasible problems in the physical world could exceed BPP (or its sampling analog), while still not being all of BQP—I think that’s tantamount to what you’re asking.

    It’s just hard for me to see any such scenario that’s consistent with what we already know. E.g., we know that it’s possible to get outside the “self-contained little playground” defined by BosonSampling, by simply adding nonlinear elements or feedforward measurements to your optical network. Similarly for IQP, DQC1, and the other non-universal models. Of course, every resource you add makes the engineering requirements all the more demanding, which is why it’s plausible that we’ll see non-universal quantum supremacy well before we see universal QC. But given what’s already been demonstrated, I personally don’t feel like there’s any mathematically natural and physically plausible stopping point beyond BPP that’s short of all of BQP—or at least, none that I know of.

  65. asdf Says:

    David Speyer #59, thanks, the Calude/Juergenson paper made sense when I looked at it, but I guess I didn’t look carefully enough. Oh well.

  66. asdf Says:

    Meanwhile, Scott’s Barbados notes makes me ask a basic QC question that’s been bugging me a while. I keep hearing that QM is just like probability theory except the probabilities are complex amplitudes instead of reals. From traditional probability theory I’m used to the probability of an event being the (real-valued) measure of that event in a probability space.

    There’s a concept of complex-valued measure (there’s a Wikipedia article about it) which is just replaces real values with complex ones in the usual description of measures. That article doesn’t say anything about amplitudes or the Born rule and I’m not sure if it’s a related topic at all.

    So what are these amplitudes really? If they’re complex-valued measures, what is the sample space? Where does the Born rule come from? Where does the tensor product come from, for what I think would be called a joint distribution in conventional probability? Is there a decent mathematical treatment of this stuff someplace, that doesn’t get too overgeneral and abstruse? Thanks.

  67. Scott Says:

    asdf #66: Amplitudes are best thought of, not as “complex-valued probabilities,” but as complex-valued “pre-probabilities”: things whose squared absolute values give you probabilities when you make a measurement, but that encode more information than probabilities do (namely, phase information). When no measurement is being made, the vector |ψ⟩ of amplitudes evolves via unitary transformations, which is mathematically analogous to a vector of probabilities evolving via stochastic transformations—but which is completely different than a stochastic evolution of the vector of probabilities that you’d get by measuring |ψ⟩ in some basis!

    Crucially, only when a measurement is made, do you get events (namely, the measurement yielding various outcomes) and a probability space. Before then, no events and no probability space.

    I’ve never heard of “complex-valued measures,” but from the Wikipedia article, I’m extremely skeptical that it could have anything to do with quantum mechanics, since there’s never any normalization of the 2-norm.

  68. Peter Morgan Says:

    asdf #66: Amplitudes are best not thought of. It’s more helpful to think of a stochastic state over an algebra as a linear map from a *-algebra (the *- indicating that there is what we can call a Hermitian conjugate) of operators into the complex numbers, that is, 𝝆:𝒜 → ℂ, which is normalized, 𝝆(1)=1; which is real, 𝝆(𝗔†)=𝝆(𝗔)*; and which maps positive operators into the positive reals, 𝝆(𝗔†𝗔)≥0; so that self-adjoint operators, the observables, are mapped into expected values. Hilbert spaces and everything else then follow through the GNS-construction. BTW, we usually write the vacuum or ground state as 𝝆₀(𝗔) = 〈0|𝗔|0〉, which lets us generate 𝘮𝘰𝘥𝘶𝘭𝘢𝘵𝘦𝘥 states such as 〈0|𝗕†𝗔𝗕|0〉/〈0|𝗕†𝗕|0〉, so that the GNS-constructed Hilbert space contains vectors of the form 𝗕|0〉 (which are sometimes called “vector states”, but they should not be confused with “stochastic states”).
    This may seem too heavy for quantum computing, but it underlies axiomatic QFT in Haag’s formulation in Chapter III of his book “Local Quantum Physics”, which is to say that it underlies quantum optics at least. In this or similar approaches, the conventional distinction between classical and quantum has been between whether the *-algebra of operators is commutative (classically, one obtains probability distributions) or noncommutative (quantumly, one obtains Wigner, Husimi, and other distributions — which, yes, they’re complex-valued, so now we’ve thought of them, but they do not correspond to observable, self-adjoint operators; and 𝑛𝑜𝑡𝑒 that these distributions also emerge naturally in classical signal processing as time-frequency distributions, for which try looking up Leon Cohen). In both the classical and the quantum case, we are effectively doing signal analysis, modulating ground or vacuum states and measuring expected values and correlations in the resulting modulated states, which, when it’s reduced to that level, I suggest is maybe not 𝑡𝑜𝑜 overgeneral and abstruse. Much less than this, and it’s not decent mathematics (although if you really want to get into quantum measurement done right and sort of accessibly, try Paul Busch et al’s “Operational Quantum Physics”, which is a thing of beauty, or something similar).

    It’s also good to be careful about introducing or, better, not to introduce tensor products, but that’s a longer story.

  69. Jan-Åke Larsson Says:

    Craig Gidney #57: Stabilizer simulation cannot produce all function maps, since the Toffoli is not a stabilizer gate. QSL can produce all function maps, using the QSL Toffoli. Different approach to simulation, different limitations.

  70. Scott Says:

    asdf: My and Peter Morgan’s QM learning advice is simply designed for different audiences. I recommend my advice for humans from earth, and Peter’s for superintelligent borgs from Planet Confusenik. Whichever you choose, good luck! 😀

  71. Alex V Says:

    Scott #67: complex measures are discussed, e.g., in chapter 6 of “Complex and real analysis” by W. Rudin. The rumors about their irrelevance to quantum mechanics from my point of view are usually overestimated.
    #70: I would better not discuss the standard GNS stuff to hide my real origins.

  72. Peter Morgan Says:

    asdf: Do both if at all possible. I’m telling you, but I’m channelling Feynman: know every way there is to do something, as far as you’re able, know how they’re related, use whichever seems best at the time, keep coming back to the ones you don’t understand yet. Trite though it is to say it, you can always understand something 𝘣𝘦𝘵𝘵𝘦𝘳, and persistence over years and decades will make you a little smarter at the same time as everything else goes downhill (though obvs never accept anyone claiming that they’re good at something because they’ve been doing it for a long time, or even because they’ve been good before: take everything on its merits).
    Actually, there are four approaches here, since Paul Busch’s approach, as I’ve called it (I know him a little, so I think of it as his, but he has a slew of people he has worked with over the years), is definitely quite distinct from both Scott’s advice and the modulate and measure approach to field theory that I’ve advocated. The fourth, due to Leon Cohen, a little hidden away in the above, is a completely different world, of classical signal processing, something that leaves conventional classical mechanics in its wake when it naturally discovers for itself that noncommutative operators are necessary; if you really want to understand some shit, you’ll try a related, fifth approach, Kisil’s https://arxiv.org/abs/1204.1858. Don’t accept for any longer than you absolutely have to anything that’s watered down.

  73. David Speyer Says:

    I was rethinking my statement that a positive proportion of Turing machines should execute “If 0=0, halt, else (arbitrary code block).” I think this should actually depend quite finely on your model of a random Turing machine. If we say that an n-state Turing machine has only one Halting state, and the probability of each other state branching to it is 1/n, then the odds that we branch to halt when we are supposed to above goes to 0.

    On the other hand, if branching to Halt is some fixed p, independent of n, then we can use the trick we described above.

    To be specific, here is a challenge: Work with Turing machines that use two symbols, n usual states and one additional Halting state. For each of the 2n combinations of state and bit, choose a symbol (0 or 1) to write, a direction (L or R) to move and one of the n+1 states to transition to uniformly at random. (So there are (4n+4)^{2n} Turing machines, all equally likely.) Is there an algorithm which takes an n-state Turing machine and predicts whether it will halt, giving the right answer with probability 1-o(1) as n –> infty? Note that “just say no” is already right with probability at least (n/(n+1))^{2n} –> e^(-2), since that is the probability that no state branches to Halt.

  74. David Speyer Says:

    And having written that, I see that it is basically answered in the Hamkins-Miaskinov paper linked before (math/0504351), except that that paper has the odd proviso that the tape is one sided and falling off the left causes the machine to halt.

  75. Scott Says:

    David #73: Interesting questions! But I agree about the extreme model dependence—that’s probably why these things haven’t been studied more than they have. I have gotten excited about model-dependent questions, like the smallest n for which BB(n) is independent of ZFC, or whether it’s computable whether BB(n) is even or odd, but it’s a niche taste.

  76. Joshua Zelinsky Says:

    David #73,

    It seems that one way of summarizing your observations is that we should expect a positive proportion to halt as long as our distribution is a distribution that in some way respects that we can do function calls or branching on programs. So, we’d expect for similar reasons the distribution of say C-like programs to have a positive probability of halting.

  77. asdf Says:

    The probability that a random program will halt is an encoding-based uncomputable constant with interesting properties:

    https://en.wikipedia.org/wiki/Chaitin%27s_constant

  78. Craig Gidney Says:

    Jan-Åke Larsson #69

    > *QSL can produce all function maps [unlike stabilizer sims], using the QSL Toffoli.*

    But QSL’s Toffoli *doesn’t work*, as I showed and as you say is even mentioned in the paper. How can it possibly be said that QSL produces all function maps if it doesn’t do so correctly, and then returns the wrong answer?

  79. jonathan Says:

    Re: Edge’s “last question”:

    I had some difficulty interpreting the prompt.

    My immediate interpretation was, “What is likely to be humanity’s last question?” In which case I think that the most likely answer is, “Are the post-humans friendly?”

    Another possibility is that the last question will be some variation of, “Are you sure this won’t destroy the world?”

    Or perhaps the *lack* of anyone asking these questions leads to the end of the world, while if they’re asked they no longer become the last question? Then they are a sort of “last non-question”? But maybe that’s actually what the Edge question is trying to solicit?

    I’m confused! I need an adult to help me figure this out!

    (Looking over the various answers, it seems that most people didn’t interpret the question the way I did, or else are severely lacking in imagination!)

  80. John Sidles Says:

    Please allow me to second Peter Morgan’s remarks (circa #68) in respect to the broad utility of quantum operation formalisms (as recently surveyed in, e.g., arXiv:1708.00769).

    We can imagine a world in which infinitesimal quantum operations are strung together to compose path integrals that encompass, not only unitary quantum dynamics, but also measurement-and-noise processes.

    With a view toward practical applications, we can further imagine a world in which engineers employed these path integrals to radically reconceive the designs of advanced gravity wave detectors.

    With a view toward mathematical understanding, we can imagine too, that quantum operations might pullback naturally onto the classical algebraic varieties popularly known as tensor networks … this would naturally associate a broad-ranging class of practical engineering examples to the ideas from complex analysis, abstract algebra, and geometry that are commonly covered in the first year of a mathematics graduate program (specifically in well-regarded “yellow books” like Schlag’s A Course in Complex Analysis and Riemann Surfaces, Lang’s Algebra, Lee’s Introduction to Smooth Manifolds, and Smith’s Invitation to Algebraic Geometry).

    This idyllic world, in which established “yellow book” mathematical formalisms are vividly illuminated by practical quantum examples, is a world in which Gil Kalai’s skeptical bones are dressed in strong mathematical muscles and applied to urgent real-world challenges.

    The main point of this comment, then, is point out that this idyllically quantum-skeptical world is our real world.

    To appreciate this, it suffices to trace the ideas of Bondarescu and Thorne’s “New family of light beams and mirror shapes for future LIGO interferometers” (PRD 2006, arXiv:gr-qc/0409083v1) first forward in history, then backward: forward in history to the recent (magnificent) fulfillment of Thorne’s marvelous vision of gravity-wave detection, and then backward to the quantum operations formalism (e.g. arXiv:quant-ph/0211108v3) whose insights, as Thorne’s article acknowledges, have concretely guided the design of Advanced LIGO.

    This synthetic and applications-centric quantum worldview explains why (as it seems to me) recent commentaries like Gil Kalai’s “The Argument Against Quantum Computers” — which appeared in this week’s Quanta magazine) — should not be appreciated immaturely, as any sort of attack on “the motte and bailey of Quantum Supremacy”, but rather should be appreciated as an enticing invitation to address the challenges of Quantum Supremacy by the PTIME simulation methods that already have contributed so crucially to the successful detection of gravitational waves.

  81. Peter Says:

    Hey Scott, Lenny Susskind recently dropped some notes on the arxiv which he says are explicative of the work that you two have been doing together (I think I remember mention of the work as early as 2014?). I’m assuming that him posting these notes means that you guys may not be close to finishing the paper (although I do hope that you will eventually because the topic is pretty much exactly what interests me in this field the most and is related to what I want to do my research in once I finish school). Do you think you can make an update or even a post talking about the topic or at least his notes? I’m very interested in your take on it all (especially in the larger context of Susskind’s proposed GR=QM that he says these notes are supportive of).

  82. Scott Says:

    Peter #81: Before you posted that comment, did you look higher in the thread to see whether anyone already asked about the exact same thing and whether I already answered them? 😉

  83. asdf Says:

    Scott #67, Peter Morgan #68, John Sidles #80: thanks! Yes I found Peter Morgan’s explanation and links hard to understand but I got some maybe-useful impressions from some parts.

    Does anyone here know the book “Introduction to Quantum Mechanics” by Bransden and Joachain? Is it good? Is it the same book as the one by the same authors titled simply “Quantum Mechanics”? My school used it and I read some parts of it ages ago, without much success but I’m thinking of trying again.

    One thing I’m wondering about is the claim that if you treat time as a complex variable and then look at Brownian motion of a particle on the imaginary time axis, you get the Schroedinger equation. Is that what these unitary operators are about, i.e. measurement is simply looking at a snapshot of something in Brownian-like motion? I’m sure I’m missing something but the measurement “collapse” would then come from the interaction of the measured state with the measurement apparatus, and the randomness comes from the underlying stochastic process. The measurement collapse is supposed to be a big mystery so obviously I’m glossing over something.

  84. Peter Says:

    Scott #82

    I actually did a ctrl f search for “black holes” and “Susskind” before I posted but I obviously forgot to check for “Lenny” or even “arxiv” so I’m sorry, that’s my mistake. As repentance I’ll ask something that hasn’t been asked above (although it’s still pretty tangental so thank you for indulging me 😉 ).

    You are someone who interfaces a lot with philosophy and is pretty willing to talk about the philosophical aspects of questions related to the fields you work in (when it’s appropriate to express them, I should say). Of course CS’s historical background being steeped in logicians and philosophers might have something to do with it, but on the physics side I feel as though Sean Carroll is another example of someone with this disposition.

    On the other hand, there are a lot of people in physics who do or did advocate the position that philosophy has died and should play no role in the discussion anymore, (Stephen Hawking, Susskind to an extent, Feynman) and two of the most prominent science popularizers, deGrasse Tyson and Krauss (not to reduce his identity to just a popularizer), vociferously oppose philosophy entering into the discussion. This may be a very loaded question or it might just be a question that requires too long of an answer, but how would you defend the position that it’s okay to and that we should address the philosophical aspects of questions about physics in a philosophical manner while still respecting the boundary of empirical results and the scientific method? It seems to me like too many people on the physics side of things are fine with talking about philosophy until someone calls it philosophy. Does there need to be clearer communication between both sides?

  85. Peter Morgan Says:

    Scott, I thought of my #68 as a reasonable attempt to channel the research tradition of abstract operator algebra and their representations in response to asdf’s #66, though admittedly as a counterpoint to your response to him, #67, so I was vaguely unhappy at your “superintelligent borgs from Planet Confusenik” jibe in #70, which was partly reflected in the tone of my #72. By the next morning, yesterday, I was spoiling for a fight and dived into a long involved comment from within my research tradition of Koopman-von Neumann presentations of classical physics and their relationship to quantum physics — then I sat on it. John Sidles’ #80, from within his own research tradition, which I want to look at, but also seeming to take flight from your jibe, saved you from most of that, but still there’s this:

    𝗧𝗵𝗲 𝗽𝗿𝗼𝗯𝗹𝗲𝗺 𝗶𝗻 𝗮𝗯𝘀𝘁𝗿𝗮𝗰𝘁 𝘁𝗲𝗿𝗺𝘀:
    I take you to present the Received View of Classical Mechanics to be that the classical algebra of observables is the commutative algebra of real-valued functions on phase space, ℱ:𝒫→ ℝ, with multiplication, ⋅:ℱ×ℱ→ℱ ;(A,B)↦A⋅B, (that is, A,B∈ℱ) —mostly implicitly because interpretation of QM/QFT is not your day job—;
    Wʜᴇʀᴇᴀꜱ the RV is in fact that the classical algebra of observables is the algebra of functions on phase space, ℱ:𝒫→ ℝ, with 𝘵𝘸𝘰 operations: multiplication, ⋅:ℱ×ℱ→ℱ ;(A,B)↦A⋅B, 𝘢𝘯𝘥 the Poisson bracket, {,}:ℱ×ℱ→ℱ ;(A,B)↦{A,B}, which is 𝘯𝘰𝘵 in the categorical form of a commutative algebra.

    𝗔 𝗿𝗲𝘀𝘁𝗮𝘁𝗲𝗺𝗲𝗻𝘁:
    The structure can be laid out in a way that closely parallels quantum physics if we follow a Koopman-von Neumann approach, conceived in abstract operator terms instead of in terms of Hilbert spaces, of restating the RV as an abstract associative algebra of operators 𝒜₊, with one operation, composition, generated by functions on phase space acting using the multiplication, Yᴀ:•↦A⋅•, 𝘢𝘯𝘥 using the Poisson bracket, Zᴀ:•↦{A,•}, satisfying the Lie algebra [Yᴀ,Yʙ]=0, [Zᴀ,Yʙ]=Y_{ᴀ,ʙ}, and [Zᴀ,Zʙ]=Z_{ᴀ,ʙ} [Unicode fail there, but hopefully understandable]. The Poisson bracket being a bilinear biderivation, Zᴀ is a linear derivation. Federico Zalamea appropriately calls the Zᴀ’s 𝘎𝘦𝘯𝘦𝘳𝘢𝘵𝘰𝘳𝘴 𝘰𝘧 𝘛𝘳𝘢𝘯𝘴𝘧𝘰𝘳𝘮𝘢𝘵𝘪𝘰𝘯𝘴, however 𝒜₊ contains operators that can be considered observables that are not contained in the commutative algebra 𝒜 that is generated by just the Yᴀ’s.

    𝗔 𝗯𝗲𝗴𝗶𝗻𝗻𝗶𝗻𝗴 𝗼𝗳 𝗱𝗲𝘁𝗮𝗶𝗹𝘀:
    It’s straightforward to introduce a *-algebraic structure and a stochastic Gaussian state over the resulting *-algebra if the Poisson bracket is trivial, with no constraints, which I do explicitly in my https://arxiv.org/abs/1709.06711, which allows the GNS-construction of a Hilbert space ℋ and of a representation of the *-algebra over ℋ. This construction is lightly peppered through the physics literature in sometimes good and sometimes bad mathematical shape (see particularly Kisil and Zalamea).

    𝗧𝗵𝗶𝘀 𝗺𝗮𝗸𝗲𝘀 𝗻𝗼𝘁 𝗺𝘂𝗰𝗵 𝗱𝗶𝗳𝗳𝗲𝗿𝗲𝗻𝗰𝗲 𝗳𝗼𝗿 𝘁𝗵𝗲 𝗽𝗿𝗼𝗷𝗲𝗰𝘁 𝗼𝗳 𝗾𝘂𝗮𝗻𝘁𝘂𝗺 𝗰𝗼𝗺𝗽𝘂𝘁𝗮𝘁𝗶𝗼𝗻 𝗿𝗲𝗹𝗮𝘁𝗶𝘃𝗲 𝘁𝗼 𝗱𝗶𝗴𝗶𝘁𝗮𝗹 𝗰𝗼𝗺𝗽𝘂𝘁𝗮𝘁𝗶𝗼𝗻:
    A stochastic state over a classical *-algebra that is all but equivalent to quantum mechanics is not the same as a discrete-time-step deterministic dynamics and a digital computer state {0,1}ⁿ.

    𝗪𝗵𝗲𝗿𝗲 𝗶𝘁 𝗱𝗼𝗲𝘀 𝗺𝗮𝗸𝗲 𝗮 𝗱𝗶𝗳𝗳𝗲𝗿𝗲𝗻𝗰𝗲:
    When you discuss the project of quantum computation in more-or-less philosophy of physics terms, which you do quite often and often with widespread implications, be clear that digital computation is far short of the RV of Classical Mechanics when the Poisson bracket is carefully considered.

  86. asdf Says:

    I need a superintelligent Borg to help me with that. Any suggestions? 🙂

  87. Alex V Says:

    asdf #86: Maybe https://ncatlab.org/nlab/show/AQFT could help? And I would rather associated with Borgs newer idea of quantum information and computations.

  88. Peter Morgan Says:

    asdf, my e-mail is easy to find. Whether you’re on Facebook or not, you can look a little at the last few weeks of my conversations with various people there, https://www.facebook.com/peter.w.morgan.98, and decide whether it’s worth any more of your time. You will see even more clearly that I’m a little crazed at the moment, but I guess Facebook is one place where the Borg, superintelligent or not, might be found. There are a few undergraduate and graduate students who have Facebook friended me, most of whom I think are like you, thinking there might, possibly, maybe, be some smoke, as well as a few established academics. All of them will do their own thing, and my ꜱᴜɢɢᴇꜱᴛɪᴏɴ is that it mostly will be beautiful or not because of their spirit and their work and yours. 🙂
    Most likely I will fail to move physics itself even a gravity wave’s deflection —KvN has been around for almost 90 years, after all—, but a few people have been moved a little. Perhaps eventually I will get this current paper to look like a paper in a journal, but I’m so slow that perhaps someone else will do the Jordan and the Dirac work.
    BTW, if you haven’t yet read Kisil’s https://arxiv.org/abs/1611.05650, look at least at the first section, because he gives a very worthwhile corrective to my overly blithe introduction of a complex structure (it’s 𝘧𝘢𝘪𝘳𝘭𝘺 natural for a free random field, but not in general) and he’s much more experienced as a teacher than I will ever be.

  89. Jan-Åke Larsson Says:

    Craig #78: Stabilizer simulation cannot give that function map.

    QSL simulation can. There are several gate arrays that give the function you use, both in quantum mechanics and in QSL. Some of the gate arrays give the desired kick-back and some do not, both in quantum mechanics and in QSL. The gate array you use does not give the desired kick-back in QSL. But if you use a different gate array (for the same function), that obeys the restriction detailed in the paper, the kick-back has the desired behavior. We explain this in detail in the paper. One such QSL gate array for your specific function has five CNOTs and two Toffolis (yes, fewer Toffolis, perhaps a better choice for an experimenter), and has the desired kick-back.

    I repeat: “The QSL framework presented above is deliberately chosen as simple as possible, …. A direct consequence of this simplicity is that the phase relation requirement of quantum computation, that enables phase kick-back, is translated into a simple requirement on the QSL oracles, presence or absence of a CNOT between query- and answer-register.” This is the reason the simulation only works for the construction used in our paper.

  90. asdf Says:

    Peter Morgan #88, I don’t use Facebook but thanks. Kisil’s article was interesting. I’m mostly having better luck with Wikipedia though.

    I get the impression that quite a lot of physics papers are woo-woo, but I can’t tell which ones they are. Maybe it will make more sense after a while.

  91. Craig Gidney Says:

    Jan-Åke Larsson #89

    > *Stabilizer simulation cannot give that [majority] function map. QSL simulation can.*

    No, it can’t. Your changed gate array only works because you massaged it unto having an odd number of CNOTs, not because the simulator is working correctly. You’re sneaking the answer in via a side channel.

    You’re effectively requiring the caller to promise that their gate array will be structured in a way that makes QSL give the right answer (by massaging the parity), but in order to do this the caller will have to determine if the function is balanced or not, which defeats the purpose.

  92. mjgeddes Says:

    Is all of reality a ‘language’ of which quantum mechanics is the basic ‘vocabulary’?

    See John Baez’s latest blog post:
    https://johncarlosbaez.wordpress.com/2018/02/11/linguistics-using-category-theory/

    “Recently Mehrnoosh Sadrzadeh and Bob Coecke have taken up Lambek’s ideas, relating them to the category of finite-dimensional vector spaces. Choosing a monoidal functor from a pregroup grammar to this category allows one to study linguistics using linear algebra!”

    “It also sets up a weird analogy between linguistics and quantum mechanics…”

    *Super-cl…just kidding 😀

  93. Peter Morgan Says:

    asdf: I can’t thank you enough for staying with me over the weekend, when I was clearly bouncing off the walls. Your comments both bounced me harder off the walls and steadied me. A+; and A+ for concision, too. Of course it’s the math that matters, but getting from woo-oo to making sense about the real depths is a process that requires some bouncing, I find, though I hope YMMV (but historically it mostly seems to take years to go from first inkling to really good review and textbook presentations).
    You can 𝘭𝘰𝘰𝘬 at Facebook pages that have been made public without 𝘶𝘴𝘪𝘯𝘨 Facebook. My Saturday post, at the height of my craziness, includes lightly annotated links to a bunch of papers I found that day that are round the edges of what I’ve struggled to clarify here.
    Scott: Many thanks for letting me use this space as a whiteboard for a moment, which was very helpful for 𝘮𝘺 understanding of the math I’ve been doing and its place. Gotta go deep on editing for the next week.
    mjgeddes #92: It looks fascinating —I’m holding myself back from really wanting to know whether there’s a natural complex structure—, but life’s too short. Thanks, however, for making me look at it a second time.

  94. Jan-Åke Larsson Says:

    Craig Gidney #91

    Please note that both your gate array and ours give the majority map in the computational basis. Stabilizer simulation cannot give the majority map in the computational basis.

    Our QSL gate array works because we require the same phase kick-back as from a QM unitary that gives the function map in the computational basis and, *crucially*, preserves the phase relation.

    One way to read our paper is that the phase relation requirement of quantum computation *also* sneaks in the answer via a side channel.

  95. The 2018 Edge Question of the Year – R. W. Richey Says:

    […] in the series. Scott Aaronson (the very first response from this year, it’s alphabetical) describes his response and the challenge of responding […]

Leave a Reply

Comment Policy: All comments are placed in moderation and reviewed prior to appearing. Comments can be left in moderation for any reason, but in particular, for ad-hominem attacks, hatred of groups of people, or snide and patronizing tone. Also: comments that link to a paper or article and, in effect, challenge me to respond to it are at severe risk of being left in moderation, as such comments place demands on my time that I can no longer meet. You'll have a much better chance of a response from me if you formulate your own argument here, rather than outsourcing the job to someone else. I sometimes accidentally miss perfectly reasonable comments in the moderation queue, or they get caught in the spam filter. If you feel this may have been the case with your comment, shoot me an email.