← 返回题目列表

Codeforces · 1002/E1

E1. Bernstein-Vazirani 算法

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

你得到了一个量子预言 - 对 N + 1 个量子位的操作,它实现了一个函数 $$f:\{0, 1\}^N \to \{0, 1\}$$。保证预言机实现的函数 f 是标量积函数(来自问题 D1 的预言机):

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

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

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

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

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

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

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