D3. Oracle for majority function

Codeforces

IDCF1002D3

Time1000ms

Memory256MB

Difficulty—

English · Original

Chinese · Translation

Formal · Original

Implement a quantum oracle on 3 qubits which implements a majority function. Majority function on 3-bit vectors is defined as follows: if vector has two or three 1s, and 0 if it has zero or one 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 3 qubits _x_ in arbitrary state (input register), * a qubit _y_ in arbitrary state (output qubit). 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) : () { body { // your code here } } } [samples]

实现一个作用于 3 个量子比特的量子预言机，实现多数函数。3 位向量的多数函数定义如下：如果向量包含两个或三个 1，则输出 1；如果包含零个或一个 1，则输出 0。有关此类量子预言机的工作原理的说明，请参阅《量子预言机简介》。你需要实现一个操作，它接受以下输入：该操作没有输出；其“输出”是它留下的量子比特状态。你的代码应具有以下签名： [samples]

**Definitions** Let $ n = 3 $ be the number of qubits. Let $ \ket{x} = \ket{x_1 x_2 x_3} $ denote a computational basis state, where $ x_i \in \{0,1\} $. Let $ f: \{0,1\}^3 \to \{0,1\} $ be the majority function: $$ f(x_1, x_2, x_3) = \begin{cases} 1 & \text{if } x_1 + x_2 + x_3 \geq 2 \\ 0 & \text{otherwise} \end{cases} $$ **Quantum Oracle Specification** The oracle is a unitary operator $ U_f $ acting on $ n+1 = 4 $ qubits: $ n $ input qubits $ \ket{x_1 x_2 x_3} $ and one ancilla qubit $ \ket{y} $. It satisfies: $$ U_f \ket{x_1 x_2 x_3} \ket{y} = \ket{x_1 x_2 x_3} \ket{y \oplus f(x_1, x_2, x_3)} $$ **Constraints** - The oracle must be implemented using reversible quantum gates. - The input qubits $ \ket{x_1, x_2, x_3} $ must remain unchanged. - The ancilla qubit $ \ket{y} $ is flipped iff $ f(x_1, x_2, x_3) = 1 $. **Objective** Implement the unitary $ U_f $ such that for all $ x \in \{0,1\}^3 $ and $ y \in \{0,1\} $: $$ U_f \ket{x} \ket{y} = \ket{x} \ket{y \oplus \mathbf{1}_{\sum_{i=1}^3 x_i \geq 2}} $$

API Response (JSON)

{
  "problem": {
    "name": "D3. Oracle for majority function",
    "description": {
      "content": "Implement a quantum oracle on 3 qubits which implements a majority function. Majority function on 3-bit vectors is defined as follows: if vector has two or three 1s, and 0 if it has zero or one 1s. F",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF1002D3"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Implement a quantum oracle on 3 qubits which implements a majority function. Majority function on 3-bit vectors is defined as follows: if vector has two or three 1s, and 0 if it has zero or one 1s.\n\nF...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "实现一个作用于 3 个量子比特的量子预言机，实现多数函数。3 位向量的多数函数定义如下：如果向量包含两个或三个 1，则输出 1；如果包含零个或一个 1，则输出 0。\n\n有关此类量子预言机的工作原理的说明，请参阅《量子预言机简介》。\n\n你需要实现一个操作，它接受以下输入：\n\n该操作没有输出；其“输出”是它留下的量子比特状态。\n\n你的代码应具有以下签名：\n\n[samples]...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n = 3 $ be the number of qubits. Let $ \\ket{x} = \\ket{x_1 x_2 x_3} $ denote a computational basis state, where $ x_i \\in \\{0,1\\} $.  \nLet $ f: \\{0,1\\}^3 \\to \\{0,1\\} $ be the ma...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments