← 返回题目列表

Codeforces · 1002/E2

E2. 另一种数组重构算法

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

你得到了一个量子预言 - 对 N + 1 个量子位的操作,它实现了函数 $$f:\{0, 1\}^N \to \{0, 1\}$$。保证预言机实现的函数 f 可以用以下形式表示(来自问题 D2 的预言机):

$$f(\vec{x}) = (\vec{b} \cdot \vec{x} + (\vec{1} - \vec{b}) \cdot (\vec{1} - \vec{x})) \mod 2 = \sum_{k=0}^{N-1} (b_k x_k + (1 - b_k) \cdot (1 - x_k)) \mod 2$$

这里$$\vec{b} \in \{0, 1\}^N$$(N个整数组成的向量,每个整数可以是0或1),而$$\overrightarrow{a}$$是N个1的向量。

你的任务是重建数组 $$\overrightarrow{b}$$ ,它可以产生给定的预言。您的代码只允许调用给定的预言机一次。

您必须实施一项采用以下输入的操作:

- 整数 N - 预言机输入中的量子比特数 (1 ≤ N ≤ 8),
- 一个预言机 Uf,实现为带有签名 ((Qubit[], Qubit) => ()) 的操作,即,以量子位数组和输出量子位作为输入的操作,并且没有输出。

操作的返回是一个长度为 N 的整数数组,每个整数为 0 或 1。

请注意,在这个问题中,我们将您的返回生成的预言与预言 Uf 进行比较,而不是将您的返回与用于生成 Uf 的 $$\overrightarrow{b}$$ 的(隐藏)值进行比较。这意味着任何类型的错误返回都会导致“运行时错误”判决,以及实际的运行时错误,例如以非零状态释放量子位。

您的代码应具有以下签名: