LogoQCoder Programming Contest 003
Sign in
← Previous ProblemNext Problem →

B4: Reflection Operator I

Time Limit: 3 sec

Memory Limit: 512 MiB

Score: 200

Writer: Not_Leonian

Editorial

For integers xx with 0≤x<2n0 \leq x < 2^n, applying the operator A=2∣0⟩⟨0∣−IA = 2\ket{0}\bra{0} - I to ∣x⟩\ket{x} results in the following:

(2∣0⟩⟨0∣−I)∣x⟩=2∣0⟩⟨0∣x⟩−∣x⟩={∣x⟩(x=0)−∣x⟩(x≠0)\begin{align} (2\ket{0}\bra{0} - I) \ket{x} &= 2\ket{0} \braket{0|x} - \ket{x} \nonumber \\ &= \begin{cases} \ket{x} & (x = 0) \\ -\ket{x} & (x \neq 0) \end{cases} \end{align}

There are multiple approaches to implementing this operation.

Solution 1

Since this problem does not concern global phase, we can consider the following operation:

∣x⟩→{−∣x⟩(x=0)∣x⟩(x≠0)\begin{equation} \ket{x} \xrightarrow{} \begin{cases} - \ket{x} & (x = 0) \\ \ket{x} & (x\neq 0) \end{cases} \end{equation}

By applying XX gates to all qubits, ∣0⟩\ket{0} is transformed to ∣2n−1⟩\ket{2^n - 1}. Next, by designating one qubit as the target bit and the remaining (n−1)(n-1) qubits as control bits, we can apply a multi-controlled ZZ gate to invert the sign of the computation basis state ∣2n−1⟩\ket{2^n - 1} only in the superposition. Finally, by applying XX gates again to all qubits, the desired operation is achieved.

For the case where n=3n = 3, the circuit diagram is shown below.

Solution 2

Similar to Solution 1, we leverage the fact that changes in the global phase are not considered. Let the lower (n−1)(n-1) bits of xx be xlx_l, and the upper 11 bit be xhx_h. Also, let the number obtained by flipping all bits of xlx_l and xhx_h be represented as ¬xl\lnot x_l and ¬xh\lnot x_h, respectively. Thus, we have ∣x⟩=∣xl⟩n−1∣xh⟩1\ket{x} = \ket{x_l}_{n-1} \ket{x_h}_1. After applying the XX gates to ∣x⟩\ket{x} and then applying the HH gate to the nn-th bit, we obtain:

∣x⟩→X∣¬xl⟩n−1∣¬xh⟩1→H{12(∣¬xl⟩n−1∣0⟩1−∣¬xl⟩n−1∣1⟩1)(xh=0)12(∣¬xl⟩n−1∣0⟩1+∣¬xl⟩n−1∣1⟩1)(xh=1)\begin{equation} \ket{x} \xrightarrow{X} \ket{\lnot x_l}_{n-1} \ket{\lnot x_h}_1 \xrightarrow{H} \begin{cases} \frac{1}{\sqrt{2}} (\ket{\lnot x_l}_{n-1} \ket{0}_1 - \ket{\lnot x_l}_{n-1} \ket{1}_1) & (x_h=0) \\ \frac{1}{\sqrt{2}} (\ket{\lnot x_l}_{n-1} \ket{0}_1 + \ket{\lnot x_l}_{n-1} \ket{1}_1) & (x_h=1) \end{cases} \end{equation}

Next, by applying a multi-controlled XX gate with the (n−1)(n-1) bits excluding the nn-th bit as control bits and the nn-th bit as the target bit, we get:

{12(∣¬xl⟩n−1∣0⟩1−∣¬xl⟩n−1∣1⟩1)(xh=0)12(∣¬xl⟩n−1∣0⟩1+∣¬xl⟩n−1∣1⟩1)(xh=1)→MCX{12(∣¬xl⟩n−1∣1⟩1−∣¬xl⟩n−1∣0⟩1)(xl=0, xh=0)12(∣¬xl⟩n−1∣1⟩1+∣¬xl⟩n−1∣0⟩1)(xl=0, xh=1)12(∣¬xl⟩n−1∣0⟩1−∣¬xl⟩n−1∣1⟩1)(xl≠0, xh=0)12(∣¬xl⟩n−1∣0⟩1+∣¬xl⟩n−1∣1⟩1)(xl≠0, xh=1)\begin{equation} \begin{cases} \frac{1}{\sqrt{2}} (\ket{\lnot x_l}_{n-1} \ket{0}_1 - \ket{\lnot x_l}_{n-1} \ket{1}_1) & (x_h=0) \\ \frac{1}{\sqrt{2}} (\ket{\lnot x_l}_{n-1} \ket{0}_1 + \ket{\lnot x_l}_{n-1} \ket{1}_1) & (x_h=1) \end{cases} \xrightarrow{MCX} \begin{cases} \frac{1}{\sqrt{2}} (\ket{\lnot x_l}_{n-1} \ket{1}_1 - \ket{\lnot x_l}_{n-1} \ket{0}_1) & (x_l=0, \ x_h=0) \\ \frac{1}{\sqrt{2}} (\ket{\lnot x_l}_{n-1} \ket{1}_1 + \ket{\lnot x_l}_{n-1} \ket{0}_1) & (x_l=0, \ x_h=1) \\ \frac{1}{\sqrt{2}} (\ket{\lnot x_l}_{n-1} \ket{0}_1 - \ket{\lnot x_l}_{n-1} \ket{1}_1) & (x_l\neq 0, \ x_h=0) \\ \frac{1}{\sqrt{2}} (\ket{\lnot x_l}_{n-1} \ket{0}_1 + \ket{\lnot x_l}_{n-1} \ket{1}_1) & (x_l\neq 0, \ x_h=1) \end{cases} \end{equation}

By noting that 12(∣¬xl⟩n∣1⟩1−∣¬xl⟩n∣0⟩1)=−12(∣¬xl⟩n∣0⟩1−∣¬xl⟩n∣1⟩1)\frac{1}{\sqrt{2}}(\ket{\lnot x_l}_n\ket{1}_1-\ket{\lnot x_l}_n\ket{0}_1)=-\frac{1}{\sqrt{2}}(\ket{\lnot x_l}_n\ket{0}_1-\ket{\lnot x_l}_n\ket{1}_1) and 12(∣¬xl⟩n∣1⟩1+∣¬xl⟩n∣0⟩1)=12(∣¬xl⟩n∣0⟩1+∣¬xl⟩n∣1⟩1)\frac{1}{\sqrt{2}}(\ket{\lnot x_l}_n\ket{1}_1+\ket{\lnot x_l}_n\ket{0}_1)=\frac{1}{\sqrt{2}}(\ket{\lnot x_l}_n\ket{0}_1+\ket{\lnot x_l}_n\ket{1}_1), after applying the HH gate to the nn-th bit and applying the XX gates to all qubits, we have:

{12(∣¬xl⟩n−1∣1⟩1−∣¬xl⟩n−1∣0⟩1)(xl=0, xh=0)12(∣¬xl⟩n−1∣1⟩1+∣¬xl⟩n−1∣0⟩1)(xl=0, xh=1)12(∣¬xl⟩n−1∣0⟩1−∣¬xl⟩n−1∣1⟩1)(xl≠0, xh=0)12(∣¬xl⟩n−1∣0⟩1+∣¬xl⟩n−1∣1⟩1)(xl≠0, xh=1)→H{−∣¬xl⟩n−1∣¬xh⟩1(xl=0, xh=0)∣¬xl⟩n−1∣¬xh⟩1(xl≠0∨xh=1)→X{−∣x⟩(x=0)∣x⟩(x≠0)\begin{align} \begin{cases} \frac{1}{\sqrt{2}} (\ket{\lnot x_l}_{n-1} \ket{1}_1 - \ket{\lnot x_l}_{n-1} \ket{0}_1) & (x_l=0, \ x_h=0) \\ \frac{1}{\sqrt{2}} (\ket{\lnot x_l}_{n-1} \ket{1}_1 + \ket{\lnot x_l}_{n-1} \ket{0}_1) & (x_l=0, \ x_h=1) \\ \frac{1}{\sqrt{2}} (\ket{\lnot x_l}_{n-1} \ket{0}_1 - \ket{\lnot x_l}_{n-1} \ket{1}_1) & (x_l\neq 0, \ x_h=0) \\ \frac{1}{\sqrt{2}} (\ket{\lnot x_l}_{n-1} \ket{0}_1 + \ket{\lnot x_l}_{n-1} \ket{1}_1) & (x_l\neq 0, \ x_h=1) \end{cases} & \xrightarrow{H} \begin{cases} -\ket{\lnot x_l}_{n-1} \ket{\lnot x_h}_1 & (x_l=0, \ x_h=0) \\ \ket{\lnot x_l}_{n-1} \ket{\lnot x_h}_1 & (x_l\neq 0\lor x_h=1) \end{cases} \\ & \xrightarrow{X} \begin{cases}-\ket{x} & (x=0) \\ \ket{x} & (x\neq 0) \end{cases} \end{align}

For the case where n=3n = 3, the circuit diagram is shown below.

Sample Code

Below is a sample program:

Solution 1

from qiskit import QuantumCircuit
from qiskit.circuit.library import ZGate
 
 
def solve(n: int) -> QuantumCircuit:
    qc = QuantumCircuit(n)
 
    qc.x(range(n))
    qc.append(ZGate().control(n - 1), range(n))
    qc.x(range(n))
 
    return qc

Solution 2

from qiskit import QuantumCircuit
 
 
def solve(n: int) -> QuantumCircuit:
    qc = QuantumCircuit(n)
 
    qc.x(range(n))
    qc.h(n - 1)
    qc.mcx(list(range(n - 1)), n - 1)
    qc.h(n - 1)
    qc.x(range(n))
 
    return qc