4 ms·

Glancing at the paper, I do not find anything that is impressive. AFAICS the algorithm they implement is of asymptotic exponential complexity, even when run on

Glancing at the paper, I do not find anything that is impressive. AFAICS the algorithm they implement is of asymptotic exponential complexity, even when run on a quantum computer. I cannot imagine how this work would have any effect on the field of asymmetric encryption algorithm research. To me it looks like they took the factorization problem, which has a lot of well-known (relatively) low-complexity algorithms and imlemented it by mapping it onto circuit-SAT [1] (the multiplication table corresponds to a multiplier circuit which they try to solve in reverse). Circuit-SAT is a proven NP-complete problem. There is currently no known quantum-algorithm that solves NP-complete problems in sub-exponential time. Note that in the complexity hierarchy NP-complete problems are "harder" than the factoring problem. These are generally bad problems, were not even a quantum-computer helps (and I know of no asymmetric encryption algorithm that is NP-complete when trying to break it, but maybe the quantum-resistant encryption algorithms are better in that regard). And that's even before we start talking about the limitations of quantum-annealers and the kind of speedups they can gain over classical computers. For a discussion of that, maybe one should start reading Scott Aaronson's blog [2]. [1] https://en.wikipedia.org/wiki/Circuit_satisfiability_problem https://en.wikipedia.org/wiki/Circuit_satisfiability_problem [2] https://www.scottaaronson.com/blog/?p=2555 https://www.scottaaronson.com/blog/?p=2555

ohvirginia 6y ago
But circuit sat is not equivalent to solving a multiplication table like this. If you're doing it that way, you're making it way too hard.
conformist 6y ago
This. Essentially, all the quantum annealing stuff that D-Wave does follows the patter of mapping a problem onto a spin glass and then finding the ground state with annealing. The only really interesting theoretical aspect is finding good maps form hard problems to spin glasses. This is a nice reference: https://arxiv.org/abs/1302.5843 https://arxiv.org/abs/1302.5843
betterunix2 6y ago
"asymmetric encryption algorithm that is NP-complete" No such cryptosystems are known, and in fact such a system would also have implications in complexity theory.

ohvirginia 6y ago

But circuit sat is not equivalent to solving a multiplication table like this. If you're doing it that way, you're making it way too hard.

conformist 6y ago

This. Essentially, all the quantum annealing stuff that D-Wave does follows the patter of mapping a problem onto a spin glass and then finding the ground state with annealing. The only really interesting theoretical aspect is finding good maps form hard problems to spin glasses. This is a nice reference: https://arxiv.org/abs/1302.5843 https://arxiv.org/abs/1302.5843

betterunix2 6y ago

"asymmetric encryption algorithm that is NP-complete" No such cryptosystems are known, and in fact such a system would also have implications in complexity theory.