C1. Distinguish zero state and plus state with minimum error

Codeforces

IDCF1002C1

Time2000ms

Memory256MB

Difficulty—

English · Original

Chinese · Translation

Formal · Original

You are given a qubit which is guaranteed to be either in state or in state. Your task is to perform necessary operations and measurements to figure out which state it was and to return 0 if it was a state or 1 if it was state. The state of the qubit after the operations does not matter. Note that these states are not orthogonal, and thus can not be distinguished perfectly. In each test your solution will be called 1000 times, and your goal is to get a correct answer at least 80% of the times. In each test and states will be provided with 50% probability. You have to implement an operation which takes a qubit as an input and returns an integer. Your code should have the following signature: namespace Solution { open Microsoft.Quantum.Primitive; open Microsoft.Quantum.Canon; operation Solve (q : Qubit) : Int { body { // your code here } } } [samples]

给定一个量子比特，其状态保证为 state 或 state 之一。你的任务是执行必要的操作和测量，以确定它原本处于哪种状态，并在是 state 时返回 0，在是 state 时返回 1。操作后量子比特的状态无关紧要。请注意，这些状态并非正交，因此无法完美区分。在每个测试用例中，你的解决方案将被调用 1000 次，你的目标是至少 80% 的次数给出正确答案。在每个测试中， state 和 state 将以 50% 的概率出现。你需要实现一个操作，该操作接受一个量子比特作为输入并返回一个整数。你的代码应具有以下签名： [samples]

**Definitions** Let $\ket{\psi} \in \{\ket{\phi_0}, \ket{\phi_1}\}$ be the input qubit state, where: - $\ket{\phi_0} = \ket{0}$, - $\ket{\phi_1} = \frac{1}{\sqrt{2}}(\ket{0} + \ket{1})$. Let $y \in \{0, 1\}$ be the true label: $y = 0$ if $\ket{\psi} = \ket{\phi_0}$, $y = 1$ if $\ket{\psi} = \ket{\phi_1}$. Let $p(y=0) = p(y=1) = \frac{1}{2}$. Let $\mathcal{A}$ be a quantum algorithm (operation) that takes $\ket{\psi}$ as input, applies a unitary $U$ and measures in the computational basis, outputting a prediction $\hat{y} \in \{0, 1\}$. **Constraints** 1. The algorithm $\mathcal{A}$ must be implemented using quantum operations (unitaries and projective measurements in the computational basis). 2. The algorithm is invoked 1000 times independently, each time with $\ket{\psi}$ chosen uniformly at random from $\{\ket{\phi_0}, \ket{\phi_1}\}$. 3. The goal is to maximize the success probability: $$ \mathbb{P}[\hat{y} = y] \geq 0.8 $$ **Objective** Design a unitary $U$ and measurement strategy such that the prediction $\hat{y}$ satisfies: $$ \mathbb{P}[\hat{y} = y] \geq 0.8 $$ over 1000 independent trials.

API Response (JSON)

{
  "problem": {
    "name": "C1. Distinguish zero state and plus state with minimum error",
    "description": {
      "content": "You are given a qubit which is guaranteed to be either in state or in state. Your task is to perform necessary operations and measurements to figure out which state it was and to return 0 if it was a",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF1002C1"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a qubit which is guaranteed to be either in state or in state.\n\nYour task is to perform necessary operations and measurements to figure out which state it was and to return 0 if it was a...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "给定一个量子比特，其状态保证为  state 或  state 之一。\n\n你的任务是执行必要的操作和测量，以确定它原本处于哪种状态，并在是  state 时返回 0，在是  state 时返回 1。操作后量子比特的状态无关紧要。\n\n请注意，这些状态并非正交，因此无法完美区分。在每个测试用例中，你的解决方案将被调用 1000 次，你的目标是至少 80% 的次数给出正确答案。在每个测试中，  stat...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $\\ket{\\psi} \\in \\{\\ket{\\phi_0}, \\ket{\\phi_1}\\}$ be the input qubit state, where:  \n- $\\ket{\\phi_0} = \\ket{0}$,  \n- $\\ket{\\phi_1} = \\frac{1}{\\sqrt{2}}(\\ket{0} + \\ket{1})$.  \n\nLet ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments