4
$\begingroup$

I want to run a experiment like this:

  1. Generate a bunch of random 12-character passwords like $``\texttt{<Bb\{Q,r2Qp8`}".$

  2. Write an algorithm to randomly generate & compare value on quantum computer.

  3. If the value was found, return number of time it take to generate, let's say $6102111820800.$

The only available quantum computer I know of is IBM's quantum computing cloud service.

Questions:

  1. Is it possible to run this program on existing quantum computers?

  2. If so, how fast would it be?

$\endgroup$
  • $\begingroup$ "12 random string" or "a string composed of 12 random chars"? You want to generate this string with a quantum computer? And then to re-generate random strings using the same procedure until the same one is found? $\endgroup$ – Nelimee Jul 5 '18 at 15:46
  • $\begingroup$ @Nelimee it's "a string composed of 12 random chars", generate it as fast & many as the system can & see if the value you want show up, it could take billion or trillion time. I just learn about quantum computer recently & wonder if it can do this kind of operation $\endgroup$ – Huang Lee Jul 5 '18 at 16:18
  • 1
    $\begingroup$ Sounds like you hope that quantum computers can run through a list of possibilities very quickly to find a needle in a haystack. Is that about right? $\endgroup$ – Niel de Beaudrap Jul 5 '18 at 17:00
  • $\begingroup$ I tweaked your question a bit as far as I could understand it, though it still seems a bit unclear to me. For one spot, is that number, $6102111820800$, meant to be a count of attempts or an amount of time? And if time, is it measured in clock cycles or something? $\endgroup$ – Nat Jul 5 '18 at 17:01
  • 1
    $\begingroup$ @NieldeBeaudrap yeah, i just found a quantum slimutalor service which is pretty similar to my question demo.riverlane.io $\endgroup$ – Huang Lee Jul 5 '18 at 17:04
3
$\begingroup$

I want to run a experiment like this:

  1. Generate a bunch of random 12-character passwords like ";Bb{Q,r2Qp8`" (changed the first character because it interefed with the citation style).

Let's say your characters are encoded in extended ASCII, i.e. they have a value between 0 and 255. You need 8 classical bits to represent one character. One could expect that you could encode this value on 3 qubits ($2^3$), but you need to do a compromise here:

  1. If you have access to an external source of randomness, then you can use it to generate a random quantum state (by applying random gates to the initial quantum state for example). In this case, the amplitudes of the obtained quantum state may represent your character (you still need to find how to represent a random character from complex non-integer numbers) and depending on the encoding you use you may need less than 8 qubits.

  2. If you don't have access to an external source of randomness or if you want your random numbers to be "perfect", you can use quantum superposition and measurement to generate perfect random integers. This can be done by taking 8 qubits, applying the H gate to the 8 qubits and measuring them in the computational basis. With this algorithm, you will have 8 qubits in the state $\vert0\rangle$ or $\vert1\rangle$ (i.e. a random number on 8 qubits). With this method, 1 character = 8 qubits.

  1. Write an algorithm to randomly generate & compare value on quantum computer.

The generation can be done in the same way as above. For the comparison, it depends on the method you used for the generation and how you represent your characters:

  1. As the characters are encoded in the amplitudes, you can use the SWAP test to check for closeness.

  2. Here, the qubits are just classical bits so you could just measure them and check classically for equality.

  1. If the value was found, return number of time it take to generate, let's say 6102111820800.

Again, depending on what you want (but the bullet points here are not related to the methods above):

  1. You could count the try-fails in a classical register, just by incrementing a classical counter at each fail. If you used the SWAP test, you can measure the ancillary qubits and update the counter.

  2. If you want to encode your counter in a quantum state, you need a circuit that will increment the value of a register. You can find a way to construct such a circuit here for example. Then, if you used the SWAP test you can either read the qubit and apply the increment operation or directly apply the increment operation controlled by the state of the ancillary qubit.

The only available quantum computer I know of is IBM's quantum computing cloud service.

Questions:

  1. Is it possible to run this program on existing quantum computers?

It depends on the method you take: the first method may be able to run on an existing chips, but the second one would need at least $96 = 12*8$ qubits to store the 12 characters, which is above the maximum number of qubits currently available.

  1. If so, how fast would it be?

It will be sloooooooooooow. The first method may be able to use quantum superposition to speed-up the computations, but the second method uses quantum superposition only to generate random numbers, and then treat them classically.

$\endgroup$
  • $\begingroup$ i keep hearing that qubits take lots of space to store data compare to classical computer? How does this make quantum computer the future? $\endgroup$ – Huang Lee Jul 6 '18 at 7:57
  • $\begingroup$ i read that the ibm service has 20qbits available, so it can run 2^20 operation. Is that correct? How different it is compare to classical computer? $\endgroup$ – Huang Lee Jul 6 '18 at 7:59
  • $\begingroup$ Can we use quantum computer to store & search data? $\endgroup$ – Huang Lee Jul 6 '18 at 7:59
  • $\begingroup$ Each comment above deserve its own question on the main site because they are not really related to your original question :) $\endgroup$ – Nelimee Jul 6 '18 at 8:04
  • $\begingroup$ ok, i keep that in mind $\endgroup$ – Huang Lee Jul 6 '18 at 8:08
1
$\begingroup$

From the question title, it sounds like you're interested in brute-force password cracking.

There is a quantum algorithm for this that outperforms brute force, in principle. It's called Grover's algorithm and it was one of the earliest quantum algorithms to be discovered.

However, to crack a password, you need as many qubits in your quantum computer as you'd need bits in a traditional computer to hash the passwords (actually more, since you have to hash them reversibly, and that involves some overhead). This is orders of magnitude more qubits than any present-day quantum computer has, even for simple password hashing techniques. Also, the computation lasts for far longer than any present-day quantum computer can maintain the integrity of its qubits. And even if it worked, it's not very fast: testing $n$ passwords with Grover's algorithm takes about as long as testing $\sqrt{n}$ passwords by brute force.

$\endgroup$
  • $\begingroup$ no, i'm not even hash, just generate & compare value $\endgroup$ – Huang Lee Jul 8 '18 at 15:08

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.