D2. Oracle for f(x) = b * x + (1 - b) * (1 - x) mod 2

Codeforces

IDCF1002D2

Time1000ms

Memory256MB

Difficulty—

English · Original

Chinese · Translation

Formal · Original

Implement a quantum oracle on _N_ qubits which implements the following function: Here (a vector of _N_ integers, each of which can be 0 or 1), and is a vector of _N_ 1s. For an explanation on how this type of quantum oracles works, see [Introduction to quantum oracles](https://codeforces.com/blog/entry/60319). You have to implement an operation which takes the following inputs: * an array of _N_ qubits _x_ in arbitrary state (input register), 1 ≤ _N_ ≤ 8, * a qubit _y_ in arbitrary state (output qubit), * an array of _N_ integers _b_, representing the vector . Each element of _b_ will be 0 or 1. The operation doesn't have an output; its "output" is the state in which it leaves 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, b : Int\[\]) : () { body { // your code here } } } [samples]

实现一个作用于 #cf_span[N] 个量子比特上的量子预言机，实现以下函数：这里是一个由 #cf_span[N] 个整数组成的向量（每个整数为 0 或 1），而是一个由 #cf_span[N] 个 1 组成的向量。有关此类量子预言机的工作原理的说明，请参阅《量子预言机简介》。你需要实现一个操作，它接受以下输入：该操作没有输出；其“输出”是它对量子比特所留下的状态。你的代码应具有以下签名： [samples]

**Definitions** Let $ N \in \mathbb{Z}^+ $ be the number of qubits. Let $ \mathbf{x} \in \{0,1\}^N $ be the input computational basis state. Let $ \mathbf{1} = (1, 1, \dots, 1) \in \{1\}^N $ be the all-ones vector. **Constraints** The oracle acts on $ N $ qubits initialized in state $ \ket{\mathbf{x}} \otimes \ket{0} $, and must transform them to $ \ket{\mathbf{x}} \otimes \ket{f(\mathbf{x})} $, where: $$ f(\mathbf{x}) = \mathbf{x} \cdot \mathbf{1} \mod 2 = \bigoplus_{i=1}^N x_i $$ **Objective** Implement a unitary operation $ U_f $ such that: $$ U_f \ket{\mathbf{x}} \ket{0} = \ket{\mathbf{x}} \ket{\bigoplus_{i=1}^N x_i} $$ This is a standard phase-flip oracle for the parity function over $ N $ bits.

API Response (JSON)

{
  "problem": {
    "name": "D2. Oracle for f(x) = b * x + (1 - b) * (1 - x) mod 2",
    "description": {
      "content": "Implement a quantum oracle on _N_ qubits which implements the following function: Here (a vector of _N_ integers, each of which can be 0 or 1), and is a vector of _N_ 1s. For an explanation on how t",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF1002D2"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Implement a quantum oracle on _N_ qubits which implements the following function:\n\nHere (a vector of _N_ integers, each of which can be 0 or 1), and is a vector of _N_ 1s.\n\nFor an explanation on how t...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "实现一个作用于 #cf_span[N] 个量子比特上的量子预言机，实现以下函数：\n\n这里  是一个由 #cf_span[N] 个整数组成的向量（每个整数为 0 或 1），而  是一个由 #cf_span[N] 个 1 组成的向量。\n\n有关此类量子预言机的工作原理的说明，请参阅《量子预言机简介》。\n\n你需要实现一个操作，它接受以下输入：\n\n该操作没有输出；其“输出”是它对量子比特所留下的状态。\n\n你...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $ be the number of qubits.  \nLet $ \\mathbf{x} \\in \\{0,1\\}^N $ be the input computational basis state.  \nLet $ \\mathbf{1} = (1, 1, \\dots, 1) \\in \\{1\\}^N $ be ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments