Editorial
You can solve this in almost the same way as the previous problem.
To gain better insight, we decompose E ( m , k ) E(m, k) E ( m , k ) n − 1 n - 1 n − 1 ∣ 0 ⟩ n − 1 \ket{0}_{n - 1} ∣ 0 ⟩ n − 1
E ( m , k ) = 1 2 n + 1 F ( m , k ) + 1 2 n G ( m , k ) \begin{equation}
E(m, k) = \frac{1}{\sqrt{2^{n + 1}}} F(m, k) + \frac{1}{\sqrt{2^n}} G(m, k)
\end{equation} E ( m , k ) = 2 n + 1 1 F ( m , k ) + 2 n 1 G ( m , k ) where
F ( m , k ) = ∑ 0 ≤ a < 2 ∑ 0 ≤ b < 2 ( − 1 ) a m + b k ∣ a ⟩ ∣ b ⟩ ∣ 0 ⟩ n − 1 \begin{equation}
F(m, k) = \sum_{0 \leq a < 2} \sum_{0 \leq b < 2} (-1)^{am + bk} \ket{a} \ket{b} \ket{0}_{n-1}
\end{equation} F ( m , k ) = 0 ≤ a < 2 ∑ 0 ≤ b < 2 ∑ ( − 1 ) am + bk ∣ a ⟩ ∣ b ⟩ ∣ 0 ⟩ n − 1 G ( m , k ) = ∑ 1 ≤ c < 2 n − 1 ( X m R c k ⊗ I 1 ⊗ I n − 1 ) ( ∣ 0 ⟩ ∣ 0 ⟩ + ∣ 1 ⟩ ∣ 1 ⟩ ) ∣ c ⟩ n − 1 \begin{equation}
G(m, k) = \sum_{1 \leq c < 2^{n-1}} \left( X^m R^{ck} \otimes I_1 \otimes I_{n-1} \right)(\ket{0} \ket{0} + \ket{1} \ket{1}) \ket{c}_{n-1}
\end{equation} G ( m , k ) = 1 ≤ c < 2 n − 1 ∑ ( X m R c k ⊗ I 1 ⊗ I n − 1 ) ( ∣ 0 ⟩ ∣ 0 ⟩ + ∣ 1 ⟩ ∣ 1 ⟩ ) ∣ c ⟩ n − 1 First, by using the hint, we express F ( m ′ , k ′ ) F(m', k') F ( m ′ , k ′ ) m right , k right , m m_{\text{right}}, k_{\text{right}}, m m right , k right , m k k k
F ( m ′ , k ′ ) = ∑ 0 ≤ a < 2 ∑ 0 ≤ b < 2 ( − 1 ) a m ′ + b k ′ ∣ a ⟩ ∣ b ⟩ ∣ 0 ⟩ n − 1 = ∑ 0 ≤ a < 2 ∑ 0 ≤ b < 2 ( − 1 ) a ( m + m right ) + b ( ( − 1 ) m k right k + k right ) ∣ a ⟩ ∣ b ⟩ ∣ 0 ⟩ n − 1 = ∑ 0 ≤ a < 2 ∑ 0 ≤ b < 2 ( − 1 ) a ( m + m right ) + b ( k + k right ) ∣ a ⟩ ∣ b ⟩ ∣ 0 ⟩ n − 1 = ∑ 0 ≤ a < 2 ∑ 0 ≤ b < 2 ( − 1 ) a m right + b k right ( − 1 ) a m + b k ∣ a ⟩ ∣ b ⟩ ∣ 0 ⟩ n − 1 \begin{align}
F(m', k') &= \sum_{0 \leq a < 2} \sum_{0 \leq b < 2} (-1)^{am' + bk'} \ket{a} \ket{b} \ket{0}_{n-1} \\
&= \sum_{0 \leq a < 2} \sum_{0 \leq b < 2} (-1)^{a (m + m_{\text{right}}) + b ((-1)^m k_{\text{right}}k + k_{\text{right}})} \ket{a} \ket{b} \ket{0}_{n-1} \\
&= \sum_{0 \leq a < 2} \sum_{0 \leq b < 2} (-1)^{a (m + m_{\text{right}}) + b (k + k_{\text{right}})} \ket{a} \ket{b} \ket{0}_{n-1} \\
&= \sum_{0 \leq a < 2} \sum_{0 \leq b < 2} (-1)^{am_{\text{right}} + b k_{\text{right}}} (-1)^{am + bk} \ket{a} \ket{b} \ket{0}_{n-1}
\end{align} F ( m ′ , k ′ ) = 0 ≤ a < 2 ∑ 0 ≤ b < 2 ∑ ( − 1 ) a m ′ + b k ′ ∣ a ⟩ ∣ b ⟩ ∣ 0 ⟩ n − 1 = 0 ≤ a < 2 ∑ 0 ≤ b < 2 ∑ ( − 1 ) a ( m + m right ) + b (( − 1 ) m k right k + k right ) ∣ a ⟩ ∣ b ⟩ ∣ 0 ⟩ n − 1 = 0 ≤ a < 2 ∑ 0 ≤ b < 2 ∑ ( − 1 ) a ( m + m right ) + b ( k + k right ) ∣ a ⟩ ∣ b ⟩ ∣ 0 ⟩ n − 1 = 0 ≤ a < 2 ∑ 0 ≤ b < 2 ∑ ( − 1 ) a m right + b k right ( − 1 ) am + bk ∣ a ⟩ ∣ b ⟩ ∣ 0 ⟩ n − 1 Therefore, when the last n − 1 n - 1 n − 1 ∣ 0 ⟩ \ket{0} ∣ 0 ⟩
If m right ≡ 1 ( mod 2 ) m_{\text{right}} \equiv 1 \ (\text{mod} \ 2) m right ≡ 1 ( mod 2 ) Z Z Z ∣ a ⟩ \ket{a} ∣ a ⟩
If k right ≡ 1 ( mod 2 ) k_{\text{right}} \equiv 1 \ (\text{mod} \ 2) k right ≡ 1 ( mod 2 ) Z Z Z ∣ b ⟩ \ket{b} ∣ b ⟩
Similarly, by using the hint, we express G ( m ′ , k ′ ) G(m', k') G ( m ′ , k ′ ) m right , k right , m m_{\text{right}}, k_{\text{right}}, m m right , k right , m k k k
G ( m ′ , k ′ ) = ∑ 1 ≤ c < 2 n − 1 ( X m ′ R c k ′ ⊗ I 1 ⊗ I n − 1 ) ( ∣ 0 ⟩ ∣ 0 ⟩ + ∣ 1 ⟩ ∣ 1 ⟩ ) ∣ c ⟩ n − 1 = ∑ 1 ≤ c < 2 n − 1 ( X m + m right R c ( ( − 1 ) m right k + k right ) ⊗ I 1 ⊗ I n − 1 ) ( ∣ 0 ⟩ ∣ 0 ⟩ + ∣ 1 ⟩ ∣ 1 ⟩ ) ∣ c ⟩ n − 1 = ∑ 1 ≤ c < 2 n − 1 ( X m + m right R ( − 1 ) m right c k + c k right ⊗ I 1 ⊗ I n − 1 ) ( ∣ 0 ⟩ ∣ 0 ⟩ + ∣ 1 ⟩ ∣ 1 ⟩ ) ∣ c ⟩ n − 1 = ∑ 1 ≤ c < 2 n − 1 ( X m R c k X m right R c k right ⊗ I 1 ⊗ I n − 1 ) ( ∣ 0 ⟩ ∣ 0 ⟩ + ∣ 1 ⟩ ∣ 1 ⟩ ) ∣ c ⟩ n − 1 \begin{align}
G(m', k') &= \sum_{1 \leq c < 2^{n-1}} \left( X^{m'} R^{ck'} \otimes I_1 \otimes I_{n-1} \right)(\ket{0} \ket{0} + \ket{1} \ket{1}) \ket{c}_{n-1} \\
&= \sum_{1 \leq c < 2^{n-1}} \left( X^{m + m_{\text{right}}} R^{c((-1)^{m_{\text{right}}} k + k_{\text{right}})} \otimes I_1 \otimes I_{n-1} \right)(\ket{0} \ket{0} + \ket{1} \ket{1}) \ket{c}_{n-1} \\
&= \sum_{1 \leq c < 2^{n-1}} \left( X^{m + m_{\text{right}}} R^{(-1)^{m_{\text{right}}} ck + ck_{\text{right}}} \otimes I_1 \otimes I_{n-1} \right)(\ket{0} \ket{0} + \ket{1} \ket{1}) \ket{c}_{n-1} \\
&= \sum_{1 \leq c < 2^{n-1}} \left( X^{m} R^{ck} X^{m_{\text{right}}} R^{ck_{\text{right}}} \otimes I_1 \otimes I_{n-1} \right)(\ket{0} \ket{0} + \ket{1} \ket{1}) \ket{c}_{n-1}
\end{align} G ( m ′ , k ′ ) = 1 ≤ c < 2 n − 1 ∑ ( X m ′ R c k ′ ⊗ I 1 ⊗ I n − 1 ) ( ∣ 0 ⟩ ∣ 0 ⟩ + ∣ 1 ⟩ ∣ 1 ⟩ ) ∣ c ⟩ n − 1 = 1 ≤ c < 2 n − 1 ∑ ( X m + m right R c (( − 1 ) m right k + k right ) ⊗ I 1 ⊗ I n − 1 ) ( ∣ 0 ⟩ ∣ 0 ⟩ + ∣ 1 ⟩ ∣ 1 ⟩ ) ∣ c ⟩ n − 1 = 1 ≤ c < 2 n − 1 ∑ ( X m + m right R ( − 1 ) m right c k + c k right ⊗ I 1 ⊗ I n − 1 ) ( ∣ 0 ⟩ ∣ 0 ⟩ + ∣ 1 ⟩ ∣ 1 ⟩ ) ∣ c ⟩ n − 1 = 1 ≤ c < 2 n − 1 ∑ ( X m R c k X m right R c k right ⊗ I 1 ⊗ I n − 1 ) ( ∣ 0 ⟩ ∣ 0 ⟩ + ∣ 1 ⟩ ∣ 1 ⟩ ) ∣ c ⟩ n − 1 In the previous problem, X m left X^{m_{\text{left}}} X m left R c k left R^{c k_{\text{left}}} R c k left X m right X^{m_{\text{right}}} X m right R c k right R^{c k_{\text{right}}} R c k right X m right X^{m_{\text{right}}} X m right R c k right R^{c k_{\text{right}}} R c k right
For any matrices U U U V V V
( U V ⊗ I 1 ) ( ∣ 0 ⟩ ∣ 0 ⟩ + ∣ 1 ⟩ ∣ 1 ⟩ ) = ( U ⊗ V T ) ( ∣ 0 ⟩ ∣ 0 ⟩ + ∣ 1 ⟩ ∣ 1 ⟩ ) \begin{equation}
(UV \otimes I_{1}) (\ket{0}\ket{0} + \ket{1}\ket{1}) = (U \otimes V^{\text{T}}) (\ket{0}\ket{0} + \ket{1}\ket{1})
\end{equation} ( U V ⊗ I 1 ) ( ∣ 0 ⟩ ∣ 0 ⟩ + ∣ 1 ⟩ ∣ 1 ⟩ ) = ( U ⊗ V T ) ( ∣ 0 ⟩ ∣ 0 ⟩ + ∣ 1 ⟩ ∣ 1 ⟩ ) Using the fact that X = X T X = X^{\text{T}} X = X T R = R T R = R^{\text{T}} R = R T
Eq. (11) = ∑ 1 ≤ c < 2 n − 1 ( X m R c k ⊗ ( X m right R c k right ) T ⊗ I n − 1 ) ( ∣ 0 ⟩ ∣ 0 ⟩ + ∣ 1 ⟩ ∣ 1 ⟩ ) ∣ c ⟩ n − 1 = ∑ 1 ≤ c < 2 n − 1 ( I 1 ⊗ ( X m right R c k right ) T ⊗ I n − 1 ) ( X m R c k ⊗ I 1 ⊗ I n − 1 ) ( ∣ 0 ⟩ ∣ 0 ⟩ + ∣ 1 ⟩ ∣ 1 ⟩ ) ∣ c ⟩ n − 1 = ∑ 1 ≤ c < 2 n − 1 ( I 1 ⊗ R c k right X m right ⊗ I n − 1 ) ( X m R c k ⊗ I 1 ⊗ I n − 1 ) ( ∣ 0 ⟩ ∣ 0 ⟩ + ∣ 1 ⟩ ∣ 1 ⟩ ) ∣ c ⟩ n − 1 \begin{align}
\text{Eq. (11)} &= \sum_{1 \leq c < 2^{n-1}} \left( X^{m} R^{ck} \otimes \left( X^{m_{\text{right}}} R^{ck_{\text{right}}} \right)^\text{T} \otimes I_{n-1} \right)(\ket{0} \ket{0} + \ket{1} \ket{1}) \ket{c}_{n-1} \\
&= \sum_{1 \leq c < 2^{n-1}} \left( I_1 \otimes \left( X^{m_{\text{right}}} R^{ck_{\text{right}}} \right)^\text{T} \otimes I_{n-1} \right) \left( X^{m} R^{ck} \otimes I_1 \otimes I_{n-1} \right)(\ket{0} \ket{0} + \ket{1} \ket{1}) \ket{c}_{n-1} \\
&= \sum_{1 \leq c < 2^{n-1}} \left( I_1 \otimes R^{ck_{\text{right}}} X^{m_{\text{right}}} \otimes I_{n-1} \right) \left( X^{m} R^{ck} \otimes I_1 \otimes I_{n-1} \right)(\ket{0} \ket{0} + \ket{1} \ket{1}) \ket{c}_{n-1} \\
\end{align} Eq. (11) = 1 ≤ c < 2 n − 1 ∑ ( X m R c k ⊗ ( X m right R c k right ) T ⊗ I n − 1 ) ( ∣ 0 ⟩ ∣ 0 ⟩ + ∣ 1 ⟩ ∣ 1 ⟩ ) ∣ c ⟩ n − 1 = 1 ≤ c < 2 n − 1 ∑ ( I 1 ⊗ ( X m right R c k right ) T ⊗ I n − 1 ) ( X m R c k ⊗ I 1 ⊗ I n − 1 ) ( ∣ 0 ⟩ ∣ 0 ⟩ + ∣ 1 ⟩ ∣ 1 ⟩ ) ∣ c ⟩ n − 1 = 1 ≤ c < 2 n − 1 ∑ ( I 1 ⊗ R c k right X m right ⊗ I n − 1 ) ( X m R c k ⊗ I 1 ⊗ I n − 1 ) ( ∣ 0 ⟩ ∣ 0 ⟩ + ∣ 1 ⟩ ∣ 1 ⟩ ) ∣ c ⟩ n − 1 Then, by expanding c c c R c k right X m right R^{ck_{\text{right}}} X^{m_{\text{right}}} R c k right X m right
R c k right X m right = R c 0 k right R c 1 ( 2 k right ) . . . R c n − 2 ( 2 n − 2 k right ) X m right \begin{equation}
R^{ck_{\text{right}}} X^{m_{\text{right}}} = R^{c_0 k_{\text{right}}} R^{c_1 (2 k_{\text{right}})} ... \ R^{c_{n-2} (2^{n-2} k_{\text{right}})} X^{m_{\text{right}}}
\end{equation} R c k right X m right = R c 0 k right R c 1 ( 2 k right ) ... R c n − 2 ( 2 n − 2 k right ) X m right Therefore, when at least one of the last n − 1 n - 1 n − 1 ∣ 1 ⟩ \ket{1} ∣ 1 ⟩
If m right ≡ 1 ( mod 2 ) m_{\text{right}} \equiv 1 \ (\text{mod} \ 2) m right ≡ 1 ( mod 2 ) X X X ∣ b ⟩ \ket{b} ∣ b ⟩ Problem A3 circuit.)
For any j ∈ { 0 , 1 , … , n − 2 } j \in \lbrace0, 1, \dots, n-2\rbrace j ∈ { 0 , 1 , … , n − 2 } c j = 1 c_{j} = 1 c j = 1 R 2 j k left R^{2^j k_{\text{left}}} R 2 j k left ∣ b ⟩ \ket{b} ∣ b ⟩ rotation gate R z Rz R z
By performing the above operations in sequence, you can obtain the desired quantum state.
The circuit diagram for n = 4 , m right = 1 n = 4, m_{\text{right}} = 1 n = 4 , m right = 1 k right = 2 k_{\text{right}} = 2 k right = 2
The circuit depth is O ( n ) O(n) O ( n )
Sample Code
Below is a sample program:
import math
from qiskit import QuantumCircuit, QuantumRegister from qiskit.circuit.library import XGate, ZGate, RZGate
def A3 ( n : int ) -> QuantumCircuit: m, k = QuantumRegister( 1 ), QuantumRegister(n) qc = QuantumCircuit(m, k)
qc.x(m[ 0 ])
qc.x(k)
qc.compose(XGate().control( len (k)), [ * k, m[ 0 ]], inplace = True )
qc.x(k)
return qc
def solve ( n : int , m_right : int , k_right : int ) -> QuantumCircuit: a, b, c = QuantumRegister( 1 ), QuantumRegister( 1 ), QuantumRegister(n - 1 ) qc = QuantumCircuit(a, b, c)
qc.x(c)
if m_right: qc.compose(ZGate().control( len (c)), [ * c, a[ 0 ]], inplace = True ) if k_right % 2 : qc.compose(ZGate().control( len (c)), [ * c, b[ 0 ]], inplace = True )
qc.x(c)
if m_right: qc.compose(A3(n - 1 ), [b[ 0 ], * c], inplace = True )
theta = 2 * math.pi / 2 ** (n - 1 ) for i in range (n - 1 ): angle = theta * k_right * ( 2 ** i) qc.compose(RZGate(angle).control( 1 ), [c[i], b[ 0 ]], inplace = True )
return qc 
