{"problem":{"name":"E1. Bernstein-Vazirani algorithm","description":{"content":"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 is scalar product function (oracle from","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF1002E1"},"statements":[{"statement_type":"Markdown","content":"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 is scalar product function (oracle from problem D1):\n\nHere (an array of _N_ integers, each of which can be 0 or 1).\n\nYour task is to reconstruct the array . Your code is allowed to call the given oracle only once.\n\nYou have to implement an operation which takes the following inputs:\n\n*   an integer _N_ - the number of qubits in the oracle input (1 ≤ _N_ ≤ 8),\n*   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.\n\nThe return of your operation is an array of integers of length _N_, each of them 0 or 1.\n\nYour code should have the following signature:\n\nnamespace Solution {\n    open Microsoft.Quantum.Primitive;\n    open Microsoft.Quantum.Canon;\n\n    operation Solve (N : Int, Uf : ((Qubit\\[\\], Qubit) => ())) : Int\\[\\]\n    {\n        body\n        {\n            // your code here\n        }\n    }\n}\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"你被给定一个量子预言机——一个作用于 #cf_span[N + 1] 个量子比特上的操作，它实现了一个函数。你保证该预言机实现的函数 #cf_span[f] 是点积函数（来自问题 D1 的预言机）：\n\n这里  （一个包含 #cf_span[N] 个整数的数组，每个整数为 0 或 1）。\n\n你的任务是重构数组 。你的代码仅允许调用给定的预言机一次。\n\n你需要实现一个操作，该操作接收以下输入：\n\n你的操作的返回值是一个长度为 #cf_span[N] 的整数数组，每个元素为 0 或 1。\n\n你的代码应具有以下签名：\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $.  \nLet $ f: \\{0,1\\}^N \\to \\{0,1\\} $ be a function implemented by a quantum oracle, defined as:  \n$$\nf(x) = x \\cdot a \\mod 2 = \\bigoplus_{i=1}^N x_i a_i\n$$  \nwhere $ a = (a_1, a_2, \\dots, a_N) \\in \\{0,1\\}^N $ is an unknown target string.\n\n**Constraints**  \n- The oracle acts on $ N+1 $ qubits and implements the unitary:  \n  $$\n  U_f: |x\\rangle |b\\rangle \\mapsto |x\\rangle |b \\oplus f(x)\\rangle\n  $$  \n  for $ x \\in \\{0,1\\}^N $, $ b \\in \\{0,1\\} $.  \n- The algorithm may invoke the oracle **exactly once**.  \n- The goal is to determine $ a \\in \\{0,1\\}^N $.\n\n**Objective**  \nReconstruct $ a = (a_1, \\dots, a_N) $ using a single query to $ U_f $, via a quantum circuit that outputs $ a $ as a classical bit string.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF1002E1","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}