You are given a quantum oracle - an operation on _N_ + 1 qubits which implements a function . You are guaranteed that the function _f_ implemented by the oracle can be represented in the following form (oracle from problem D2):
Here (a vector of _N_ integers, each of which can be 0 or 1), and is a vector of _N_ 1s.
Your task is to reconstruct the array which could produce the given oracle. Your code is allowed to call the given oracle only once.
You have to implement an operation which takes the following inputs:
* an integer _N_ - the number of qubits in the oracle input (1 ≤ _N_ ≤ 8),
* an oracle _Uf_, implemented as an operation with signature _((Qubit\[\], Qubit) => ())_, i.e., an operation which takes as input an array of qubits and an output qubit and has no output.
The return of your operation is an array of integers of length _N_, each of them 0 or 1.
Note that in this problem we're comparing the oracle generated by your return to the oracle _Uf_, instead of comparing your return to the (hidden) value of used to generate _Uf_. This means that any kind of incorrect return results in "Runtime Error" verdict, as well as actual runtime errors like releasing qubits in non-zero state.
Your code should have the following signature:
namespace Solution {
open Microsoft.Quantum.Primitive;
open Microsoft.Quantum.Canon;
operation Solve (N : Int, Uf : ((Qubit\[\], Qubit) => ())) : Int\[\]
{
body
{
// your code here
}
}
}
[samples]
你被给定一个量子预言机——一个作用于 #cf_span[N + 1] 个量子比特上的操作，它实现了一个函数。你被保证该预言机实现的函数 #cf_span[f] 可以表示为以下形式（来自问题 D2 的预言机）：
其中 （一个由 #cf_span[N] 个整数组成的向量，每个整数为 0 或 1），而 是一个由 #cf_span[N] 个 1 组成的向量。
你的任务是重构出能够生成该预言机的数组 。你的代码只能调用给定的预言机一次。
你需要实现一个操作，其输入如下：
你的操作的返回值是一个长度为 #cf_span[N] 的整数数组，每个元素为 0 或 1。
注意，在本题中，我们比较的是由你的返回值生成的预言机与预言机 #cf_span[Uf]，而不是将你的返回值与用于生成 #cf_span[Uf] 的（隐藏）值 进行比较。这意味着任何错误的返回都会导致 "Runtime Error" 的评测结果，包括实际的运行时错误，例如以非零态释放量子比特。
你的代码应具有以下签名：
[samples]
**Definitions**
Let $ N \in \mathbb{Z}^+ $.
Let $ f: \{0,1\}^N \to \{0,1\} $ be a function implemented by a quantum oracle $ U_f $, such that:
$$
U_f |x\rangle |y\rangle = |x\rangle |y \oplus f(x)\rangle
$$
for all $ x \in \{0,1\}^N $, $ y \in \{0,1\} $, where $ \oplus $ denotes XOR.
The function $ f $ is guaranteed to be of the form:
$$
f(x) = a \cdot x \mod 2 = \bigoplus_{i=1}^N a_i x_i
$$
for some unknown $ a = (a_1, a_2, \dots, a_N) \in \{0,1\}^N $, where $ \cdot $ denotes the dot product over $ \mathbb{F}_2 $.
**Constraints**
- The oracle $ U_f $ can be called exactly once.
- The input state to the oracle is $ N+1 $ qubits: $ N $ for $ x $, 1 for $ y $.
- The goal is to reconstruct $ a \in \{0,1\}^N $ using a single query to $ U_f $, with auxiliary operations (Hadamard, etc.) allowed.
**Objective**
Construct a quantum circuit that, using exactly one call to $ U_f $, outputs the vector $ a \in \{0,1\}^N $ such that $ f(x) = a \cdot x \mod 2 $.
The solution is obtained via the Bernstein-Vazirani algorithm:
1. Initialize $ N $ qubits to $ |0\rangle^{\otimes N} $, and one ancilla qubit to $ |1\rangle $.
2. Apply Hadamard gates to all $ N+1 $ qubits.
3. Apply $ U_f $.
4. Apply Hadamard gates to the first $ N $ qubits.
5. Measure the first $ N $ qubits; the result is $ a $.
**Output**
Return the classical bitstring $ a = (a_1, a_2, \dots, a_N) \in \{0,1\}^N $ obtained from the measurement.