← 返回题目列表

Codeforces · 1357/B2

B2. “这个数字能被3整除吗?”甲骨文

中文机器翻译题面 查看原题

在 $$$N$$$ 量子位上实现量子预言机,检查输入位串是否是可被 3 整除的数字的小端表示法。

您的操作应接受以下输入:

- 任意状态下 $$$N \le 8$$$ 量子位“输入”的数组。
- 任意状态下的量子位“输出”。

您的操作应该对那些可以通过其对基础状态的影响来描述的量子位执行酉变换:如果“输入”处于基础状态 $$$|x\rangle$$$ 且“输出”处于基础状态 $$$|y\rangle$$$,则应用该操作的结果应为 $$$|x\rangle|y \oplus f(x)\rangle$$$,其中如果位串 $$$x$$$ 表示的整数可被 $$$3$$$ 整除,则 $$$f(x) = 1$$$,否则为 $$$0$$$。

例如,如果传递给您的操作的量子位处于状态 $$$\frac{1}{\sqrt{2}}(|110\rangle + |001\rangle)_x \otimes |0\rangle_y = \frac{1}{\sqrt{2}}(|3\rangle + |4\rangle)_x \otimes |0\rangle_y$$$,应用该操作后系统的状态应为 $$$\frac{1}{\sqrt{2}}(|3\rangle_x\otimes |1\rangle_y + |4\rangle_x |0\rangle_y) = \frac{1}{\sqrt{2}}(|110\rangle_x\otimes |1\rangle_y + |001\rangle_x |0\rangle_y)$$$。

您的代码应具有以下签名(请注意,您的操作应为其定义 Adjoint 和 Controlled 变体;操作签名中的 Adj+Ctl 将根据您的代码自动生成它们):

您的代码不允许使用测量或任意旋转门。该操作可以仅使用 X 门及其受控变体(可能使用多个量子位作为控制)来实现。