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 ?
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.



and he added;


  Anyone afraid of quantum hash-collision algorithms already has much more 
   to fear from non-quantum hash-collision algorithms.




1 Special-Purpose Hardware for Attacking Cryptographic
Systems 

2 Special Thanks to Ella-Rose for the article.