C2. Distinguish zero state and plus state without errors

Codeforces

IDCF1002C2

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, 1 if it was state or -1 if you can not decide, i.e., an "inconclusive" result. 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 10000 times, and your goals are: * never give 0 or 1 answer incorrectly (i.e., never return 0 if input state was and never return 1 if input state was ), * give -1 answer at most 80% of the times, * correctly identify state at least 10% of the times, * correctly identify state at least 10% 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]

给定一个量子比特，其状态保证为 $\ket{0}$ 态或 $\ket{+}$ 态。你的任务是执行必要的操作和测量，以确定它原本处于哪种状态，并返回 0（如果是 $\ket{0}$ 态）、1（如果是 $\ket{+}$ 态）或 -1（如果无法确定，即“无结论”结果）。操作后量子比特的状态无关紧要。请注意，这些态不是正交的，因此无法完美区分。在每个测试用例中，你的解决方案将被调用 10000 次，目标如下：在每个测试中，$\ket{0}$ 和 $\ket{+}$ 态以 50% 的概率提供。你需要实现一个操作，该操作以一个量子比特作为输入并返回一个整数。你的代码应具有以下签名： [samples]

**Definitions** Let $|\psi\rangle \in \{ |\psi_0\rangle, |\psi_1\rangle \}$ be the input qubit state, where $|\psi_0\rangle$ and $|\psi_1\rangle$ are non-orthogonal pure states in $\mathbb{C}^2$, with $\langle \psi_0 | \psi_1 \rangle \neq 0$. Let $p(|\psi_0\rangle) = p(|\psi_1\rangle) = \frac{1}{2}$. **Constraints** 1. The states $|\psi_0\rangle$ and $|\psi_1\rangle$ are fixed but arbitrary non-orthogonal states. 2. The measurement strategy must be implemented as a quantum operation (unitary evolution + projective measurement) on a single qubit. 3. The output is an integer $r \in \{ -1, 0, 1 \}$: - $r = 0$ if the output is "state $|\psi_0\rangle$", - $r = 1$ if the output is "state $|\psi_1\rangle$", - $r = -1$ for "inconclusive". 4. The procedure is repeated 10,000 times per test, with independent draws of $|\psi_0\rangle$ or $|\psi_1\rangle$ with equal probability. **Objective** Maximize the probability of correct identification: $$ P_{\text{correct}} = \frac{1}{2} P(r=0 \mid |\psi_0\rangle) + \frac{1}{2} P(r=1 \mid |\psi_1\rangle) $$ while allowing inconclusive outcomes ($r=-1$) to improve reliability. The optimal strategy is a **POVM with three outcomes**: $ \{ E_0, E_1, E_{\text{inc}} \} $, where $E_0 + E_1 + E_{\text{inc}} = I$, and $E_0 \propto |\psi_1^\perp\rangle\langle\psi_1^\perp|$, $E_1 \propto |\psi_0^\perp\rangle\langle\psi_0^\perp|$, $E_{\text{inc}} = I - E_0 - E_1$, corresponding to the **Helstrom measurement for unambiguous state discrimination**. The output $r$ is determined by the measurement outcome: $$ r = \begin{cases} 0 & \text{if outcome } E_0 \text{ occurs} \\ 1 & \text{if outcome } E_1 \text{ occurs} \\ -1 & \text{if outcome } E_{\text{inc}} \text{ occurs} \end{cases} $$

API Response (JSON)

{
  "problem": {
    "name": "C2. Distinguish zero state and plus state without errors",
    "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": "CF1002C2"
  },
  "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": "给定一个量子比特，其状态保证为 $\\ket{0}$ 态或 $\\ket{+}$ 态。\n\n你的任务是执行必要的操作和测量，以确定它原本处于哪种状态，并返回 0（如果是 $\\ket{0}$ 态）、1（如果是 $\\ket{+}$ 态）或 -1（如果无法确定，即“无结论”结果）。操作后量子比特的状态无关紧要。\n\n请注意，这些态不是正交的，因此无法完美区分。在每个测试用例中，你的解决方案将被调用 10000 ...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $|\\psi\\rangle \\in \\{ |\\psi_0\\rangle, |\\psi_1\\rangle \\}$ be the input qubit state, where $|\\psi_0\\rangle$ and $|\\psi_1\\rangle$ are non-orthogonal pure states in $\\mathbb{C}^2$, wi...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments