Menu

Quantum-computing related developments

On this page we post about interesting quantum-computing related research and news which we are following.

Variational Quantum Factoring

Variational Quantum Factoring

Cryptography

Ever since the publication of Shor’s algorithm in 1994, efficient integer factorization has been a key application area envisioned for quantum-computers, with important implications for the security of some of the most used cryptosystems. Because Shor’s algorithm requires a large-scale fault-tolerant quantum-processor, RSA-3072 encryption was so-far believed to remain safe until 2030. However, in recent years hybrid (classical-quantum) alternatives have been developed for many important quantum-algorithms. Such hybrid algorithms can be run on current-day noisy and small-scale quantum-processors. In this paper Eric Anschuetz et al. describe such a hybrid alternative for Shor’s algorithm, which they call variational quantum factoring (VQF). If some pre-processing is applied VQF scales with O(n), n being the number of bits of the integer being factored. If VQF can be optimized to scale well up to 3000+ qubits, which is very challenging, but not completely unthinkable, and if we assume the number of physical qubits in quantum-processors doubles every year, quantum-processors could have sufficiently high qubit count to break RSA-3072 as early as 2025. However, as VQF relies on a quantum-optimization algorithm (QAOA) it seems unlikely that the speed-up of VQF could be more than quadratic, which means that the runtime for breaking RSA-3072 could very well be prohibitively long and that doubling the RSA-6144 (double the key-length) would again be just  as safe as RSA-3072 is currently.

Design of quantum annealing machine for prime factoring

Design of quantum annealing machine for prime factoring

Cryptography

Quantum annealers can be used to solve optimization and sampling problems. However,  they can also solve certain combinational logic problems on the basis of an Ising-model implementation of Boolean logic. In this paper, Maezawa et al. propose a prime factoring machine operated in a frame work of quantum annealing (QA). The idea is inverse operation of a quantum-mechanically reversible multiplier implemented with QA-based Boolean logic circuits. They discuss their plan toward a practical-scale factoring machine from concept to technology.

Low qubit-resource quantum factoring algorithm

Low qubit-resource quantum factoring algorithm

Cryptography

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.