B2: The Hidden Polynomial I

問題文

ストーリー

量子プログラミングを崇める QCoder 教団には、古くから伝わる秘伝の多項式 $f(x)$ がある。 この多項式 $f(x)$ は $n$ ビットの奇数 $A$ と $n$ ビットの整数 $B$ を用いて、以下のように定義される。

かつて、この多項式をオラクル $O$ へと書き込む神聖な儀式が執り行われた。 儀式が成功していれば、オラクル $O$ は次のような作用をするはずである。

ただし、$\oplus$ はビットごとの排他的論理和を表し、$(f(x)\bmod 2^n)$ は $f(x)$ を $2^n$ で割った余りを表す。

...しかし困ったことに、儀式の手続きは極めて難解であり、オラクルが正しく書き込まれたかどうかは誰にも分からない。 もし儀式が失敗していた場合、係数 $A$ は $0$ として誤って書き込まれてしまうという。

あなたに与えられた任務は、儀式が成功し、オラクル $O$ が正しく実装されているかどうかを判定することである。

ただし注意してほしい。 多項式 $f(x)$ は教団の最高機密情報であるため、オラクルを何度も呼び出して $f(x)$ の中身を特定することは許されない。 すなわち、オラクルは $1$ 回しか呼び出せないものとする。

問題の詳細説明

整数 $n$ が入力として与えられる。

あなたは、$2n$ 量子ビットをもつ量子回路 $\mathrm{qc}_{\mathrm{before}}$ と、$2n$ 量子ビットおよび $1$ つの古典レジスタをもつ量子回路 $\mathrm{qc}_{\mathrm{after}}$ 上に好きな操作を実装できる。

これらの量子回路上に、次の条件を満たす操作を実装せよ。

オラクル $O$ として、次のオラクル $O_1$ または $O_0$ が与えられる。

$0 \leq x < 2^n$ と $0 \leq y < 2^n$ を満たす任意の整数の組 $(x,y)$ に対して

ゼロ状態 $\ket{0}$ に $\mathrm{qc}_{\mathrm{before}},\,O,\,\mathrm{qc}_{\mathrm{after}}$ をこの順序で作用させたとき、$O=O_1$ であれば $1$ が古典レジスタに測定結果として書き込まれ、$O=O_0$ であれば $0$ が書き込まれる。

制約

• $n > 2$
• $0 \leq A, B < 2^n$
• $A$ は奇数
• 整数は リトルエンディアン にしたがってエンコードすること
• グローバル位相 は問わない。
• 提出されるコードは次のフォーマットにしたがうこと
  • before_oracle(n: int) -> QuantumCircuit : オラクル呼び出し前の量子回路 $\mathrm{qc}_{\mathrm{before}}$。
  • after_oracle(n: int) -> QuantumCircuit : オラクル呼び出し後の量子回路 $\mathrm{qc}_{\mathrm{after}}$。ただし、回路中で古典レジスタ c に測定結果を書き込むこと。

from qiskit import ClassicalRegister, QuantumCircuit, QuantumRegister
 
"""
You can apply measurement as follows
         (e.g., when measuring x[0]):
qc.measure(x[0], c[0])
"""
 
 
def before_oracle(n: int) -> QuantumCircuit:
    x = QuantumRegister(n)
    y = QuantumRegister(n)
    qc = QuantumCircuit(x, y)
 
    # Write your code here:
 
    return qc
 
 
def after_oracle(n: int) -> QuantumCircuit:
    x = QuantumRegister(n)
    y = QuantumRegister(n)
    c = ClassicalRegister(1)
    qc = QuantumCircuit(x, y, c)
 
    # Write your code here:
 
    return qc

なお、ジャッジにおいては以下の順番で関数が呼び出されます。

1. before_oracle(n)
2. (オラクル $O$)
3. after_oracle(n)

その後、$c = 1$ のとき「儀式が成功した」と判定し、$c = 0$ のとき「儀式が失敗した」と判定します。

ヒント

from qiskit_aer import AerSimulator
from qiskit import ClassicalRegister, QuantumCircuit, QuantumRegister, transpile
 
# before_oracle / oracle / after_oracle をここで定義するか、import してください。
 
# 入力例
n: int = 3
A: int = 1  # A は奇数
B: int = 4
 
# 回路構築
x = QuantumRegister(n)
y = QuantumRegister(n)
c = ClassicalRegister(1)
main_qc = QuantumCircuit(x, y, c)
main_qc.compose(before_oracle(n), inplace=True)
main_qc.compose(oracle(), inplace=True)
main_qc.compose(after_oracle(n), inplace=True)
 
# 回路をシミュレートし、レジスタ c の中身を取得する
simulator = AerSimulator()
job = simulator.run(
    transpile(main_qc, simulator),
    shots=1024,
)
counts: dict[str, int] = job.result().get_counts()
print(f"測定結果の統計: {counts}")