1

D-Wave has teased the ability to perform integer factorization previously, but if you jump to ~10:00 in this presentation they actually appear to outline how they can perform integer factorization using quantum annealing and at ~12:10 they can produce a D-Wave machine (maybe as an NSA special order) that can factor 2n bit number with 2n2 qubits.

  1. How many qubits does this translate into using their architecture, i.e. is their "chain length" caveat relevant here?
  2. Is there a simple way to apply this to ECC?

The numbers are seriously fuzzy (annual vs biannual qubit doubling, coherence limits, etc) but if it is simply a matter scaling up their raw qubit counts, then the expected lifetime for key length estimates get flattened out a bit for larger RSA lengths. If ECC is affected in a linear manner, then their expected lifetimes could be half that of the current estimates (2030-2060 vs 2050-2100).

Note: Please do not simply repeat generic complaints about D-Wave here. There are plenty of forums for that discussion, this is not one of them.

Indolering
  • 852
  • 6
  • 21
  • It's still uncertain if D-Wave has managed to build a quantum computer or not. – Mark Dec 06 '14 at 02:07
  • @Mark The smart money is that D-Wave is pulling off quantum computation, however, debates on D-Wave's general quantum-ness are off-topic (i.e. stating that the "chain length" issue is of a concern is on topic, saying it's "debatable" is not). – Indolering Dec 06 '14 at 02:09

1 Answers1

2

if you jump to ~10:00 in this presentation they actually appear to outline how they can perform integer factorization using quantum annealing and at ~12:10 they can produce a D-Wave machine (maybe as an NSA special order) that can factor 2n bit number with 2n^2 qubits.

First he describes that you can describe RSA as an optimization problem. But you can do that is a large class of problems, many of which are not believed to be efficiently computable on QCs. It should be straightforward to encode SAT problems like this, and those are NP complete. I'm also pretty sure that you can encode breaking symmetric crypto that way. The optimality results around Grover's algorithm make it unlikely that there is a generic algorithm that can efficiently solve all problems that can be encoded like this.

He does not mention any RSA/factoring specific insight. It's theoretically possible that the specific structure of factoring means that the optimization algorithm would solve the problem efficiently. But the talk did not contain any hint of evidence towards this. It's also lacking any evidence for a speedup beyond grover or even classic computing.

CodesInChaos
  • 11,854
  • 2
  • 40
  • 50