A6: Generate One-hot Superposition State III

Editorial

In the intended solution for problem A5, the depth of the quantum circuit would be $n + 2$, which does not solve this problem. So, how can we improve the quantum circuit?

Let's examine the following example with 6 qubits:

This quantum circuit generates the quantum state $\frac{1}{\sqrt{6}} (\ket{100000} + \ket{010000} + \ket{001000} + \ket{000100} + \ket{000010} + \ket{000001})$. We will explain each block of the quantum circuit separated by barriers ¹.

In the 1st block, we apply an $X$ gate to the first qubit.

In the 2nd block, we create an equal superposition of $\ket{100000}$ and $\ket{010000}$.

In the 3rd block, we further split $\ket{100000}$ and $\ket{010000}$.

Finally, the transition in the 4th block is expressed as follows:

The rotation angles $\theta_i$ are given by:

This quantum circuit has a depth of 4, which is much smaller than the intended solution for A5.

Next, let's generalize these operations. The problem is the way to determine the rotation angles.

For the case with 6 qubits, consider the following tree structure:

Each node $(a, b)^{(i, j)}$ represents an operation where a portion of the $i$-th qubit's amplitude, specifically $\sqrt{a/n}$ out of $\sqrt{b/n}$, is transferred to the $j$-th qubit. Thus, the rotation angle $\theta$ of the controlled $R_y$ gate with control on qubit $i$ and target on qubit $j$ can be determined by solving the following simultaneous equations:

Solving this equation yields the following solution within the range $0 \leq \theta \leq 2\pi$:

In this tree structure, for the parent node $(a, b)^{(i, j)}$, the child nodes above and below are represented by $(\lfloor\lfloor b/2 \rfloor/2\rfloor,\lfloor b/2 \rfloor)^{(i, ?)}$ and $(\lfloor \lceil b/2 \rceil/2 \rfloor,\lceil b/2 \rceil)^{(j, ?)}$, respectively. If $a = 0$, such an operation is not defined. The target qubit index $j$ is assigned to each node in the order from 2 to $n$, starting from nodes closest to the tree root.

By designing the quantum circuit based on this algorithm, the circuit depth can be reduced to $2 \lceil \log_{2}{n} \rceil + 1$, solving this problem.

For implementation, methods like breadth-first search can be used for constructing the tree structure.

Sample Code

Below is a sample program:

import math
 
from qiskit import QuantumCircuit
 
 
def solve(n: int) -> QuantumCircuit:
    qc = QuantumCircuit(n)
    qc.x(0)
 
    count = 1
 
    # queue = [(a, b, control bit of CRy), ...]
    queue = [(n // 2, n, 0)]
 
    # breadth first search
    while len(queue):
        a, b, control = queue.pop(0)
 
        if a == 0:
            continue
 
        theta = 2 * math.atan(math.sqrt((b - a) / a))
 
        qc.cry(theta, control, count)
        qc.cx(count, control)
 
        queue.append(((b // 2) // 2, b // 2, control))
        queue.append((math.ceil(b / 2) // 2, math.ceil(b / 2), count))
 
        count += 1
 
    return qc