5 ms·

Since questions about crypto came up, here's a summary paper by Daniel Bernstein about it: https://eprint.iacr.org/2017/314.pdf https://eprint.iacr.org/2017/31

Since questions about crypto came up, here's a summary paper by Daniel Bernstein about it: https://eprint.iacr.org/2017/314.pdf https://eprint.iacr.org/2017/314.pdf Symmetric cryptography would be safe even with quantum computers (they just half the effective bit length of the cypher with Grover's algorithm, which can be compensated for by increasing the key length). Classical asymmetric cryptography would be in danger, but there are alternative systems for which no quantum based attacks are known. They can be a bit unwieldy to use and have much larger key sizes than what we currently use - but methods that are hopefully quantum-proof may exist. The Lamport signature scheme is probably one of the methods that is the easiest to understand. Not all hope is lost for cryptography even with quantum computers.

dsacco 9y ago
The forecast for hash functions is also optimistic (same deal as symmetric encryption with respect to Grover's algorithm). Not all asymmetric key cryptography is in danger either. Lattice-reduction and McEliece encryption schemes don't have a known weakness to post-quantum computing.
reikonomusha 9y ago
As someone who works in the field of quantum computation, it's actually a little unpleasant that crypto always comes up. Crypto is interesting and quantum computers do have a part in it, but it's one of the least interesting things to talk about when it comes to what quantum computers can do. It's like at the advent of the regular computer, and the application everyone talks about is how it will be able to do accounting. It's right, but there are so many other interesting things it can do. To offer some fodder for further discussion, how about molecular and atomic simulation? Wouldn't it be nice if we could just simulate the behavior of a molecule to predict what useful properties it has? One could imagine just exhaustively searching for molecules of interest on a quantum computer. Or how about using a quantum computer to bootstrap itself? Using a QC to build a better QC is in the realm of its utility. Or how about solving some of these nasty computer science problems that crop their heads up everywhere, like graph coloring (or any of its equivalent incarnations)? Factoring integers and searching boxes are really interesting developments in the theory of quantum computation, but the above stuff, to me, sounds a lot cooler.
- comicjk 9y ago
  > Wouldn't it be nice if we could just simulate the behavior of a molecule to predict what useful properties it has? We already do this with classical computers to a significant extent. It requires a lot of approximations, but it works fairly well for several useful applications, such as drug/protein binding prediction. I am really looking forward to quantum co-processors to help with this kind of calculation.
- drdre2001 9y ago
  Good point. NIST has a list of 50 or so algorithms that will provide speedups when implemented on a Quantum Computer:http://math.nist.gov/quantum/zoo/ http://math.nist.gov/quantum/zoo/.
- Cybiote 9y ago
  I enjoyed your post but I have a disagreement. Graph Coloring is np-complete or np-hard depending on what question you're asking. Grover's algorithm for unstructured search only provides a quadratic boost. If you're pulling from the papers on adiabatic evolution, these are simulated small instances with acceptance probabilities that would likely not be economical in real world scenarios. For quantum computers to solve np-complete problems in polynomial time would be highly surprising and seems just too good of an outcome. Especially considering the work showing exponential slowdowns for simple problems that defeat local search algorithms like QA. That said, there'll likely be many practical problems for which quantum annealing provides speed ups which vastly outstrip classical computers.
  - p1esk 9y ago
    Can we use QC for deep learning?
runeks 9y ago
> Classical asymmetric cryptography would be in danger, but there are alternative systems for which no quantum based attacks are known. What about asymmetric crypto schemes executed on a quantum computer? All the discussions I've heard so far assume attackers have a quantum computer and everyone else have classical computers. To me, this seems like an unreasonable assumption. Won't there be a way to use a quantum computer to do asymmetric encryption in a way that makes it hard for it to reverse it?
- AnimalMuppet 9y ago
  There will be a long period of time (probably at least a decade, maybe even several) where large government agencies have quantum computers, maybe large businesses, but most people (and many small businesses) don't. (Remember that "computers" now includes your phone. I'm not sure how soon quantum chips come to phones...)
  - p1esk 9y ago
    What about D-Wave computers?
    - AnimalMuppet 9y ago
      If I understand correctly, D-Wave is not a general purpose quantum computer. It only works on certain specialized problems. And even there, there's still question of whether it actually works faster than a non-quantum computer.

dsacco 9y ago

The forecast for hash functions is also optimistic (same deal as symmetric encryption with respect to Grover's algorithm). Not all asymmetric key cryptography is in danger either. Lattice-reduction and McEliece encryption schemes don't have a known weakness to post-quantum computing.

reikonomusha 9y ago

As someone who works in the field of quantum computation, it's actually a little unpleasant that crypto always comes up. Crypto is interesting and quantum computers do have a part in it, but it's one of the least interesting things to talk about when it comes to what quantum computers can do. It's like at the advent of the regular computer, and the application everyone talks about is how it will be able to do accounting. It's right, but there are so many other interesting things it can do. To offer some fodder for further discussion, how about molecular and atomic simulation? Wouldn't it be nice if we could just simulate the behavior of a molecule to predict what useful properties it has? One could imagine just exhaustively searching for molecules of interest on a quantum computer. Or how about using a quantum computer to bootstrap itself? Using a QC to build a better QC is in the realm of its utility. Or how about solving some of these nasty computer science problems that crop their heads up everywhere, like graph coloring (or any of its equivalent incarnations)? Factoring integers and searching boxes are really interesting developments in the theory of quantum computation, but the above stuff, to me, sounds a lot cooler.

comicjk 9y ago
> Wouldn't it be nice if we could just simulate the behavior of a molecule to predict what useful properties it has? We already do this with classical computers to a significant extent. It requires a lot of approximations, but it works fairly well for several useful applications, such as drug/protein binding prediction. I am really looking forward to quantum co-processors to help with this kind of calculation.
drdre2001 9y ago
Good point. NIST has a list of 50 or so algorithms that will provide speedups when implemented on a Quantum Computer:http://math.nist.gov/quantum/zoo/ http://math.nist.gov/quantum/zoo/.
Cybiote 9y ago
I enjoyed your post but I have a disagreement. Graph Coloring is np-complete or np-hard depending on what question you're asking. Grover's algorithm for unstructured search only provides a quadratic boost. If you're pulling from the papers on adiabatic evolution, these are simulated small instances with acceptance probabilities that would likely not be economical in real world scenarios. For quantum computers to solve np-complete problems in polynomial time would be highly surprising and seems just too good of an outcome. Especially considering the work showing exponential slowdowns for simple problems that defeat local search algorithms like QA. That said, there'll likely be many practical problems for which quantum annealing provides speed ups which vastly outstrip classical computers.
- p1esk 9y ago
  Can we use QC for deep learning?

runeks 9y ago

> Classical asymmetric cryptography would be in danger, but there are alternative systems for which no quantum based attacks are known. What about asymmetric crypto schemes executed on a quantum computer? All the discussions I've heard so far assume attackers have a quantum computer and everyone else have classical computers. To me, this seems like an unreasonable assumption. Won't there be a way to use a quantum computer to do asymmetric encryption in a way that makes it hard for it to reverse it?

AnimalMuppet 9y ago
There will be a long period of time (probably at least a decade, maybe even several) where large government agencies have quantum computers, maybe large businesses, but most people (and many small businesses) don't. (Remember that "computers" now includes your phone. I'm not sure how soon quantum chips come to phones...)
- p1esk 9y ago
  What about D-Wave computers?
  - AnimalMuppet 9y ago
    If I understand correctly, D-Wave is not a general purpose quantum computer. It only works on certain specialized problems. And even there, there's still question of whether it actually works faster than a non-quantum computer.