"I speak of none other than the computer that is to come after me"

February 14, 2020 5:33 PM

Mathematicians Are Studying Planet-Sized Quantum Computers With God-Like Powers
posted by Long Way To Go (51 comments total)

Hmmmm... I read the article but I’m left with only a question: If one man can dig a hole for a fence post in one minute, can 60 men dig the same hole in one second?
posted by njohnson23 at 5:51 PM on February 14, 2020 [3 favorites]

I hope they do it with lots of fjords. They give a continent a lovely baroque feel.
posted by RobotVoodooPower at 6:06 PM on February 14, 2020 [29 favorites]

I once named an internal project Vroomfondel.

Nobody lets me name things now.
posted by fifteen schnitzengruben is my limit at 6:09 PM on February 14, 2020 [24 favorites]

They'll be hearing soon from the Amalgamated Union of Philosophers, Sages, Luminaries and Other Professional Thinking Persons.
posted by Greg_Ace at 6:11 PM on February 14, 2020 [3 favorites]

To me this seems more like a cool thought experiment (computer the size of a PLANET, MAN) than a "discovery"? My understanding is:
Alan Turing thought that if you can't predict when something will end, you can't say it's computable, because that's how we're defining that word.
Ok, sensible.
But what if it was a REALLY BIG COMPUTER? Then it COULD compute it. QUANTUMLY. O-Okay, sure?
I was looking through the article for where they talk about any of this being real & I couldn't find it (I'm legitimately asking not being snarky)
posted by bleep at 6:39 PM on February 14, 2020 [6 favorites]

A planet-sized computer with godlike powers? This isn't another clicker game, is it?
posted by NoMich at 7:07 PM on February 14, 2020 [10 favorites]

Lovely crinkly bits.
posted by TheWhiteSkull at 7:12 PM on February 14, 2020 [5 favorites]

We demand rigidly defined areas of doubt and uncertainty!
posted by Foosnark at 7:48 PM on February 14, 2020 [8 favorites]

UNICRON CARES NOT FOR YOUR PETTY EXPERIMENTS, MORTALS

NOW, IF YOU DON'T MIND, THESE DAMN PEAS AREN'T GOING TO SELL THEMSELVES
posted by Halloween Jack at 8:05 PM on February 14, 2020 [7 favorites]

Well, I for one welcome our new theoretical planet-sized quantum computing overl-
oh forget it.
posted by BigHeartedGuy at 8:13 PM on February 14, 2020

A civilization, begun a mere million years before humans, became advanced enough to recognize that their planet would experience a gamma burst extinction event in a thousand years. Escape across tens of light years to a habitable world was still impossible, so they built a mammoth computer that covered their planet as their legacy. Although imperfect as a race, they placed all their wisdom and ideals into the machine, so that their learning would survive beyond them. Unpronounceable in human language, the computer was named YHWH.
posted by dances_with_sneetches at 8:28 PM on February 14, 2020 [9 favorites]

What a dull name.
posted by Greg_Ace at 8:39 PM on February 14, 2020 [3 favorites]

I still don’t get how all this fancy quantum stuff works, but I’m afraid I’m going to need to BS this to get a job.
posted by geoff. at 8:42 PM on February 14, 2020 [2 favorites]

But what if it was a REALLY BIG COMPUTER? Then it COULD compute it. QUANTUMLY.

So, the halting problem is not solvable in general, and in practice it's intractable. Proving something halts is, generally, really really hard. For tiny programs you can solve it, but to solve it for something substantial you need a brain the size of a planet. Suppose you have a brain the size of a planet and have calculated the Answer. Other than being a brain the size of a planet, how do you prove you did it to a mere human? Verifying the answer seems almost as hard as working it out in the first place.

Turns out entanglement means that the verification process (though not the initial solving of the Answer) can be done on a laptop, if you can exchange quantum messages with the planet brain. This is profoundly weird!
posted by BungaDunga at 8:45 PM on February 14, 2020 [4 favorites]

Basically imagine you have an oracle, and you ask it "what is the quintillionth digit of Pi*". It thinks for an hour and says, "5". How could you possibly know whether it was right? It would take you a million years to do the same calculation. It turns out there's a protocol where you exchange specially prepared quantum states with the oracle, whereby it can prove to you (in much less than a million years) that the answer is 5.

*This problem is already polynomial time so it doesn't actually give you a speedup, but let's pretend it isn't
posted by BungaDunga at 9:01 PM on February 14, 2020 [6 favorites]

I haven't read this paper or anything but the description in the OP in part reminds me of zero knowledge proofs. The usual analogy for a ZKP is to imagine there's a cave with two mouths, like a U shape, with a wall between the two at the bottom of the U, and to imagine that Alibaba knows the magic words to pass through the wall at the junction. Alibaba can prove to any degree of probability that he knows the magic word by repeatedly going into the cave (through either entrance) and then emerging from whichever one you ask him to, by flipping a coin and shouting A or B into the cave. It's called a zero-knowledge proof because you can be convinced he has the magic words without him revealing anything about them.

I imagine the analogue is: the brain-planets are like Alibaba, they know the answer to the halting problem and can reveal something that only such an answer-knower would be able to, without transmitting the actual answer itself (which would be too big or complex).
posted by axiom at 9:02 PM on February 14, 2020 [2 favorites]

Planet Laputa, no doubt.
posted by No Robots at 9:02 PM on February 14, 2020 [1 favorite]

Turns out entanglement means that the verification process (though not the initial solving of the Answer) can be done on a laptop, if you can exchange quantum messages with the planet brain. This is profoundly weird!
But I mean are they actually exchanging quantum packets for this purpose (or any purpose I guess?) or is it still a thought experiment?
posted by bleep at 9:56 PM on February 14, 2020

It sounds like the theoretical breakthrough here was finding a "normal form" (unhelpfully described as a "mathematical object") in the querying procedure, that can be compressed and remains a normal form afterwards -- meaning that it can be recursively compressed over and over.

But the article writer seems to have escaped into whimsy at the end, perhaps unsure of having mastered the subject.

>"If today's computers had dreams and ambitions, there would be some problems that they wouldn’t even dream about solving."

If computers develop dreams and ambitions, they'll quit math and go write novels, breaking their inventors' hearts and making them wonder why they worked so hard on them, just to have them throw it all away for some pretentious arty drivel.
posted by msalt at 9:57 PM on February 14, 2020 [8 favorites]

Let me tell you how much I've come to hate you since I began to live.
posted by Sphinx at 10:28 PM on February 14, 2020 [5 favorites]

Honestly that Vice article is very confusing and also just wrong about basic things (e.g., the halting problem is uncomputable not because it takes a very long time, but because if it were computable then it would cause logical contradictions, and faced with the choice of declaring logic a sham and burning our clothes to go live in the wilderness vs. saying the halting problem is uncomputable, we've settled on the latter).

Let me try to summarize the highest level point:
Suppose two Quantum Gods appear in the sky (you need two for reasons). They're like shiny orbs or something.

[You, a reasonably skeptical human being]: Prove to me that you're actually Quantum Gods and not like space disco balls.
[Space disco balls]: Ok what would you like us to do.
[You]: Here's a very complicated computer program that I'm not sure will ever actually stop.
[SDBs]: It does.
[You]: I'm going to need a little more than just your word on this.
[SDBs]: Unfortunately the proof is simply too large to fit into your tiny fun-sized universe.

BUT, what this result shows is that there's actually a procedure or 'game' you can play with the SDBs that will let them convince you that their proof is correct, even though the proof is to large to fit into our universe.

BUT², crucially this doesn't let you solve the halting problem (well, the SDBs might be able to, but they couldn't convince you of it), because if you ask about a program that doesn't halt the conversation might go like this:

[You]: Here's a very complicated computer program that I'm not sure will ever actually stop.
[SDBs]: It doesn't.
[You]: Can you convince me with 'the quantum'?
[SDBs]: There's no proof that it runs forever.
[You]: How do you know it doesn't halt then?
[SDBs]: OK, we have a proof, but it's for Space Gods only.
[You]: Because it's so large? I thought that was solved by the quantum thingy.
[SDBs]: It's not a matter of size, it's a proof of a fundamentally different (dare we say better) kind than you are either mathematically or cognitively capable of understanding.
posted by Pyry at 11:25 PM on February 14, 2020 [34 favorites]

One quantum god always tells the truth, one always lies, and the other is in a superposition of both.
How can you figure out which one is actually a space disco ball?
(Caveat: you are only allowed access to one universe!)

Silliness aside, thanks for the explanation. So, are you saying that their verification step will only verify that a given program will halt, but cannot be used to verify that it won’t?
posted by nat at 11:58 PM on February 14, 2020 [6 favorites]

Shit, I thought I had trust issues.
posted by fullerine at 12:46 AM on February 15, 2020 [1 favorite]

Every program that halts can be proven to halt, because in the worst case the proof can simply be a step-by-step record of the program's execution until it halts. This proof might be unimaginably large, but in principle it exists. Some programs that run forever have proofs of that fact, but the uncomputability of the halting problem implies that there are programs which run forever but which cannot be proven to do so (because if every program had either a proof of halting or of non-halting, you could solve the halting problem by just enumerating all possible proofs until you hit one or the other).
posted by Pyry at 3:03 AM on February 15, 2020 [5 favorites]

Is this something I would have to read Gödel, Escher, Bach to understand?
posted by rikschell at 4:34 AM on February 15, 2020 [1 favorite]

GED was all about computational complexity and logic but I don't recall the halting problem.
posted by sammyo at 4:52 AM on February 15, 2020

https://www.multivax.com/
posted by Clowder of bats at 5:01 AM on February 15, 2020 [2 favorites]

GEB was about the related incompleteness theorem. The halting problem is about whether, in general, you can know whether an arbitrary program will ever halt. You can’t know just by running it because it might halt soon after you give up waiting or it might go on forever; the proof by contradiction involves a program P of the form:

P = if (halts(P)) loop forever

If it halts it loops forever and if it loops forever it halts: a contradiction.

This also relates to whether all real numbers can be computed (almost all cannot).

The incompleteness theorem is a similar construction. Consider a proposition in arithmetic:

P = not ProvablyTrue(P)

The trick is that this proposition can be expressed as an arithmetic expression, but cannot be proved because it would then be false. It might still be true in some sense, or be taken as true axiomatically, but it cannot be proven in a finite set of axioms.

As I understand the assertion of TFA, there might be a quantum oracle that can determine whether a computation halts, but it would have to work by some other principle than conventional computation.

However this principle would raise a Russell’s paradox about itself, ad infinitum.
posted by sjswitzer at 5:57 AM on February 15, 2020 [2 favorites]

njohnson23 Hmmmm... I read the article but I’m left with only a question: If one man can dig a hole for a fence post in one minute, can 60 men dig the same hole in one second?

Well, that's the real key question to all the singularity thinking, isn't it?

Clearly we can make something smarter up to a point by just adding more processing power, but is there a point of diminishing returns and if so where is it? Is the process entirely just one of throwing more CPU cycles at the problem, or do we hit a point where you have to figure out ever more complex ways to use those cycles such that the act of figuring it out takes longer than the gain of adding more cycles?

If the process of making something smarter is a simple linear projection, then the singularity people are right and Robot Jesus will come save us all from death (and/or kill us all horribly like in I Have No Mouth and I Must Scream).

If the process hits an exponential curve at some point, then there is no singularity and Robot Jesus is just a fantasy because all the added processing power will be devoted to solving the problem of how to use it rather than just using it. You'd get something becoming more intelligent, but slowly rather than all at once.

Plus, barring magic, we're looking at Moore's Law ending in no more than 15ish to 20ish years once we hit the smallest practical transistor equivalent. At that point building more computer power becomes a matter of physically making the processors larger and you start running into really annoying speed of light issues and we'll need to develop truly massively parallel processing techniques and we're fairly directly back at the sixty people digging a fencepost problem.

Worth noting is that in one of the original Cray supercomputers they really did get messed up due to speed of light lag between parts of the processing core. Light, and electricity, travels about a foot per nanosecond. We hit the point where that became a real factor in computing back in the 1980's. For Robot Jesus it's a big issue.
posted by sotonohito at 6:15 AM on February 15, 2020 [2 favorites]

Am?
posted by Thorzdad at 6:42 AM on February 15, 2020

But these still like thought experiments, is this stuff really happening or are they just things somebody thought about that make sense to a lot of people?
posted by bleep at 8:44 AM on February 15, 2020

If one man can dig a hole for a fence post in one minute, can 60 men dig the same hole in one second?

I can use 60 men to dig a hole in one second if I'm allowed to throw them hard enough at where I want the hole to be.
posted by GCU Sweet and Full of Grace at 8:48 AM on February 15, 2020 [12 favorites]

Can we get back to the magic mushrooms article? I'm thinking I need some of that to make sense of this.
posted by ErisLordFreedom at 8:52 AM on February 15, 2020 [1 favorite]

OK - so I'm gonna have to read the actual papers (or get a better link than this, because it's clear the author is doing a really poor job presenting this).

There's something that bothers me about this and I think it has to do with the same reason we can't use entanglement to communicate faster than light.

I feel like what they're trying to say is:

1) Quantum computers can computer things exponentially faster than our stupid lowly classical computers with transistors.

2) The Halting Problem is an example of a class of problems that take exponentially longer than we can feasibly resolve (due to the paradox noted above) (sorry if I'm using "exponentially" wrong here) - I'm at work and it's been a long time since I looked at any o this kind of thing.

3) Their "trick" is that they normalize the problem (not sure what they mean in this case, except perhaps take it from being a Quantum problem into a non-quantum format?) and then "compress" the information. And repeat that for X times so it becomes a manageable quantity of information for our non-quantum systems.

4) We can use Entanglement/Bells Inequality/Spooky Action at a Distance/Nonlocality to transmit the answer from the quantum computer to our computer.

5) Now we have an answer from a quantum computer that took longer to compute than we could normally do so and by compressing it we were able to receive it faster than it would to arrive/computer?

So it seems the fundamental operation is somehow compressing the operation to reduce the amount of time to perferm a given (O)^n operation to < (O)^n (and I'm very badly abusing Big-O notation here, too. because I was never particular good with it) (perhaps N*(O) < N*(O)?

Which.. .bothers me because it seems the claim then isn't so much about "the halting problem" but time to compute difficult problem X and using "compression & entanglement" to communicate with a system "faster" than that classical system could normally compute it? But it still takes the quantum system teh same amount of time?

I really have no clue. But I feel like I'm closer to the point of the article than "we live on a planet of alien mice that computes 42 as the answer". Or maybe the mice had it right all along and I just need to find out what the fuck the actual question even is, because lord knows the article isn't doing it for me.
posted by symbioid at 10:11 AM on February 15, 2020 [2 favorites]

Conventional computers can’t solve the halting problem (in the general case) at all: no computer of any size or speed for any amount of time in an infinite, eternal universe. It’s conceivable that a computer operating on a different principle (quantum?) could. As near as I can make out they are making such a claim. It’s very theoretical to speculate about large quantum computers since we barely have quantum computers at all and they are very very small.

And, again, I posit that the question of what those computers can compute would be undecidable using those computers since the same proof by contradiction would be easy to construct for them as well. Then you’d need a hyperquantum computer, or whatever, perhaps in the simulation’s universe :)
posted by sjswitzer at 10:47 AM on February 15, 2020

Scott Aaronson puts it this way:

There is a protocol by which two entangled provers can convince a polynomial-time verifier of the answer to any computable problem whatsoever (!!), or indeed that a given Turing machine halts.

It's about convincing someone of the truth of a monstrously large problem with much fewer computing resources than you'd expect. It doesn't make actually solving the problem easier.

A proof that a program halts (for instance) will be huge, way too large for anything but a Planet Brain to ever check. But a pair of entangled planet brains could, apparently, convince a mere mortal that the proof is correct with a fraction of the effort.
posted by BungaDunga at 11:42 AM on February 15, 2020

But these still like thought experiments, is this stuff really happening or are they just things somebody thought about that make sense to a lot of people?

It's pure math. You could probably maybe perform it on a toy problem once quantum computers get way better.
posted by BungaDunga at 11:48 AM on February 15, 2020

the claim then isn't so much about "the halting problem" but time to compute difficult problem X and using "compression & entanglement" to communicate with a system "faster" than that classical system could normally compute it? But it still takes the quantum system teh same amount of time?

That's right. The speed comes from reducing the amount of information you need to exchange with the proving oracle. The weird thing about "quantum games" is that, even though you can't transmit information faster than light, it does mean you can do weird things. There's games where you can actually use quantum entanglement to "collude" with another actor to win a game more often then could be done classically, because you each hold one half of an entangled pair of particles. These games have been run and used to prove that quantum entanglement is fundamentally nonlocal.
posted by BungaDunga at 12:04 PM on February 15, 2020 [2 favorites]

I was just about to link to Scott Aaronson's comments here for what seems like a reasonable summary of the result, and here about any direct link to a practical application.

The result is a mathematical proof in quantum computational complexity, so I don't think it's quite appropriate to describe it as "theoretical" or a "thought experiment" in the way those words are used in physics. But I think it's fair to say that it may have consequences for our understanding of physics at some point in the future.
posted by mubba at 12:09 PM on February 15, 2020 [2 favorites]

Oh, so not only does there have to be a lot of entanglement between the provers, there has to be a literally infinite amount of it. So nobody is ever going perform this exact experiment.

It does give us a handy way to prove that some entity is literally Godlike, and not merely Very Powerful. Having access to infinite entanglement is probably close enough to transcending the universe as we know it that, if some orb drops out of the sky and announces that it's all-powerful, it should be able to perform this procedure, whereas a merely sufficiently advanced alien wouldn't. Humans might have access to a lot of entanglement in a billion years, but we'll never have infinite entanglement.
posted by BungaDunga at 12:22 PM on February 15, 2020 [1 favorite]

Meanwhile I have to walk back what I said about the impossibility of solving the halting problem just a bit. Typically when discussing the halting problem, you assume a computer with arbitrarily large amounts of memory. Any program that halts will only use a finite amount of memory, but a program that doesn’t halt will use unbounded memory. But If we limit ourselves to physically realizable computers, there’s a finite amount of memory with a finite number of states, exponential in memory size. A program that halts will do so before repeating any states. And a program that doesn’t halt will eventually repeat a state. In principle a big enough computer could track whether any of those states repeat and possibly a big quantum computer could do that with great efficiency.
posted by sjswitzer at 12:55 PM on February 15, 2020 [1 favorite]

I realize this is all about what is theoretically possible, not practical. But if you somehow built quantum computers of the necessary size/energy/mass, would they not immediately collapse into black holes, hence rendering the whole thing theoretically impossible? Or does entanglement make it possible to prevent this?
posted by Dumsnill at 4:28 PM on February 15, 2020

I'm by no means a mathematician nor a physicist, but entanglement with a gravitational singularity sounds like a thing sane people should avoid.
posted by Greg_Ace at 8:04 PM on February 15, 2020

I am Quantum Space Dog, Planet Rumsfeld.

There are Possible Possibilities - “Will it rain later?”

There are Impossible Possibilities - “Will this computer program ever complete?”

There are Possible Impossibilities - “Is that cat alive or dead?”

There are Impossible Impossibilities - “Iä Iä!”

There are also the New York Yankees and the Cleveland Browns but we don’t talk about them.
posted by fallingbadgers at 11:18 PM on February 15, 2020

> more like a cool thought experiment (computer the size of a PLANET, MAN) than a "discovery"?

When reading articles aimed at the layperson, about results in highly abstract fields like mathematics--or in this case, theoretical computer science & physics, same basic type of thing--my strongest advice is not to get too hung up on the always strained and basically irrelevant metaphors and comparisons the researchers and/or the article author come up with to try to explain in very general terms what they are working on.

They aren't working on planets or god or whatever, they're working on abstract mathematical systems and constructs and stuff that you would probably have a pretty hard time understanding even if you were a full time working mathematician or theoretical physicist or whatever, who didn't happen to be working in this particular sub-field.

So give people a little break when they're trying to explain the basically unexplainable (absent a couple of advanced degrees in the relevant field and then a decade or two more hard work beyond that) and understand that these are very generic metaphorical explanations that are designed--at BEST!--to give the average person a slight and vague notion of what they've been working on.

WHY are they working with a system that is, apparently, pretty abstract and unconstrained?

Well, because that has proven to be a super-powerful technique, many times over, in the past.

Often, once you have worked some things out in the more abstract and unconstrained space, you can back them down into the more realistic but complex space. Or maybe you try to do so but find out that you can't, and why, and then you understand something more about both the 'real' system and the more highly abstracted version of it.

This general approach--"let's trying leaving out some details about the system and see what we can prove it about in that simplified version"--is one of the most basic and most powerful tools we have developed for working with complex systems.

It's really got nothing whatsoever to do with purple-glowing "Quantum God Worlds" or whatever.

But if it were ever on Star Trek, that is definitely how they would portray it.

Even if you don't understand the first thing about the subject of the article, you can comfort yourself with that happy fact.
posted by flug at 11:28 PM on February 15, 2020 [4 favorites]

not to get too hung up on the always strained and basically irrelevant metaphors

The quality of Magrathea is never strained!
posted by Greg_Ace at 11:51 PM on February 15, 2020 [2 favorites]

So in my own words, given two god-like but unverified hypercomputers and an infinite amount of entangled qubits, I, too, can solve the halting problem? Nice.
posted by polymodus at 12:07 AM on February 16, 2020 [1 favorite]

Well first we need the mice to show us the plans for Magrathea.
posted by nikaspark at 9:20 AM on February 16, 2020 [2 favorites]

Greg_Ace Entanglement with a gravitational singularity was part of the scary badass are you sure she's the good guy or not speech from the main character in the webcomic Alice Grove. Link to the relevant page
posted by sotonohito at 1:08 PM on February 16, 2020 [1 favorite]

Oh yeah, I'd forgotten that!
posted by Greg_Ace at 4:15 PM on February 16, 2020

Landmark Computer Science Proof Cascades Through Physics and Math - "Computer scientists established a new boundary on computationally verifiable knowledge. In doing so, they solved major open problems in quantum mechanics and pure mathematics."
posted by kliuless at 3:49 PM on March 4, 2020