# what benefits quantum offer over classical parallelism

What is the benefits of quantum computing vs parallel processing using classical computer ?

Can classical parallel processors outperform quantum computing ?

• Remainder: one 1970 Intel 4004 outperforms by orders of magnitude any available quantum computing device of a structure hoped/feared to become, in the future, usable for cryptanalysis (this excludes quantum-named computers specialized in quantum annealing, which do not aim at running Grover's or Shor's algorithms). – fgrieu Oct 23 '18 at 17:23

1. What is the benefits of quantum computing vs parallel processing using classical computer?

The answer is in terms of Cryptography;

## Quantum Computing (QC)

• Key search on Block ciphers; Grover's algorithm is a brute-force quantum algorithm with complexity $$\mathcal{O}(\sqrt{N})$$ with asymptotically optimal on unstructured data.

• Public key algorithms;

• RSA factorization problem; Shor's algorithm can efficiently factor integer $$n$$ in $$\mathcal{O}((\log n)^2(\log \log n)(\log \log \log n)$$
• Discrete logarithm problem; Shor's algorithm can efficiently solve.

Therefore, RSA, Diffie–Hellman, and Elliptic Curve Diffie–Hellman could be broken easily.

## Parallelization

• Parallel computing in keys searches only help linear time whereas using single QC already gives quadratic speed up. Examples are Distributed.net, DES Cracker, COPACOBANA hashcat
• Parallel computing is used in factorization algorithms where the help again is linear with complexity;

General Number Field Sieve with superpolynomial scaling: $$\mathcal{O}(exp [ c (\ln n)^{1/3} (\ln \ln n)^{2/3}])$$

2. Can classical parallel processors outperform quantum computing?

Firstly, quantum give new complexity classes;

The class of problems that can be efficiently solved by quantum computers is called BQP, for "bounded error, quantum, polynomial time".7

BQP is suspected to be disjoint from NP-complete and a strict superset of P, but that is not known. Both integer factorization and discrete log are in BQP.

Some $$NP$$ problems can be solved efficiently.

A Turing machine can simulate a QC and QC can simulate A Trung machine too,. So, once A QC is built, you can outperform a QC only by money.

## Cost2

An important subject is also the cost of running the algoriths.

Daniel J. Bernstein asked the question in "Cost analysis of hash collisions: Will quantum computers make SHARCS1 obsolete". Some results if a QC is built;

• Factorization; QC much more scalable and much more cost effective

• The number-field sieve factors b-bit RSA moduli in time $$2^{b^{1/3+\mathcal{o}(1)}}$$
• If a QC can be built for $$b^{\mathcal{\Theta}(1)}$$ Euros can factor b-bit integer in $$b^{\mathcal{\Theta}(1)}$$ seconds.
• Pre-Image Search;

• Traditional hardware can find in $$2^bh$$ operations
• Quantum; much more cost effective

• Grover $$2^{b/2}h$$ operations on $$\mathcal{\Theta}(h)$$ qubits.
• Shor’s speedup from $$2^{b^{1/3+\mathcal{o}(1)}}$$ to $$b^{\mathcal{\Theta}(1)}$$
• Collision search; He claims that all quantum algorithms upto his paper are less cost-effective than the traditional.

• Parallelization

• A size-$$M$$ machine finds collisions in time roughly $$2^b/M^{3/2}$$. if size $$2^{b/3}$$ than collision time is $$2^{b/2}$$ with $$\epsilon$$ time with $$\epsilon$$ probability.
• a size-M QC after $$2^{b/2}h\epsilon$$ quantum operations each unit has $$\epsilon^2$$ success probability. After $$2^{b/2}h/M^{1/2}$$ total quantum operations the size-M machine has $$M\epsilon^2$$ success probability. If the size a quantum computer is $$2^{b/3}$$ then the time for finding collisions is approximately $$2^{b/3}$$. Compare to classical.