G. Oracle for f(x) = k-th element of x

Codeforces

IDCF1001G

Time1000ms

Memory256MB

Difficulty—

English · Original

Chinese · Translation

Formal · Original

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 work, see [the tutorial blog post](https://codeforces.com/blog/entry/60319). ## Input You have to implement an operation which takes the following inputs: * an array of qubits _x_ (input register), * a qubit _y_ (output qubit), * 0-based index of the qubit from input register _K_ (). The operation doesn't have an output; the "output" of your solution is the state in which it left the qubits. Your code should have the following signature: namespace Solution { open Microsoft.Quantum.Primitive; open Microsoft.Quantum.Canon; operation Solve (x : Qubit\[\], y : Qubit, k : Int) : () { body { // your code here } } } [samples]

实现一个作用于 #cf_span[N] 个量子比特上的量子预言机，该预言机实现函数 #cf_span[f(x) = xk]，即函数的值为输入寄存器中第 #cf_span[k] 个量子比特的值。有关量子预言机工作原理的说明，请参见教程博客文章。你需要实现一个操作，该操作接受以下输入：该操作没有输出；你的解决方案的“输出”是它最终留下的量子比特状态。你的代码应具有以下签名： ## Input 你需要实现一个操作，该操作接受以下输入：一个量子比特数组 #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 } }} [samples]

**Definitions** Let $ N \in \mathbb{Z}^+ $ be the number of qubits. Let $ k \in \{0, 1, \dots, N-1\} $ be the index of the target qubit. Let $ \mathcal{H} = (\mathbb{C}^2)^{\otimes N} $ be the Hilbert space of $ N $ qubits. Let $ \{|x\rangle \mid x \in \{0,1\}^N\} $ be the computational basis of $ \mathcal{H} $. Let $ f: \{0,1\}^N \to \{0,1\} $ be defined by $ f(x) = x_k $, the $ k $-th bit of the input string $ x $. **Objective** Implement a unitary operator $ U_f: \mathcal{H} \to \mathcal{H} $ such that for all $ x \in \{0,1\}^N $: $$ U_f |x\rangle = (-1)^{f(x)} |x\rangle = (-1)^{x_k} |x\rangle $$ **Constraints** - The operation acts only on the $ N $ input qubits. - No ancilla qubits may be used. - The implementation must be exact (no approximation). - The operator must be unitary and reversible. **Implementation Note** The 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.

API Response (JSON)

{
  "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...",
      "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## I...",
      "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 H...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments