A4: Cyclic Shift Oracle II

Editorial

Consider the swap gate that we implemented in problem A2.

Solution 1

First, let's consider $2$ qubits swap. Swapping the first and second qubits can be achieved using a controlled $X$ gate, and the state transitions are as follows.

Next, we focus on the state transitions when the second qubit is $0$, i.e., $\ket{00}$ and $\ket{10}$.

Consequently, we can see that the first $CX(0, 1)$ and the next $CX(1, 0)$ realize the swap of $2$ qubits. By utilizing this, we can solve this problem.

Given that $x_{n-1} = 0$, $x_{n-2}$ and $x_{n-1}$ can be swapped in $2$ steps, and the state transitions are give by

Similarly, when $x_{n-1} = 0$, $x_{n-3}$ and $x_{n-1}$ can be swapped in $2$ steps, and the state transitions are given by

By repeating this operation $n-1$ times, the desired quantum state $\ket{x_{n-1} x_0 x_1 \cdots x_{n-2}}$ can be prepared with a depth of $2(n-1)$.

The circuit diagram for $n = 3$ is as follows.

Solution 2

As mentioned in the editorial of A2, the XOR swap algorithm is a classical algorithm to swap $2$ variables $x$ and $y$ in $3$ steps. When $y=0$, the third step of "replace $y$ with $x + y \pmod 2$" can be omitted, so XOR swap can be achieved in $2$ steps by replacing "replace $y$ with $x + y \pmod 2$" and "replace $x$ with $x + y \pmod 2$". By utilizing this, we can solve this problem.

First, replace $y$ with $x + y \pmod 2$ using a controlled $X$ gate for $1, 2, \ldots, n-1$ bits.

for i in reversed(range(n - 1)):
    qc.cx(i, i + 1)  

Next, replace $x$ with $x + y \pmod 2$ using a controlled $X$ gate for $1, 2, \ldots, n-1$ bits.

for i in reversed(range(n - 1)):
    qc.cx(i + 1, i)  

Consequently, the desired quantum state $\ket{x_{n-1} x_0 x_1 \cdots x_{n-2}}$ can be prepared with a depth of $2(n-1)$.

The circuit diagram for $n = 3$ is as follows.

Sample Code

Below is a sample program:

Solution 1

from qiskit import QuantumCircuit
 
 
def solve(n: int) -> QuantumCircuit:  
    qc = QuantumCircuit(n)  
 
    for i in reversed(range(n - 1)):
        qc.cx(i, i + 1)
        qc.cx(i + 1, i)
 
    return qc

Solution 2

from qiskit import QuantumCircuit
 
 
def solve(n: int) -> QuantumCircuit:  
    qc = QuantumCircuit(n)
 
    for i in reversed(range(n - 1)):
        qc.cx(i, i + 1)
 
    for i in reversed(range(n - 1)):
        qc.cx(i + 1, i)
 
    return qc