Quantum Computers Mainstream in 2018 and race ahead of Supercomputer power

Quantum Supremacy is when quantum computers become faster than classical computers. Once Quantum Computers surpass classical computers they will continue to improve at a FAR more rapid pace. Doubling the transistors on a regular chip might achieve double the performance doubling the qubits on a quantum computer can provide an exponential speedup depending upon the kind of problem it is trying to solve. Dwave has shown speed ups of 10,000 time or more by doubling the qubits in their quantum annealing systems.

This week IBM Q scientists announced that they built and measured a 50 qubit processor prototype. IBM aims to demonstrate capabilities beyond today’s classical systems with systems of this size.

Google and the startup Rigetti are also expected to hit 50 qubit universal quantum computers in the next few months.

The number of qubits in the universal systems are likely to be 100-200 by the end of 2018 and doubling every year thereafter. DWave will probably have improved architecture and 4000-10000 qubits by the end of 2018.

By 2020, a thousand universal qubits will be probable. These systems should be many times faster than classical computers in a broad range of problems.

There will likely be multiple announcements from DWave and the other players over the next few months.

Shor’s algorithms runs exponentially faster than the best known classical algorithm for factoring, the general number field sieve.

In 2010, classical factorisation of a 768-bit number, using hundreds of modern computers over a period of 2 years, with a total computational effort of ~10^20 operations.

A 2,000-bit number could be factorized by a quantum computer using ~3×10^11 quantum gates, and approximately a billion qubits, running for just over a day at a clock rate of 10 MHz.

A low-resource quantum factoring algorithm

A new quantum factoring algorithm that, assuming standard heuristics, uses just (log N) 2/3+o(1) qubits to factor an integer N in time L q+o(1) where L = exp((log N) 1/3 (log log N) 2/3) and q = p38/3 ≈ 1.387. For comparison, the lowest asymptotic time complexity for known pre-quantum factoring algorithms, assuming standard heuristics, is L p+o(1) where p > 1.9. The new time complexity is asymptotically worse than Shor’s algorithm, but the qubit requirements are asymptotically better, so it may be possible to physically implement it sooner.

They apply Shor’s algorithm serially. First they use Shor’s algorithm to split M into two factors, then they use Shor’s algorithm to split the largest factor that remains.

In April 2016 the 18-bit number 200099 was factored using quantum annealing on a D-Wave 2X quantum processor. In 2016, 291311 was factored using NMR at higher than room temperature

Grover’s algorithm runs quadratically faster than the best possible classical algorithm for the same task. Grover’s algorithm for searching an unstructured database or an unordered list.

The quantum Fourier transform is the quantum analogue of the discrete Fourier transform, and is used in several quantum algorithms. The Hadamard transform is also an example of a quantum Fourier transform over an n-dimensional vector space over the field F2. The quantum Fourier transform can be efficiently implemented on a quantum computer using only a polynomial number of quantum gates.