Quantum Computing Stack Exchange is a question and answer site for engineers, scientists, programmers, and computing professionals interested in quantum computing. It only takes a minute to sign up.
Sign up to join this community
I want to run a experiment like this:
Generate a bunch of random 12-character passwords like $``\texttt{<Bb\{Q,r2Qp8`}".$
Write an algorithm to randomly generate & compare value on quantum computer.
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:
Is it possible to run this program on existing quantum computers?
If so, how fast would it be?
I want to run a experiment like this:
- 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:
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.
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.
- 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:
As the characters are encoded in the amplitudes, you can use the SWAP test to check for closeness.
Here, the qubits are just classical bits so you could just measure them and check classically for equality.
- 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):
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.
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:
- 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.
- 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.
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.
