{"problem":{"name":"I. Deutsch-Jozsa 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 either constant (returns 0 on all in","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF1001I"},"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 either constant (returns 0 on all inputs or 1 on all inputs) or balanced (returns 0 on exactly one half of the input domain and 1 on the other half).\n\nThere are only two possible constant functions: _f_(_x_) = 0 and _f_(_x_) = 1. The functions implemented by oracles in the two previous problems (_f_(_x_) = _x__k_ and ) are examples of balanced functions.\n\nYour task is to figure out whether the function given by the oracle is constant. Your code is allowed to call the given oracle only once.\n\n## Input\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,\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 a Boolean value: true if the oracle implements a constant function and false otherwise.\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) => ())) : Bool\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] 要么是常数函数（对所有输入返回 0 或对所有输入返回 1），要么是平衡函数（对输入域中恰好一半的输入返回 0，另一半返回 1）。\n\n只有两种可能的常数函数：#cf_span[f(x) = 0] 和 #cf_span[f(x) = 1]。前两个问题中预言机实现的函数（#cf_span[f(x) = xk] 和 ）是平衡函数的示例。\n\n你的任务是判断该预言机给出的函数是否为常数函数。你的代码只能调用给定的预言机一次。\n\n你需要实现一个操作，该操作接收以下输入：\n\n你的操作返回一个布尔值：如果预言机实现的是常数函数则返回 true，否则返回 false。\n\n你的代码应具有以下签名：\n\n## Input\n\n你需要实现一个操作，该操作接收以下输入：一个整数 #cf_span[N] —— 预言机输入的量子比特数，一个预言机 #cf_span[Uf]，其作为具有签名 _((Qubit[], Qubit) => ())_ 的操作实现，即一个接收量子比特数组和一个输出量子比特作为输入、无返回值的操作。你的操作返回一个布尔值：如果预言机实现的是常数函数则返回 true，否则返回 false。你的代码应具有以下签名：namespace Solution {    open Microsoft.Quantum.Primitive;    open Microsoft.Quantum.Canon;    operation Solve (N : Int, Uf : ((Qubit[], Qubit) => ())) : Bool    {        body        {            // your code here        }    }}\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $. Let $ f: \\{0,1\\}^N \\to \\{0,1\\} $ be a function implemented by a quantum oracle.  \nLet $ \\mathcal{O}_f $ be the unitary operator acting on $ \\mathbb{C}^{2^{N+1}} $ such that:  \n$$\n\\mathcal{O}_f |x\\rangle |y\\rangle = |x\\rangle |y \\oplus f(x)\\rangle, \\quad \\forall x \\in \\{0,1\\}^N, y \\in \\{0,1\\}.\n$$\n\n**Constraints**  \nThe function $ f $ is guaranteed to be either:  \n- **Constant**: $ f(x) = 0 $ for all $ x \\in \\{0,1\\}^N $, or $ f(x) = 1 $ for all $ x \\in \\{0,1\\}^N $;  \n- **Balanced**: $ |\\{x \\in \\{0,1\\}^N : f(x) = 0\\}| = |\\{x \\in \\{0,1\\}^N : f(x) = 1\\}| = 2^{N-1} $.\n\n**Objective**  \nDesign a quantum algorithm that, using a single query to $ \\mathcal{O}_f $, outputs:  \n$$\n\\begin{cases}\n\\texttt{true} & \\text{if } f \\text{ is constant}, \\\\\n\\texttt{false} & \\text{if } f \\text{ is balanced}.\n\\end{cases}\n$$\n\nThe algorithm must act on $ N+1 $ qubits, initialized to $ |0\\rangle^{\\otimes N} |1\\rangle $, apply Hadamard gates to all qubits, query $ \\mathcal{O}_f $, apply Hadamard gates to the first $ N $ qubits, and measure the first $ N $ qubits. Return **true** if the measurement outcome is $ |0\\rangle^{\\otimes N} $, **false** otherwise.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF1001I","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}