7 ms·

In short, no. 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 yo

In short, no. 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.

OscarCunningham 9y ago
>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.
- Moodles 9y ago
  > 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?
  - charlieflowers 9y ago
    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.
    - OscarCunningham 9y ago
      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.
      - Kemschumam 9y ago
        Have you seen this recent result http://news.mit.edu/2018/physicists-create-new-form-light-0215 http://news.mit.edu/2018/physicists-create-new-form-light-02.... Does it change your thoughts on the utility of quantum cryptography?
        OscarCunningham 9y ago
        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.
  - OscarCunningham 9y ago
    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.
- notfed 9y ago
  > 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.
  - OscarCunningham 9y ago
    >but despite common belief, quantum cryptography doesn't solve this! ? You might not think that quantum cryptography is likely to be practical soon. But it is definitely resistant to quantum computers.
    - notfed 9y ago
      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: - https://www.schneier.com/essays/archives/2008/10/quantum_cryptography.html https://www.schneier.com/essays/archives/2008/10/quantum_cry... - https://cryptome.org/2012/09/bernstein-qke.htm https://cryptome.org/2012/09/bernstein-qke.htm
mirekrusin 9y ago
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.
- greeneggs 9y ago
  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.
xyproto 9y ago
A neural network can have many inputs but only one input. That could be useful?
zenhack 9y ago
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: https://en.m.wikipedia.org/wiki/Lattice-based_cryptography https://en.m.wikipedia.org/wiki/Lattice-based_cryptography The bigger worry I think is what about all of the existing traffic that has been archived?
- nhaehnle 9y ago
  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.
  - Buge 9y ago
    >All useful applications need at least some asymmetric crypto, even if it's just to distribute keys for more efficient symmetric crypto. File encryption, whether it be my entire hard drive, or just my password database, doesn't need asymmetric crypto.
  - zenhack 9y ago
    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.

OscarCunningham 9y ago

>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.

Moodles 9y ago
> 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?
- charlieflowers 9y ago
  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.
  - OscarCunningham 9y ago
    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.
    - Kemschumam 9y ago
      Have you seen this recent result http://news.mit.edu/2018/physicists-create-new-form-light-0215 http://news.mit.edu/2018/physicists-create-new-form-light-02.... Does it change your thoughts on the utility of quantum cryptography?
      - OscarCunningham 9y ago
        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.
- OscarCunningham 9y ago
  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.
notfed 9y ago
> 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.
- OscarCunningham 9y ago
  >but despite common belief, quantum cryptography doesn't solve this! ? You might not think that quantum cryptography is likely to be practical soon. But it is definitely resistant to quantum computers.
  - notfed 9y ago
    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: - https://www.schneier.com/essays/archives/2008/10/quantum_cryptography.html https://www.schneier.com/essays/archives/2008/10/quantum_cry... - https://cryptome.org/2012/09/bernstein-qke.htm https://cryptome.org/2012/09/bernstein-qke.htm

mirekrusin 9y ago

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.

greeneggs 9y ago
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.

xyproto 9y ago

A neural network can have many inputs but only one input. That could be useful?

zenhack 9y ago

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: https://en.m.wikipedia.org/wiki/Lattice-based_cryptography https://en.m.wikipedia.org/wiki/Lattice-based_cryptography The bigger worry I think is what about all of the existing traffic that has been archived?

nhaehnle 9y ago
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.
- Buge 9y ago
  >All useful applications need at least some asymmetric crypto, even if it's just to distribute keys for more efficient symmetric crypto. File encryption, whether it be my entire hard drive, or just my password database, doesn't need asymmetric crypto.
- zenhack 9y ago
  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.