Problem Statement
Let n n n k k k Q F T ( k ) \mathrm{QFT}(k) QFT ( k ) ∣ k m o d 2 n ⟩ \ket{k \bmod 2^n} ∣ k mod 2 n ⟩
Q F T ( k ) = 1 2 n ∑ 0 ≤ a < 2 n ω a k ∣ a ⟩ \mathrm{QFT}(k) = \frac{1}{\sqrt{2^n}} \sum_{0 \leq a < 2^n} \omega^{ak} \ket{a} QFT ( k ) = 2 n 1 0 ≤ a < 2 n ∑ ω ak ∣ a ⟩ where ω \omega ω
ω = exp ( 2 π i 2 n ) \omega = \exp \left( {\frac{2 \pi i}{2^n}} \right) ω = exp ( 2 n 2 π i ) Given integers n n n k const k_{\text{const}} k const n n n O O O q c \mathrm{qc} qc
For any integer k k k 0 ≤ k < 2 n 0 \leq k < 2^n 0 ≤ k < 2 n
Q F T ( k ) → O Q F T ( k ′ ) \mathrm{QFT}(k) \xrightarrow{O} \mathrm{QFT}(k') QFT ( k ) O QFT ( k ′ ) where 0 ≤ k ′ < 2 n 0 \leq k' < 2^{n} 0 ≤ k ′ < 2 n
ω k ′ = ω k const ω k \omega^{k'} = \omega^{k_{\text{const}}} \omega^{k} ω k ′ = ω k const ω k Constraints
2 ≤ n ≤ 10 2 \leq n \leq 10 2 ≤ n ≤ 10 0 ≤ k const < 2 n 0 \leq k_{\text{const}} < 2^n 0 ≤ k const < 2 n The quantum circuit depth must not exceed 1 1 1 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 , k_const : int ) -> QuantumCircuit: qc = QuantumCircuit(n) # Write your code here:
return qc Sample Input
n = 2 n = 2 n = 2 q c \mathrm{qc} qc
1 4 ( ∣ 0 ⟩ + ω k ∣ 1 ⟩ + ω 2 k ∣ 2 ⟩ + ω 3 k ∣ 3 ⟩ ) → q c 1 4 ( ∣ 0 ⟩ + ω k ′ ∣ 1 ⟩ + ω 2 k ′ ∣ 2 ⟩ + ω 3 k ′ ∣ 3 ⟩ ) \frac{1}{\sqrt{4}} \left( \ket{0} + \omega^{k} \ket{1} + \omega^{2k} \ket{2} + \omega^{3k} \ket{3} \right)
\xrightarrow{\mathrm{qc}}
\frac{1}{\sqrt{4}} \left( \ket{0} + \omega^{k'} \ket{1} + \omega^{2k'} \ket{2} + \omega^{3k'} \ket{3} \right) 4 1 ( ∣ 0 ⟩ + ω k ∣ 1 ⟩ + ω 2 k ∣ 2 ⟩ + ω 3 k ∣ 3 ⟩ ) qc 4 1 ( ∣ 0 ⟩ + ω k ′ ∣ 1 ⟩ + ω 2 k ′ ∣ 2 ⟩ + ω 3 k ′ ∣ 3 ⟩ ) Hints
Open
Thinking of a a a a = a 0 + 2 a 1 + ⋯ + 2 n − 1 a n − 1 a = a_0 + 2 a_1 + \cdots + 2^{n-1} a_{n-1} a = a 0 + 2 a 1 + ⋯ + 2 n − 1 a n − 1
Related problem: QCoder Programming Contest 002 - B5
