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

Editorial

In the expected solution for Problem A4, the depth of the quantum circuit is $\lfloor n/2 \rfloor + 3$ with respect to the number of qubits $n$, which is not sufficient to solve this problem. What kind of quantum circuit should be designed to further reduce the depth of the quantum circuit?

It is necessary to apply the technique learned in Problem A4, which is to avoid applying quantum gates consecutively to the same qubit as much as possible. Let's examine the following example with 8 qubits.

In this case, the operations within each block, divided by the barriers on the quantum circuit¹, act on different qubits, allowing them to be executed simultaneously. Therefore, the depth of each block is 1. Thus, the depth of the quantum circuit above is 5.

By generalizing this circuit, the depth of the quantum circuit becomes $\lceil \log_{2}{n} \rceil + 2$, which satisfies the given constraint.

Sample Code

Below is a sample program:

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