QCoder Programming Contest 005

← 前の問題次の問題 →

B1: Action in the Fourier Basis

実行時間制限：3 秒

メモリ制限：512 MiB

配点：300点

問題文

$n$ を正の整数とする。非負整数 $k$ に対し、 $\mathrm{QFT}(k)$ を次式で定義する。

\mathrm{QFT}(k) = \frac{1}{\sqrt{2^n}} \sum_{0 \leq a < 2^n} \omega^{ak} \ket{a}

ここで、 $\omega$ は

\omega = \exp \left( {\frac{2 \pi i}{2^n}} \right)

とする。

整数 $n$ , $k_{\text{const}}$ が入力として与えられるので、次の条件を満たすオラクル $O$ を、 $n$ 量子ビットをもつ量子回路 $\mathrm{qc}$ 上に実装せよ。

$0 \leq k < 2^n$ を満たす任意の整数 $k$ に対して

\mathrm{QFT}(k) \xrightarrow{O} \mathrm{QFT}(k')

ただし、 $0 \leq k' < 2^{n}$ は以下の式を満たす必要がある。

\omega^{k'} = \omega^{k_{\text{const}}} \omega^{k}

制約

$2 \leq n \leq 10$
$0 \leq k_{\text{const}} < 2^n$
量子回路の深さは $1$ を超えてはならない。
整数はリトルエンディアンにしたがってエンコードすること
グローバル位相は問わない。
提出されるコードは次のフォーマットにしたがうこと

from qiskit import QuantumCircuit
 
 
def solve(n: int, k_const: int) -> QuantumCircuit:
    qc = QuantumCircuit(n)
    # Write your code here:
 
    return qc

入力例

$n = 2$ : 実装された量子回路 $\mathrm{qc}$ は次式を満たす。

\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)

ヒント

開く

$a$ を $a = a_0 + 2 a_1 + \cdots + 2^{n-1} a_{n-1}$ のように二進展開すると考えやすくなるかもしれません。
類題：QCoder Programming Contest 002 - B5

解答を提出するにはログインしてください。