2
$\begingroup$

I've been trying around different things with Grover's algorithm, and would want to experiment a practical scenario with it by building an oracle to find an 8-bit key.

Very shortly explained, my thoughts for the oracle are as follows:

  1. The oracle would take the plaintext (in binary) and the ciphertext (in binary) as inputs.
  2. All the key candidates, e.g. all the 2^8=256 possibilities would be in superposition
  3. the plaintext would be applied the binary XOR operation with a key candidate to acquire the ciphertext.
  4. Compare the original ciphertext and the generated ciphertext. If they match, mark the state as correct (the state would be the key that was used to generate the ciphertext).

I've been trying to build the oracle using Qiskit, and have gotten to the point where i should implement the ciphertext comparison, and the marking of the correct state. but for some reason just cannot wrap my head around on how to do it.

For the XOR operation, I have used the BitwiseXORGate.

Any help would be appreciated

$\endgroup$
1
  • $\begingroup$ Hi and welcome to Quantum Computing SE. I would recommend to post your code to help others understand better where the problem is. $\endgroup$ Commented Jun 25 at 6:25

1 Answer 1

0
$\begingroup$

If I understand correctly, the plaintext and the ciphertext are the inputs of the problem, in the sens that the oracle you build is built from them. However, we can simply consider them as classical information. By doing so, the oracle thta we build accepts an $8$-qubit input and flips the input state if it is equal to $|\text{key}\rangle$ such that $\text{key}\oplus\text{plaintext}=\text{ciphertext}$.

In order to compute $\text{key}\oplus\text{plaintext}$, it is enough to apply $X$ gates on the indexes on which $\text{plaintext}$ is non-zero (by definition of the XOR operation).

From there, we want to check whether the resulting (basis, assuming the input is also a basis state, which is enough by linearity) state is equal to $\text{ciphertext}$. One way to do it is to apply a multi-controlled $Z$ gate. However, such a gate typically flips the state only if it is equal to $1\cdots1$. What we can do is thus to flip the indices where the ciphertext is supposed to be equal to $0$, so that if $\text{key}\oplus\text{plaintext}$ is equal to the ciphertext, this operation would transform it into $1\cdots 1$.

We can then apply our multi-controlled $Z$ gate by using a mcx gate surrounded by h gate, using the $HXH=Z$ identity.

Finally, now that we have flipped our state for the right input, we have to uncompute the transformations that our state underwent (at the exception of the flipping of course).

All in all, this gives the following code in Qiskit.

from qiskit.circuit import QuantumRegister, QuantumCircuit def get_oracle(plaintext: str, ciphertext: str, insert_barriers: bool = True) -> QuantumCircuit: assert len(plaintext) == len(ciphertext), "The lengths of the plaintext and ciphertext must match" n_bits = len(plaintext) # Key is n_bits-bit long qc = QuantumCircuit(n_bits) # We have to check whether the key XORed with the plaintext is equal to the ciphertext # First, we compute the key XORed with the plaintext, which is done via X gates for index, bit in enumerate(plaintext[::-1]): # [::-1] to comply with Qiskit's little-endian if bit == "1": qc.x(index) if insert_barriers: # Just for better visualization qc.barrier() # We now want to flip the state if it is equal to the ciphertext # A C^n-Z operation will flip the state if all qubits are in 1, we just have to # flip the bits of the state that should correspond to a 0 in the ciphertext for index, bit in enumerate(ciphertext[::-1]): # [::-1] to comply with Qiskit's little-endian if bit == "0": qc.x(index) if insert_barriers: # Just for better visualization qc.barrier() # Apply MCZ gate using MCX qc.h(n_bits - 1) qc.mcx(list(range(n_bits - 1)), [n_bits - 1]) qc.h(n_bits - 1) if insert_barriers: # Just for better visualization qc.barrier() # Reverse the X gates for index, bit in enumerate(ciphertext[::-1]): # [::-1] to comply with Qiskit's little-endian if bit == "0": qc.x(index) if insert_barriers: # Just for better visualization qc.barrier() for index, bit in enumerate(plaintext[::-1]): # [::-1] to comply with Qiskit's little-endian if bit == "1": qc.x(index) return qc 

As an example, we can try to build a $4$-qubit oracle with the plaintext being 0101 and the ciphertext being 1100 like so.

qc = get_oracle("0101", "0100") qc.draw("mpl") 

This gives us the following circuit. Oracle

You can convince yourself that this oracle will flip the (basis) input state if and only if it is equal to $|0001\rangle$. Note that I used Qiskit's little-endian convention, where the rightmost qubit in a tensor product is indexed $0$.


Tested with qiskit in version 1.4.2.

$\endgroup$
2
  • $\begingroup$ Thank you for your answer! I think this will help me get forward. $\endgroup$ Commented Jun 25 at 11:26
  • $\begingroup$ I edited your oracle to fit my present setup, so i ran it as it was in your answer. I randomly choose any printable ASCII character, and XOR encrypt that with another randomly chosen printable ASCII. So in binary, they are 8-bit. Your oracle succeeded in an AERsimulator execution with 99,99% probability of finding the correct encryption key, e.g. the randomly chosen ASCII key. $\endgroup$ Commented Jun 25 at 12:03

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.