Is it possible to massively speed up ray tracing by representing geometry in a quantum program and then using superposition to evaluate many ray paths simultaneously? That would be exciting in <N> years for real time accurate ray tracing.
This is just a wild guess without much knowledge of quantum computing at all though.
Quantum computers don't really compute many things in parallel. Or rather, they do, but the problem is getting the results out.
To stick with your ray tracing question, you could probably indeed trace an exponentially (in the size of the computer) number of rays, but at the end you have to do go back to the classical world to actually read out data, and you'd essentially be able to only read out the result of one ray picked at random.
Quantum computers are only know to provide exponential speedups in cases where there is some algebraic structure to exploit when condensing the exponentially many computations down to a single result. That's why you can get an exponential speedup for factoring or discrete logarithm, but not for symmetric cryptography or really any other useful problem (except for the kind of circular problem of simulating quantum systems).
That's what makes me personally hope that quantum computers will never scale. The likely outcome of quantum computing is the worst of all worlds: all known practically useful cryptography will be broken, and practically nothing will really benefit.
Quantum computers do not break "all known practically useful cryptography".
For symmetric crypto, some schemes will have to be dropped, and others will require larger keys. But we can (for example) just keep right on using AES 256.
For asymmetric crypto, we'll have to switch to some new schemes, but those exist (though I don't know of any current software using them). For example:
It's true that symmetric crypto isn't entirely broken by quantum computers, although in many cases the key sizes need to be doubled. However, I wrote my original statement with that fully in mind, because symmetric crypto by itself is not really all that useful. All useful applications need at least some asymmetric crypto, even if it's just to distribute keys for more efficient symmetric crypto.
As for the alternatives to asymmetric crypto: I like lattices, I've studied them a lot myself, though not in a crypto context. But have you looked at the required key sizes of those alternative schemes? They're pretty horrible and not at all comparable to what we have today.
Obviously people will continue research on this, and perhaps something close to elliptic curves in terms of efficiency will be found. I certainly hope so, but I'm not holding my breath.
I agree that archived traffic is an issue as well, but personally I'm more worried about the future than the past.
I hadn't previously looked at lattice crypto in much detail, and was not aware the keys were as big as they are; thanks for pointing that out. That said, a big performance hit isn't necessarily the same thing as being practically unusable. It certainly explains why nobody's using it now. I'd be curious to read some concrete performance analyses.
A sibling comment points out one use case for symmetric-only crypto.
I'm also curious what people would actually do if forced to deal with a symmetric-only world.
I think it is more likely that we'd see cumbersome ways of dealing with key distribution than that people would just stop using crypto in all the places we rely on public key schemes today. Think symmetric keys printed on your bank statement (maybe with a qr code?) We'd definitely see it used a lot less than now.
That said, we'd probably have about the same number of people doing end to end email encryption; key distribution with an asymmetric scheme is no picnic either :P.
>The likely outcome of quantum computing is the worst of all worlds: all known practically useful cryptography will be broken, and practically nothing will really benefit.
I agree with you on the technical points, but I think this is a tad pessimistic.
Firstly, by the time we have quantum computing we will probably also have quantum cryptography. Quantum cryptography is secure against quantum computers and is also vastly more simple than existing crypto (no complicated algorithms to mess up). So I expect cryptography to improve.
Secondly, while quantum computers won't be useful for everything, they will have amazing applications. The "simulating quantum systems" thing will be hugely useful for studying chemistry. And Grover's algorithm will provide a significant speedup for a whole host of interesting problems, especially in machine learning.
> Firstly, by the time we have quantum computing we will probably also have quantum cryptography.
I disagree for two reasons.
First, because there is a huge difference between having a single quantum computer and quantum computers in every household.
Second, because we don't need quantum cryptography, we need post-quantum cryptography. Quantum computers break only asymmetric cryptosystems, but despite common belief, quantum cryptography doesn't solve this! Post-quantum cryptography does, and there is already good promise in this field.
My point was that quantum cryptography doesn't solve anything that classic cryptography doesn't. (And yes there is classic cryptography that isn't broken by quantum computers.) I'll defer to two of the world's leading cryptographers to back me up:
> Quantum cryptography is secure against quantum computers and is also vastly more simple than existing crypto (no complicated algorithms to mess up).
Can you explain this statement? I understand that algorithms such as RSA might require particular padding or what have you to be secure in practice, but is quantum-resistant crypto much different?
The phrase "quantum-resistant crypto" usually means classical algorithms (e.g. those involving elliptic curves) that are resistant to quantum computers.
What I'm talking about is "quantum cryptography", in which qubits are actually used in the protocol. Quantum cryptography is also known to be secure against quantum computers (indeed it's secure against arbitrary amounts of computing resources, unless our theories of physics are wrong).
It's also simpler than RSA or elliptic curves, so I hope that (after the kinks are worked out) it will also be less susceptible to bad implementations and side-channel attacks.
Apologies as I misread "quantum" as "quantum-resistant" above. However, I would still contest that quantum key exchange is "simpler". I mean, you need a quantum channel and to accurately exchange qubits without disturbance. Not to mention a small initial secret. It doesn't really work too well with our current infrastructure.
Agree with most of your points. But I suspect building a quantum infrastructure will be easier (and therefore occur earlier) than building quantum computers.
>Not to mention a small initial secret
This is interesting, what are you referring to here?
Doesn't quantum transmission infrastructure require direct connections from A to B? I.e. you could use it for a single uninterrupted fiber cable, or for the channel between your antenna and a satellite, but not with our common fiber infrastructure that relies on repeaters / re-transmitters.
As soon as there's any device between you and the recipient that breaks the entanglement, all the guarantees of quantum encryption go out of the window, and it's possible to attack the comms at that retransmission point.
>Doesn't quantum transmission infrastructure require direct connections from A to B?
No, the retransmitters can preserve the entanglement (and A and B can verify that this has been done).
In fact (providing qubits can be stored) the transmission can be done indirectly and in advance.
The telecom company produces lots of entangled qubits and gives a bunch to each customer, keeping half of each pair for itself. Then when Alice wants to communicate securely with Bob they ask the telecom company to take the corresponding qubits and perform a joint measurement. This entangles Alice's qubits with Bob's (like making a connection at a telephone exchange). Then Alice and Bob can measure their qubits (in various bases) to create a one-time-pad.
The clever thing is that Alice and Bob can (by checking that on a portion of the qubits their results always matched when they used the same basis) verify that they did indeed have maximally entangled qubits and therefore no one was listening-in.
Encryption has become pervasive in modern communication, yet it is clear that we still need more to properly protect the things we are doing. Does the quantum infrastructure that you are proposing not imply an almost complete replacement of the current global communications network with quantum channels, or at least to shadow it with a co-extensive one for key distribution? Is that close to being feasible for mobile and other radio-connected devices?
It's completely different. The underlying mechanism is the fact that observing the state on one member of an entangled pair changes the state of the other member.
More specifically, the important fact is that it's impossible for three particles to be (maximally) entangled simultaneously. So you can verify that no one eavesdropped when you agreed your one-time-pad.
They get three photons to be entangled, but not "maximally entangled" in the (impossible) way that would be needed for someone to listen to a communication without being detected.
There were some researchers working on noise saying that entangling more qubits has exponential difficulty, it's easy to create quantum computer with couple of quibits that we're seeing now, but it will be impossible to use more. If that's the case, we're safe.
You're not wrong, but that is a fairly extreme fringe view. There is a strong consensus, based on very solid physics experiment and theory, that that is not the case.
Ray tracing is typically the kind of things you want to do as fast as possible, ideally in real time. Quantum computers will never work fast.
Also if I'm not mistaken ray tracing scales well with conventional computers : the quality of your output is proportional to the number of rays you simulate. So it's not an appropriate use case for quantum computers.
but it's not linear with the number of reflections and transissions, I guess, if you want physically correct materials. Or if you want aberations and, well, "quantum effects" like in the slit experiment.
This is just a wild guess without much knowledge of quantum computing at all though.