B2. Distinguish GHZ state and W state

Codeforces

IDCF1002B2

Time1000ms

Memory256MB

Difficulty—

English · Original

Chinese · Translation

Formal · Original

You are given _N_ qubits (2 ≤ _N_ ≤ 8) which are guaranteed to be in one of the two states: * state, or * state.Your task is to perform necessary operations and measurements to figure out which state it was and to return 0 if it was GHZ state or 1 if it was W state. The state of the qubits after the operations does not matter. You have to implement an operation which takes an array of _N_ qubits 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 (qs : Qubit\[\]) : Int { body { // your code here } } } [samples]

给定 #cf_span[N] 个量子比特（#cf_span[2 ≤ N ≤ 8]），它们保证处于以下两种状态之一：你的任务是执行必要的操作和测量，以确定它处于哪种状态，并在是 GHZ 态时返回 0，在是 W 态时返回 1。操作后量子比特的状态无关紧要。你需要实现一个操作，该操作以一个包含 #cf_span[N] 个量子比特的数组作为输入，并返回一个整数。你的代码应具有以下签名： [samples]

**Definitions** Let $ N \in \mathbb{Z} $ with $ 2 \leq N \leq 8 $. Let $ \mathcal{H} = (\mathbb{C}^2)^{\otimes N} $ be the Hilbert space of $ N $ qubits. Let $ |\text{GHZ}\rangle = \frac{1}{\sqrt{2}}(|0\rangle^{\otimes N} + |1\rangle^{\otimes N}) $ and $ |\text{W}\rangle = \frac{1}{\sqrt{N}} \sum_{i=1}^N |0\rangle^{\otimes (i-1)} |1\rangle |0\rangle^{\otimes (N-i)} $ be the two possible quantum states. Let $ \psi \in \{ |\text{GHZ}\rangle, |\text{W}\rangle \} $ be the unknown initial state of the $ N $-qubit system. **Constraints** 1. The system is initialized in either $ |\text{GHZ}\rangle $ or $ |\text{W}\rangle $. 2. Only quantum operations (unitaries, measurements) on the $ N $ qubits are permitted. 3. The goal is to distinguish between the two states with certainty. 4. The final state of the qubits after measurement is irrelevant. **Objective** Design a quantum algorithm (measurement strategy) that, given access to a single copy of $ \psi $, outputs: $$ \begin{cases} 0 & \text{if } \psi = |\text{GHZ}\rangle \\ 1 & \text{if } \psi = |\text{W}\rangle \end{cases} $$ with probability 1. Implement an operation $ \mathcal{A} : \mathcal{H} \to \{0,1\} $ that performs the required measurement and returns the correct label.

API Response (JSON)

{
  "problem": {
    "name": "B2. Distinguish GHZ state and W state",
    "description": {
      "content": "You are given _N_ qubits (2 ≤ _N_ ≤ 8) which are guaranteed to be in one of the two states: *   state, or *   state.Your task is to perform necessary operations and measurements to figure out which s",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF1002B2"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given _N_ qubits (2 ≤ _N_ ≤ 8) which are guaranteed to be in one of the two states:\n\n*   state, or\n*   state.Your task is to perform necessary operations and measurements to figure out which s...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "给定 #cf_span[N] 个量子比特（#cf_span[2 ≤ N ≤ 8]），它们保证处于以下两种状态之一：\n\n你的任务是执行必要的操作和测量，以确定它处于哪种状态，并在是 GHZ 态时返回 0，在是 W 态时返回 1。操作后量子比特的状态无关紧要。\n\n你需要实现一个操作，该操作以一个包含 #cf_span[N] 个量子比特的数组作为输入，并返回一个整数。\n\n你的代码应具有以下签名：\n\n[s...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N \\in \\mathbb{Z} $ with $ 2 \\leq N \\leq 8 $.  \nLet $ \\mathcal{H} = (\\mathbb{C}^2)^{\\otimes N} $ be the Hilbert space of $ N $ qubits.  \nLet $ |\\text{GHZ}\\rangle = \\frac{1}{\\sqr...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments