Quandoom: A port of DOOM for a quantum computer | Hacker News Reader

Quandoom: A port of DOOM for a quantum computer

github.com

134 pointslgtx45 comments

"Please note - it will use about 5-6 GB of ram and take a while to load since it's a very large circuit file."

I love it. So absurd. 200 years from now people will be running Doom on artificial black holes or programmable matter and the readmes will be pretty much the same.

Meanwhile, you can run the Z-Machine, at least up to v3 games (most of Infocom games) under a PostScript interpreter like PostScript.

So, it might run under 1GB or ram and less.

Next up: Doom running on this Z Machine: https://en.wikipedia.org/wiki/Z_Pulsed_Power_Facility

The Z-machine could run under 64k or RAM, or less, back in the day.

1GB is probably more than you'd need to store all the Infocom releases!

I know, there are even ports for the original Game Boy (not even the Color, the less powerful B/W one). I ran Calypso and Tristam Island on these as an experiment.

But I meant 1GB for the quantum computer OFC.

I've never seen the GB port. Are you sure? A quick google didn't return anything.

All Infocom releases PLUS all scanned manuals and Invisiclues...

The interesting part of this project is compiling doom into a weird target architecture: a .qasm circuit file. This requires you to do things like decompose additions into TOFFOLI gates. But the code in the repo doesn't include that part, it only includes the code for interpreting the circuit and the produced qasm file.

The author is aware of this (from the readme):

> For now I'm still tidying up the engine code, but basically I have about 8,000 lines of c++ functions allowing a number of reversible binary and arithmetic operations on quantum registers, for example "flipIfLessThanOrEqualTo" which flips all qubits in a register if the value of another register is less than some given value. Everything is done with integers.

Kinda ironic they left out the most interesting part.

Given that there's only 174 qubytes of storage (72376 qubits total - 6986 qubits ancilla - 64Kqb screen) it's clear that almost the entire world state is in the series of gates rather than in qubits. So, like, the wall locations are probably implicit in the series of instructions rather than being data-driven, so you wouldn't be able to make a wall that was in a superposition of two places. It would be interesting if the author said what specifically was in the qubits; I'd imagine it's probably things like health/ammo/position/enemyposition but an explicit list would be good.

They say this is a reimplementation of Doom, as opposed to a cross compilation. That makes sense to me. For example, I doubt there's anything like a tree data structure anywhere in the rendering, since that stuff doesn't really translate from programs to circuits. Tree structures work efficiently around the fetch-decode-execute bottleneck, but circuits lack that bottleneck. Also, a "true" quantum implementation of the rendering would struggle to do any kind of truncation of what to render since the camera position can be in superposition. Frustrum culling would implicitly measure the position of the camera, preventing some potential interference effects, and so would be an approximation instead of a pure optimization.

From a high level view there's not much point in allowing most of doom's state to be in superposition, since constantly rendering them to the screen measures them preventing interesting interference effects. You could maybe make it so that enemies in rooms not being rendered were undergoing a quantum walk, so their positions behaved sort of analogous to an electron in a potential well. So entering the room at different times would result in different distributions of positions.

> Given that there's only 174 qubytes of storage (72376 qubits total - 6986 qubits ancilla - 64Kqb screen) it's clear that almost the entire world state is in the series of gates rather than in qubits. So, like, the wall locations are probably implicit in the series of instructions rather than being data-driven, so you wouldn't be able to make a wall that was in a superposition of two places.

I'm also wondering how much of the computation is really ... quantum? I.e. is anything in superposition, phase shifted, entangled, etc.?

This looks to me like it's entirely relying on reversible classical logic gates. Impressive! But not quantum computing on its own.

Well, certainly, no computation has ever been quantum in nature or concrete reality.

I guess it’s fun to imagine or simulate though.

> You could maybe make it so that enemies in rooms not being rendered were undergoing a quantum walk, so their positions behaved sort of analogous to an electron in a potential well. So entering the room at different times would result in different distributions of positions.

I look forward to the day Nintendo sues a student for their quantum pokemon clone

cyberdemons in superposition? no thanks :O

I both have and have not beaten quandoom.

Pics or it is in a super-position of happened/didn't happen

I think the correct quantum name would be: woop

"No Fair! You changed the outcome by measuring it!"

I was all on board until I saw the video. Black and white! Has this been designed for a quantum gameboy? I don't think you can claim this to be truly useful until you've achieved 8 bit colour depth.

Gameboy wasn't black and white, it was a mushy greenish gray. Thank you very much. I've seen some nice monochrome screens with 8-bit depth, but the Gameboy was only 2-bits. Maybe you could do some time based dithering...

Quantum CGA will be mind-blowing.

Including Quantum Sound Blaster™

pfft gameboy, this was clearly designed to run on a quantum virtualboy

What is all the "reversibility" the readme is talking about? How are non x-ray walls, reversibility and quantum connected?

Basically, quantum gates are mathematically represented as multiplying your state by unitary matrices. Unitary matrices are ones where their inverse is their own conjugate transpose (i.e. XX*=I). Since each gate has an inverse, for any computation you can reverse it (in other words find a circuit that recovers the inputs from the outputs).

In practice this means that you sometimes have to keep around extra bits called Ancilla bits that just contain garbage, but are necessary for reversibility.

So by 'reversibility' they mean that good graphics would require too much memory (bc quantum can't reuse memory as traditional computers do), and we don't have the resources for that yet.

But what does this have to do with it being xray?

Layman speculating, but wouldn't occlusion throw away visual data? Discarding data is disallowed because it breaks reversibility.

Though I'm not sure about this becuase I would guess the current implementation also discards data where wireframes intersect.

Generally all quantum computing operations have to be reversible at the gate level, so you can’t have a simple thing like an AND gate, and this can make things more complex. As you either need to put some out put to a qubit you don’t care about, or find some other way to handle it.

If something opens up a portal to hell, it's gonna be this.

I know that it is only the early days of quantum, and this is already a marvellous achievement given the current state of the technology, however I wonder how well a quantum computer will eventually be able to render a ray tracing version.

I really like these doom ports. As if they've become a standard to learn, try something new and let others test it out. We had entirely AI generated DOOM and now DOOM for quantum computer. Maybe let's try a Doom in Go which is fully CLI? :-)

it's in C but this was the first result for "ascii doom": https://github.com/wojciech-graj/doom-ascii

There's also Doom in Notepad: https://arstechnica.com/gaming/2022/10/how-to-get-doom-runni...

AI generated DOOM

Was that discussed on HN? How well did it replicate the original game, and what were the subtle defects?

https://news.ycombinator.com/item?id=41375548

There's a port of Quake for the Z-Machine, but just the first level.

I just had to see that: https://ifdb.org/viewgame?id=lkr2jf03np19ieix It's playable online and quite well done!

A pity is not libre; if if were I could make a few more levels for it as the Inform6 language it's literally a dumbed down OOP language (except for the non-English/Spanish grammar library methods/commands, the ones made in Inform6 itself) and the objects in the game are self-explanatory to code. Really simple, even a 10 year old could make a shortish game.

Quantum computers are a superset of normal computers, so im not sure what the fuss is here.

Getting your quantum computer to do a classical task (and actually simulating it) is far from easy.

This is not strictly correct.

Quantum computers can do some things normal computers can't, but the reverse is also true.

I don't think that's true. What's your example? As far as I know any operation on a classical computer can be emulated on a quantum computer in some short amount of time; constant time, maybe.

i think essentially it's translating from classical logic gates operations to these weird gate types they have on quantum computers. This atleast, i think, is what 'compilers' do which target quantum computers or simulations.

https://en.wikipedia.org/wiki/Quantum_logic_gate

There's a few types, and I imagine most things can be translated between them.

I think the most things are possible between the two, either will just be faster / more optimized for certain things, so it's less ideal to pick one or the other depending on what you're doing.

70,000 Qubits to run. That's the ballpark number to break RSA encryption!

the most important file (the .qasm) is missing from the repo...

The most important code would be that which generated the .qasm file. That's not included in the repo, just the "compiled" result and a little program to run it. The code generator will look like a conventional C++ program that turns geometry operations (like line drawing) into subroutines which are written out to the .qasm file. There's no point to commit generated code to the repo.

The .qasm file can be found in the downloads/releases section.

I'm both glad and slightly disappointed it doesn't use aalib(-patched).[0]

0. https://github.com/billagee/aalib-patched

Reply on news.ycombinator.com