1
$\begingroup$

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

Can classical parallel processors outperform quantum computing ?

$\endgroup$
  • 1
    $\begingroup$ 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). $\endgroup$ – fgrieu Oct 23 '18 at 17:23
1
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Related paper by djb that discusses how the cost of some quantum attacks are not less than the cost of classical attacks $\endgroup$ – Ella Rose Oct 18 '18 at 19:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.