Skip to main content
Quantum Computing

Return to Answer

added 66 characters in body
Source Link
Tristan Nemoz ♦
Tristan Nemoz ♦
  • 8.9k
  • 3
  • 11
  • 39
from qiskit.circuit import QuantumRegister, QuantumCircuit def get_oracle(plaintext: str, ciphertext: str, insert_barriers=Trueinsert_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

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.

from qiskit.circuit import QuantumRegister, QuantumCircuit def get_oracle(plaintext: str, ciphertext: str, insert_barriers=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

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$.

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

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.

Source Link
Tristan Nemoz ♦
Tristan Nemoz ♦
  • 8.9k
  • 3
  • 11
  • 39

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=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$.