LogoQCoder Programming Contest 001
Sign in
← Previous EditorialNext Editorial →

B2: XOR Oracle

Time Limit: 3 seconds

Memory Limit: 512 MiB

Score: 200 points

Writer:admin

Editorial

The state after the application of the oracle y′=y⊕x1⊕x2⊕...⊕xny' = y \oplus x_1 \oplus x_2 \oplus ... \oplus x_n can be represented by placing parentheses and nesting the operation ⊕\oplus for two qubits as follows:

y⊕x1⊕x2⊕...⊕xn=(((y⊕x1)⊕x2)⊕...)⊕xn)\begin{equation} y \oplus x_1 \oplus x_2 \oplus ... \oplus x_n = (((y \oplus x_1) \oplus x_2) \oplus ... ) \oplus x_n) \end{equation}

That is, using each qubit from x1x_1 to xnx_n as control bits and yy as the target bit, the oracle can be realized by applying a total of nn CXCX gates.

y→CX(x1,y)y⊕x1→CX(x2,y)y⊕x1⊕x2       ...→CX(xn,y)y⊕x1⊕x2⊕...⊕xn\begin{align} y &\xrightarrow{CX(x_1, y)} y \oplus x_1 \nonumber\\ &\xrightarrow{CX(x_2, y)} y \oplus x_1 \oplus x_2 \nonumber\\ &\ \ \ \ \ \ \ ... \nonumber\\ &\xrightarrow{CX(x_n, y)} y \oplus x_1 \oplus x_2 \oplus ... \oplus x_n\\ \end{align}

Sample Code

Below is a sample program:

from qiskit import QuantumCircuit, QuantumRegister
 
 
def solve(n: int) -> QuantumCircuit:
    x, y = QuantumRegister(n), QuantumRegister(1)
    qc = QuantumCircuit(x, y)
 
    for i in range(n):
      qc.cx(x[i], y)
 
    return qc