Problem Statement
Let n n n m m m k k k 0 ≤ m < 2 0 \leq m < 2 0 ≤ m < 2 0 ≤ k < 2 n 0 \leq k < 2^n 0 ≤ k < 2 n E ( m , k ) E(m, k) E ( m , k )
E ( m , k ) = 1 2 n + 1 ∑ 0 ≤ a < 2 ∑ 0 ≤ b < 2 ( − 1 ) a m + b k ∣ a ⟩ ∣ b ⟩ ∣ 0 ⟩ n − 1 + 1 2 n ∑ 1 ≤ c < 2 n − 1 ( X m R c k ⊗ I 1 ⊗ I n − 1 ) ( ∣ 0 ⟩ ∣ 0 ⟩ + ∣ 1 ⟩ ∣ 1 ⟩ ) ∣ c ⟩ n − 1 , \begin{align}
E(m, k) =
& \frac{1}{\sqrt{2^{n+1}}}
\sum_{0 \leq a < 2} \sum_{0 \leq b < 2}
(-1)^{am + bk} \ket{a} \ket{b} \ket{0}_{n-1} \nonumber \\
& + \frac{1}{\sqrt{2^n}} \sum_{1 \leq c < 2^{n-1}}
\left( X^m R^{ck} \otimes I_1 \otimes I_{n-1} \right)
\left( \ket{0}\ket{0} + \ket{1}\ket{1} \right)
\ket{c}_{n-1}, \nonumber
\end{align} E ( m , k ) = 2 n + 1 1 0 ≤ a < 2 ∑ 0 ≤ b < 2 ∑ ( − 1 ) am + bk ∣ a ⟩ ∣ b ⟩ ∣ 0 ⟩ n − 1 + 2 n 1 1 ≤ c < 2 n − 1 ∑ ( X m R c k ⊗ I 1 ⊗ I n − 1 ) ( ∣ 0 ⟩ ∣ 0 ⟩ + ∣ 1 ⟩ ∣ 1 ⟩ ) ∣ c ⟩ n − 1 , where the matrices X X X R R R X X X rotation gate R z ( 2 π / 2 n − 1 ) Rz\left( 2 \pi / 2^{n - 1} \right) R z ( 2 π / 2 n − 1 )
X = ( 0 1 1 0 ) , R = R z ( 2 π 2 n − 1 ) = ( exp ( − 2 π i 2 n ) 0 0 exp ( 2 π i 2 n ) ) . X = \begin{pmatrix}
0 & 1 \\
1 & 0
\end{pmatrix},
\quad
R = Rz\left( \frac{2 \pi}{2^{n - 1}} \right) = \begin{pmatrix}
\exp \left( - \frac{2\pi i}{2^n} \right) & 0 \\
0 & \exp \left( \frac{2\pi i}{2^n} \right)
\end{pmatrix}. X = ( 0 1 1 0 ) , R = R z ( 2 n − 1 2 π ) = ( exp ( − 2 n 2 πi ) 0 0 exp ( 2 n 2 πi ) ) . Given integers n n n m left m_{\text{left}} m left k left k_{\text{left}} k left ( n + 1 ) (n + 1) ( n + 1 ) O O O q c \mathrm{qc} qc
The oracle O O O
E ( m , k ) → O E ( m ′ , k ′ ) , E(m, k) \xrightarrow{O} E(m', k'), E ( m , k ) O E ( m ′ , k ′ ) , where m ′ m' m ′ k ′ k' k ′
X m ′ R k ′ = X m left R k left X m R k . X^{m'} R^{k'} = X^{m_\text{left}} R^{k_\text{left}} X^{m} R^{k}. X m ′ R k ′ = X m left R k left X m R k . Note : We recommend referring to the hints for this problem.
Constraints
2 ≤ n ≤ 10 2 \leq n \leq 10 2 ≤ n ≤ 10 0 ≤ m left < 2 0 \leq m_{\text{left}} < 2 0 ≤ m left < 2 0 ≤ k left < 2 n 0 \leq k_{\text{left}} < 2^n 0 ≤ k left < 2 n The circuit depth must not exceed 30 30 30 Integers must be encoded by little-endian .
Global phase is ignored in judge.The submitted code must follow the specified format:
from qiskit import QuantumCircuit
def solve ( n : int , m_left : int , k_left : int ) -> QuantumCircuit: qc = QuantumCircuit(n + 1 ) # Write your code here:
return qc Hints
Open
The existence of m ′ m' m ′ k ′ k' k ′ X X X R R R X 2 = R 2 n = I , R X = X R − 1 . X^2 = R^{2^n} = I, \quad RX = XR^{-1}. X 2 = R 2 n = I , RX = X R − 1 . X m ′ R k ′ = X m left R k left X m R k = X m left ( R k left X m ) R k = X m left ( X m R ( − 1 ) m k left ) R k = X m left + m R ( − 1 ) m k left + k \begin{align}
X^{m'} R^{k'}
& = X^{m_\text{left}} R^{k_\text{left}} X^{m} R^{k} \nonumber \\
& = X^{m_\text{left}} \left( R^{k_\text{left}} X^{m} \right) R^{k} \nonumber \\
& = X^{m_\text{left}} \left( X^{m} R^{(-1)^m k_{\text{left}}} \right) R^{k} \nonumber \\
& = X^{m_\text{left} + m} R^{(-1)^m k_{\text{left}} + k} \nonumber
\end{align} X m ′ R k ′ = X m left R k left X m R k = X m left ( R k left X m ) R k = X m left ( X m R ( − 1 ) m k left ) R k = X m left + m R ( − 1 ) m k left + k m ′ = m left + m ( mod 2 ) k ′ = ( − 1 ) m k left + k ( mod 2 n ) . \begin{gather}
m' = m_{\text{left}} + m \ \left(\text{mod} \ 2 \right) \nonumber \\
k' = (-1)^{m} k_{\text{left}} + k \ \left(\text{mod} \ 2^{n} \right). \nonumber
\end{gather} m ′ = m left + m ( mod 2 ) k ′ = ( − 1 ) m k left + k ( mod 2 n ) .
