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 circuit below:

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

In this case, the rightmost controlled gate acts on the 2nd and 4th qubits, while the adjacent gate to the left operates on the 1st and 3rd qubits. Since these operations involve different qubit pairs, they can be executed simultaneously, reducing the 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 2nd qubit as the control bit and the 4th qubit as the target bit.

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

When generalizing this idea to a circuit with $n$ qubits, the following operations are repeated:

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

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

With the above operations, the depth of the 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