4
$\begingroup$

Let's assume we developed a hashcat-like programs for quantum computer. How many qubits we need to find the correct hash (WPA, MD5,...) from a 10 characters password make from upper, lower & numeric characters (about 604,661,760,000,000,000 combinations)

$\endgroup$
4
$\begingroup$

$$ \log_2 604,661,760,000,000,000 \approx 59.07 $$

So use $60$ qubits for the data lines where you will put a uniform superposition. This gives a total of $61$ qubits to run Grover's.

$2^{59} = 5.764607523034e+17$ so if you can throw away about $2.8e+16$ possibilities first, you would be able to do it $60$.

Edit: As cautioned this is for logical qubits.

$\endgroup$
  • 2
    $\begingroup$ Should note these are logical error-corrected qbits, not physical qbits (lest we give the impression existing quantum computers can do this). $\endgroup$ – ahelwer Oct 2 '18 at 16:25
  • 1
    $\begingroup$ Also it will take millions of years to run, because you need to do a billion MD5 applications under superposition and a single AND gate takes on the order of a millisecond to apply under superposition. You're better off using a bunch of GPUs. $\endgroup$ – Craig Gidney Oct 2 '18 at 21:18
  • $\begingroup$ Thanks. I read that grover's algorithm can reduce search space to 2^(n/2) (2^30 in this case). Apply it to the program, can we make it to do the task with 30 qubits? $\endgroup$ – Dan Minh Toan Oct 3 '18 at 2:21
  • $\begingroup$ That's the asymptotic for length of the circuit not number of qubits. $\endgroup$ – AHusain Oct 3 '18 at 19:26
  • 1
    $\begingroup$ @QuanLee What do you mean by "in one go"? Grover's algorithm requires O(sqrt(N)) applications of the function, not just one. And overcoming the huge constant factor penalty of quantum computation vs classical computation means you need an unstructured problem with implausibly gigantic N before you see any advantage in absolute dollars. $\endgroup$ – Craig Gidney Oct 8 '18 at 6:26

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.