{"problem":{"name":"G. Oracle for f(x) = k-th element of x","description":{"content":"Implement a quantum oracle on _N_ qubits which implements a function _f_(_x_) = _x__k_, i.e. the value of the function is the value of the _k_\\-th qubit. For an explanation on how the quantum oracles","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF1001G"},"statements":[{"statement_type":"Markdown","content":"Implement a quantum oracle on _N_ qubits which implements a function _f_(_x_) = _x__k_, i.e. the value of the function is the value of the _k_\\-th qubit.\n\nFor an explanation on how the quantum oracles work, see [the tutorial blog post](https://codeforces.com/blog/entry/60319).\n\n## Input\n\nYou have to implement an operation which takes the following inputs:\n\n*   an array of qubits _x_ (input register),\n*   a qubit _y_ (output qubit),\n*   0-based index of the qubit from input register _K_ ().\n\nThe operation doesn't have an output; the \"output\" of your solution is the state in which it left the qubits.\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 (x : Qubit\\[\\], y : Qubit, k : 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] 个量子比特上的量子预言机，该预言机实现函数 #cf_span[f(x) = xk]，即函数的值为输入寄存器中第 #cf_span[k] 个量子比特的值。\n\n有关量子预言机工作原理的说明，请参见教程博客文章。\n\n你需要实现一个操作，该操作接受以下输入：\n\n该操作没有输出；你的解决方案的“输出”是它最终留下的量子比特状态。\n\n你的代码应具有以下签名：\n\n## Input\n\n你需要实现一个操作，该操作接受以下输入：一个量子比特数组 #cf_span[x]（输入寄存器）、一个量子比特 #cf_span[y]（输出量子比特）、输入寄存器中量子比特的从零开始的索引 #cf_span[K]。该操作没有输出；你的解决方案的“输出”是它最终留下的量子比特状态。你的代码应具有以下签名：namespace Solution {    open Microsoft.Quantum.Primitive;    open Microsoft.Quantum.Canon;    operation Solve (x : Qubit[], y : Qubit, k : Int) : ()    {        body        {            // your code here        }    }}\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $ be the number of qubits.  \nLet $ k \\in \\{0, 1, \\dots, N-1\\} $ be the index of the target qubit.  \nLet $ \\mathcal{H} = (\\mathbb{C}^2)^{\\otimes N} $ be the Hilbert space of $ N $ qubits.  \nLet $ \\{|x\\rangle \\mid x \\in \\{0,1\\}^N\\} $ be the computational basis of $ \\mathcal{H} $.  \n\nLet $ f: \\{0,1\\}^N \\to \\{0,1\\} $ be defined by $ f(x) = x_k $, the $ k $-th bit of the input string $ x $.  \n\n**Objective**  \nImplement a unitary operator $ U_f: \\mathcal{H} \\to \\mathcal{H} $ such that for all $ x \\in \\{0,1\\}^N $:  \n$$\nU_f |x\\rangle = (-1)^{f(x)} |x\\rangle = (-1)^{x_k} |x\\rangle\n$$  \n\n**Constraints**  \n- The operation acts only on the $ N $ input qubits.  \n- No ancilla qubits may be used.  \n- The implementation must be exact (no approximation).  \n- The operator must be unitary and reversible.  \n\n**Implementation Note**  \nThe oracle $ U_f $ is a phase-flip oracle: it applies a phase of $ -1 $ if and only if the $ k $-th qubit is in state $ |1\\rangle $. This is equivalent to applying the $ Z $ gate on the $ k $-th qubit.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF1001G","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}