5,203 karma · joined June 22, 2010
Note the 2013 paper wasn't making the same point. They weren't pointing out that Shor's algorithm succeeds quickly regardless of how well the quantum computer works when factoring small numbers. They proved the period-matching "precompilation" tricks experimentalists were doing at the time weren't okay, because those tricks could turn any factoring problem into a trivial two qubit circuit (and were equivalent to knowing the factors).
Something I initially did't understand is why their classical solver ever takes more than 4 moves to solve the puzzle. At most one move to ensure a green square is in the top row, and then at most two moves to move the other green square into the other top row slot, and then a move to certify the solution. The issue is that the puzzle can start in superposed states, where the classical solver can only permute which states have which amplitudes and so always only has a chance of verification succeeding and relatively few variations on this. Whereas the quantum solver can use interference effects to make a big amplitude that it can then move to the solved state.
I was sort of hoping that they would show, for example, that superposed moves could transition from some classical unsolved states to the solved state in fewer steps deterministically. Some sort of known-source-known-destination variation on Grover's algorithm. But nothing like that unfortunately. An obvious obstacle to this is that the square-root-of-swaps don't commute with each other in a simple way, so almost all sequences of them don't correspond to a classical permutation; you basically have to undo what you did to get back to the classical manifold.
I don't even think the delayed choice eraser is a "quantum" paradox. It involves quantum particles, but they're really just there for flair. They're not crucial. You can apply the same confusion to a classical experiment. Set up some basic correlation between A and B, with A revealed first and then a choice to reveal B or an unrelated C. Then describe the situation so badly that it sounds like choosing to measure B vs C is changing the probability distribution of A backwards in time (since if you condition on B you'll see the correlation vs A, but conditioning on C shows no correlation).
If you want to see the progress in quantum computing today, pay attention to component reliability. For example, in 2014, the best rep code run on a quantum computer had a 1% error rate per round [1]. In 2024, it was 0.00000001% and it had become possible to run full quantum codes with a 0.2% error rate per round [2]. If it takes another decade for that 0.2% to go down by a factor of a thousand, then you've got lots of time. Maybe you'll be dead before progress exceeds the coarseness of factoring. If it takes a year instead of decade (because the cost of error correction is frontloaded) then, well, pay appropriate attention to that.
Still would have appreciated it being in the article.
Suppose two players notice each other at the same time (e.g. as would naturally happen when walking around a corner in a shooter), first to shoot wins, and their total latencies are identical Gaussians with a standard deviation of 100ms. Then a 6.5ms reduction in latency is worth an additional 2.5% chance of winning the trade. Maybe you won't notice this on a moment by moment basis, but take statistics and its impact should be measurable.
In ELO terms a 2.5% gain in win rate is around a 10 point increase (simplifying by assuming that single Gaussian is the entire game). That's small, but if you were a hardcore player and all it took to raise your ELO by 10 points was using a better monitor/mouse/OS... why not? Doing that is cheap compared to the time investment required to improve your ELO another 10 points with practice (unless you're just starting).
Also, I think you'd be surprised what people can perceive in a context where they are practiced. Speed runners hit frame perfect tricks in 60FPS games. That's not reaction time but it does intimately involve consistent control latency between practice and execution.
That said, wherever you convert the quantum data into classical data there will be potential side channels. For example, there have been attacks based on using a laser down the communication line to track the orientation of the measurement device at the receiver.
In general, the more you can do while the data stays quantum the better. For example, if you transduce the photon into a qubit inside a quantum computer, then the measurement can be hidden away inside the computer, instead of exposed to the communication line. And the measurement basis can be chosen after transmission arrival, instead of before.
I recommend just simulating the specific case you're worried about. It's only a 15 qubit circuit; not at all expensive to check. You'll either see it working and stop worrying, or have an amazing concrete counter example to publish.
First, it says if you can't do accurate rotations then you can't factor. But the premise is false. Quantum error correction allows you to do arbitrarily accurate rotations. Specifically, you can achieve arbitrarily accurate 45 degree rotations around the X and Z axes by using state distillation and gate teleportation [1], and all rotations can be approximated by a sequence of these 45 degree rotations with the error decreasing exponentially versus the length of the sequence [2]. The paper's justification for saying you can't do accurate rotations is that they think quantum mechanics will end up being wrong (see section 4).
Second, even if you assume for the sake of argument that rotations are inherently noisy, the conclusion doesn't actually follow. The mistake the paper makes is to assume the algorithm will use the textbook QFT circuit [3], which uses n^2/2 rotations for an n-qubit QFT, allowing large amounts of error to accumulate. But in practice, because this QFT is at the end of a circuit, you would use the qubit-recycling QFT which only performs n rotations [4]. Alternatively, if rotations were really such a problem, you could perform ~30 rotations to prepare what's known as a phase gradient state. You can then achieve later rotations via the phase kickback of adding a constant into the phase gradient controlled by the qubit you want to rotate [5]. In other words, the paper asserts you need millions of rotations to factor a 2048 bit number when actually you only need dozens. Everything else can be done with Clifford+Toffoli gates.
So yeah, this paper is not at all a convincing takedown of quantum factoring. The formal part focuses on the wrong cost and the informal justification is that they think quantum mechanics is wrong.
[1]: https://en.wikipedia.org/wiki/Magic_state_distillation
[2]: https://www.mathstat.dal.ca/~selinger/newsynth/
[3]: https://en.wikipedia.org/wiki/Quantum_Fourier_transform#/med...
[4]: figure 3 of https://arxiv.org/pdf/1706.07884#page=5 is an example
A ball falling on the ground can be converted into a math problem. To get the conversion exactly right you will need to write down the exact state of the ball. But you will invariably incur small inaccuracies while doing this. For example, maybe the mass you write down is off by 1 part in a trillion. The math problem is the ground truth, so any conversion inaccuracies are now errors in the ball. In practice these inaccuracies will prevent even the original ball from solving the written down problem much better than you could with a computer.
In the case of random circuit sampling, the written down problem is a tensor network [1] (that happens to also be a shallow quantum circuit). Fundamentally, a tensor network just specifies a bunch of matrix multiplications to do. It's not even that big of a problem: only a few kilobytes of information (whereas the exact state of a ball would be gargantuan). All you have to do is perform the specified multiplications, interpret the result as a probability distribution, and sample from it. The obstacle is that these multiplications create intermediate values that are really really large. The quantum computer bypasses this obstacle by executing the tensor network as a circuit.
I do agree quantum computers disprove local hidden variable models. Because they can run Bell tests, and local hidden variable models can't violate the Bell inequalities.
I'm often tempted to argue quantum computers at least clearly favor ontic interpretations (ones where quantum states are real). Because good luck computing things by subjectively having a computer instead of actually having a computer. But, as far as I know, you don't see quantum-bayesianism-ists having any qualms with quantum computers. I think because if you're already biting the bullet of interpreting diagonally polarized light as subjective, and Bell tests as subjective, then interpreting a computation as subjective isn't fundamentally different. It's just more in your face about it.
There are several experiments that claim to factor 15 with a quantum computer (e.g. [1][2]). But beware these experiments cheat to various degrees (e.g. instead of performing period finding against multiplication mod 15 they do some simpler process known to have the same period). Even without cheating, 15 is a huge outlier in the simplicity of the modular arithmetic. For example, I think 15 is the only odd semiprime where you can implement modular multiplication by a constant using nothing but bit flips and bit swaps. Being so close to a power of 2 also doesn't hurt.
Beware there's a constant annoying trickle of claims of factoring numbers larger than 15 with quantum computers, but using completely irrelevant methods where there's no reason to expect the costs to scale subexponentially. For example, Zapata (the quantum startup that recently went bankrupt) had one of those [3].
[1]: https://www.nature.com/articles/414883a
Depending on your interests, the initial insensitivity of largest-number-factored as a metric is either great (it reduces distractions) or terrible (it fails to accurately report progress). For example, if the actual improvement rate were 10x per year instead of 2x per year, it'd be 3 years until you realized RSA2048 was going to break after 2 more years instead of 12 more years.
This is the first quantum error correction experiment showing actual improvement as size is increased (without any cheating such as postselection or only running for a single step). It was always believed in theory that bigger codes should have more protection, but there are have been various skeptics over the years saying you'd never actually see these improvements in practice due to the engineering difficulty or due to quantum mechanics breaking down or something.
Make no mistake; much remains to be done. But this experiment is a clear indication of progress. It demonstrates that error correction actually works. It says that quantum computers should be able to solve qubit quality with qubit quantity.
disclaimer: worked on this experiment
Disclaimer: am one of the authors, but not a main contributor. I wrote the simulator they used and made some useful suggestions on how to use it to extract information they wanted for training the models more efficiently, but know nothing of transformers.
(2) easier experiments. Currently, doing a loophole free Bell inequality test is hard enough that people get PhDs for it. With a quantum network that experiment is way easier, because the network solves the hard part (distributing the entanglement). You could probably also use quantum networks for other experimental tasks, like coherently linking telescopes on separate continents, though the bandwidth and computational requirements for that would probably be a bit insane.
There are also some more out there ideas, like if stock markets contain Bell inequalities then you could use a quantum network to build up entanglement that is then consumed to win those games more often which equals $$$. But it's hard to imagine concrete scenarios that would create such an inequality, nevermind one where the expected dollars gained from the quantum strategy exceeded the cost of operating the network.
No, you don't have to do that. A quantum network would be a web of point-to-point quantum links, with paths formed by routers choosing links. Same as a classical network.
To be a bit more concrete what an operating quantum network would look like is a bunch of routers using links to build up entanglement with their neighbors. When an endpoint wants to send a message across the network, a path from source to destination would be determined and entanglement across the links of that path would be consumed to move the message across the network [1][2]. The reason it's done this way, instead of directly sending the message, is that entanglement can be cross-checked before using it [3] and quantum networks really don't like dropping packets due to the no-cloning theorem.
> We typically don't call them networks until we start linking them all together with simple routing logic
Yeah I agree that it would be more accurate for this press release to say they made a quantum link.
> To me these are all just signs that the whole scheme is/was and will forever be mostly crankery.
Don't confuse difficulty with crankery. It'll be awhile before anyone reports an experimental realization of a true quantum network, because it'll be awhile because anyone can make a quantum router. The issue is that a quantum router is for all intents and purposes a fault tolerant quantum computer, and that is its own hard challenge being worked on separately. In particular, a quantum router needs to be able to store qubits reliably for non-trivial amounts of time, and to perform reliable operations on those qubits in order to cross-check stored entanglement.
[1]: https://en.wikipedia.org/wiki/Quantum_teleportation
[2]: https://en.wikipedia.org/wiki/Quantum_entanglement_swapping
[3]: https://en.wikipedia.org/wiki/Entanglement_distillation
In figure 3 of the paper [1] the heralded infidelity of entanglement is reported to be around 45%. That's not good enough for computation, but it's less than 50% which means it makes purification to arbitrarily low infidelity possible. However, the conversion rates would be pretty brutal for such a high infidelity start (e.g. millions of physical pairs consumed per logical pair good enough for use in a fault tolerant computation e.g. a target logical infidelity of 1e-6 or 1e-9).
> With an error rate of 1% the surface error correction code requires ~ 500 physical qubits required to encode one logical qubit.
This was the correction near the end:
> With an error rate of 0.3% the surface error correction code requires ~ 10 thousand physical qubits to encode one logical qubit to achieve 10^-10 logical qubit error rate.
The qubit count at an error rate of 1% was clearly off because the threshold of the surface code under circuit noise is a bit below 1%. Meaning at 1% it would have infinite cost; way more than 500. To get good numbers you need be well below the threshold. At a 0.1% error rate, assuming a square grid of qubits with local connections, the best physical-per-logical estimate that I'm aware of is 600, from surface codes plus a few extra parity checks layered on top [1][2]. Another code that achieves a teraquop footprint of ~600 on a planar grid is the honeycomb code [3][4] but that number requires a dissipative two qubit gate which seems to be harder to build than the usual unitary ones.
[1]: https://www.youtube.com/watch?v=Ge7fEaXjvq4
[2]: https://arxiv.org/pdf/2312.04522
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.