A4: Generate State $\frac{1}{\sqrt{2}}\lparen\ket{0}-\ket{2^{n}-1}\rparen$ II

Editorial

The expected solution for Problem A3 has a quantum circuit depth of $n+1$, which exceeds the depth limit of this problem. So, how should we design the quantum circuit?

To reduce the depth of the quantum circuit, it's essential to avoid continuously applying quantum gates to the same qubit. Let’s take a look at the example of a $4$-qubit quantum circuit below:

The difference from the expected solution for Problem A3 is that the control qubit of the rightmost controlled $X$ gate has been changed from the $1$st qubit to the $2$nd qubit.

In this case, the rightmost controlled gate acts on the $2$nd and $4$th qubits, while the adjacent gate to the left operates on the $1$st and $3$rd qubits. Since these operations involve different qubit pairs, they can be executed simultaneously, reducing the quantum circuit depth by one.

Let’s examine the transition of the quantum states. Until the application of the second controlled $X$ gate, it is the same as the expected solution for Problem A3.

Next, apply a controlled $X$ gate with the $2$nd qubit as the control qubit and the $4$th qubit as the target qubit.

Finally, by applying a $Z$ gate, the phase of $\ket{11 \cdots 11}$ is inverted.

When generalizing this idea to a quantum circuit with $n$ qubits, first apply a Hadamard gate to the $1$st qubit and a controlled $X$ gate with the $1$st qubit as the control qubit and the $2$nd as the target qubit. Then, for $i = 1, 2, \ldots$, repeat the following operations while the target qubit does not exceed $n$:

• Apply a controlled $X$ gate with the $1$st qubit as the control qubit and the $2i + 1$-th qubit as the target qubit.
• Apply a controlled $X$ gate with the $2$nd qubit as the control qubit and the $2i + 2$-th qubit as the target qubit.

For example, when $n = 7$, the following quantum circuit can be constructed.

With the above operations, the depth of the quantum circuit becomes $\lfloor n/2 \rfloor + 3$ or less, which satisfies the given constraint.

Sample Code

Below is a sample program:

from qiskit import QuantumCircuit
 
 
def solve(n: int) -> QuantumCircuit:
    qc = QuantumCircuit(n)
 
    qc.h(0)
    qc.cx(0, 1)
 
    for i in range(2, n - 1, 2):
        qc.cx(0, i)
        qc.cx(1, i + 1)
 
    if n % 2 != 0:
        qc.cx(0, n - 1)
 
    qc.z(0)
 
    return qc