Quantum Computers and Games

I don't understand quantum computers. Not really. I've read probably a dozen articles on them over the last ten years or so, and at the end of them I'm usually going, "Huh. OK.. . So . . . Er . . . " and that's pretty much where I stand today.

So break it down for me in gamer terms: What, if anything, could a quantum computer do in regards to video games that a regular computer can not do?

AI seems to be the obvious one.
Pattern recognition which has obvious ties to the former but can have applications in many other areas.
It should be pretty good at making projections for things like the outcome of a player vs. player contest.

jrralls wrote:

So break it down for me in gamer terms: What, if anything, could a quantum computer do in regards to video games that a regular computer can not do?

Nothing and everything?

What can your gaming rig today do that a 1981-vintage machine couldn't do?

Nothing, it's just doing the same things several orders of magnitude faster. And *that* allows it to do more things.

Disclaimer - I don't know the first thing about quantum computers either, but I'm assuming that the functional difference is one of computational power.

The functional difference with quantum computers is that instead of working with bits of 1 and 0, they work with qubits, which take advantage of way quantum mechanics have superposition and entanglement. They can be in 1, 0, or in a superposition of both. This lets them do things like factor large numbers quickly, in a way that is literally impossible for current computers.

What this would mean for games? I'm not sure. It would allow certain calculations to be done much faster, but without diving into the research literature, it's hard to say which calculations. Cryptography, I know about. Graphics? Probably, though I have no idea how. I'm sure someone has written about what what general kinds of algorithms will work better with quantum computing, and I'd like to read more about it.

The other catch is that the world record for quantum computers is currently 12 qubits. And I'm not entirely clear as to whether they'll have the ease of manufacture we've currently got with etched silicon.

Gremlin wrote:

The functional difference with quantum computers is that instead of working with bits of 1 and 0, they work with qubits, which take advantage of way quantum mechanics have superposition and entanglement. They can be in 1, 0, or in a superposition of both.

Yes, but working with trinary representation of numbers instead of binary just changes how you do the math, not what math you can do.

It's another case of "faster", not necessarily "different".

Jonman wrote:
Gremlin wrote:

The functional difference with quantum computers is that instead of working with bits of 1 and 0, they work with qubits, which take advantage of way quantum mechanics have superposition and entanglement. They can be in 1, 0, or in a superposition of both.

Yes, but working with trinary representation of numbers instead of binary just changes how you do the math, not what math you can do.

It's another case of "faster", not necessarily "different".

My understanding is that it's not necessarily ternary; the qubit doesn't have three states, it has two states plus the superposition of both states: not [0, 1, 2] but |0) and |1) with probabilities of being one or the other. Which can apparently encode up to two bits of information. But I'll freely admit I don't understand all of the details.

You are, however, definitely correct that it doesn't change the math. Just which kinds of math are faster.

The real difference would be if someone could build a computer that isn't a Turing machine. Quantum computers still can't solve NP-complete problems in polynomial time, so they're still in the general class of Turing machines.

One of the bigger short term impacts on gaming is probably going to result from the cryptographic issues and resulting account security issues for online games.

ETA: Given that virtually all systems will have the same problem people are likely going to be more worried about their bank accounts than their WoW accounts though.

What would it take for a computer to qualify as a non-Turing machine?

jrralls wrote:

So break it down for me in gamer terms: What, if anything, could a quantum computer do in regards to video games that a regular computer can not do?

Run a proper RNG?

Cryptography is moving to the chip, even in Intel chips, so that it can happen at line speed for network transactions. That's not something you'd buy a quantum computing chip for. (Mass decryption, on the other hand, on a Very Large System Indeed, that's a different thing.)

What you'll see with quantum computing is stuff like being able to do very tight compression on images, or run complex simulations with large numbers of variables, or optimize collections of hundreds of things (choices). I'd see it as at most something that would provide a service to a game company, like the aforementioned video compression, or map design/pathing prediction for a game like World of Tanks. Anything involving massive statistical analysis would probably fare well, too.

What it does not do is run "fast", in the sense of one thing happening quickly after another. Instead, it works more like a brain, with an array of qubits that is reconfigurable for each task it's asked to do. So it seems to me that it has massively parallel characteristics, in addition to being able to "compress" tasks that require the evaluation of multiple states.

It's nothing you'll see on your desktop in the next 35 years or so. I *think* they are up to 512 qubit processors. That's 512 quantum "transistors". Current technology (SPARC M7) tops out at 10 billion transistors in a traditional computing chip. IF D-Wave can literally double their SQUIDs each year, it's
24 years until they cross that line.

Eventually, I'd expect to see quantum processors used as coprocessors and special compute platforms, but nothing general purpose for gaming for decades, if ever. I suspect that it would be like trying to figure a way to use technology from those giant dump trucks from open pit mines for, say, F1 racing. Probably not fit for purpose until our entire software and hardware platforms change radically.

Then, someday, we'll be remotely racing giant dump trucks on the moon with quantum signaling.

RNGs are easy. You can buy them on Amazon for $50 and plug them right in if you don't like the one inside your chip. Now if you want random AND cryptographically secure, you're in a whole new world of specialized gear. But that's not something that applies to gaming.

Looks like what I said about the 12-qubit thing was outdated; to update what Robear said, D-Wave now says it has a 1152-qubit system.

Robear wrote:

RNGs are easy. You can buy them on Amazon for $50 and plug them right in if you don't like the one inside your chip. Now if you want random AND cryptographically secure, you're in a whole new world of specialized gear. But that's not something that applies to gaming.

Yeah. Plus, for games you mostly don't want real random numbers unless you're running a gambling operation. The determinism of PRNGs actually makes them more useful for games than a true RNG.

Robear wrote:

RNGs are easy. You can buy them on Amazon for $50 and plug them right in if you don't like the one inside your chip. Now if you want random AND cryptographically secure, you're in a whole new world of specialized gear. But that's not something that applies to gaming.

Relevant XKCD: http://xkcd.com/221/

Two words..

Hair Physics

And on that line crowd sim or flocking...

But again... It's not designed to be *fast*, it's designed to be *thorough*... You could do fantastic hair physics on a 3000 processor HPC grid, but it won't produce 100 frames per second of *real-time* output...

I think for gaming purposes you would see three main improvements. Physics simulation for collision, ballistics, armour and what have you. Data encryption in regards to reducing file sizes. And data encryption in regards to network speed.

Tamren wrote:

And data encryption in regards to network speed.

Quantum entangling for networking would be a huge deal. Wikipedia says that the 2014 record is 10 feet, though, so it'll have to improve quite a bit to be viable...

Still won't be enough AI power for Dwarf Fortress 2.

Tamren wrote:

Data encryption in regards to reducing file sizes. And data encryption in regards to network speed.

Not really. Right now, the biggest cause of latency for an internet transfer is the distance between the client and the server. Every foot of line adds approximately 1 ns of latency to the equation. So from SF to NYC(approximately 2.5k miles), that's 13.8 ms of latency for a one-way trip if we were able to just send photons. Encryption and compression, even at high data rates, adds maybe 2-3 ms on each end, much less with on-board NIC hardware support.

Well latency is always going to be a problem until we invent ansible network cards. But just imagine how FAST you could download things if you could compact them to the nth degree. Guild Wars streams in assets as you need them (which leads to a fragmented hell of a game folder but I digress). Imagine being able to play a game like Star Citizen with asset streaming in realtime. Something like a ship or planet texture would zip over the net and into your RAM faster than a computer could load the file off an SSD, even if it was rendered in 6 zillion p. It would be entirely seamless.

Please correct my summary if wrong...

So far, everything everyone has said here about quantum computing is about doing things we can already do, but doing them faster.

Which is going to happen without quantum computing anyway. Moore's Law etc etc, right?

So, going back to the question posed in the OP:

jrralls wrote:

What, if anything, could a quantum computer do in regards to video games that a regular computer can not do?

the answer still seems to be "nothing"

I think it is the case of a mile wide and an inch deep. Except the quantum computer can do a mile wide and a mile deep tasks but yet is slower than a typical computer at a mile wide and an inch deep tasks.

Or perhaps a semi versus a pickup...

On the subject of compression: there are fundamental limits to lossless compression, and quantum computers won't make a difference. There are ways that they might help, mostly by making some parts of the operation faster, but only to a point. (This quickly turns into a discussion of Kolmogorov complexity and Shannon's source coding theorem.)

Networking, on the other hand, could use quantum entanglement to build a quantum internet that would be perfectly secure against outside tapping. I'm not sure how much faster it would actually be, since most of the information I can find is pretty speculative. I'd guess that quantum teleportation would be somewhat faster, but I'm not sure what the actual results would be.

Tamren wrote:

Well latency is always going to be a problem until we invent ansible network cards. But just imagine how FAST you could download things if you could compact them to the nth degree. Guild Wars streams in assets as you need them (which leads to a fragmented hell of a game folder but I digress). Imagine being able to play a game like Star Citizen with asset streaming in realtime. Something like a ship or planet texture would zip over the net and into your RAM faster than a computer could load the file off an SSD, even if it was rendered in 6 zillion p. It would be entirely seamless.

But you are forgetting that the decompression on the receiving end will be done with a regular processor. While that is fast, it's not clear to me whether that's faster or slower than a quantum computer. (I suspect faster for small amounts of data, but much slower for fantastically large sets.) But in any case, you have to factor in decompression time, either before you store the data on disk (meaning the actual game RAM loading will be relatively inefficient, since it's no longer compressed) or every time you actually use compressed data from RAM (which has to be decompressed for use).

I was assuming that in an age of quantum computing everyone would have one.

Tamren wrote:

I was assuming that in an age of quantum computing everyone would have one.

Everyone both has one, and doesn't.

Jonman wrote:
Tamren wrote:

I was assuming that in an age of quantum computing everyone would have one.

Everyone both has one, and doesn't.

And when you have one, never look away from it.

Whatever you do, don't open your eyes Miriam!

This seems to be the only existing thread for quantum computers, so I'll put this here.