Low qubit-resource quantum factoring

04 June 2017

Additional Info

  • Paper Title:

    ”A low-resource quantum factoring algorithm"

  • Paper Authors:

    Daniel J. Bernstein, Jean-François Biasse, and Michele Mosca (Univ. of Illinois, Eindhoven Univ., Univ. of South Florida, Univ. of Waterloo, Perimeter Institute, Canadian Institute for Advanced Research)

Qu&Co comments on this publication:

Shor's algorithm  for breaking both RSA and discrete-log public-key cryptography depend on the availability of a relatively large-scale quantum computer (e.g. Kutin et al. showed in 2006 that factoring a 1024-bit number requires 3132 qubits and 5.7x10^9 T gates). However, in quantum hardware developments are progressing while at the same time quantum algorithms are getting more efficient. So the timing when quantum computers will be able to break e.g. RSA is shifting. In this paper, Berstein et al. present a factoring algorithm that, assuming standard heuristics, uses a sublinear number of qubits. The time complexity of their new algorithm is asymptotically worse than Shor's algorithm, but the qubit requirements are asymptotically better, so it may be possible to physically implement the new algorithm sooner than Shor's algorithm.

What's Interesting?

How can we help you?

Invalid Input

Invalid Input

Invalid Input

Invalid Input

Invalid Input

Invalid Input

Copyright © Qu & Co BV
close